How could you disclose what you like and have someone respond with what you want without revealing who you are?

All Bob needs is to generate an Ephemeral key: just make (say) an RSA key, use it to initiate and proceed with communications with Alice, then delete it when he's done, taking care never to use it to process any personally-identifying information.
In fact, this is what web browsers do every time you connect to a website: by default, only the server has a certificate anchoring its identity; clients are anonymous until or unless they supply authentication. Your queries to, say, Searx are confidential, known only by the host and the anonymous client which started that TLS session.
(The bit about "no central authority certifying Alice" is a massive, separate question -- it is the puzzle which X.509, DANE, and an entire host of decentralized proto-solutions are still struggling to solve to this day; but I'll include a proto-solution to it as well.)
With any public-key cryptosystem, it's trivial to implement an ephemeral or "anonymous" key, by simply not attaching identity attestations to a freshly-generated public key and then throwing it away afterwards; if you're only concerned with the authenticity of one party (Alice is a recognized fruit seller or someone whom Bob otherwise knows the public key of; Bob is an anonymous client with no identity persisting beyond the scope of a single discussion session), it's quite easy -- For example (all messages listed are both signed by the sending key and encrypted by the receiving key):
Bob: (Acquires Alice's putative pk_A)
Bob: (Generates a keypair sk_B, pk_B)
Bob -> Alice (sk_B -> pk_A): "Buying oranges for 3 bitcoin, reply-to [pk_B]"
Alice -> Bob (sk_A -> pk_B): [initiate zero-knowledge proof of orange possession]
Bob -> Alice (sk_B -> pk_A): [challenge proof]
Alice -> Bob (sk_A -> pk_B): [complete proof]
Alice -> Bob (sk_A -> pk_B): "send 3 bitcoins to [btc_A] if you want them"
Bob -> Alice (sk_B -> pk_A): [transaction]
Alice -> Bob (sk_A -> pk_B): [oranges]
Bob: (deletes sk_B and all trace of pk_B off his computer)

In the real-world, something like this happens if you buy something from an online merchant using a burner e-mail (or no e-mail) and either General Delivery or inherently digital data served over the same TLS connection, though without a "proof" of the online merchant's legitimacy (which, again, is a whole separate scope from merely allowing bidirectional secure communications with an anonymous participant).

[Note that Bob and Alice are switched from their canonical roles in your question; I have written my answer to reflect that, but, in the future, you should use "Alice" to represent the initiator/sender of communications and Bob as the recipient or secondary participant. Additionally, "Eve" is used to denote the malicious party -- the hacker or "Eavesdropper" -- who may be just eavesdropping, or may be launching interactive or invasive MitM attacks; her abilities are generally assumed to comprise control of the network.]


The Wikipedia article points out a good reason for using a random challenge value: preventing replay attacks.

If the hash was always the same (as the hash of the symmetric key would be), then having listened in on one challenge-response cycle, a malicious listener could pass further handshake tests.


How can I use an XML detached signature when the file may be stored anywhere?

You do not need to include a URI in the Reference element of a detached signature. Just include the signature algorithm and the digest value, then you can associate signature and file by yourself.


What's a quadratic map and how do I invert it?

In cryptographic applications a quadratic map is generally conceived as a system of n quadratic equations in n variables.  Each equation is generally represented as an n-long vector of n variables x and a matrix Mi (for equation i of the system.  The equation is then:

(x^T)Mi(x) = ai

Your are then given the n matrices Mi, and a resultant vector of the ai.  The inversion you are looking for is to find a vector x such that:

(x^T)Mi(x) = ai for all i

If the Mi are chosen at random then the problem of finding a solution to this problem is believed to be intractably hard (NP-hard in fact).  If the Mi are specially chosen (not random at all) one can make inversion easy.  Mulivariate Quadratic cryptography tries to take an easy to solve quadratic map and transform it into a seemingly difficult to solve map.

If you look at the Unbalanced Oil and Vinegar schemes:

https://en.wikipedia.org/wiki/Unbalanced_Oil_and_Vinegar

you get an idea of one such system.


Can you correct my understanding of Argon2?

A) Don't hash Email. Store it as plain text or don't store at all.

If hashed, then looking up will be impossible. One would need to iterate through every single record in the database. On average 50% records need to be tested each time. In case there are 1 000 000 users, for every login case the application will need to check on average 500 000 records. Hashing needs to be expensive. Suppose it takes 1s. It means, checking of a single login will take 500 000 s, which is about 6 days. Even for a small database with 1 000 user this will take 500 s = more than 8 minutes to check login every time user logs in. No user will accept it.

B) Store login ID as a plain text, exactly as entered by user, without any transformation and obfuscation.

If you use any transformation, it must produce each time the same result, otherwise you will not be able to look up login in the database. If the result is always the same, then also an attacker will be able to easily generate the same code. Means, not more security, but more obscurity and thus more error prone.

C) Where random data are needed, use random generator, don't add anything else.

The RD is not random. Thus Blake3(RD) is also not random. Thus the salt is not random. Instead, use random generator. Furthermore, adding complexity or making an algorithm more obscure does not make it more secure, not even a little.

Also don't make Email address or any other fixed data a part of the secret. Such data are not really random. Each user has some more or less limited number of such attributes (nobody generates a new Email address every day). That's why such data don't give much entropy. But using them makes the algorithm more obscure and gives a false feeling of security.

D) Try to keep an algorithm as simple as possible.

Think of Kerckhoffs's principle. Adding obscurity does not give any more security. But more obscurity means more complexity in the implementation, which makes implementation more error prone and thus actually less secure.

E) Separate different goals clearly. Don't mix them.

Hashing of secret data (password) is one goal. It seems you want to protect personal data that easily identify a person (Email address). This is another goal. It is not good to mix them. This leads to dependency between them. Trying to reach one goal can lead to problems achieving another goal. In our case, Email should not be a part of secret used for login. Furthermore, if you want to keep Email secret, encrypt it with a password that only user knows (not necessarily the same as login password). But then also your application will not be able to use this Email address, e.g. to send info to restore forgotten password. And if your application can decrypt it, then also an attacker can easily decrypt it. Means, either store it as is, as a plain text, or don't store at all.

F) "The best" doesn't mean "approved".

It is true, that Argon2 has won the competition. But before deciding to use it please consider also following (this happens not so often, but still there are such cases):

Make sure your customer approved using of Argon2 for password hashing. It may be that this customer has some conservative process and Argon2 is not (yet) approved for usage in this organization. May be they still accept PBKDF2 only. Especially some organizations close to the government may have such regulations.
Make sure your customer approved usage of particular library that implements Argon2 for your software platform (depending on what you use - C++, C#, Java, etc.). If not approved, I would not recommend to implement Argon2 by yourself. Instead, use some other algorithm provided by some of the libraries approved by this customer, even if it is PBKDF2, bcrypt or scrypt.


Does shift cipher with non-uniform plain text probability have perfect secrecy?

For any ciphertext $c \in C$ and message $p \in P$ we have
$$P(c|p) = \frac{P(p\cap c)}{P(p)} = \frac{P(p\cap k)}{P(p)},$$
where $k = c-p$. This is because if the plaintext is $p$, the ciphertext is $c$ if and only if the key is $k$. Now, if the key is chosen independently of the plaintext we have $P(p\cap k) = P(p)\cdot P(k)$, and so finally $P(c|p) = P(k) = 1/8$ if the key is chosen uniformly.


Generation of a cyclic group of prime order

One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group.

Obvious questions:

How do you find a large prime factor $q$, given that $p-1$ is hard to factor?  Well, you pick the prime factor $q$ first, and you look for a prime $p$ in the form $kq+1$.
How likely is it that $h^{(p-1)/q} \ne 1$?  Well, if $h$ is selected randomly from the range $[1, p-1]$, that will be one with probability $1/q$, and so you'll almost always get a usable $g$ with just one random $h$.

Another way to do this is pick a prime $p$ with $q = (p-1)/2$ also prime and $p \equiv 7 \pmod{8}$.  In this case, $g=2$ is guaranteed to be a generator of order $q$.  This is a bit more work, however you can use the primes $p$ from this RFC; all those primes have these properties.


On the paper Low Depth Circuits for Efficient Homomorphic Sorting (page 5), the authors present circuits to homomorphically evaluate comparisons.
Their "Less Than Circuit" compares $\ell$-bit integers in the following way:
They define a bit level "less than": $f(x, y) = y \cdot (x + 1) \mod 2$  (where $x$ and $y$ are encryptions of bits).
They define a bit level "equal to":  $g(x, y) = y + x + 1 \mod 2$.
Then, the less than circuit for two encrypted $\ell$-bit integers is
$$C_{LT}(X, Y) =  \sum_{k=1}^{\ell} (f(X_k, Y_k) \cdot \prod_{k<t<\ell}g(X_t, Y_t))  \mod 2$$
where $X = (X_1, X_2, \cdots, X_\ell)$ is a vector of ciphertexts in which each $X_k$ is the encryption of the $k$-th bit of the first plaintext (and the same for $Y$ regarding the second plaintext).
Since the only thing it requires is the ability to encrypt bit a bit and to homomorphically operate $\mod 2$, it seems you can evaluate this circuit using Helib.


Can you fake messages from recorded message-history?

If Bob does NOT care to check signatures (as in the question), Eve can send ANY message she wants to Bob pretending to be Alice, including but not limited to messages Eve got from Alice; all Eve needs is Bob's public key (which, as the name implies, is assumed public knowledge thus known to Eve) and straight use of PGP.

Therefore the right question is: Can Eve reuse signatures she got from Alice, so that Bob concludes that a message sent by Eve is from Alice, even though Bob DOES care to check signatures?

The answer is YES, if Eve sends to Bob a message with exactly the content the message had when signed by Alice. So if Alice sent to Eve a message like "Let's meet at the bar at 11 pm", Eve can impersonate Alice and send that same message to Bob, who might conclude he has an invitation from Alice, when that invitation really was for Eve, perhaps another bar than the one he expects, and/or a past day. PGP gives insurance to Bob that the message was signed by Alice, and gives him a chance to detect a change of day (for PGP signatures include a "signature time stamp"). PGP does NOT give insurance to Bob that the message was for him.

Note: having an history of many recorded messages only helps Eve by giving her a wider choice of messages she can send to Bob pretending they came from Alice; Eve can not cut and paste fragments from past messages to compose a new one.


mikeazo has the answer in a comment:

  RSA with proper padding

So, use RSA (or actually any trap door one way function) with proper padding. For instance: OAEP padding. These are designed to achieve indistinguishability, which has also been mentioned in the comments. The padding which uses a hash internally kills all homomorphic properties of the cipher.


What cipher mode is suitable for independantly decryptable short messages?

Reflex answer: EAX. EAX does encryption and authentication, with minimal space overhead. EAX also has light requirements on the IV: it just needs a non-repeating value, so a simple counter can work. Possibly you already have a suitable counter or time stamp in your packets, that can be used as IV.

About replay attacks: you already expect that some packets will be dropped, or reordered. Be warned that if your protocol tolerates it, then the attacker can force it upon you, mechanically. I suppose that your protocol already includes some sort of frame counter so that you can reject frames which are too old (or too new !) and merge duplicates. That frame counter would work nicely as an IV for EAX.

If you want to do it old-style, use CBC with a random IV (IV must be transmitted along the packet), and then a MAC (HMAC, for instance) computed over the encrypted data (including the IV) and appended to the packet. You will need more code, cryptographically strong generation of an IV for each packet, and space overhead is likely to be higher than for EAX. That's the price of being old-style.


Cryptographic data structure: sparse array without membership test

This answer builds on the answer supplied by @otus.  There is also an important worry about whether the main solution works at all as advertised.  I am posting it now to make clearer to @otus a question I asked in a comment.  I will eventually either delete it or substantially revise it.

First off, let me emphasize that if the table is going to be used to store arbitrary data, then an attacker who suspects k is a key may be able to test the suspicion by checking whether get(k) is data-like.  So the natural guarantee in this case is just that an attacker cannot recover any information from the table without possessing the key to that data.  If this guarantee is all we require, the problem can be completely solved using the @otus's idea of hashing the keys and using the hash as a symmetric encryption key.  Let me explain this solution as a preliminary.

Assume, as @otus does, that an initial hash has been performed.  (Questions: do standard cryptographic hash functions actually come with a guarantee that the hashes are indistinguishable from draws from the uniform distribution?  Also, if we are willing to hash to a larger space than the domain, can we be guaranteed that the hash function is injective?)

A simple version of the data structure is as follows.  We maintain a list of data items.  Each item in the list is of the form $E_k(k,v)$ for a $k$ that is unique in the list.  To retrieve the value associated with $k$, we decrypt the list members using $k$ and check for one that returns to $(k,v)$.  To store $(k,v)$, we first check if $k$ already has a value associated with it and, if so, remove the corresponding data item from the list.  Then we add $E_k(k,v)$ to the list.

The simple version has linear time overhead, but it is straightforward to eliminate that inefficiency by using hash tables with collision resolution.

Now back to the full version of the problem, which is mainly interesting in the case where the stored data will be indistinguishable from random bit strings.

@otus gives a solution to this problem, but it has three drawbacks: it is probabilistic, it requires super-quadratic space to have low error probability, and it the eventual size of the data structure must be known in advance.  The first and third drawbacks seem to me inescapable, though I have no proof of this conjecture.  I have an idea about how to eliminate the second drawback, but it depends on the existence of a certain kind of error-correcting code.

The data structure is an array of $N$ bits initialized to random values.  To store $(k,v)$, we use $k$ to seed a pseudo-random number generator to generate a sequence of indices into the table.  We blow up $E_k(v)$ to double its original size using an error-correcting code, and we store the successive bits of this blown up version of $E_k(V)$ at the successive pseudo-random indices into the table.  This code can correct errors in up to half bits, so as long as the probability of a collision at any bit is significantly less than a half, we can be virtually certain of recovering the data.  If the table is four times size of the data stored in it then the expected number of bits stored at each index will be 1/2.  We can think of the number of collisions at a location as following a Poisson distribution with mean 1/2, so the probability of no collisions at a location will be about .61.  Assuming the data is long, there will be an overwhelmingly high probability that we can recover it from the code.  And the total space requirement is only four times the amount of space we need to hold the data.

The only problem is that with normal error-correcting codes, it is easy to tell whether an bit string is a code or not, and it is probably also easy to tell if a bit string is close to being a code in the Hamming metric.  So an attacker in possession of $k$ would be able to confirm that $k$ was likely a key, precisely what we don't want.  I am not sure if this problem dooms the whole approach I am contemplating here or whether there are special codes that do not have this problem.  Now with any code there will be some bit strings that it is easy to see are not code words because they have short Hamming distance to bit strings that decode to something different.  But maybe such bit strings could be rare, or even impossible to find, and bit strings that do not have that property would be indistinguishable from codes.


Homomorphic encryption for multiplication (AND) on bits only?

Assuming that I only want to encrypt 0 or 1, is there a partial HE that can do ANDs (aka multiplication)?

Yes.
In fact, there is a generic way of converting any additively homomorphic encryption scheme with large plaintext space into a PHE for AND with plaintexts in $\{0,1\}$.
Here is the idea: let $(\mathsf{KeyGen}, \mathsf{Enc},\mathsf{Dec})$ be an additively homomorphic encryption scheme; for simplicity, suppose that the plaintext space is $\mathbb{Z}_p$ for some large prime $p$. Define $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ as follows:
$\mathsf{KeyGen}^*$: same as $\mathsf{KeyGen}$.
$\mathsf{Enc}^*(m)$: if $m=0$, sample a uniformly random value $R \gets \mathbb{Z}_p$. If $m = 1$, set $R \gets 0$. Output an encryption $\mathsf{Enc}(R)$ of $R$ with the original scheme.
$\mathsf{Dec}^*(C)$: decrypt $C$ with $\mathsf{Dec}$ to get $R$. If $R = 0$, output $1$; else, output $0$.
Claim: $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ is a multiplicatively homomorphic encryption scheme over $\{0,1\}$, with negligible correctness error; the procedure for homomorphic multiplication is just the procedure for homomorphic addition of the original scheme.
This is easy to check: a sum of any number of encryptions of zero is still an encryption of zero. However, if a single ciphertext encrypts a nonzero value, the result becomes nonzero. In terms of the scheme $\mathsf{Enc}^*$, this translates to the fact that the AND of many 1's is still 1, but if a single bit is zero, the result is zero.
Since the addition is done mod $p$, there is a tiny chance that a sum of nonzero values will give a zero, hence the homomorphic algorithm has imperfect correctness; however, if $p$ is large enough, this happens only with negligible probability.
Two additional comments:

The above transformation gives an additional useful property: if the original encryption scheme is rerandomizable, then so is the new encryption scheme. Said otherwise, you canc guarantee that the homomorphic AND of $n$ ciphertexts only leaks the AND of the plaintexts, and nothing about the individual values of the plaintext (a generic PHE does not necessarily satisfy that, but this is often needed in applications - for example, this is needed in the example application of unanimous voting in your question)
The additively homomorphic variant of ElGamal (a ciphertext is of the form $(g^r, h^r\cdot g^m)$) can be used here: it does not enjoy efficient decryption, but it is easy to check that it is not important in this transformation, since we only need to be able to check whether a ciphertext decrypts to 0 or not, and this can always be checked given $g^m$ (which is what you get when decrypting ElGamal).


Well, in this particular case, AES-GCM is being used.  As GCM adds authentication tags to the output stream, the size of the output stream is greater than the size of the input stream.  Writing the data in place would require a certain amount of buffering that could become difficult if the input stream is large enough.

Not to mention this helps defend against a power failure/crash in the middle of the encryption.  Imagine if the encryption process was stopped at some point.  When the system recovered how would it know where to start encrypting again?  With a separate encrypted stream the recovery process is easy - just start over at the beginning.


What is KEK and how is used for key sharing?

A Key Encryption Key or KEK is simply a key that is solely used to encrypt keys. The keys that are encrypted are usually keys that have a specific meaning such as domain specific keys. It could also be that the encrypted keys have shorter life time such a as session keys.
A KEK may be used in combination with ECB mode as the encrypted key material should be indistinguishable from random. This is one of the few places where ECB encryption does not leak information. Note that it is an extremely bad idea to encrypt structured information with ECB; this includes most asymmetric keys as they generally consist of multiple encoded components.
Currently I would advice a scheme such as AES-SIV or AES-GCM-SIV. This will create a randomized ciphertext if the key only differs by a single bit. The calculated synthetic IV in SIV mode double acts as an authentication tag. This means that any changes (deliberate or not) of the key value can be detected. Beware that it is still possible to e.g. swap encrypted key values though - this is something that the wrapping algorithm itself cannot provide protection for.
Key encryption is sometimes also called wrapping. The KEK is then called a wrapping key and the protected key is of course called the wrapped key.


Elliptic Curve Discrete Log in a Composite Ring

Well, if you have a pseudocurve [1] based on the formula:

$$y^2 = x^3 + ax + b \pmod{ pq }$$

what you have is really two different curves stapled together; that is, the curves based on:

$$y^2 = x^3 + ax + b \pmod{ p }$$

$$y^2 = x^3 + ax + b \pmod{ q }$$

You can look at a point in the $pq$ curve as really being a point in the $p$ curve and a point in the $q$ curve; and when you perform an operation, the two component curves act independently.

So, if we denote a point $A$ as the pair $(A_p, A_q)$ and the point $B$ as the pair $(B_p, B_q)$, then the result of the point addition $A+B$ is the pair $(A_p + B_p, A_q + B_q)$, where the first addition is an addition in the $p$ curve, and the second addition is in the $q$ curve.  And if exactly one of $A_p+B_p, A_q+B_q$ is the point at infinity, then it turns out that the value $A+B$ is not defined in the $pq$ curve - that's why it's called a pseudocurve, because not all operations within the pseudocurve have defined results - it fails to be a group because it is not closed.

More to the point, if you take a point $P$ in the original $pq$, and compute $kA$, then that is equivalent:

Mapping the point $P$ to a point on the $p$ curve (by taking the $x$ and $y$ coordinates modulo $p$), and then computing $kA_p$
Mapping the point $P$ to a point on the $q$ curve (by taking the $x$ and $y$ coordinates modulo $q$), and then computing $kA_q$
Recombining $kA_p$ and $kA_q$ by reconstructing both the $x$ and $y$ coordinates using the Chinese Remainder Theorem.

With this observation, we have the following method to solve the original $A = xB$ problem:

Factor $n$ into $p, q$
Point count both the $p$ curve and the $q$ curve
Solve $A = xB$ over the $p$ curve (resulting in $x \bmod n_p$, where $n_p$ is the number of points on the $p$ curve)
Solve $A = xB$ over the $q$ curve (resulting in $x \bmod n_q$, where $n_q$ is the number of points on the $q$ curve)
Use the Chinese remainder theorem to combine $x \bmod n_p$ and $x \bmod n_q$ into $x$

These operations are jointly cheaper than solving an ECDLog problem over a prime the same size as $pq$

[1]: I'll explain why it's called pseudocurve below


Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$

On one hand, what's asked in the question's title is finding the factorization of $n'$ given the factorization of "the previous" $n$ as $n=p\,q$. As far as we know, that can't be done for $n'$ of cryptographic interest, for a definition of "previous" implying a small increase in value.
That's part of surrogate factoring, which is to factorization what perpetual motion is to movement.

On a second hand, what's asked in the question is different: finding the factorization of $n'$ given that it is of the form $p'\,q'$ with $p'$ (resp. $q'$) a prime "generated by increasing" some known $p$ (resp. $q$). That makes the task easy, for a definition of "increasing" implying a small increase in value. All there is to do is explores the integers $p'$ above $p$ sequentially, and try if they divide $n'$, until hitting the factorization; it is not even necessary to check that $p'$ is prime.

On a third hand, a comment tells that "$n$ grows by a digit each round", which implies that at least one of $p$ or $q$ has changed a lot in value. If only one has changed a lot, we can try the above method on both $p$ and $q$. If both have changed, and we have no clue about how, then the factorization of $n$ is useless to find that of $n'$, and we are back to the problem of factorization of $n'$ without clue, which can be handled up to 800 bits (240 decimal digits) give or take 50%, depending on resources.


How to check runtime of e.g. Ed25519 signature algorithm

In elliptic curve cryptography, the main operation is point multiplication: given an integer $k$ and a point $P$, compute $kP$ ($P$ added to itself $k$ times).

If the point $P$ is known beforehand, the computation can be sped up by using precomputation tables.

EdDSA signing requires computing $rB$ where $B$ is a fixed point (the "base"), therefore can be sped up.

EdDSA verifying requires computing $sB - hA$, i.e one fixed point multiplication and one "random" point multiplication ($A$ comes from the signer's public key). If you assume the fixed point multiplication is twice as fast than random point multiplication, then the result is that verification is three times slower than signing.

But of course, it depends on the implementation. In a naive implementation that doesn't optimize the fixed point case, verification will be two times slower than signing. It also depends on the size of the precomputation tables used.

This is described abstractly in sections 3.3 and 3.4 of the RFC 8032 (which are slightly confusing due to the $2^c$ factors), and more concretely in 5.1.6, 5.1.7 for Ed25519 and 5.2.6, 5.2.7 for Ed448 (which explain that you can ignore the $2^c$ factors).


E-voting: public tallying vs. vote selling

The second property is formally called receipt freeness.  Any voting system based on probabilistic encryption cannot be receipt free, because the voter uses  a random value to construct the vote, this random value can serve as a receipt.
The solution given to this problem is by having an authority create the vote and the voter simply selects it from a presented list.
The first protocol to achieve this is as far as I know is the one described in the paper Receipt-free secret-ballot elections from Benaloh and Tuinstra. A more widely used example is  Efficient receipt-free voting based on homomorphic encryption from Hirt and Sako.
You can check these references especially the second one on details about how to achieve verifiability.


OpenPGP Public-Key Encrypted Session Key Packet Key ID generation

An OpenPGP "key" is actually a structure that may contain many public keys. Typically, it contains two, a signing key and an encryption key. The signing key is considered the top-level key, as it issues signatures claiming ownership of all the subordinate keys, be they encryption or signing keys.

The key ID of the whole structure as you'd see it in a program is the key ID of the top-level signing key. The keyID if the ESK packet is the key ID of the encryption key. That's why they're different.

Put your whole key into the dump program at http://www.pgpdump.net/ and you'll get the whole thing dumped out for you.


How to verify a shared secret using only AES?

Why over-complicate it like that,

D1 and D2 generates random 64-bit P (half the block size of AES)
they send it to each other
both generate AES(key,P_own||P_other) and again send to each other (note that these are different for each)
then both can verify that what they received is equal to AES(key,P_other||P_own)

Upside here is that it is a fully symmetric protocol.


How to Implement Deterministic Encryption Safely in .NET

You can safely use HMAC-SHA256 instead of the SIV mode custom PRF to derive the nonce/authentication tag.  There's some caveats:

HMAC-SHA256 gives a 256-bit output; you'll have to truncate it to the nonce size.
HMAC-SHA256 takes in a single bit string, so it can't distinguish the boundary between a header (unencrypted associated data) and payload (encrypted message); the SIV mode custom PRF is defined on a tuple of bit strings.  So make sure that if you compute HMAC over more than just a ciphertext, you uniquely encode the tuple of $(a, c)$ as a bit string you pass to HMAC-SHA256.
Beware limits on total volume of data for AES-SIV or similar!  For example, if your ‘AES-CTR’ takes a 96-bit nonce (as AES-GCM uses), you must limit your total volume of data to well below $2^{48}$ messages, so that there is no danger of nonce collision.  For example, you might limit it to a billion messages, $2^{30}$.

AES-SIV internally uses $\operatorname{AES}_k(n) \mathbin\| \operatorname{AES}_k(n + 1) \mathbin\| \operatorname{AES}_k(n + 2) \mathbin\| \cdots$ with a 128-bit nonce $n$, instead of what is usually meant by AES-CTR, which is $\operatorname{AES}_k(n \mathbin\| 0) \mathbin\| \operatorname{AES}_k(n \mathbin\| 1) \mathbin\| \operatorname{AES}_k(n \mathbin\| 2) \mathbin\| \cdots$ with a (say) 96-bit nonce $n$ and 32-bit block counter like AES-GCM uses.  The details don't matter that much as long as you pay close attention to the advertised adversary advantage and data volume limits.
Make sure to write known-answer test vectors for the system you think you're implementing, using another tool or another library, so that you can do quick self-tests to confirm interoperability.
Avoid the term ‘zero-knowledge’ unless you're actually doing cryptography involving zero-knowledge proofs, which are a specific technical concept involving provers, verifiers, extractors, and simulators.  Saying ‘zero-knowledge encryption’ proudly announces that you have more money for a marketing department than for a cryptography engineering department.

Even if you encrypt identifiers, there's lots of information to be learned from network structures and databases with ‘anonymized’ (really, pseudonymized) identifiers.  So ‘zero-knowledge’ is especially inappropriate here if you're only concealing the labels, not the structure of the database.
In this scenario, I would advise you to either (a) persuade your management to invest more money in cryptography engineering including hiring competent implementors and auditors, or (b) start polishing your CV, because this job is doomed.  This is not a comment on your value or intelligence as a person!  Obviously you're working hard to learn.  But it is not confidence-inspiring to hear that your management are tasking someone who has to ask a pseudonymous forum of strangers on the internet for help with cryptographic basics in order to handle private banking information for thousands of clients over the internet.


The best answer is almost certainly to use a cryptographic hash.

Your reason for avoiding a cryptographic hash makes no sense to me.  Your problem does not explain the motivation for your question, but I suspect you've fallen prey to the XY problem (see also here).

You haven't told us what you're ultimately trying to accomplish, but I suspect the right answer in practice is ultimately going to be:

Use /dev/urandom to generate cryptographic-quality pseudorandom numbers.
If you have a source of entropy, feed it into /dev/urandom (e.g., cat somekindarandombits > /dev/urandom), then see step 1 above.

Internally, this effectively uses a hash.

I also recommend you read the following:

https://security.stackexchange.com/q/89/971
https://security.stackexchange.com/q/3936/971
https://security.stackexchange.com/q/14292/971


PAN authenticatable irreversible tokenization algorithm

If the PAN space is sufficiently large then you can use a SHA3-256(Keccak family) and use the required number of bits of the output. I guess in that case you may have to maintain a Card-Data vault for the lookup thing.


In your code you use the modular inverse with the respect to the modulus 0x11b, which is an operation quite different from taking the inverse in the field GF(2^8).

For getting an idea what you have to do instead, take a look at finite field arithmetic in the wikipedia.


How much data can we encrypt using AES 256 before changing the key?

AES-GCM is not the same thing as AES. AES-GCM uses a 96-bit IV, or transforms a non-96-bit IV into a 96-bit IV before use. The particular constraints of the RBG and Deterministic constructions mean that not all of those 96 bits are expected to change between invocations. An IV collision (two uses of the same IV with a given key) is catastrophic to GCM's security, and therefore must be avoided.
The "Birthday bound" of an n-bit value is $2^\frac{n}{2}$, so a 96-bit IV has a bound of only $2^\frac{96}{2}=2^{48}$ blocks. But both recommended IV constructions keep some bits of the IV fixed, resulting in the lowered block count recommendation. EG

this  Recommendation  suggests,  but  does  not  require,  that  the  leading  (i.e.,  leftmost) 32 bits of the IV hold the fixed field; and that the trailing (i.e., rightmost) 64 bits hold the invocation field

means that only 64 bits of the IV would vary, so $2^\frac{64}{2}=2^{32}$ blocks can be safely encrypted with those GCM settings. Other IV generation methods similarly tend to reduce the number of varying bits. Fixing some bits allows for multiple sources to encrypt data using the same key. If one bit is fixed, two devices can share a key. If two bits are fixed, 4 devices can. Etc. If no bits are fixed, then each device must have its own send and receive key for each other device. Since this part of the spec is about fixed, shared keys the storage requirements would quickly overwhelm small systems.


An ECDSA signature consists of two integers that can range between 0 and $n$, where $n$ is the curve order.

For secp521r1, the curve order is just a shade under $2^{521}-1$, hence it requires 521 bits to express one of those integers, or 1042 to express two.

130 bytes would not be sufficient, as that has only 1040 bits.

131 bytes would suffice; however the convention is to express those two integers separately; each integer takes up 66 bytes, and hence 132 is used for the two.  You could combine the top byte of each integer into a single byte (as the top byte of each integer is either 0 or 1), reducing the signature size to 131 bytes; however I haven't heard of anyone bothering.


Simulation based proofs, what am I missing?

Basically, what you are missing is that the real view for a given input pair must be indistinguishable from the simulated view for the same input pair.

Remember that, put simply, the requirement is that the view of each party can be simulated based only on its input and output. So, in the case of $P_2$, for each pair of input bits the simulator is given the input $y$ of $P_2$ and the output bit $x \wedge y$, where $x$ is the input bit of $P_1$, and must simulate the view $(y,x)$ of $P_2$ (input and received message). Now, consider the two cases where $y = 0$. In both those cases, the simulator has input $(0,0)$, so its output in both cases will be the same. But the real view is not the same ($x$ can be $0$ or $1$), so the simulator, no matter what it does, can't possibly simulate both views.

Concretely, consider for example the following simulator $S_2$. On input $(y,w)$ (where $w = x \wedge y$),

if $y = 0$, chose $b \gets \{0,1\}$ randomly and output $(0,b)$;
if $y = 1$, output $(1,w)$.

Recall also that for all input pairs $(x,y)$, we have $\mathsf{view}_2(x,y) = (y,x)$. Consider now the following distinguisher $D$. $D$ gets as input a pair of bits $(a,b)$; if $(a,b) = (0,0)$, $D$ outputs $1$, and otherwise $D$ outputs $0$. The question is, if the inputs to the parties are $(0,0)$, what does $D$ output if we give it a real vs. simulated view of $P_2$? A real view will be $(0,0)$, so $D$ will always output $1$. A simulated view will be $(0,0)$ or $(0,1)$ each with probability $1/2$, so $D$ will output $1$ with probaility only $1/2$, hence the two probability ensembles (real and simulated views) are distinguishable.


How is an AES S-Box cyclically shifted to the left?

Yes they are talking about shifting each individual byte.

In the example in the paper, s-box input 00 becomes input A4 (output 63), 01 becomes A5 (7C), and so on. This is a 92 byte left rotation of the s-box elements, which is equivalent to a 164 byte right rotation, all done mod 256.

Without going into extreme detail, I would strongly recommend against using this... ever, it is not a good idea, and actually makes the cipher weaker. There are only 255 new s-boxes generated using this method, and they are all weaker than the original.

The example s-box given shows the following properties:

Differential Uniformity: 8 (lower is better)
Non-linearity: 94 (higher is better)
AutoCorrelation: 88 (lower is better)
SSI: 260608 (lower is better)

The AES standard s-box has these values for the same properties:

Differential Uniformity: 4 (lower is better)
Non-linearity: 112 (higher is better)
AutoCorrelation: 32 (lower is better)
SSI: 133120 (lower is better)

The new s-box also inherits the undesirable properties of the original, such as simple algebraic representation and CCZ equivalence.


What is the PRG period of stream ciphers such as RC4 or Salsa20?

The internal state of RC4 consists of a shuffled 256-element array and two pointers into that array.  Thus, there are a total of $$256! \times 256^2 \approx 2^{1700.00}$$ possible states.  Since the state update function of RC4 is reversible, it acts as a permutation on this set of possible states, so that every starting state will eventually recur after sufficiently many iterations.

How many is sufficiently many?  Well, if we assume that the update function behaves like a random permutation (which it, of course, does not, but it's a good first approximation), then the expected cycle length is approximately $2^{1700}/2 = 2^{1699}$ iterations(!).  Indeed, the probability that the cycle length starting from a random state is at least $k$ iterations is approximately $1 - k/2^{1700}$; this means that hitting a cycle of less than, say, $2^{200}$ iterations should happen less than once in $2^{1700-200} = 2^{1500}$ initializations, i.e. basically never within the lifetime of the universe.

Of course, as noted, the RC4 state update function is not a random permutation.  For example, there's a known class of $254!$ short cycles of $256^2-256 = 65280$ states each; fortunately, the standard RC4 key setup is guaranteed never to hit them.  For more information on the actual cycle structure of RC4, see e.g. "Cryptanalysis of RC4-like Ciphers" by S. Mister and S. E. Tavares.


Determining if a ciphertext can be decrypted

In the first part of this answer, I consider the problem of decryption using leaked keys of a protocol not intended for that, which was my original reading of the question. I'll ignore that dominant industry practice is to use random symmetric session keys, leaving little opportunity to "hold a couple of secret keys" without knowing to what session they belong to.

The mode used with symmetric secret keys sometime provides message integrity (e.g. AES-GCM). This gives you a robust mean to determine if a secret key is correct or not, by checking if the integrity test passes. Odds of the wrong key accidentally letting the integrity check pass are demonstrably at least as low as the odds of forgery, thus won't occur for secure modes.

When only encryption is used, any known redundancy of the plaintext can be used to test if the correct secret key was used (deciphering with the wrong key will lead to incorrect plaintext which will be indistinguishable from random). An example of redundancy is the magic number found at the beginning of many practical payloads. Also, for encryption modes with message padding, often the padding is enough for reliable recognition of correct decryption.

For something more general, performing a chi-squared test of the distribution of bytes, or byte pairs for long enough messages, will often work. Exceptions include already compressed plaintext, and plaintext which really is cyphertext.

It is impossible to detect if the right key was used in attempting to decipher a payload consisting exclusively of cyphertext for some other cipher (including OTP, or AES-CTR), as this ability would match the modern definition of an attack of the other cipher.

The actual question turns out to be about building a demonstrably secure protocol intended for selective decryption. Such situation occurs in e.g. satellite internet or TV, and many network applications.

If hiding who the packets are for is not a security objective, it can not harm to include a label in clear in each packet, identifying the key that enciphered the packet, since that's public data. That's the practice in many TCP/IP protocols, where the label is that of the TCP/IP session, thus of the session key. That allows the receivers to decipher the packet with at most one key: the right one, if and only if they hold it. That saves effort/energy. Addition per comment: the tag must somewhat be decided. A sequential number would be fine, if practical (and again if that can be made public). Using a (first-preimage-resistant) hash of the key value would also do, if the hash and cipher are unrelated. The hash can be truncated to save bandwidth, but must be next to $(r-1+2\log_2m)$-bit wide if $m$ keys are around in order to limit the residual risk that two keys get the same tag to $2^{-r}$. An issue (more practical than theoretical) is that hashing a random value and checking if a (truncated) hash is among the keys might well become the best brute-force attack for an adversary, therefore the keys must be at least $(n+\log_2m)$-bit for $n$-bit security.

A situation that can be encountered (e.g. in satellite TV) is that many different receivers need the same large data set. In order to save bandwidth, an option is to encipher all the packets of such large data set with a random key dedicated to this set, and send (previously) that dedicated key enciphered with the key of each intended recipient. The label of the dedicated key can be in clear in the packets for the data set, and in the previous packets for the dedicated key value.

In the rest of this answer, I consider that hiding who the packets are for is an objective. I'll disregard side channel leaks from receivers (which in practice could very well reveal if a receiver uses or disregards a packet, contrary to the objective).

One option (already discussed) is to encipher the packets in a mode with integrity, such as AES-GCM. We do not need to modify this mode, thus can reuse its security analysis. Main issues with this approach: every holder of a key will need to check the integrity of every packets with its key(s), that's effort/energy; and modes with integrity require more effort/energy and bandwidth than pure confidentiality modes.

Another simple and unobjectionable thing is to start all plaintext packets with constant data (e.g. 12 bytes at zero), have all receivers decipher all ciphertext packets with their key(s) and stop wasting effort/energy on this packet/key pair when it is determined that the plaintext does not match the condition. If the cipher is secure by modern standards (CPA), adding this known plaintext demonstrably does not harm. Addition per comment: padding (or better prefixing) the plaintext with a cryptographic hash of the secret key before encryption would also work, but I see no clear advantage compared to the simplest solution. Don't put the bare secret key in the plaintext, that could conceivably have bad interaction with the cipher (e.g. AES-128's first step is a XOR of plaintext and key, so enciphering the key is a slightly special case).

If we go into something bidirectional (e.g. with acknowledge or retries), then things get more complex, and quite hard, in particular because the mere existence of packets sent by receivers will tend to be revealing of something we try to hide. And again, we should fear side channels.


A Carter-Wegman -style MAC gives you easy deniability when you use a one-time pad to encrypt the universal hash. You can compute a hash for your fake message and choose the key accordingly, just like you do with the one-time pad that you use to encrypt the message contents.

This is actually available widely to programmers: NaCl has crypto_onetimeauth which uses Poly1305 (a polynomial evaluation MAC) with the latter half of the single use key used as a one-time pad. To get the same MAC value for another message you can just compute the MAC, then modify the pad part to match your target.

Not all uses of Poly1305 give you perfect deniability, however. The ones where the key or pad comes from AES (Poly1305-AES) or another cipher (e.g. crypto_secretbox) likely do not because you cannot freely choose the value of it without affecting message decryption or the authentication of other messages.


How does GRC password generator get 512 bit of secret data?

And how they XOR 512bit of data with 128-bit from the monolitic counter?

He doesn't.  Look carefully at the algorithm you posted.  All XOR operations occur on 128 bit values.  The 256 bit entry is the key for a 256 bit AES implementation.  The SPDT switch starts off using the secret IV and then switches to running with a 128 bit counter.  The 512 bits comes from 512 = |IV| + |counter| + |key|. This is all a bit  nonsensical as he's putting in  512 bits of (alleged) entropy and only generating a password of 128 bits.  This is exactly what you've proved to yourself.
 Typically the AES-CTR-PRNG algorithm is as below (without any switches) and Steve's method is characteristically unusual.

  How do they get 512 bit of "secret" data?

Who knows?  It's probably calls to CryptGenRandom (Steve's a Windows man), but perhaps it's just hard coded somewhere. And in assembly only no doubt. Or it might come from his Ultra-High Entropy Pseudo-Random Number Generator based on Latin Squares. Another doozy.

  No one is going to figure out what passwords you have just received.

Reach for the salt.  This is clearly false.  Any SSL intercepting router along the line can decrypt and read the web traffic (on the fly).  And Steve knows too.  Perhaps the moral of this question is - do not use a web service to obtain your password or key from.  If you're really stuck for a key /password either use dice or just randomly hit keys on the keyboard.  That was good enough for top secret one time pads during WW2 so it should suffice for you.

You have actually asked the wrong question.  You should have asked who is Steve Gibson?  Google him and find out.  There are masses of articles.  I can't write any more without sacrificing my composure and professionalism.


Can two files/strings have the same SHA-256 value?

I'm not sure where you're getting $16^{256}$. SHA-256 produces a hash that
is $256$ bits long, so there are $2^{256}$ possibilities.

So, let us consider all $256$-bit inputs. Will they map onto the set of
$256$-bit SHA-256 outputs, one-to-one, no collisions? Almost certainly
not.

If we were encrypting $256$-bit blocks, then yes, they would, because by
definition encryption has to be reversible, so encryption algorithms do
map things one-to-one. But secure hash algorithms are not designed in
this way.

So, instead of thinking there are $2^{256}$ inputs, and $2^{256}$ outputs, and
therefore they're one-to-one, instead think that you are selecting from
a set of $2^{256}$ items, randomly, with replacement. There will probably be
many collisions. Some inputs will map to the same output.

And, of course, once you start considering longer inputs, there are more
inputs than outputs and collisions are inevitable, by the pigeonhole
principle.

However, this does not mean that SHA-256 is broken. Not at all. This
problem of collisions is inherent in any secure hashing system, but
still, we use secure hashes and they work. We wouldn't be able to buy
things online if they didn't work.

In theory, there are collisions, yes. But a hash is only broken if there
is a practical way to generate collisions on purpose. Thus far, no one
has published any such attack on SHA-256, or any of the SHA-2 family of
hashes.


What are access structures in Attribute-Based Encryption?

An access structure is the set of sets that should have access. For example, if the set of parties is $\{P_1, P_2, P_3, P_4\}$ and the access structure, $\mathbb{A}$, is
$$\{\{P_1, P_2\}, \{P_3, P_4\}, \{P_1, P_2, P_3\}, \{P_1,P_2,P_4\},\{P_1, P_3, P_4\}, \{P_2, P_3, P_4\}, \{P_1,P_2,P_3,P_4\}\}$$
then $P_1$ and $P_2$ together have access, $P_3$ and $P_4$ together have access, but $P_2$ and $P_3$ together don't. Note that this access structure is monotonic. Since $\{P_1, P_2\}$ has access, $\{P_1, P_2, P_3\}$, $\{P_1, P_2, P_4\}$, and $\{P_1, P_2, P_3, P_4\}$ all have access.
Yes, it is meant to be the power set. $\mathbb{A}$ is a set of sets of parties.


How can one build $2^{c/2}$ attack on sponge hash?

The hash function, by definition of rate, processes messages in $r$ bit long blocks. Generate about $2^{c/2}$ ($r$ bit) message blocks until you a pair of messages, say $m$ and $m'$ such that you get a collision in the $c$ bits associated with capacity. That is $T_c(\pi(iv \oplus (0^c \| m)) = T_c(\pi(iv \oplus (0^c \| m'))$ where $T_c$ is a function that truncates* the $n$ bit output of $\pi$ to $c$ bits, $iv$ is the internal state of the hash function prior to absorbing any message, $0^c$ is a string of c zero bits, and $\|$ is the concatenation operator.

The internal state of two instances of the hash function after one absorbs $m$ and the other $m'$ now have identical capacity bits, but $\pi(iv \oplus (0^c \| m)) \neq \pi(iv \oplus (0^c \| m'))$ because $m \neq m'$ and $\pi$ is a permutation. Select any value $m_2$ for the second message block for the first instance of the hash function. Then select $m_2'$ for the second block of the second hash such that $m_2 \oplus m_2' = \pi(iv \oplus (0^c \| m)) \oplus \pi(iv \oplus (0^c \| m'))$.

Prior to absorbing the second message block both instances have just their capacity bits identical. You select the second message block to cancel the remaining $r$ unequal bits before the second time $\pi$ gets applied. Since the inputs to $\pi$ are the same, so are the outputs. Now you have a full internal collision. For this reason, just requesting the output of the hash function at this point will yield an output collision. But a collision in a hash function's internal state is more powerful than just a collision between outputs. You can keep generating collisions by choosing a different $m_2$ or by extending the input to both hash functions with new identical message blocks.

The reason you (may) need $2r$ bits of input is so you can cancel the difference in the non-capacity part of the sponge's state. A sponge based hash can be defined such that the last step isn't necessary. Note that once you have a collision in the capacity bits it's trivial to choose the next message block values such that you have a collision.

The algorithm can be defined such that instead of remembering all $n$ bits of output from $\pi$ it only stores the capacity bits. This changes the algorithm. The outputs of two hash functions that differ only by this detail will be different, but the collision resistance of the two is the same.

It may be defined such that performs state updates as in $h_{i} = \pi(h_{i-1} \oplus (0^c \| m_i))$. Where $h$ is the $n$ bit state of the hash function, $m_i$ is the $i$th r-bit long message block, and $0^c \| m_i$ is n bits because $|0^c| + |m_i| = c + r = n$.

Or it could also be defined to do updates as in $h_i = T_c(\pi((h_{i-1} \| m_i))$. Where  $h_i$ is instead $c$ bits long.

Intuitively the difference is that the latter definition overwrites the new message block bits into the sponge state and the former XORs bits into the sponge state. Whether a sponge based hash function is defined one way or the other has no affect on its collision resistance.

TLDR: Just brute force the first message block such that the capacity bits match. Then just pick the second message block to cancel out the remaining r-bit difference.

* In this case discarding the last $r$ bits. I chose to assume in this answer that the hash function was defined such that the rate bits of the sponger were the last $r$ bits and the capacity bits were the first $c$ bits)


Request decryption for three blocks ( 2 is enough);
\begin{align}
P_1 =& Dec_k(C_1) \oplus IV\\
P_2 =& Dec_k(C_1) \oplus C_{0}\\
P_3 =& Dec_k(C_2) \oplus C_{1}\\
\end{align}
Now remove the first ciphertext, and request decryption;
\begin{align}
P'_2 =& Dec_k(C_1) \oplus IV\\
P_3 =& Dec_k(C_2) \oplus C_{1}\\
\end{align}
Now use the equations of $P_2$ and $P'_2$
$$\begin{align}
P_2 \oplus P'_2 &= Dec_k(C_1) \oplus C_{0} \oplus Dec_k(C_1) \oplus IV\\
& = C_{0} \oplus IV \\
P_2 \oplus P'_2 \oplus  C_{0} &= IV \\
\end{align}$$

In programmer aspect
defn CBCDecryptionOracle(c[]):
   return Dec(c[])

c = (c1,c2)

p1 = CBCDecryptionOracle(c)

d = c[0]

p2 = CBCDecryptionOracle(d)

print( p1[0] ^ p2 ^ c0)


Do you need to grant someone the ability to encrypt messages whom you do not want to grant the ability to decrypt messages?  If so, you need public-key encryption—and you probably want public-key authenticated encryption.

For example, if you want to separate the ability to create archives from the ability to read archives at a later time, then you probably need public-key (authenticated) encryption, like Tarsnap.

Although you might be the only human in the system handling the archives, the machine that creates the archives—a virtual server hosted at Amazon constantly listening to the internet, say—might be meaningfully distinct from the machine that reads them—e.g., a laptop deployed only once, in an emergency, with a USB key stored under your mattress—and as such you might impose a meaningful privilege boundary between them.
Consider using NaCl box instead of building something yourself out of difficult parts like RSA with OAEP.

As a bonus, NaCl box is smaller than anything you build out of RSA, and decryption is much faster, and the code will be simpler, and you naturally get public-key authenticated encryption where it would take much more work to design a bespoke system with RSA.

Is the party that encrypts messages the same as the party that decrypts messages, with no meaningful privilege boundaries?  If so, then NaCl secretbox is fine.


Using Pollard's lambda in a key-recovery attack on DH

it simply tells a user to "calculate $y^*$", a calculation which itself appears to require several unknown values

Nope, it has $y^* = y / g^V$, where at this point, you know $y$, $g$ and $V$.

The original discrete log problem was given as $y = g^x$, and so you were given $y$ and $g$

In addition, $V = x \bmod z$, where $z$ is a smooth factor of $n$ (the group order, which the algorithm assumes you know). You can find the value of $V$ by taking the group order $n$, doing a partial factorization to obtain $z$ (even if it is infeasible to complete factor $n$, it's easy to find the small factors of $n$), and then by solving the Discrete Log problem $y' = g'^V$, where $g' = g^{n/z}$ and $y' = y^{n/z}$.  This particular Discrete Log problem can easily be solved by the Pohlig-Hellman algorithm, as $g'$ is in a subgroup of order $z$, which is smooth.


Generating a secure random number in javascript

I would take a look at https://github.com/mdp/gibberish-aes/ From that you can see well implemented ECMAscript, (javascript) and AES can be used to generate random numbers. It might be slightly over-kill for your needs, but should not let you down in the medium-term.


Is the polynomial reconstruction problem really "intractable"?

The polynomial $p$ of degree $k$ can be reconstructed if at least $k+1$ correct points
are known (that is, we know that $(x_i,y_i), 0 \leq i \leq k$ are correct meaning that
$y_i = p(x_i), 0 \leq i \leq k$), and in this
case, Lagrangian interpolation works. If the points are being made available one at
a time instead of all at once, Newtonian interpolation is an even better method for
on-line interpolation.

If an adversary finds out $n$ points of which at least $t > k$
points are correct (though the adversary does not know which
$t$ points are correct), then the adversary can use Reed-Solomon
decoding techniques to determine
$p$ as long as $t \geq \frac{n-(k+1)}{2}$, that is, among the
$n-(k+1)$ "extra points", there are
at least as many correct points as there are incorrect points.
The Reed-Solomon decoding process will also tell the adversary
which of the points are incorrect. Note that the adversary
knows the values of $k$ and $n$ but not necessarily the value
of $t$ but can still use the Reed-Solomon decoding process,
and this process is guaranteed to find $p$ (as well as $t$)
and to identify the incorrect points as long as there are
at least as many correct extra points as incorrect points.

What happens when there are fewer correct extra points than incorrect points?
Well, the adversary does not know this and can launch the
Reed-Solomon decoding process but the process will recover $p$
only in extraordinarily rare circumstances. The process will
find some polynomial $\hat{p}$ but the adversary can readily
determine that this is not the right answer by checking whether
$\hat{p}(x_i)$ equals $y_i$ for most of the points (as it should
for the correct $p$).


Oblivious transfer impossible from noiseless channels

Information theoretic OT cannot be achieved because OT can compute any function in a two party setting, that is, OT is complete (meaning, it is among the hardest problems in its complexity class)  as shown by Kilian[0]. We know that there are functions that cannot be information theoretic securely in a two party setting[1]. Hence, information theoretic OT is impossible.
[0] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.9265&rep=rep1&type=pdf
[1] https://eprint.iacr.org/2006/183.pdf


Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency

Yes!  There are verifiably pseudorandom functions or VRFs made out of elliptic curves including EC-VRF, related to ECDSA, and VXEdDSA, related to EdDSA.  In addition to getting a unique output for each message, the output is a pseudorandom function of the message, and you get a proof of uniqueness.

More references on VRFs.


Rationale of the SHA-256 sigma function definitions

It is the naming of functions and the functions are already defined - rotations (ROTR) and x-ors ($\oplus$). There are two $\Sigma$ and $\sigma$ functions for SHA-256 and SHA-512 series. And, in Greek, the $\Sigma$ is capital of $\sigma$.

The upper index represents the SHA family as 256 and 512. The sub-index, selects the function. $\Sigma_{0}^{\{256\}}$ means the first $\Sigma$ function of SHA-256 series. Note the curly braces.

Note: the functions are started to appear with SHA-2 series. It is not listed with SHA-1, the document can be seen from archive.org


Why does it make sense to use min-entropy for measuring cryptographic random data?

Ignore NIST. It has more important legally binding agendas to debate outside of this forum. Use common sense.

Does min-entropy satisfy the properties of an entropy measuring function laid out by Shannon? If not, why is it being used for measuring entropy?

No. $H_{\infty}$ is to Shannon entropy as is JPEG to BMP. Shannon was interested in encoding all the data in the transmission channel.  $H_{\infty}$ is lossy and the original data cannot be retrieved in it's entirety. $H_{\infty}$ is used before transmission.

entropy is produced in raw random data

Yes. So measure it. You will have a lot more luck if you can prove the data to be IID.
It boils down to this:-

You need to separate information entropy from cryptographic entropy.
We want true random bits.
We get them via some generic form of hardware processing.
Current mathematical thinking revolves around the left over hash lemma which dictates the eventual output bias.
The thinking is predicated on $H_{\infty}$.
Thus $H_{\infty}$.


How to calculate elliptic curve parameters?

It is possible to find the desired values in an acceptable amount of time.

TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order.

First, you can use yyyyyyy's answer to find the order $n$ of the described curve using Schoof's algorithm. Please note that this order should be prime or a small multiple (4x-8x) of the a prime for enhanced security but it doesn't have to have those properties for the schemes to work.

In the next step, you need to actually factor that order. This is feasible as this order usually will be around 500 bits of length (or a lot less if you're not going for the 256-bit security level), which can be done and was done for FREAK. Of course, if the curve order is prime or a small multiple of a prime (4x-8x) the factorization may not need to be obtained with the GNFS but may be either given (prime case) or findable by trial division (small multiple case).

Finally you just select a curve point and determine its order until you hit one with the desired order $t$ which will also yield the cofactor as $h=n/t$. Usually you'll want to have $h\leq 8$ and usually you'll also start with the points having small x-Coordinates and try all incrementally until you reach one fullfilling your conditions.

The algorithm for this can be found in a variety of places in the literature and I'll quickly restate the one from the Handbook of Applied Cryptography, assuming we're testing the point A and that $n=p_1^{e_1}\cdot p_2^{e_2} \cdot\cdot\cdot p_k^{e_k}$:

Set $t\gets n$
For $i$ from $1$ to $k$ do the following:

Set $t\gets t/p_i^{e_i}$
Compute $A_1\gets t\cdot A$
While $A_1\neq \mathcal O$ do the following: compute $A_1\gets p_i*A_1$ and set $t\gets t\cdot p_i$

Output $t$ as the order of $A$

Please note: I strongly recommend against using custom curves where the parameters are chosen by the user. These may be vulnerable to attacks documented in the safe curves project. Standardized curves (like Curve448 or Curve25519) should be preferred for easier implementation and better analyzed security properties.


Why there isn't a consistent key transform function of HMAC?

Why does HMAC do that?

The process of expanding or compressing the key material to exactly one block length this way shouldn't be necessary from a security perspective. The reason for this transformation is to enable an optimization when the same key will be used to process multiple messages. (See RFC 2104)

If this optimization is used, it means that you can eliminate the need to process the inner key more than once. This part of the specification allows an implemenation take a snapshot of the hash function state after processing a whole block. If anything less than one block were used, then this wouldn't help. A hash function cannot process part of a message until after it knows the full block.

Because the first block never contains message bits, it is possible to pre-compute this hash function state as soon as you know the key. Had the first block been allowed to contain message bits, there wouldn't be much work HMAC's underlying hash function could do until it knew those message bits.

Consistently padding keys to a multiple of the block size would also allow pre-computation. But I'm guessing that method was ruled out to save a few bytes RAM/ROM and keep things related to this optimization simple.

The one security downside to the actual HMAC specification is that it is trivial to generate distinct but equivalent keys.

(That's only an issue if the source that provides the key is untrusted, key sizes are variable, and there is something application-specific that requires it be impossible to find equivalent keys. For basic message authentication a trusted source or fixed length key is enough to avoid that potential issue.)

Why is it inconsistent?

I don't know, but it was published in 1996. There are a bunch of examples of 90's cryptography that seem strange in hindsight.

HMAC could have been designed in some other way that enables similar optimizations. Something as simple as prepending the key length to the inner key then padding the new string with zeros to a multiple of one block size, for example.

In practice there isn't much need to implement case 3. Most modern hash algorithms (and even insecure algorithms from the same era as HMAC, like MD5, SHA-1, and RIPEMD) have block sizes much bigger than the length needed for symmetric keys.

(However, key exchange algorithms may generate larger shared secrets, but then you probably have access to something like HKDF. (You shouldn't use the same key for encryption and authentication, after all.))

It wouldn't be unreasonable to write an implementation that only supports case 1 and 2. (The decision should be documented and trying to use HMAC with overly long keys should be treated as an error.) In my opinion it's probably a good idea to force programmers to explicitly pre-hash long keys if they need full compatibility with HMAC.


1024 RSA Hash Signature attack. Forge a valid signature

A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach.  And, you can't control the output of MD5, and so it'll give you effectively random values.

A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ is the MD5 hash of the $i$th message).  Then, you would factor each $M_i$, and look for linear combinations of common factors.  At the same time, you would hash a large number of messages, and look for a message  with an MD5 hash $M$ that can be represented by a linear combination of signed messages $M = M_a^{i_a} M_b^{i_b} ... M_z^{i_z}$.  When you find such a linear combintation, you then have the signature for that message $S = S_a^{i_a}S_b^{i_b} ... S_z^{i_z}$


How to generate a ciphertext independently decodable with multiple keys?

One way to do it is to generate a random, single-use key $K$ and encrypt (and preferably authenticate) the message with that. Store the (authenticated) encryption of $K$ under each of $key_1, …, key_N$ alongside the message. The required storage is $\Theta(N + \text{message length})$.

This is routinely done when transmitting messages using asymmetric encryption, for example when sending an email encrypted with PGP to multiple recipient. A the message is encrypted and authenticated with a single-use key, and the encrypted email contains the encryption of that key with each recipient's public key in addition to the ciphertext.


Known methods for constant time (table-free) AES implementation using 'standard' operations?

Generally speaking, a lookup-table can be implemented in constant time by doing it as if it was a hardware circuit.

Consider a multiplexer: this is a circuit which accepts three inputs $a$, $b$ and $c$, and yields one output $d$ which is equal to $a$ if $c = 0$, to $b$ otherwise (I am talking about single-bit values here). A multiplexer can be used to implement a $1\rightarrow1$ lookup table: set $a$ to the value of the table for a "0" input, $b$ to the value for a "1" input, and set $c$ to the actual input you want to transform.

If you store single bit values in variables, the corresponding C code looks like:

d = (a & ~c) | (b & c);

which has a constant execution time.

If you know how to implement $n\rightarrow1$ lookup tables with constant-time code, a $n+1\rightarrow1$ lookup table is obtained by isolating the last bit: you consider the two $n\rightarrow1$ sub-tables, the first one being the table you get by setting the last bit to 0 or 1, respectively. Then you use the outputs of those two sub-tables as $a$ and $b$ inputs for an extra multiplexer controlled by the last input bit. This means that a $n+1\rightarrow1$ table is just a pair of $n\rightarrow1$ tables and extra bit which decides which of the two tables we were actually talking about.

With this construction, a $8\rightarrow1$ table is implementable as a tree of 255 multiplexers like the one above. The AES S-box is an $8\rightarrow8$ table, and is applied to 16 values in parallel at each round, so you end up to having to evaluate $128\times255$ multiplexers per round.

However, with the C code above, you are actually computing several multiplexers in parallel. If the C variables are 64-bit values, then you are doing 64 multiplexers simultaneously: bits of index 0 talk to other bits of index 0, bits on index 1 with bits of index 1, and so on, up to bits of index 63. This is known as bit slicing. Due to the similarity of structure in AES, you can use that to reduce the number of multiplexer evaluations to $4\times 255$ per round: a mere thousand...

With such techniques, you can end up with a constant-time, plain C implementation of AES which should evaluate a block in, say, 20000 clock cycles. Which is awfully slow, but still doable. However, this is only the beginning. There are many optimizations which can be applied to such a structure (e.g. you can replace multiplexers with a not-exactly-a-multiplexer construction "a ^ (b & c)", which selects between $a$ and $a \oplus b$ ($a$ xor $b$), and is enough to implement a lookup table; also, the first row of multiplexers in a tree can often be collapsed since its inputs are known values of 0 or 1). For the DES S-boxes (eight distinct $6\rightarrow4$ tables), very optimized bitsliced implementations were designed by Matthew Kwan back in 1998. Moreover, the AES S-box has an internal algebraic structure which can probably be further exploited.

A google search on "bitslice implementation AES" links to a few research papers, but apparently none being publicly downloadable.


Is F' a pseudorandom function when F is composed with G, a pseudorandom generator?

Certainly yes.
Proof
A pseudorandom function must produce pseudorandom output for any given input. So, any seed value will provide a pseudorandom output. However, this might not work if the function has a limited input domain (list of possible inputs) causing incompatibility with the two functions. In your case, $F$ should be able to process the input provided by $G$, and vice-versa for the second case.
Proof of concept
Let $F$ be a hash function, say SHA-3, and $G$ be AES-CTR, Then:
Case 1, $F'_k(x)=F_k(G(x))$: AES-CTR would generate a pseudorandom sequence which would be hashed by SHA-3, and, needless to mention, cryptographic hash functions are supposed to produce strong pseudorandom output, regardless of what the input is.
Case 2, $F'_k(x)=G(F_k(x))$: The hash digest of $x$ produced by SHA-3 will be used as a seed for AES-CTR, and, once again, block ciphers are also meant to produce strong pseudorandom output regardless of the input.
Verdict
Both the implementations suggested in the Proof of Concept section explain how $F'$ acts as a pseudorandom function. It is important to know that the security and quality of pseudorandomness is highly dependent on the outer function, $F$ in case 1, and $G$ in case 2, as it's output is what determines the required. The underlying function will only work as an internal state generator, where the state could have been anything, not necessarily pseudorandom.
So, building a PRNG by chaining two different PRNGs (as you did in your post) will surely work out.


Why ISO/IEC 9796 (signature with message recovery) instead of just encrypt the short message with private key?

I'll be taking the question as: when signing short-enough messages, why don't we simply put the message where there is the message's hash in RSA signature padding like RSASSA-PKCS1-v1_5 or RSASSA-PSS of PKCS1v2.2?

Usual RSA deterministic signature as appendix goes $M\mapsto M\mathbin\|((P(H(M)))^d\bmod N)$ where $M\mapsto P(H(M))$ is a one-way function from the message space to $[0,N)$, built from a reversible injection $P$, and a hash $H$ for the one-wayness. The proposal is to change this to $M\mapsto (P(M))^d\bmod N$. That removes the one-wayness.

We don't have a constructive argument that's secure, and it should be reason enough not to do this. Worse, the gone one-wayness had a security role: preventing turning arithmetic properties of $x\mapsto x^d\bmod N$ into attack, by preventing going from $x$ with suitable arithmetic properties and in the right subset of $[0,N)$, to message $M$ with $P(H(M))=x$ allowing exploitation of said properties.

For some padding shemes, that removal of the one-wayness is enough to allow attack. Consider RSASSA-PKCS1-v1_5: we can obtain the signature of one message from the signature of three chosen ones, which is a break.

With the modification, the signature of $m$-byte message $M$ using private key $(N,d)$ with $n$-bit $N$ is, assimilating bistrings to integers per big-endian convention
$$\begin{align}
\mathcal S(M)&=(\mathtt{00\,01\,FF\dots FF\,00\,XX\dots XX}\mathbin\|M)^d\bmod N\\
&=(R\cdot2^{8m}+M)^d\bmod N\end{align}$$
with some fixed public integer $R\lesssim2^{193}$, when $m=\left\lceil\displaystyle\frac n8\right\rceil-26$. For example, consider message $M$ of $m=230$ bytes signed with $n=2048$-bit (256-byte) RSA key.

Now, if we find 4 distinct $m$-byte messages $M_0$, $M_1$, $M_2$, $M_3$ with $$(R\,2^{8m}+M_0)\,(R\,2^{8m}+M_1)=(R\,2^{8m}+M_2)\,(R\,2^{8m}+M_3)\tag{1}\label{eq1}$$
then it follows that $\mathcal S(M_0)\,\mathcal S(M_1)\equiv\mathcal S(M_2)\,\mathcal S(M_3)\pmod N$, and thus
$$\mathcal S(M_0)=\mathcal S(M_1)^{-1}\,\mathcal S(M_2)\,\mathcal S(M_3)\bmod N$$
which is easy to compute from $N$ and the signatures $\mathcal S(M_1)$, $\mathcal S(M_2)$, $\mathcal S(M_3)$.

We can take
$$\begin{align}
M_0&=R\,((2^{4m+i}+a)\,(2^{4m-i}+b)-2^{8m})\\
M_1&=R\,((2^{4m+i}+c)\,(2^{4m-i}+d)-2^{8m})\\
M_2&=R\,((2^{4m+i}+a)\,(2^{4m-i}+d)-2^{8m})\\\
M_3&=R\,((2^{4m+i}+c)\,(2^{4m-i}+b)-2^{8m})\\
\end{align}$$
which insure $\eqref{eq1}$ holds; and suitably small $i$, $|a|$, $|b|$, $|c|$, $|d|$ so that $0\le M_j<2^{8m}$. For example, $i=0$, $a=b=1$, $c=2$, $d=3$ will do.

Using that large class of messages, we can easily obtain $s$ bogus signatures from $s+3$ signatures of chosen messages. Or/and, since there's considerable freedom in the choice of the messages, we can force some application-imposed bytestring into some section of the messages, bringing that theoretical attack closer to practice. There are further classes of messages allowing other attacks.


Is the any QR code with built-in hash of the information?

There are encrypted QR codes from DENSO ADC.  I know that these can be encrypted or just signed; however, DENSO ADC has never been forthcoming with how they work.  They seem to work by putting data after the "data section" of the QR code that would otherwise be ignored.  If you were going to have something similar, I would take that approach.


How to prove the PRF, $F(k,x) = (k \wedge x ) \oplus k$ is PRP?

Your definition tries to say that a permutation must be invertible.

When the key is $0$, we can not determine the inverse of 0 and the inverse of 1 doesn't exist.


What is the motivation behind Key-policy Attribute-based Encryption?

I believe the answer cygnusv gave is not fully correct. If an object is tagged with "NUCLEAR, TOPSECRET" it can potentially be decrypted by someone not having the TOPSECRET attribute (or NUCLEAR attribute). Why? Because it all depends on the structure of the private keys in the system.

A private key could for example be: "NUCLEAR or SCIENCE LAB A". Thus it would suffice for the object to be tagged with NUCLEAR for this person to gain access.

This is also one of the reasons to why KP-ABE is "less intuitive" because the encryptor does not specify the relation between the attributes that are tagged. Instead it is the key authority (or just authority) which will decide how these attributes needs to be combined for access.


Zero Knowledge Proofs: to establish a public key cryptography encryption

By using SPAKE2, we can achieve this as Poncho said in comments.

Let $s_a$ be the salary of Alice
Let $s_b$ be the salary of Bob
Let we have Ed25519 curve with the base point G.

Exchange part;

Alice  pics a random scalar $x$ and calculates $X = x\cdot G$ and $T = s_1\cdot M+X$, where $M$ is another point on ECC and sends the value $T$ and $M$ to Bob (pake message).
Bob pics a random scalar $y$ and calculates $Y= y\cdot G$ and $S = s_2\cdot N + Y $, where $N$ is another point on ECC and sends the value $S$ and $N$ to Alice.

Key calculation part:

$Key_{Alice} = x ( S - s_a \cdot N) = x ( s_b N + Y - s_a N ) = x(s_b - s_a)+xyG $
$Key_{Bob} = y ( S - s_b \cdot M) = x ( s_a M + X - s_b M ) = x(s_a - s_b)+xyG $

if $s_a = s_b$ then we will have a cancelation to $xyG$ on both sides. Now, two sides can assume that they have a key agreement, without knowing the equality. They can encrypt pre-agreed plaintexts and sent each other, after this, they can conclude that their salaries are the same if the decryptions are successful, they conclude otherwise if not successful.

After the conclusion of success, one can convert the result into a bit $b$ by;

if p1 == Dec(xyG,c1)
   return 1
else
   return 0


Do I have to transfer the private key to digitally sign a remote document?

It is logically impossible to transfer a private key. The key will continue to be a signature key, but it will cease to be "private" the minute it is transferred. A signature key that isn't private isn't a private key. If you want the document to be signed by the user (in any semantically coherent sense), this operation has to take place on a device exclusively controlled by the user.

This doesn't mean that it is logically impossible to delegate digital signing to a third party, it just means it has to be done slightly differently. If (in real life) you appoint someone to act as your proxy, you don't authorize that person to sign documents using your signature. Instead, you sign a letter of appointment that authorizes your proxy to sign documents on your behalf. The proxy will then use its own signature.


Why is the permutation in AES (and other ciphers) not random or key-dependent?

You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks.  It would not.

ShiftRows and MixColumns were carefully selected to work in tandem, such that every byte affects every other byte in the state within just two rounds.  MixColumns ensures that every column of four bytes has a minimum of five differentially active bytes before and after that step (i.e. if you add the differentially active bytes in the column before MixColumns to the active bytes in the column after MixColumns, the number is at least 5).  ShiftRows ensures that every column after the step includes a byte from every column before the step.

Together, the two steps operate to put a high lower bound on the number of differentially active s-boxes over 4 rounds:  the AES creators proved that a minimum of 25 s-boxes are active over 4 rounds, minimizing the probability of any differential characteristic/trail.

There are alternatives to ShiftRows that do the same thing (see e.g. the cipher SQUARE which swaps columns and rows).  But a random byte permutation would likely not ensure such a high minimum number of active s-boxes over as few rounds as ShiftRows.


The term "plaintext" in cryptography does not imply that the input is actual text. Traditionally, the plaintext was often actual text, but the term just refers to the input (other than the key) to the encryption algorithm. Plaintext can be a sequence of letters, like in many classical ciphers; it can be an analog telephone signal; it can be an image or map; it can be whatever the cipher uses as an input. In modern digital ciphers, the plaintext is a stream of bits, possibly with length constraints, because that's the kind of data you already have when you're working with computers. Modern ciphers can handle any stream of bits (again, possibly within those length constraints); it doesn't matter what the stream of bits represents. An EXE file is a stream of bits, so it can be encrypted.


Sending the MAC key with the message pretty much negates the point of a MAC, since anyone can modify the message and regenerate a new MAC using the key. Nothing theoretical with that. You might as well omit the MAC entirely.(1)

So yes, the MAC key should be considered a secret, just like the encryption key.

I think the answer in the question you linked pretty much answers the rest of your questions: Yes, you should use independent keys for the encryption and the MAC, because otherwise you run the risk of subtle interactions between the algorithms foiling your scheme. Though in the case of AES and HMAC-SHA256 you'll likely get away with it, but it would still be good hygiene to use distinct keys. Run your master key through a KDF (or just a strong hash like SHA-512) to get separate keys for the encryption and the MAC.

Of course you could generate the MAC key from random bytes given by your system's RNG, but you'd still need to transfer the key to the other end. That would need to be done similarly to how the encryption key is transmitted, not at the per-message logic which you've shown.

(1) Though an unkeyed hash would still serve to detect accidental corruption.


Covert two-party/multi-party computation provides exactly what you're looking for.  The two-party case was introduced by von Ahn, Hopper, and Langford, and a more formal definition and multi-party protocol was given by Chandran, Goyal, Ostrovsky and Sahai.

Covert secure computation even hides whether or not the parties participated in the computation at all, unless the result of the computation determines that it should be revealed.  For Alice and Bob, their inputs would be one bit each, indicating whether each is romantically interested in the other, and the function to be computed on these bits is AND.  If the function output is 1, then that fact is revealed to both of them and they live happily ever after.  Otherwise, they don't even learn whether the other even played the protocol.  So if Bob likes Alice but not vice-versa, Alice won't even learn that Bob participated at all, thus saving him from eternal embarrassment in her presence.

The von Ahn et al paper gives many more applications of the concept, e.g., two undercover spies from allied countries who may want to collaborate.


Why blake2b is the fastest despite it being 512 bits hashing algorithm?

I am struggling to understand why blake2b is faster than blake2s, despite that blake2b is 512 bits hashing.

Comparing is not easy. They designed

BLAKE2b for 64-bit platforms including NEON enabled ARMs. That can produce between 1 and 64-byte digest

BLAKE2s for 8- to 32-bit platforms. That can produce between 1 and 32-byte digest

They are fast on their target

Each one is portable to any CPU, but can be up twice as fast when used
on the CPU size for which it is optimized; for example, on a Tegra 2 (32-bit ARMv7-based SoC) BLAKE2s is expected to be about twice as fast as BLAKE2b, whereas on an AMD A10-5800K (64-bit, Piledriver microarchitecture), BLAKE2b is expected to be more than 1.5 times as fast as BLAKE2s.

Even BLAKE2b does 12 rounds, and BLAKE2s does 10 rounds it still faster on their platform. And the CPU word size has a huge effect, too.
They modified the original design of BLAKE with the confidence it's security well tested. From the Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition

Keccak received a significant amount of cryptanalysis, although not quite the depth of analysis applied to BLAKE, Grøstl, or Skein

Some of the modifications; BLAKE2b uses 24-bit rotations that use SSS3 and can perform two rotations on parallel. Originally BLAKE was using 25 (now 24) and 11 (now 63) bit rotations. In addition, the 63-bit rotation can be also fastened on some recent Intel CPUs.
AVX and AVX2 (Advanced Vector Extensions) can boost any code whenever applicable. BLAKE2b benefits form AVX/2 whenever available. More detail can be found at BLAKE and 256-bit advanced vector extensions paper.
As having past experience on Cray Vector Machines, I can pretty surely say that if your code is vectorizable, you gain huge speed up.


what Pedersen commitments are

In a commitment scheme such as Pedersen

the committer (or sender) decides (or is given) a secret message $m$ taken in some public message space with at least two elements;
decides a random secret $r$;
produces from that $m$ and $r$ a commitment $c=\mathcal C(m,r)$ by applying some public method (the commitment algorithm $\mathcal C$) defined by the scheme;
makes $c$ public;
later reveals $m$ and $r$.
The verifier (or receiver) is given $c$, $m$, $r$ and can check if indeed $\mathcal C(m,r)=c$. That will always hold if 1/2/3/4/5 are carried out as stated.

Informally, that must not hold in any other case met, including if the committer changes $m$ between steps 1 and 5 or chooses $r$ maliciously. Further, $c$ must give no clue about $m$ before step 5.

More formally: an adversary succeeds if s/he can exhibit any of the following

$m$, $m'$, $r$ and $r'$ with $m\ne m'$ and $\mathcal C(m,r)=\mathcal C(m',r')$
$m$ and $m'$ with $m\ne m'$ and such that, for a random secret choice of $r$ and given a randomly chosen value among $c=\mathcal C(m,r)$ and $c'=\mathcal C(m',r)$, the adversary can decide with probability sizably better than 50% it the given value is $c$ or $c'$.

Pedersen commitment uses a public group $(G,\cdot)$ of large order $q$ in which the discrete logarithm is hard, and two random public generators $g$ and $h$. Random secret $r$ is chosen in $\Bbb Z_q$, the message $m$ is from any subset of that. The commitment is $\mathcal C(m,r)=g^m\cdot h^r$.

The reference description is section 3 of Torben Pryds Pedersen's Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, in proceedings of Crypto 1991.

  what they are used for

Commitments are the cryptographic equivalent of secretly writing $m$ in a sealed, tamper-evident, individually numbered (or/and countersigned) envelope kept by who wrote the message. The envelope's content can't be changed (binding property), and the message can't leak (hiding property). Among improvements brought by cryptography, we do not need to check that the envelope was actually sealed, and things can be done remotely; numbers are aplenty and recyclable. On the other hand, we need computers, and the method will convince only those that trust both math and the computer they use.

An example application is fairly deciding who serves first in a tennis match between Bob and Carol, in a way convincing both of them and Valery (acting as referee). It is agreed that if Bob can guess Carol's choice, Bob serves first; otherwise, Carol does.

Using such envelope, that could be done as:

Carol secretly decides $m$ in $\{0, 1\}$, writes it on a paper, puts it the envelope, seals it, shows that to Bob and Valery, but keeps the envelope.
Bob announces a guess $m_b$ in $\{0, 1\}$; he and Valery do not know the outcome yet, but Carol does.
Carol states her choice of $m$ and gives the envelope to Valery.
Valery checks if $m\ne m_b$ and (needed only in the affirmative) opens the envelope to check if it does contain a paper with $m$ written on it; in which case Carol serves first. Otherwise, Bob does.

Using a commitment, Carol acting as committer and Valery acting as verifier:

Carol secretly decides $m$ in $\{0, 1\}$ and performs 2/3/4, announcing $c$.
Bob announces a guess $m_b$ in $\{0, 1\}$; he and Valery do not know the outcome yet, but Carol does.
Carol states her choice of $m$ and $r$.
Valery checks if $m\ne m_b$ and (needed only in the affirmative) $\mathcal C(m,r)=c$; in which case Carol serves first. Otherwise, Bob does.

Bob can't cheat, because $c$ (which he knows when choosing $m_b$) gives him no clue about $m$.

Carol can't cheat by choosing $r$ so that $\mathcal C(0,r)=\mathcal C(1,r)$ and giving the resulting value as $c$, which would allow her to announce $m$ per $m_b$. Having failed that, she can't reverse her choice of $m$, because the check $\mathcal C(m,r)=c$ will then catch that.

As pointed by Poncho, $H(m,r)$ where $H$ is a (preimage-resistant) hash is a commitment of $m$. Compared to this, Pedersen commitments:

Allow things such as proving additive equalities (modulo the group order) among committed values, without revealing them; and more.
Maintain their hiding property even w.r.t. computationally unbounded adversaries.


Can private data be encrypted and stored safely in public?

The short answer is: if and only if the key is never compromised and the algorithm is never severely broken.

To inject some realism into this question, one real-life event that's worth knowing is how Wikileaks' encrypted file of USA diplomatic cables got compromised.  Bruce Schneier had a good summary at the time (it's not a primary source, but he links such sources).  But the basic idea is:

Wikileaks encrypts a file with lots of sensitive information, using password-based encryption.
Wikileaks shares the file and password with a journalist.
Wikileaks posts the encrypted file into Bittorrent as a backup/survival measure.
The journalist, who is not technically savvy at all, writes a book and uses the password as a chapter title.
Observers manage to put two and two together, download the torrent, and decrypt it with the password from the book.

How does this address your question?  Well, if the file had not been uploaded to a public system like Bittorrent, the damage from the exposure of the password would have been much smaller.  So publicizing a ciphertext widely certainly carries additional risks.

That's not a yes/no answer to your scenario, because there isn't one.  Restricting the circulation of the ciphertext is always safer, but this is really a risk vs. convenience tradeoff where you might reasonably opt for convenience, depending on the application.


Curves intended for both signing and key agreement

Technically, any elliptic curve can support both signing and key agreement. However, Curve25519 as described in the original paper is meant for $x$-only arithmetic. This means that one never computes the $y$-coordinate. The issue is that you need the $y$-coordinate for signature verification in the standard algorithms (ECDSA, EdDSA).

Therefore, if you want to do signatures with the Curve25519 curve, you need to compute the $y$-coordinate. There are different ways to do this, one is to simply leave the curve as is (in "Montgomery form") and compute its $y$-coordinate. A different way, is to transform the curve into a new shape (the "twisted Edwards form") and do arithmetic there. This new curve is called Ed25519, and it is "(birationally) equivalent" to the old curve. There are even more flavours.

Again, the choice you make will be for efficiency and security. Not because one curve can be used for signatures while the other can't. I suppose the $y$-coordinate computation on Curve25519 is slow enough for people to prefer using Ed25519 instead.


In q-SDH problem, where are those points $\frac{1}{\beta+x}g_1$ or $g_1^\frac{1}{x+c}$ on elliptic curve?

The linked paper is not about Elliptic Curves which relies on additive groups. It is about the multiplicative groups. For both of them the discrete logarithm is defined. There are common notations that confuse people about them.
In the multiplicative version, the division is actually not a division like in the reals. It is the inverse in the group and sometimes written both way.
$$\frac{1}{\beta+x}g_1 = (\beta+x)^{-1}g_1$$
Similarly $$g_1^{1/(x+c)} = g_1^{(x+c)^{-1}}$$
If you want to convert the idea in to elliptic curve you need to replace the exponent with the elliptic curve scalar multiplication. We can see this from here
The power in the multiplicative group is actually a definition by
$$g^x := \underbrace{g \cdot g \cdots g}_{x-times}$$
and similarly the scalar multiplication in elliptic curve is also a definition by
$$ [x]P : = \underbrace{P + P + \cdots + P}_{x-times}$$
Both have faster calculation methods see the Wikipedia Pages.

For multiplicative groups see the Exponentiation by squaring
For Elliptic curves see the Elliptic curve point multiplication


I believe there is strong enough precedence for using the term threshold decryption for the second.

The abstract of this paper states:

  A threshold decryption scheme is a multi-party public key cryptosystem that allows any sufficiently large subset of participants to decrypt a ciphertext, but disallows the decryption otherwise.

Sounds to me like what you are talking about. A search for "threshold decryption" turns up plenty of hits too.


The circuit term in the evaluation of functions with FHE is a coming from  Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $f$ with available FHE operations so that we can evaluate the $f$ with FHE.
Somewhat Fully Homomorphic schemes allow us to operations on ciphertexts. In the bitwise case, for example; you will have two operations on the ciphertext bits;
$$ E(p_1) + E(p_2) = E(p_1 +p_2)$$ and
$$ E(p_1) * E(p_2) = E(p_1 *p_2),$$ where $p_1$ and $p_2$ are plaintext bits and E is a fully homomorphic scheme as;

Fully Homomorphic Encryption over the Integers
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

To evaluate a function $f$ with FHE, we consider it's circuit implementation with the two above operations. It is similar to what we do in Electronics, that is; we can build a circuit for $f$ by using the binary operations, AND, OR, NOR, etc. and see universal logic gates and Functional Completeness
In FHE we have two operations and this is enough, up to some point. The name Fully is meaning that it supports two operations.
Unfortunately (or fortunately), The FHE schemes are semantically secure, this means that;
$$a = b \not\Rightarrow E(a) = E(b),$$ and even the equality only hold with negligible probability. As a result of this; currently, it is not practical to build a circuit for every function to evaluate.

Some FHE circuits
In the below demonstrations, I'll stick to HELib based on Fully Homomorphic Encryption without Bootstrapping. Using different schemes may require different circuit implementation. In HeLib case; we have these binary FHE operations on the ciphertext;

$+$ is $\oplus$ and
$*$ is $\wedge$ opereation.

NAND Gate
Although the NAND gate is universal, we can construct it by using the AND and XOR
$A  \text{ nand } B = ( A * B ) + 1$
Full adder
Let $A=E(a),B=E(b),C=E(c)$ we will calulate the sum $S$ and carry $S'$ as;
$S= A \oplus B$ and $S'= A \wedge B$, as the usual circuit.
n-bit Full adder
can be implemented same as ripple carry adder
if/else
we can build it with a 2:1 multiplexer as;
$$Q = (A * S) + (B * S'),$$ this circuit is the combinational logic of the if/else statement and we can construct this with FHE.

FHE encrypted $S$ is the input by the if statement.

FHE encrypted $A$ is the input by the  then statement

FHE encrypted $B$ is the input by the  else statement

FHE encrypted $Q$ is the output of the expression.
Actually, This is the base of the FHE PIR implementation. Remember all values are encrypted semantically.

Equality
Given to 2 $n$-bit numbers $x$ and $y$;

$x= \{x_{n-1}, \ldots, x_{0}\}$
$y= \{y_{n-1}, \ldots, y_{0}\}$

with the FHE encrypted values;

$X= \{E(x_{n-1}), \ldots, E(x_{0})\}$
$Y= \{E(y_{n-1}), \ldots, E(y_{0})\},$

where $X$ and $Y$ holds the encrypted lists of $x$ and $y$.
we can compute two plaintext equality under FHE by using the following circuit;

component wise $\oplus$, $Z = \{E(x_{n-1}) \oplus E(y_{n-1}),\ldots,E(x_{0}) \oplus E(y_{0})\}$
component wise invert; $Z' = Z \oplus \{E(1),\ldots,E(1)\}$
$\wedge$ the bits; $R = z'_0 \wedge \ldots \wedge z'_n$

$$ R =
\begin{cases}
E(1),  & \text{if equal} \\
E(0),  & \text{else}
\end{cases}$$
To reduce the depth of the $\wedge$, a binary tree is preferred.
Comparison
Calculate comparsion by $\operatorname{C}(X,Y) = \operatorname{MSB}(X-Y)$ and 2's complements. This will keep $1$ if $X \geq Y$ and $0$ if $ X < Y$
Sorting SWAP with FHE
The swap of two FHE variable can be performed by the following equation;
$$ \operatorname{SWAP}(X,Y) = X*\overline{\operatorname{C}(X,Y)}+ Y*\operatorname{C}(X,Y), X*\operatorname{C}(X,Y)+ Y*\overline{\operatorname{C}(X,Y)}$$
where the overbar represents the complement.
Note that; the server doesn't know the output and doesn't need to know the real plaintext of the Comparison to perform a swap. This $\operatorname{SWAP}$ routine is used in sorting implementations that require a swap function (usual in comparison-based sortings), according to the FHE encrypted comparison $C$ result, the values are either swapped or not swapped and the server still doesn't know.

Some implementations articles;

Depth Optimized Efficient Homomorphic Sorting
Homomorphic AES Evaluation Using NTRU
Bandwidth Efficient PIR from NTRU
Searching and Sorting of Fully Homomorphic Encrypted Data on Cloud