$h_3$ is at most as collision and 2nd-preimage resistant as $h_0$.

Proof:
Suppose we have a collision for $h_0$, that is, we know $x\neq y$ with $h_0(x)=h_0(y)=h$. Now observe that $h_3(x)=h_3(y)$ as follows: $$h_3(x)=h_1(h_0(x))\parallel h_2(h_0(x))=h_1(h)\parallel h_2(h)=h_1(h_0(y))\parallel h_2(h_0(y))=h_3(y)$$

Now that we have established that $h_3$ cannot be more secure than $h_0$, let's look at the "lower bound". Let $c_i$ be the boolean variable that indicates that a collision on hash function $h_i$ is known. Then the following holds:
$$c_3\rightarrow c_0\oplus(c_1\land c_2)$$
(with $\oplus$ denoting XOR)

That is, $h_3$ is at least as secure as $h_0$ or ($h_1$ and $h_2$). This assumes there are no subtle interactions between the hash functions which would facilitate a structure-lead collision search.

Suppose we have a collision on $h_3$, that is we know $x\neq y$ such that $h_3(x)=h_3(y)$. $h_3(x)=h_3(y)$ implies that $h_1(h_0(x))=h_1(h_0(y))$ and $h_2(h_0(x))=h_2(h_0(y))$ (by simple decomposition) and so we would have found a collision on $h_1$ with the values $h_0(x)$ and $h_0(y)$ and a collision on $h_2$ with the same values. This assumes that $h_0(x)\neq h_0(y)$ is allowed to be called a proper collision. If this is not the case we would have found a collision on $h_0$ instead. So we have $c_0\oplus (c_1\land c_2)$ being true, deduced from $c_3$ being true.

Actually the right-side of the found collision is worth "more" than a normal collision on a hash function. Because we have found a collision on both hash functions, which is equivalent to finding a collision on $h'(M)=h_1(M)\parallel h_2(M)$ which with the constraints given in the question has $n/2$ bit security.

So what does all of the above mean?

If you can break $h_0$ you can break $h_3$.
If you can break $h_3$ you can either break $h'$ or $h_0$.
If either $h_1$ or $h_2$ is a permutation, then breaking $h_3$ is exactly as hard as breaking $h_0$.
If you can break $h'$ you can trivially break $h_1$ and $h_2$.
Two "normal" collisions on $h_1,h_2$ are very likely not sufficient to break $h'$.
A collision on $h'$ very likely does not yield a collision on $h_3$ (because you would still need to find a pre-image with respect to $h_0$).
If $h_0,h_1,h_2$ lack structural weaknesses, $2^{n/2}$ operations are required to break $h_3$ (which is the expected value).

Reading hint for the uninitiated: "if you can break x then you can [logical formula involving breaks of $y_i$]" needs to be negated on both sides and then the sides need to be swapped for a security statement. That is "if [negated logical formula] is secure, so is x".


The authors state in 4.3 that the design of the cipher has the following clever feature:

  The dependencies between the LFSRs and the keystream vary greatly with the initial value of $R_4$ and since the variables of $R_4$ play no role in the value of the keystream, so it is not possible to find them.

So, later on they suggest the values of $R_4$ must be bruteforced, as a precomputation.

As for your question 2, you need to plug things in, as in the equations at the end of section  4.3.


Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?

One method of doing this would be to construct a Feistel network using the n-bit blockcipher as a round function. A drawback of this approach is that because you're using a blockcipher (a pseudo-random permutation) in place of a pseudo-random function, you are almost immediately limited to being secure to only $q \ll 2^{n/2}$ queries as a result of the Birthday Paradox. For $n = 64$, this could be quite problematic. (And I guess might be the type of scenario that led you to ask this question in the first place).

One way around this is to build a PRF $f_{K_1 K_2}(x) = E_{K_1}(x) \oplus E_{K_2}(x)$, where $E$ is your blockcipher. (See "The Sum of a PRPs is a secure PRF"). This is secure for $q \ll 2^{2n/3}$ queries. The result generalizes to $q \ll 2^{dn/(d+1)}$ when you XOR the outputs of $d$ independently keyed blockciphers. So you could use this for your round function. But since your round functions have to have different keys, you end up using a lot of key material, and there's a significant performance hit.

As an aside, there's a lot of literature on constructing $m$-bit "tweakable" blockciphers out of $n$-bit blockciphers for arbitrary $m > n$. This line of work is motivated mostly by full-disk encryption. See, for example, EME, HEH, HCTR. But almost all of these are again only secure up to $q \ll 2^{n/2}$ queries.


Is Blake2b vulnerable to length extension attacks?

All from the BLAKE2 paper BLAKE2: simpler, smaller, fast as MD5
First of all

BLAKE2b is optimized for 64-bit platforms — including NEON-enabled
ARMs — and produces digests of any size between 1 and 64 bytes.

and from the abstract of the article

BLAKE2 is often faster than MD5, yet provides security
similar to that of SHA-3: up to 256-bit collision resistance, immunity
to length extension, indifferentiability from a random oracle, etc

The reason for the resistance to length extension attack
The countermeasure comes from the compression function. The last parameter is set to false when the processed chunk is not the last one.
Compress(h, chunk, cBytesCompressed, false)

It is set to true when the last chunk is compressed.
Compress(h, chunk, cBytesCompressed, true)

So, if an attacker tries to extend a hash, during the recalculation the verifier will arrive in a different hash value then the attackers provided.


Deletion complexity in a RSA accumulator

Given the trapdoor, one would delete an element from RSA accumulator in constant time. In particular, produce an inverse to the element with extended Euclid algorithm and power-to accumulator to the inverse. The element in question would cancel-out from accumulator this way.


Currently, there is no formal proof of NTRU being based on a lattice problem, but you can find a description of NTRU in terms of lattices in Section 5.2 of [Ber09]. For lattice-based attacks for NTRU you can review [HPS98]. There is, however, a provably-secure variant of NTRU that is ultimately based on the hardness of the SVP problem [SS11].

References:

[Ber09] Post-quantum cryptography (2009). Springer Berlin Heidelberg.

[HPS98] Hoffstein, J., Pipher, J., & Silverman, J. H. (1998). NTRU: A ring-based public key cryptosystem. In Algorithmic number theory (pp. 267-288)

[SS11] Stehlé, D., & Steinfeld, R. (2011). Making NTRU as secure as worst-case problems over ideal lattices. In Advances in Cryptology–EUROCRYPT 2011 (pp. 27-47).


Use cases and implementations of RSA CRT

The following potential reasons occur to me why someone might not choose to use the CRT optimization:

The implementor worries about induced faults (but not quite enough to implement the obvious protection against it).  That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them.  That means that if the attacker can induce a miscomputation in one of the sides, we'll get the correct answer mod p (say), but not mod q.  This can leak the factorization of the modulus
The CRT optimization requires us to hold the prime factors; perhaps the implementer has restrictions on the amount of memory that can be used for a private key.  Note that it's possible to factor the modulus anyways if you have both the public and private keys, and so security isn't likely to be an issue here.
The implementer doesn't care about performance, and instead values simplicity
The implementer is clueless, and doesn't know about the CRT optimization


Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's only one answer.
321 + 607 = 928
But if you only know the output, how do you know what the two inputs are?
928 = 119 + 809
928 = 680 + 248
928 = 1 + 927
...

Now you might think that it doesn't matter - if the two inputs sum to the correct value, then they must be correct. But no.
What happens in a real hash function is that hundreds of one-way operations take place sequentially and the results from earlier operations are used in later operations. So when you try to reverse it (and guess the two inputs in a later stage), the only way to tell if the numbers you are guessing are correct is to work all the way back through the hash algorithm.
If you start guessing numbers (in the later stages) wrong, you'll end up with an inconsistency in the earlier stages (like 2 + 2 = 53). And you can't solve it by trial and error, because there are simply too many combinations to guess (more than atoms in the known universe, etc)
In summary, hashing algorithms are specifically designed to perform lots of one-way operations in order to end up with a result that cannot be calculated backwards.
Update
Since this question seems to have attracted some attention, I thought I'd list a few more of the features hashing algorithms
use and how they help to make it non-reversible. (As above, these are basic explanations and if you really want to understand, Wikipedia is your friend).

Bit dependency: A hash algorithm is designed to ensure that each bit of the output is dependent upon every bit in the input. This prevents anyone from splitting the algorithm up and trying to reverse calculate an input from each bit of the output hash separately.
In order to solve just one output bit, you have to know the entire input. In other words, when reversing a hash, it's all or nothing.

Avalanching: Related to bit dependency, a change in a single bit in the input (from 0 to 1 or vice-versa) is designed to
result in a huge change in the internal state of the algorithm and of the final hash value. Since the output changes so dramatically with each input bit change, this stops people from building up relationships between inputs and outputs (or parts thereof).

Non-linearity: Hashing algorithms always contain non-linear operations - this prevents people from using linear algebra techniques
to "solve" the input from a given output. Note the addition example I use above is a linear operation; building a hash algorithm using
just addition operators is a really bad idea! In reality, hashing algorithms use many combinations of linear and non-linear operations.

All of this adds up to a situation where the easiest way of finding a matching hash is just to guess a different input, hash it and see if it matches.
Lastly, if you really want to know how hard reversing a hash is, there's no better substitute than just trying it out for yourself.
All good hashing algorithms are openly published and you can find plenty of code samples. Take one and try to code a version that reverses each step; you'll quickly discover why it's so hard.


In the original Pinocchio [GGPR13], the authors didn't use R1CS at all.
As a ZKP friendly computational representation, R1CS was proposed later that year in [BCGTV13] Appendix E. The reduction from an arithmetic circuit to R1CS is quite straightforward, which I guess is the reason why there's no dedicated papers introducing such a computation model.
Soon after its introduction, the BCGTV13 authors started to implement the system into libsnarks, and people started to realise that R1CS is quite easy to be arithmetized. (normally a SNARK is based on Linear IOP or a polynomial IOP that operates on polynomials, thus the efficiency of the arithmetization of R1CS or other representation into polynomials is important).
Ben-Sasson et.al has a pretty good empirical reason on why R1CS became a popular choice in his 2018 Aurora paper (Page 4):

We choose R1CS because it strikes an attractive balance: it generalizes circuits by allowing “native” field arithmetic and having no fan-in/fan-out restrictions, but it is simple enough that one can design efficient argument systems for it. Moreover, R1CS has demonstrated strong empirical value: it underlies real-world systems [Zca] and there are compilers that reduce program executions to it (see [WB15] and references therein). This has led to efforts to standardize R1CS formats across academia and industry [Zks].


By parallelizable, what we mean is that the encryption/decryption process can be broken down into multiple tasks that can be run at the same time. For block cipher modes, this means that if we have multiple copies of the block cipher, we can use that to go faster.

For example, in CBC decryption mode, the decryption transform of several adjacent blocks is defined as:

$$P_i = C_{i-1} \oplus D_k( C_i )$$
$$P_{i+1} = C_{i} \oplus D_k( C_{i+1} )$$
$$P_{i+2} = C_{i+1} \oplus D_k( C_{i+2} )$$

($C_i$ is the $i$th ciphertext block, $P_i$ is the $i$th plaintext block, and $D_k$ is the block cipher run in decryption mode)

Now, we assume that we see the entire ciphertext, including $C_{i-1}$ through $C_{i+2}$ at the same time.  So, if we have three hardware implementations of $D_k$, then we can feed each one with $C_i, C_{i+1}, C_{i+2}$, have them perform the decryption, then do the xor's, and thus produce $P_i, P_{i+1}, P_{i+2}$ all at the same time.

So, by having three hardware implementations, we can decrypt three times as fast.

On the other hand, let us consider CBC mode encryption.  Here, the standard definition for this is:

$$C_i = E_k( C_{i-1} \oplus P_i )$$

$$C_{i+1} = E_k( C_i \oplus P_{i+1} )$$

$$C_{i+2} = E_k( C_{i+1} \oplus P_{i+2} )$$

Here, we run into a problem when we try to run it in parallel.  To generate $C_{i+1}$, we need to have the value $C_i$ before we can start encrypting.  Hence, to generate the next encrypted block, we have to compute the previous one first.  Hence, if we have three encryption engines, we can't take advantage of them; we end up only using one at a time.


Format Preserving Encryption for 32 or 64 bit plaintext values

I'm not aware of any implementations, but I'm also not aware of any patents on this algorithm.

Furthermore, that algorithm can quite directly be made tweakable,

as that paper describes on pages 10-13.


Fake non-membership proof in RSA accumulator

Yes. More generally, suppose you know the size of the group $\mathbb{G}$ you are working in (RSA, class group etc).
Let $A = g^n$ where $n$ is the product of the elements in the committed set. Assuming $n$ is co-prime to $|\mathbb{G}|$, you can compute integers $a_1$, $a_2$ such that $$a_1 x + a_2 n \equiv 1 \pmod{|\mathbb{G}|}\;\;,\;\; |a_2| < |x|.$$ Setting $w:= g^{a_1}$ yields $w^{x}A^{a_2} = g$ and hence, the pair $(w, a_2) \in \mathbb{G} \times \mathbb{Z}$ works as a fake non-membership proof.
This is a fake non-membership proof for a single element. But with a little more work, you can also create a fake constant-sized proof for an arbitrarily large subset as in the BBF19 paper (https://eprint.iacr.org/2018/1188). The PoKE protocol in the paper (which is necessary for non-membership proofs) depends on the strong-RSA and adaptive root assumptions, both of which assume the group order is unknown.


No, it's not.

Here, Bruce Schneier estimates the cost of finding a SHA-1 collision. He estimates that this would require approximately 274 CPU cycles and cost about \$700 thousand in 2015. Trying 296 AES keys would require approximately 2100 CPU cycles and cost about \$50 trillion.


Unforgeability proof of partially blind signature (schnorr signature based)

If the probability (over random choice of the random tape $\rho$ and the random oracle $\mathcal{H}$) of a particular trial being successful is at least $\mu'$, then the probability that $1/\mu'$ independent trials* are unsuccessful is at most $(1-\mu')^{1/\mu'}$ --- this expression converges to $1/e$. The claim follows.

*Here, independence refers to the choice of $\rho$ and $\mathcal{H}$.


How do signatures or MACs achieve authenticity, integrity or non-repudiation？

The 3 properties have commonly accepted meaning in Cryptography:

Authenticity: The message comes from the party associated with the verification key.
Integrity: The message had not been modified.
Non-repudiation: The signer cannot deny themselves signing the message.

We usually model the security against the weakest point of the signature/MAC - being forged; whereas other types of attacks such as key-recovery automatically implies the algorithm is insecure.

The unforgeability implies the other 3 (2 in case of MAC) properties, because the ability to forge a signature/MAC under a particular algorithm implies that

the message may come from someone capable of forging the signagure/MAC (authenticity),
capable of modifying a signed message (integrity), and
capable of signing messages against the wish of the holder of the private key (non-repudiation).


There is no known classical algorithm that can factor a 2048-bit modulus in feasible time.

Shor's algorithm could do it in feasible time but this algorithm needs to be run on a large-scale quantum computer and as of now there are too many obstacles to create a large-scale quantum computer.


Using SHA512 (or other hash) for message authentication

I need to encrypt and authenticate a stream of data so that it is resilient against unexpected power loss, so I cannot write authentication data at the end of the stream.

This is a fairly confusing question you're asking, and I needed to read the whole thing over and over to come to a point where I felt I understood it.  What you want is to authenticate the data you're sending incrementally so that the recipient can establish the authenticity of chunks or prefixes without having to wait for the end of the whole stream.

The solution to this is to move the authenticated encryption inside the protocol that you're using to send data over the stream.  Instead of globally encrypting and authenticating a stream of plaintexts, you probably should send a stream of individually encrypted and authenticated ciphertexts.  AES-GCM will work fine for that—don't play around with homebrew ideas like what you're proposing.  You do have to be very careful about IV reuse.  (And about writing your own cryptography—are you sure you want to do this?)

One nuance here is whether you're trying to authenticate individual messages or stream prefixes.  This is related to the question of what should the recipient do if one message in the stream is adulterated:

Skip it and carry on processing the subsequent ones;
Abort the whole thing and don't process any more messages.

What's the correct thing to do depends on the application.  I'd put a bit of thought into that question.  But for case #2, there are tricks that can be done to cause the authenticity of later messages to depend on that of earlier ones.

  I am currently using AES-GCM, just for encryption, as my understanding is that the authentication tag for GCM must be written at the end of the stream.

There is no logical requirement to write the authentication tag at the end of the stream. It's just a very convenient way of doing it, since:

It allows you to write the ciphertext into the stream incrementally as you compute it;
You can't emit the tag until you've encrypted the whole message anyway.

If you buffer the whole ciphertext and tag into memory before writing them to the stream you could write them in the opposite order if you so preferred.  I figure some specific AES-GCM implementations may be hardcoded to write the tag at the end, though.

  My understanding is that truncating the SHA512 sum to save space is okay.

If you're truncating to 256 bits, there's a newer SHA-2 variant called SHA-512/256 which already does that.  But the larger issue is that SHA-2 is not a message authentication code, so it's not a substitute for GCM's authentication.


Is it safer to use timestamp in REST authentication?

Might need some clarification, but it sounds like you are wondering how to 'salt' the hash. First if you intend to concatenate the secret key with anything else, the standard way to handle this is a HMAC. A common way to handle this is PBKDF2:

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

Basically this does a secure combination of secret codes and the timestamp/salt. While the user can supply the timestamp, the probability that they could guess a timestamp that gives the same hash is very unlikely.

So PBKDF2 with a timestamp salt may be what you're looking for. Good Luck!


A sufficient (but not quite necessary*) condition for a cryptosystem to provide perfect secrecy is that:

every key is equally likely (and independent of the message), and
for every message $m$ and every ciphertext $c$, there exists a unique key $k$ such that $k$ encrypts $m$ to $c$.

The relationship between $m$, $c$ and $k$ does not necessarily need to be a linear one; it is sufficient that it be one-to-one, so that we can always find a unique matching key $k$, given $c$ and $m$.

In particular, let $M$, $C$ and $K$ be random variables denoting the unknown message, ciphertext and key respectively, and let $\Pr[M = m]$ and $\Pr[M = m \mid C = c]$ respectively denote the attacker's subjective probabilities of $m$ being the correct message before and after observing the ciphertext $c$.  Then, by Bayes' law, $$\Pr[M = m \mid C = c] = \frac{\Pr[C = c \mid M = m]}{\Pr[C = c]}\, \Pr[M = m],$$ where $\Pr[C = c \mid M = m]$ is the probability of the message $m$ yielding the ciphertext $c$, and $$\Pr[C = c] = \sum_{m'} \Pr[C = c \mid M = m'] \Pr[M = m']$$ is the marginal probability of any message yielding the ciphertext $c$.

Now, by the assumptions that:

the key $k$ is uniquely determined by $m$ and $c$,
the key $k$ is independent of the message $m$, and
each key is equally likely to be chosen by the encryptor,

we have $\Pr[C = c \mid M = m] = \Pr[K = k(m,c) \mid M = m] = \Pr[K = k(m,c)] = \frac1n,$ where $n$ is the total number of possible keys — a constant independent of $m$.  Since the marginal probability $\Pr[C = c]$ is also clearly independent of $m$ (and, in fact, also equal to $\frac1n$), we find that $\Pr[M = m \mid C = c] = \Pr[M = m]$.

Thus, observing the ciphertext $c$ will not change the attacker's belief in the likelihood of a given message $m$, which is the definition of perfect secrecy.

*) Strictly speaking, the key $k$ need not actually be unique; all that's needed is that, for each $(m, c)$ pair, the number of distinct keys that encrypt $m$ to $c$ is the same.  We could also relax, or even completely eliminate, the requirement that all keys are equally likely, but then we'd have to rephrase the remaining criteria in terms of the probabilities of the sets of keys encrypting $m$ to $c$, rather than just their number, being equal.


Public Randomness-Based Random Number Generator using Mobile Phone?

Be careful about the phrase “True Random Number Generator”. There's a bit of hype in that phrase. You do not need to use a TRNG directly to do things like generate cryptographic keys — in fact, you should not, because all TRNG have biases, because even if the underlying physical process has a truly uniform probability distribution, it's impossible to build a perfect measurement apparatus. A good random number generator for cryptography is always hybrid: a cryptographically secure pseudo-random number generator ((CS)PRNG, also called a deterministic random bit generator ((CS)DRBG)), which is seeded by one or more entropy sources. A physical device whose purpose is to serve as an entropy source is sometimes called a “TRNG”, but a less misleading name is HRNG (hardware random number generator).

An entropy source needs to have two properties:

It needs to be unpredictable. It needs to depend on a physical process whose outcome cannot be predicted in advance. This is typically a either a chaotic physical process or a process with physically theorized unpredictability such as radioactive decay.
It needs to remain unpredictable even after the fact, i.e. its output needs to remain secret. An entropy source is no good if it's public. If your adversary can construct the same system state as you because they can read the same entropy sources, then they can generate the same keys that you're generating.

Obtaining entropy from outside is dodgy because it violates the second property. You have no way to know that the data you're collecting from smartphones is actually coming from a HRNG, and even if it is, you have no way to know that it's only sent to you and not leaked to anyone else.

Fortunately, if you do things right, then when you mix entropy sources, a bad source (not sufficiently random or not sufficiently secret) doesn't hurt: it'll contribute 0 to the total entropy of your system, but it won't nullify other, good entropy sources. So assuming that your server-side code is perfect and that at least one of your entropy sources is good, then the result is ok. The flaw in this argument is that code is never perfect.

All modern server hardware has a built-in HRNG. (If you don't trust it, you have no reason to trust the rest of the processor. So “I fear a backdoor in the processor's RNG” is not a valid argument.) Collecting additional entropy from outside has no benefit. It's a lot of infrastructure, meaning a lot of failure points and a large attack surface, for no benefit.

Gathering entropy in a distributed way like this does have a benefit for a very specific application: when you want to generate a public value which should be demonstrably random. In that case, allowing everyone to contribute their entropy, and using a public, deterministic way to combine all the submissions, does result in a demonstrably random value.


If you look at the algorithm description, you see that, at a high-level, the encryption algorithm looks like this:

            addRoundKey(0);
            for (int i = 1; i < rounds; i ++) {
                    subBytes();
                    shiftRows();
                    mixColumns();
                    addRoundKey(i);
            }
            subBytes();
            shiftRows();
            addRoundKey(rounds);

The decryption algorithm will then look like this:

            addRoundKey(rounds);
            for (i = 1; i < rounds; i ++) {
                    invShiftRows();
                    invSubBytes();
                    addRoundKey(rounds - i);
                    invMixColumns();
            }
            invShiftRows();
            invSubBytes();
            addRoundKey(0);

Now, if you view the 16-byte state as a vector in space (Z2)128, then the ShiftRows() and MixColumns() transforms are linear, and so is the addition of a round key (addRoundKey() -- really, a bitwise XOR). Moreover, the ShiftRows() is byte-oriented, therefore it can commute with SubBytes() (since SubBytes() works on each state byte independently). Therefore, it is customary for AES implementations to combine SubBytes(), ShiftRows() and MixColumns() into a single step with 8->32 lookup tables (you need four of them, for a total of 4 kB of tables). This optimization is what the Wikipedia page alludes to.

If you try to do that with decryption, in the loop above, you will see that the addRoundKey() step happens between invSubBytes() and invMixColumns(), which is inconvenient. The solution is to move the addRoundKey() one step down, but then the round key must be modified to account for the move (in simple words, if you add the round key after the invMixColumns(), then you must add a round key that has been already "invMixColumnsed"; it works because of linearity).

In that case, decryption becomes:

            addRoundKey(rounds);
            for (i = 1; i < rounds; i ++) {
                    invShiftRows();
                    invSubBytes();
                    invMixColumns();
                    addRoundKeyAlreadyInvMixed(rounds - i);
            }
            invShiftRows();
            invSubBytes();
            addRoundKey(0);

With that new algorithm layout, the invShiftRows(), invSubBytes() and invMixColumns() steps are again together, and can be optimized into a single set of lookup tables. However, this requires the "inner" subkeys (all but the first and last one) to be preprocessed with invMixColumns() so that the computations still work.

I believe this is what you observe in the implementation you are inspecting.


What does the encrypt function from Stanford JS Crypto Library do?

The SJCL demo page suggests that what it's doing is symmetric-key authenticated encryption using either the CCM or the OCB2 mode.  The cipher used appears to be AES, not that that matters much.  (Any other secure block cipher with similar block and key sizes would work just as well.)

Actually peeking into the code reveals that there's more to it than that.  For example, for the encryption key, it can apparently accept either a password string (which will be hashed using PBKDF2 to derive the actual key), an ECC ElGamal public key (used to generate and encapsulate a random symmetric encryption key) or, presumably, a raw AES key in the library's internal format.

In any case, besides the demo, the sparse auto-generated documentation, and the code itself, I have not been able to find any proper documentation or specification for this library.  While at a glance the design of the library seems sound enough, and while the author list includes Dan Boneh, who certainly seems a reputable and competent enough cryptographer, I still would not recommend using this library given its lack of documentation.

Simply put, even if the library itself worked perfectly and did exactly what it was supposed to, without proper documentation you simply have no way to tell (short of reviewing the whole source code yourself) whether you're using it correctly and securely or not.  Given that most crypto failures in practice arise from putting the right parts together in the wrong way, that's a glaring flaw in my book.


Proving knowledge of a value and computation that uses it

This looks like your typical Schnorr identification protocol. Here $r$ is some secret value, which we could think of as having two public keys $r\cdot P$ and $r\cdot Q$. You'll probably want to assume that the DLPs wrt base $P$ and $Q$ are hard as well, as otherwise Alice could possible solve one of these two for $r$. Let's just assume the group has prime order $n$.

Now we could proceeds as follows (similar to the questions the @SEJPM referred to):

Bob chooses random $s\in \mathbb{Z}/n\mathbb{Z}$.
Bob sends $(s\cdot P, s\cdot Q)$ to Alice.
Alice chooses random $c\in \mathbb{Z}/n\mathbb{Z}$.
Bob computes $t = (s + cr)\bmod{n}$.
Bob sends $t$ to Alice.
Alice checks that $tP = (s\cdot P) + c(r\cdot P)$ and $tQ = (s\cdot Q) + c(r\cdot Q)$.

If the checks of Alice pass, she will believe that Bob knows the DLP of $r\cdot P$ and $r\cdot Q$. I haven't done a too thorough checking, but the properties of a sigma protocol seem to hold.

Moreover the secrets must both be equal to $(t-s)c^{-1}\bmod{n}$, so they are the same.


Is python a secure programming language for cryptography?

Python is a scripting language, so if you've got the program, you usually also have the source code. So you don't even have to reverse-engineer. That doesn't matter much for two reasons:

other languages are pretty easy to reverse engineer (or they are complex for both the programmer and the attacker);
the algorithm does not have to be kept safe anyway, due to Kerckhoffs' principle

Now the above does not directly make Python suitable for cryptography. One of the main things about cryptography is security. Without a secure programming environment, you can have any strength of cryptography, and still not have a secure system.

Languages have many constructs that make them more or less suitable for security and cryptography, so I show a few and indicate how Python fares:

type system: it has a dynamic type system with strong typing - with regards to security this is not as good as a static type system but it is better than weak typing;
character encoding: not good, python may confuse bytes and characters if specialized classes are not used;
operations on bytes, 16 bit words, 32 bit words and 64 bit words: not good, python simply regards everything as an unbounded number;
operations on large integers: good; modular exponentiation can be done directly on numbers using pow();
destruction of keys & state: this is a problem for any language that doesn't directly manage it's memory; Python is not likely to fair better than the rest, it may be hard to prove that keys can be safely destroyed while the program is running.

Finally, in general people like their systems to be fast. Unfortunately, scripting languages are often not fast with regards to binary operations required for symmetric cryptography (SHA-256, AES). Interpreted languages such as Java are already much faster, but languages such as C and assembly are faster than that (when used correctly).

More important for regular use of cryptography is the maturity of cryptographic support provided in libraries. Python has a relatively well kept crypto libraries called PyCrypto, PyOpenSSL available; those libraries however are mainly implemented mainly in C. These and other libraries are discussed here. One advantage of PyOpenSSL is that it should be possible to securely store and use keys from a hardware module (for instance a smart card or HSM).

Note that side channels may apply when using Python for direct implementation of cryptographic primitives. I'd say that Python is especially OK for fast prototyping of cryptographic primitives rather than library creation.

All in all, I would summarize that Python is OK-ish, but not great for cryptography if such a generalist statement can be made at all.


Indeed the text quoted is wrong; at the very least, by using incorrect vocabulary. That should be: if you sign a message with your private key, the paired public key can be used to verify the signed message's integrity and origin.
What small amount of truth there is in the original statement boils down to: in some asymmetric cryptosystems, including RSA¹ (but not including ECDSA used in bitcoin and many other protocols), the sign operation includes a step similar to a step used in encryption, except with the private key instead of the public key; and that's undone in the verify operation, which includes a step similar to a step used in decryption, except with the public key instead of the private key.

¹ And then not the variant of RSA most used in practice for performance reasons, which uses the Chinese Remainder Theorem in private-key operations. That has no equivalent for public-key operations, and uses the private key in a form that makes it not interchangeable with the public key. That makes the twist in the text quoted unworkable.


RSA Accumulators with auxiliary information or known trapdoor information

For the inclusion proof you might need the trapdoor or the accumulated set. The exclusion proof can be generated without knowing the trapdoor. See this related question and answer.

How can one generate inclusion proofs if knew the trapdoor, i.e. the factorization of $N=p\cdot q$?

Let's $A$ denote the accumulator's value, $x$ be an item to-be-accumulated and $N$ the modulus whose factorization is known.

Generating a valid membership proof for an item $x$ essentially means taking $x$-th root of $A$ $\mod N$. Since you know the factors of $N$ you can just compute $x$-th root $\mod p$ and then $\mod q$ and afterwards compute the $x$-th root $\mod N$ by applying the Chinese-remainder theorem for moduli $p,q$.

Note, that computing efficiently arbitrary roots mod a prime is simple. See, for instance, here.


Is it reasonable to consider that an encryption scheme must be invertible?

Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?

Yes, strictly speaking: Encryption is the process of turning a plaintext message into a ciphertext (encryption) which then can later be turned back into the original plaintext (decryption).

If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?

Gary Kessler has published An Overview of Cryptography.
In chapter 3 "Types of cryptographic algorithms" you can see that there is a distinction drawn between encryption and hash functions.

If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?

Encryption, decryption and cryptographic hashes all belong together in the realm of cryptography but they can definitely not be used interchangable (see this earlier answer from a different question). Some differences include:
Reversability
Encryption schemes can usually be transformed back into their original form, i.e. a once encrypted plaintext message can usually be decrypted back into the original plaintext. Hashes, on the otherhand, are created in a manner that the input undergoes a loss of information, ultimately making it irreversible.
You can always create a hash from a given input but it's not possible to be sure what the original message once was if you're only given the hash (see pigeonhole principle).
Keys
Encryption schemes always use keys. Hashes do not require keys.
Length
A long plaintext message results in a long encrypted ciphertext & a short plaintext message results in a short encrypted ciphertext.
Hashes will always have a predefined length, no matter the input.


What does a "cycle" mean in cryptography benchmarks?

"Cycles" are CPU instruction cycles. Cycles per byte roughly measures how many instructions, in a given instruction set, are needed to produce each byte of output. They're a reasonably-good relative measure of the performance of different algorithms.

Generally, when you measure an algorithm's cycles per byte, you use carefully controlled conditions. You ensure the system isn't doing anything else, you ensure the code cache is populated, you try to avoid measuring memory speed, and so on.

Some ciphers are dependent on their data. To help control for this, you try to use a large data set and average it out.

You can't measure asymmetric ciphers this way, because they don't operate on bulk data. For them, it makes more sense to talk about cycles per operation, operations per second, or the like.

I noticed on that data set, they have a lower cycles per byte for SHA256 than SHA512. If they had used their CPU's 64-bit instruction set, the results would have been the other way around. So the results are heavily dependent on how the code is compiled (instruction set, optimizations, and so on).


Which are the current solutions to the illegal values in the homomorphic secret sharing?

This is a "known vulnerability" of Shamir's secret scheme. While it is known to be information-theoretically secure, here security means privacy.
Shamir's scheme has no authenticity properties --- a single party can change the output by modifying a single share.
There have been recent suggestions to augment the notion of "secret sharing" to impart it with a notion of authenticity as well. This can be viewed similarly to how the primitive of "Encryption" (which only gives privacy) was augmented to "Authenticated Encryption" (which gives both privacy and authenticity).
I've seen this proposed in the RealWorldCrypto 2020 talk Adept Secret Sharing, presented by Phil Rogaway (Mihir Bellare and Wei Dai are listed as co-authors/co-contributors though). It seems that there hasn't been a paper/slides made public as a result of the talk though.
The talk itself is available here.
I don't remember the entirety of the talk, but the conclusion was something along the lines of a generic transformation to get private + authentic secret sharing, but the privacy becomes computational (rather than information theoretic).
This likely does not work for your purposes though --- such a scheme is likely no longer homomorphic (I cannot remember details from the talk currently though). So what do people do in practice? I believe some combination of "standard" Shamir's secret sharing, and a non-interactive zero knowledge (NIZK) proof that $a_0\in (a,b)$.
This is called a "Range proof" (see for example this).


using hash function of (key||plaintext) instead of random value for IV

No, it's not semantically secure.

Proof: select two plaintexts with identical initial 128 bits; and present them to the Oracle to be encrypted.  The resulting ciphertexts will also have identical initial 128 bits, hence the encryptor can be distinguished from something that generates random outputs.


How does PKCS 1.5 solve the insecureness of Textbook RSA?

PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into
$\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$, where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near-uniformly-random non-zero bytes. Then (with big-endian conversion between bytestring and  integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

While plaintext $M$ might still be easily guessable, verifying such guess becomes much harder. A brute-force method becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That strategy requires $255^{k-\mathrm{mLen}-3}/2$ try on average (for each possible $M$). That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem; but we have no formal proof that it does.

Thanks to $\mathtt{0x02}$ at the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues :

any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. Even for $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, such as $e=3$. That's because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$ and allowing recovery of $\mathrm{mLen}$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of one message, or computing one signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.


Proof of probability of weak keys in block cipher

However the author doesn't give a proof to this theorem, I want to know if it's possible to prove it and how can I prove it?

The author likely doesn't bother with the proof because it is so straight-forward; we also need to note that the figure $2^{k-tn}$ is not exact, but merely an approximation (albeit a very close one for realistic key and block sizes); once we skip the approximation, the proof becomes slightly less trivial.

First, the assumption we make: that the cipher acts like an ideal cipher, in particular, if we give an incorrect key to the cipher, that it generates random ciphertext blocks (and ones that are independent of the ones generated with the correct key).

Then, if we consider giving the known $t$ plaintexts to the cipher with an incorrect key, it will generate $t$ random ciphertexts, each of which is $n$ bits.  Given that these are random, the probability that all $n$ of them are precisely the same bits as the expected ciphertext bits is $2^{-nt}$ (as there are a total of $nt$ bits, all of which need to be precisely the correct value.

Now, this isn't quite accurate.  The block cipher, even given an incorrect key, is still a permutation, and assuming that all the plaintext blocks are distinct, all the generated ciphertext blocks will be distinct.  This means that, if $t>1$, that certain outputs (such as the all-0 output) will be impossible (because the cipher will never encrypt two different plaintexts into the same all-0 ciphertext block); the precise probability for an incorrect key is $(2^n-t)! / 2^n! = \frac{1}{2^n \cdot (2^n-1) \cdot (2^n-2) \cdot … \cdot (2^n-t+1)}$.  If $2^{n/2} \ggg t$, that is, we're considerably under the "birthday bound", this is quite close to $2^{-nt}$

Now, this is the expected value for one incorrect key, and the total expected value is the sum of the expected values for all the various disjoint possibilities.  There are a total of $2^k$ incorrect keys, and so the total expected value is $2^k \cdot 2^{-nt} = 2^{k - nt}$

Now, this also isn't quite accurate, there are $2^k-1$ incorrect keys (as we assumed that there was a correct key); obviously, for the key sizes we use, $2^k$ is quite a good approximation; we've also seen that $(2^k-1)(2^n-t)! / 2^n!$ is the precise (if generally less useful) expectation.


There are many ways of doing this. A very nice read (but with informal presentation) is this paper by Fagin, Naor and Winkler on Comparing Information without Leaking It. A very fast protocol exists which requires a single oblivious transfer for every bit. Let $n$ be a security parameter; say $n=128$, and let $\ell$ be the bit-length of the inputs.

For $i=1,\ldots,\ell$, Party 1 chooses a pair of random values of length $n$, denoted $x_i^0,x_i^1$.
For $i=1,\ldots,\ell$, the parties run an oblivious transfer where Party 1 inputs $x_i^0,x_i^1$ and party 2 inputs $b_i$ (the $i$th bit of its input)
Party 1 sends Party 2 the value $A=\sum_{i=1}^\ell x_i^{a_i}$ (where $a_i$ is the $i$th bit of its input)
Party 2 outputs 1 if and only if the sum of the values it received equals $A$.

The nice think about this protocol is that it is secure even for malicious adversaries if an oblivious transfer protocols that is secure for malicious adversaries is used.

Note that if party 1 also needs to get output then more needs to be done.


Encrypting a broadcast message decryptable by a subset of receivers

Perhaps Attribute-based Encryption is what you are looking for.
From the two schemes (KP-ABE, CP-ABE), CP-ABE can solve your problem. You can set the attributes of each identity according to their domain set and encrypt the file with policy using OR. The example you have given, Msg(D1,D3) can use (D1 OR D3) as a policy to encrypt.
For more detailed information on the mathematics behind the scheme, you can read this paper. Also, there is an opensource implementation available too Zeutro's OpenABE if you are interested.


Quadratic residue problem on composite integers

The computation of square roots modulo a composite $N$ is hard, because a method for computing square roots can be turned into a factoring method in the following way:

Choose an element $a$ modulo $N$ uniformely at random and compute $A=a^2 \pmod{N}$
Apply the square root computation technique on $A$, get result $a'$
If $a'=\pm a$ retry, else $gcd(a-a',N)$ is a non-trivial factor of $N$

An important argument here is that the square root computation cannot systematically return $a$ because it has no way to know which of the possible square roots of $A$ you started from (they are all equiprobable since you choose $a$ uniformly and kept it secret).

If you are asking about deciding whether an element is a square modulo $N$, the situation is a bit different. First, an element $a$ is not a square modulo $N$ if its Jacobi symbol of $a$ and $N$ is not $1$. But if the Jacobi symbol is $1$, the problem of deciding whether a number is a square is believed to be hard. However, for the decision problem contrary to the computational version, I am not aware of reduction to factoring.


hash functions preimage and second collision resistance

No, the implication is wrong.
Pre-image resistance means that it is not possible to calculate a pre-image from the image alone.
But this does not exclude the existence of an algorithm, which calculates a second pre-image, given the image and the first pre-image.


Key derivation function in theory & practice

Do NOT generate your own key derivation function.  Use one of the known and trusted ones... industry standard ones, such as PBKDF2 https://en.wikipedia.org/wiki/PBKDF2

Use your starting (pseudo-random) value, and plug it into PBKDF2 for different numbers of iterations for each desired output (new seed) that you need.


Difference between server salt and client salt?

Disclaimer: The following is tentative. Before the question I did not knew about client salt.
The client salt is combined on the client side with the password. When that's used, the client no longer sends the password, but a password-equivalent obtained by hashing. Client salt is often deterministic and near-public, e.g. < DNS of the realm, converted to uppercase> | <user name> (other reference). The  client salt's role is that compromise of what the client stores or sends, or what the server receives, does not leak the password (other than by exhaustive search requiring a new effort for each user).
The server salt is combined on the server side with the password (or the password-equivalent resulting from a password hash with the client salt on the client side, as above). A common practice is that server salt is random, and secret in whole of part (in which case that's pepper). The server salt's role is that compromise of what the server stores does not leak the password (or other information allowing login such as the above password-equivalent) other than by exhaustive search requiring a new effort for each user and server. Using pepper splits the information necessary to carry this attack in two: the hashed passwords+salts (typically in a database), and the pepper (typically in a config file or source fragment).


Is there any research on the problem of making a number more memorable to humans?

I look forward to seeing more research on ways of representing cryptographically significant numbers in ways that are easier for humans to memorize or use in other ways.

memorizing and typing

There are several ways to bidirectionally convert a series of completely random bits into a series of English words and back again.
(That series of English words is easier for a touch-typist to type in, easier for a human to memorize, easier for a human to visually compare two sequences, etc. than the same bits in the form of hex digits).

The most popular wordlists seem to be:

the Diceware wordlist of 7,776 unique words: any 64 bit number can be encoded into five words and back again.
The S/KEY one-time password system uses 2048 unique words: any 64 bit number can be encoded into 6 words and back again.
The mnemonicode system uses a dictionary of 1633 unique words: any 64 bit number can be encoded into 7 words and back again.
The PGP word list of 512 unique words: any 64 bit number can be encoded into 8 words and back again. (This system has an extra feature, not found in the other systems, that allows a repeated word to be immediately detected and the duplicated word dropped without error).

I find all of these systems much easier to use than raw hex digits.
And by definition (because they are all various ways of encoding a completely random 64 bit number) they are all just as secure as 64 bits represented as raw hex digits or as a series of ASCII characters that includes lowercase, digits, punctuation, etc.

The size of the dictionary is a tradeoff:
small dictionaries let you use common words that are much easier to remember how to spell, but force you to use more words to store a 64 bit number.
Larger dictionaries force you to use uncommon words that may be difficult to spell or to distinguish from each other, but allow you to use fewer words to store that same number.

Alas, all the research I've seen in designing such wordlists involves making the words as distinguishable as possible from each other when one human reads the series of words to another over a noisy audio link.

comparing

The "visual host key" is intended to make it easy for humans to compare two SSH fingerprints. (See
"ASCII Art Fingerprints"; also
"Easy to remember fingerprints for data?"  )
Compared to hex digits or English words, this "visual host key" seems to be easier for humans to visually compare two fingerprints.
Alas, compared to a series of English words, it seems to be more difficult for a human to memorize and type back in a key in this form.


Pairings, or bilinear maps, have indeed found a great deal of applications in crypto; hence, researchers have soon pointed out that further "degrees" of linearity (trilinear maps, etc.) would provide even more powerful applications.

Nowadays, multilinear maps are one of the most powerful cryptographic primitives. They are at the heart of indistinguishability obfuscation, witness encryption, multiparty key exchanges, among many other applications. As one can expect, building such a powerful primitive is not an easy task. The story of multilinear maps, which schemes have been created, which have been broken, etc., would be really long to tell (although I could try to look for some survey if you're interested). To make it short:

-The last thing you've described, $e: \mathbb{G}_0 \times \mathbb{G}_0 \mapsto \mathbb{G}_0$, is referred to as an ideal multilinear map. I know of a single paper which proposed such a scheme, and it was broken within a few months.

-There are currently two major constructions (and many variants of each of them) of graded encoding schemes, which are close variants of multilinear maps and are associated to some degree, which corresponds to its degree of linearity. The first scheme is usually called the GGH scheme and is based on ideal lattices; the second one relies on the hardness of factorization and is usually called the CLT scheme.

-The expected security of a graded encoding scheme is defined through a set of assumptions on the scheme which are conjectured to be intractables. The assumptions might require some particular components to be made available (one important case for multilinear maps is whether it provides encodings of the zero value). Different applications require different assumptions, so there's really a patchwork of schemes whose security is related to some assumption on some multilinear map. Essentially, most assumptions have been broken. Multilinear maps have suffered from a collection of very powerful attacks, denoted zeroizing attacks (a recent result seems to indicate that a new, an even more effective way of attacking multilinear maps has been discovered; it was introduced under the name of annihilation attacks). Zeroizing attacks have broken most assumptions on major candidate constructions, and I don't think many cryptographers would confidently advocate the use of these constructions as a safe choice.

However, it should be mentioned that this is not a full break. In particular, these attacks do not rule out several constructions of indistinguishability obfuscation from multilinear maps, which is one of the most important applications.

This was regarding security. Regarding efficiency, things are not better: even if they were really secure, current candidates are very slow. For multilinear maps of small degree (say, less than 10), an optimized implementation in a very simple setting might allow you to execute a protocol using them in a few minuts, but when parameters grow, the running time will soon make this solution entirely impractical. Indeed, building multilinear maps (or graded encoding schemes) with a better-understood security, and a better efficiency, is one of the major goals in theoretical cryptography.


When is an RNG a CSPRNG, a CSRNG, or a TRNG?

There seems to be a lot of confusing terminology here. Let me define everything to the best of my knowledge.

RNG: Some mechanism that produces random numbers.
CSRNG: An RNG that is safe for cryptographic use.
PRNG: An RNG that is a deterministic algorithm based off of a seed.
TRNG: An RNG that is based off of some unpredictable physical process.
CSPRNG: A PRNG that is safe for cryptographic use. (Assuming the seed is picked correctly)

I've never heard the term CSTRNG, but I could imagine it meaning a TRNG which is cryptographically secure. In general conversation, this is redundant because TRNGs are assumed to be cryptographically secure regardless. Even though it is not explicitly defined that way.

  Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?

Depends how the noise source is used. If the source is used as a seed for a PRNG, then it is in fact pseudo, since most of the randomness is "made up" by the algorithm.

If every bit of output is influenced by a different bit of input, then it can be considered a TRNG.

  If, where do we draw the line between a CSPRNG and a CSRNG?

From my understanding, a CSPRNG is a subset of CSRNG.

CSRNG means Cryptographically Secure Random Number Generator. It may be pseudorandom, it may not. The only requirement is that it is safe for cryptographic use.

CSPRNG means Cryptographically Secure Pseudo Random Number Generator. This has the same requirements of a CSRNG (hence it being a subset), with the additional requirement that it be some sort of deterministic algorithm that accepts a seed.

  And where do we place a TRNG in this picture?

The best description I've ever heard of a TRNG is an RNG based off of physical noise that has a mathematical basis for how every bit is based off of a different part of said physical noise. (Paraphrasing)

  Or is a CSRNG always a TRNG and vice versa

I could trivially make a TRNG by recording my voice and using the bytes from the recording as randomness without any processing. That isn't cryptographically secure, making it a TRNG but not a CSRNG. This isn't common because a TRNG that isn't good for cryptography is a waste of money for the most part.

However, there are CSRNGs that are TRNGs (See: random.org).

They are separate categories with separate requirements. They do overlap, but they do not depend on each other.

  making every other RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

A PRNG with a seed derived from a TRNG is still a PRNG. This is actually how a lot of random entropy is generated quickly. It isn't efficient to generate megabytes of entropy using physical sources. (Have you ever tried generating a public/private key pair using /dev/random? It's harsh) It's usually done by using physical sources to seed a CSPRNG, which does the heavy lifting.

Also, there are a lot of RNGs that are not CSPRNGs. Xorshift, LFSR, ARC4Random (when it was based off of RC4), and Mersenne Twister to name a few. These algorithms have biases or other problems that render them bad for cryptograpic use. However, they still output numbers that seem random to the naked eye.


Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the password. If the password is constrained to characters in [20h..7Fh], that will further remove $49/50$ of the candidates.

Many CRCs found in practice (including 32-bit CRC CCITT) are not "XOR-preserving" in the sense $CRC(x \oplus y) = CRC(x) \oplus CRC(y)$.
However it allways holds that $CRC(x \oplus y \oplus z) = CRC(x) \oplus CRC(y) \oplus CRC(z)$ for any $x$, $y$, $z$ of identical length (including with $z$ all-zero); that (and a little linear algebra) is enough to organize the computation. At the end of the day, with $n=32$, one can compute the last 4 bytes by XOR-ing the values found in precomputed tables (one table for each preceding byte, with each table $256·32$ bits).


Given that the bottleneck on the embedded device is local non-interactive public-key signature verification, the best industry standard for that is RSA (with a standard signature padding, such as PKCS#1 RSASSA-PSS, PKCS#1 RSASSA-PKCS1-v1_5), which is usually significantly faster than ECDSA for signature verification including for the common $e=65537$; and for good implementations always faster when using $e=3$, which allows a speedup by a factor of about $8$. Rabin signature verification is nearly twice faster than RSA with $e=3$, and is also standard if not common, e.g. was in ANSI X9.31:1988 and is in ISO/IEC 9796-2:2010.

Note: the absolutely fastest seems to be Daniel J. Bernstein's A secure public-key signature system with extremely fast verification (2000); this is essentially Rabin with an expanded signature allowing extremely fast verification, using an idea he first outlined there.

Both RSA and Rabin are based on modular arithmetic modulo $N$ of secret factorization. The time for signature verification is dominated by $17$ (RSA, $e=65537$), $2$ (RSA, $e=3$), or just $1$ (Rabin, $e=2$) multiplication(s) modulo $N$, where $N$ has $n$ bits. $n=2048$ is acceptably secure till 2030 according to NIST and French ANSSI.

When appropriately implemented using standard (quadratic) algorithms working on $w$-bit words, the computation time for one multiplication modulo $N$ is dominated by $\approx(n/w)^2$ executions of an elementary operation consisting of

two multiplications of two $w$-bit word giving a $2w$-bit result
addition with carry of the corresponding two results into temporary values
three reads of a $w$-bit word
one write of a $w$-bit word
on register-starved CPUs only, some read-writes for temporaries

Notoriously, careful optimization of the core loop is essential (assembly language shines!); and using the wrong algorithm will impact speed (in particular: separating modular multiplication from modular reduction increases the memory accesses; Montgomery arithmetic at best does not help).

Actual execution time can be in seconds on a mere 8-bit CPU (for 2048-bit RSA, $e=3$, an implementation I wrote verifies a signature in $1.25$s on a 8051 core with 5M cycle/s and 4-cycle multiplication of bytes giving 16-bit result, and no hardware 16-bit addition).

Execution time decreases about quadratically with the word size, allowing time in milliseconds for a modern 32-bit CPU (the question does not specify which core is used; ARM CPUs tend to be good at this, especially those with UMLAL and UMAAL).

Per eBACS benchmarks, on an ARM Cortex-A8, RSA-2048 ($e=3$) is timed at a median of 555418 cycles (28ms scaled to 20MHz), versus 2594303 cycles for one of the fastest elliptic-curve signature system, ed25519.


Why is an IV used in Merkle–Damgård transform?

In most Merkle–Damgård hash functions, it uses a block cipher in the compression function, with the inputs being the padded message blocks and the IV.

The IV is the fixed width input plaintext to the cipher, and the message becomes the key. The hashing of the input block x1 works by expanding it (using a key expansion) so that there are as many subkeys as there are rounds (for SHA at least, this may/will vary with other hash functions). Then the IV is encrypted over $N$ rounds using the compression function. Wikipedia has a nice image that gives a general high level overview of this.

In SHA2 hashes, the compression function is an unbalanced Feistel network that encrypts 2 of the 8 words of the IV using a single subkey and a round constant during each round. Once all the rounds have completed, the output of the block cipher becomes the plaintext input for the next block x2, and so forth until all blocks have been used. The output of the cipher then becomes the hash value, truncated if necessary.

SHA256 uses 32-bit words and 64 rounds, with 512-bits of message being expanded to 2048-bits of subkeys. SHA512 uses 64-bit words and 80 rounds, with 1024-bits of message being expanded to 5120-bits of subkeys.

Without a specified IV, the block cipher may output results that follow a pattern, since it is not an ideal cipher. Most hash functions use IVs based on irrational numbers, which generally have a fairly balanced hamming weight, while also not being part of a defined pattern. SHA1 uses the initial values from MD4, which are not irrational or random, and are built from a very specific pattern, but have an average hamming weight of $1/2$ per bit.


Let $E$ be an elliptic curve over $\mathbf F_p$ given by the equation $y^2 = x^3 + Ax + B$. Then a quadratic twist $E'$ of $E$ is given by the equation $\beta y^2 = x^3 + Ax + B$ where $\beta$ is not a square.

Now you have a point $(x_0, y_0)$ you suppose is not on $E'$. Then to make it on a twist, you need to find $\beta$ such that $\beta {y_0}^2 = {x_0}^3 + Ax_0 + B$. If $\beta$ is not a square, then you found a quadratic twist of the curve with $(x_0, y_0)$ belonging on it.

Now, if you want $E'$ to have a short Weierstrass form, you can instead look for a non-square $\beta$ such that the following equation is satisfied:
\begin{equation}
\beta^3({y_0}^2 - {x_0}^3) - \beta Ax - B = 0.
\end{equation}
Then, $E'$ is given by the equation $y^2 = x^3 + A'x + B'$ where $A'=\frac{A}{\beta^2}$ and $B'=\frac{B}{\beta^3}$.

Example

Let $E$ the elliptic curve of equation $y^2 = x^3 - 3x + 60$ over the field $\mathbf F_{101}$ and the point $P=(5,17)$ that is not on the curve.

We will try to find the short Weierstrass equation of the twist $E'$ where $P$ lies on it.

We take the above equation and solve for $\beta$:
\begin{equation}
\beta^3 ({y_0}^2 - {x_0}^3) + 3 \beta x_0 - 60 = 0.
\end{equation}
With our favourite computer algebra software, we find $\beta = 67$. Then the equation of $E'$ is
\begin{equation}
y^2 = x^3 + 74x + 97.
\end{equation}

Let's check everything:

sage: p = 101
sage: E = EllipticCurve(GF(p), [-3, 60])
sage: q = E.cardinality()
sage: q
113
sage: x_0, y_0 = 5, 17
sage: E.is_on_curve(x_0,y_0)
False
sage: R.<X> = GF(p)[]
sage: f = X^3*(y_0^2 - x_0^3) + 3*X*x_0 - 60
sage: f.roots()
[(67, 1)]
sage: F(67).is_square()
False
sage: EE = EllipticCurve(GF(p), [-3/beta^2,60/beta^3])
sage: qq = EE.cardinality()
sage: qq
91
sage: sage: EE.is_on_curve(x_0,y_0)
True
sage: q + qq == 2*(p + 1)
True

The last instructions check the relation between the cardinality of $E$ and its quadratic twist.

Final remark.

This shows how to construct a specific quadratic twist having a specific point, but if you do this with another random point, not on $E$, then it might not be on the previously constructed twist $E'$.


Find prime $p$ such that $a^x\equiv b\pmod p$ for many $x\in[1,p)$

You asked for my one-in-a-million attack; here is what it looks like:

Step 1: find a large prime factor of $b^i - 1$, for some small $i$.  This can be done by iterating through the various small values of $i$ (starting with $i=1$ naturally), use the known factorizations (e.g. $b^2 - 1 = (b+1)(b-1)$), and then for the various subfactors, scrap off the easy small factors and hope what's remaining is a prime (e.g. $b+1 = hp$, for some small $h$ and prime $p$.

If this step succeeds, then we have $a^{0} \equiv b^i \pmod p$; check to see if this yields an $x$ (i.e.. if $a^{n(p-1)/i} \equiv b \pmod p$ for some $n \in \{0, …, i-1\}$).

An initial estimate is that we will manage for find just an appropriate $p$ (and $x$) about 1 in 1000 arbitrary $b$ values in the "thousand bit" range.

Step 2: find $k$.  To do this, find the small factors of $p-1$, and for various small (not necessarily prime) factors $k$ in the appropriate range, check if $a^{(p-1)/k} \equiv 1 \pmod p$.  If $a$ is random, this happens for a particular $k$ with probability $1/k$ (actually, perhaps a bit less if $i > 1$ in the previous step...)

Again, a very rough guess would be that this may succeed about 1 every 1000 times (that we have a factor $k$ of the appropriate magnitude, and that $a$ happens to be in that subgroup).

If both steps succeed, you have $p, x, k$ as requested (although, looking back at it, perhaps a probability of "one in a million" is a tad optimistic; "one in ten million" might be closer...


Forward security (a protocol level feature) and key exchange schemes are indeed two orthogonal topics.

Forward security says the break of a current key does not allow the attacker to learn any communication in the past. To this end, any protocol that uses ephemeral key exchange scheme (i.e., use new keys for new sessions) is forward secure. The only requirement the protocol may have on the key exchange scheme is that the public/secret key pairs can be generated fairly efficiently. (This was not true for RSA, and hence, all the fuss about forward security.) For NTRU-HRSS-SKY this is indeed true. So you will have forward secrecy if you use fresh NTRU keys for every new sessions.


Evaluating Algebraic Complexity of a S-box

The interpolation of Sbox is based on Lagrange algorithm.
the following three steps are used to calculate the interpolation of S-box:

represent the S-box values as polynomial system, where P and C are polynomial representation of S-box input and output.
M (N x N ) is a matrix composed of P power polynomial. N is sbox size (256 for 8-bit sbox)
solve B form the following equation: M.B=C

# the Equation is M.B=C.
#     1  p0  p0^2  p0^3  p0^4  p0^5 .......  p0^d
#     1  p1  p1^2  p1^3  p1^4  p1^5 .......  p1^d
#  M= 1  p2  p2^2  p2^3  p2^4  p2^5 .......  p2^d
#     1  p3  p3^2  p3^3  p3^4  p3^5 .......  p3^d
#       .
#       .
#       .
#     1  pn  pn^2  pn^3  pn^4  pn^5 .......  pn^d
#  size of M is dXn , d and n are equal for sbox, they are GF (2^8) (8-bit sbox)
# Calculation steps.
#   1. convert Sbox table to polynomial of input and output, vectors (P is input  and C is output)
#   2. calculate M table
#   3. B=M.solve_right(C)
#

The following code is implementation of interpolation representation of Rijndael S-box

f=x^8+x^4+x^3+x^1+1  # irreducible polynomial
L.<z>= GF(2^8,modulus=f)
R=PolynomialRing(L,'x')
N=256
M=matrix(L,N,N)
S=[0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
                             0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
                             0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
                             0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
                             0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
                             0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
                             0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
                             0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
                             0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
                             0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
                             0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
                             0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
                             0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
                             0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
                             0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
                             0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16] # rajS-box

C=vector(L,N)
P=vector(L,N)

# step 1
for i in range(0,N):

    P[i]= (i) + z^1*(i>>1) + z^2*(i>>2) + z^3*(i>>3) + z^4*(i>>4) + z^5*(i>>5) + z^6*(i>>6) + z^7*(i>>7)
    C[i]= S[(i)] + z^1*(S[i]>>1) + z^2*(S[i]>>2) + z^3*(S[i]>>3) + z^4*(S[i]>>4) + z^5*(S[i]>>5) + z^6*(S[i]>>6) + z^7*(S[i]>>7)

#print P
#print C
# step 2
for j in range(0,N):
    for i in range(0,N):
        M[j,i]= P[j]^i

#step 3
B=M.solve_right(C)

print B


Elliptic Curve Cryptography Point Arithmetic Libraries

Here is a github repository link with which you can implement ECC arithmetic
and a research paper which gives you some idea on how to implement a software library for ECC

Hope this helps !


Semantic Security and Equal Message Length in the Context of Public Key Cryptography

There are two styles of definition that deal with the issue of message "length" in different ways.

One style considers an encryption algorithm that is capable of encrypting bit strings of arbitrary length.  Such an algorithm cannot completely hide the message length, for information-theoretic reasons.  (Padding short messages to conceal their lengths doesn't overcome the problem; however much padding the algorithm uses, there are always longer messages that cannot fit into the same total length.)  Therefore, in this context a definition of security should require that the adversary produce two messages of the same bit length.

A second style considers an encryption algorithm that is only well defined for messages that come from some finite "message space," which may depend on the security parameter or even the public key.  For such algorithms, there's no inherent problem with message length, because all valid messages have a bounded "length" (or representation).  In this context, the security definition need not require that the adversary's messages are of equal length; it should only require that the messages are both valid, i.e., that they belong to the message space.  (If one message was invalid, the adversary could easily distinguish the two experiments because encryption fails in one and succeeds in the other.)

There are many examples of encryption schemes that fit into the second framework.  Symmetric encryption of fixed-length messages using a (fixed output length) PRF is one.  "Algebraic" cryptosystems like ElGamal or RSA, where the message space is some finite group $G$ or $\mathbb{Z}_n^*$ (respectively), are another.  Systems like Goldwasser-Micali, where the message space is just $\{0,1\}$, are further examples.


Determine AES key given encrypted and unencrypted files

The simple answer is no, known plaintext attacks should not be possible on an AES-encrypted file, assuming that AES is applied correctly. No information about the encrypted file or key should be leaked even if the adversary can guesss  the contents of "the original unencrypted (cleartext) file".

Beware that any mistake into a protocol specification or implementation may negate the security of AES - and this could include the security of the key used. Point in case: some "AES encrypted" USB devices stored the key next to the ciphertext, in case somebody forgot the password.


They are very different. GMW is a multi-party computation protocol while secret sharing is a technique to distribute a secret. GMW uses secret sharing as a building block but it also uses other primitives like an oblivious transfer (OT). GMW deals with the problem that multiple parties jointly compute a function (over their inputs) securely without revealing anything else except the final output value of the function. Note that a simple difference is that GMW does not have a particular secret distributor (well actually every party distributes secrets), as opposed to secret sharing.


Why does the EdDSA use a 2b-bit hash function?

Why does EdDSA use of $2b$-bit hash function?

It insures $r\bmod\ell$ is almost uniformly distributed in $\{0,1,\ldots\ell-1\}$. That's explained at the end of the section on Pseudorandom generation of $r$, which also explains $H$ of $b+61$-bit would be enough for this purpose.

Is there any security problem with this?

Update: I know no I'm told there's is actually a purely cryptographic attack if we reduce $H$ to $b$-bit. It

leaks the private key to lattice or FFT algorithms on relatively small numbers of signatures, with Howgrave–Graham/Smart or Bleichenbacher. The setting is very weak: you just need to get a decently large number of signatures on distinct messages, not even chosen messages, and—bam—the private key falls out. In the Minerva attack, there was a separate side channel giving additional information about the per-signature secrets even if they were uniformly distributed; this enabled the adversary to do rejection sampling to give a nonuniform distribution for the lattice attack.  With b-bit secrets reduced modulo the curve order, the distribution is already nonuniform enough for the lattice attack.

Turns out that a less-than-uniform modulo $\ell$ not only invalidate the security argument, it allows an attack! It also (and more badly) affects ECDSA, and there was precedents as explained earlier in the section on Pseudorandom generation of $r$ of Bernstein's paper.


The modern approach is still to use binary Goppa codes.  See, e.g., McBits from 2013:

  Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." Pages 250–272 in Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, edited by Guido Bertoni, Jean-Sébastien Coron. Lecture Notes in Computer Science 8086, Springer, 2013. ISBN 978-3-642-40348-4.

https://binary.cr.yp.to/mcbits-20130616.pdf

Other proposals, such as Niederreiter's using generalized Reed–Solomon codes, have been broken:

  V.M. Sidelnikov, S.O. Shestakov. "On insecurity of cryptosystems based on generalized Reed–Solomon codes." Discrete Mathematics and Applications, 2(4), pp. 439–444, 1992.

https://doi.org/10.1515/dma.1992.2.4.439 (paywalled, sorry!)


Looking for commutative asymmetric cipher for data matching

Rather than using a commutative encryption scheme, I'd suggest looking at private set intersection.  From the description in your first paragraph, it sounds like that's what you're looking for.


rotational cryptanalysis on modulo multiplication?

The rotational cryptanalysis considers applying the transformation $E$ to both $X$ and $\overrightarrow{X}$, where
$$
\overrightarrow{(x_1, x_2,x_3,\ldots, x_n)} = (x_{r+1},x_{r+2},\ldots, x_n, x_1,\ldots, x_r)
$$
for some integer $r$. You know that $\overrightarrow{X} \oplus \overrightarrow{Y} = \overrightarrow{X\oplus Y}$ always, and
$$
\overrightarrow{X} \boxplus\overrightarrow{Y} = \overrightarrow{(X\boxplus Y)}
$$
with quite high probability.

For the modulo multiplication the property does not seem to hold.  I guess you were thinking of applying it to the IDEA block cipher. However, in some situations a modified property holds. For instance, if $X = q2^l$  and $Y = p2^t$ for some small $q,l,t,p$, then
$$
\overrightarrow{X} \odot \overrightarrow{Y} = (q2^{l+r}) (p2^{t+r}) = (pq)2^{t+l+2r} =
\overrightarrow{\overrightarrow{(X\odot Y)}},
$$
i.e. you have double rotation (again with some probability). I wonder if you could exploit in the attacks, because generally we want the same rotation distance $r$ in all internal variables.

To summarize, no one has yet applied rotational cryptanalysis to the multiplication, though there are hopes.


Proofs by reduction and times of adversaries

Reductionist security

In a reductionist security proof for some cryptographic protocol $\Pi$
to some alleged hard problem $P$ means, that we can build an algorithm
$\cal B$ for solving $P$ if we have access to a hypothetical algorithm
$\cal A$ that efficiently breaks the security definition for the
protocol $\Pi$.

In general, showing a polynomial time reduction only shows asymptotical
equivalence of the problems. In practice-oriented security (or concrete
security) for reductionist security proofs, one wants to relate the
running times of the hypothetical adversary against a protocol $\Pi$
with the running time of the concrete reduction. This may then be seen
as showing "practical equivalence".

Tight vs. non-tight reductions

Let the adversary, i.e., the algorithm $\cal A$, take time $t$ and win
with probability $\epsilon$ in the security game of $\Pi$ and say we can
use $\cal A$ to build an algorithm $\cal B$ to solve $P$ and $\cal B$ runs
in time $t'$ and wins with probability $\epsilon'$.

Then, we are interested in tight reductions, i.e., that $t\approx t'$
and $\epsilon\approx \epsilon'$. If $\cal B$ takes much longer, i.e.,
$t'>>t$, and has much lower success probability, i.e.,
$\epsilon'<<\epsilon$, then the reduction is called non-tight (which is
not desirable).

Why not?

If the reduction is tight (and we assume that the security definition of $\Pi$ is
meaningful - which is important, as otherwise even a tight security
proof may be meaningless for practical applications of the protocol),
then we know that breaking the protocol $\Pi$ is at least as hard as
solving the alleged hard problem $P$. And then, we know that when we
take the security parameter for the protocol as the current status
indicates, then we are secure.

If on the other hand the reduction is not tight, then we only have the
assurance that the protocol $\Pi$ requires at least as much effort as a
certain fraction of what we think it requires to break $P$, e.g.,
breaking RSA, since it takes much less time to break the protocol $\Pi$ than it takes for the reduction to the problem to work. Now, this means that we may have to take a
much larger security parameter for the protocol to still achieve
reasonable security.

If we increase the security parameter, we consider the gap that is introduced between the adversary and the reduction and we need to choose them in a way that we can guarantee security of the protocol relative to the concrete reduction.

Why is this a problem?

We have to take larger security parameters, which makes the schemes
typically more inefficient. Secondly, what the advocates of
concrete security criticise, is that often a paper may not indicate that
the security reduction is non-tight and thus someone implementing the
protocol may choose the security parameters as if the reduction were tight.
Consequently, the so implemented protocol may be (highly) insecure in
practice.

A brief example

For instance, the original reduction for the RSA-FDH
(RSA full domain
hash) signature scheme is not tight. It bounds the probability $\epsilon$
of breaking RSA-FDH in time $t$ by $\epsilon'\cdot q_H$, where $\epsilon'$
is the probability of inverting RSA in time $t′ \approx t$ and $q_H$ is the
number of hash queries made by the adversary $\cal A$. Consequently, the
reduction looses a factor of $q_H$. Now, assume that you want to have a security
level of 80 bits and you assume that $\cal A$ can make $2^{60}$ queries, then
one should use a security parameter for the signature scheme such that inverting the RSA function cannot be achieved in fewer than $2^{60}\cdot 2^{80}=2^{140}$ operations. If one takes the ECRYPT recommendations
for key sizes for instance, 80 bit security is equivalent to 1248 bit for the RSA modulus. This would apply
if the reduction would be tight. However, the reduction is non-tight and one would actually require a modulus size of about 4000 bits.

Choosing the security parameter for the scheme according to the reduction (in the example 4000 bit) we can be sure that we can cope with an adversary in practice (in the example against 1248 bit RSA). Basically, we have an idea how hard it is to break RSA today and then we need to adjust the security parameter accordingly.


Well, supposing everything is properly domain separated, nonces are always generated randomly for encryption queries, and your KDF behaves like a perfectly random function, the first step is to bound the probability of a nonce repeat. A birthday bound tells us that this happens with probability at most
$$
q^2/2^{256}\,,
$$
where $q$ is the number of encryption/decryption queries. So let's rule this case out, and move to the case where this never happens.
Next is the event of key collisions. Again, a simple birthday bound gives us a probability of at most
$$
q^2/2^{256}
$$
that there are repeated derived keys.
Now what we have here is, in fact, an instance of multi-user GCM where the same nonce is always used. That is, you have up to $q$ independent instances of GCM, and to break the scheme it suffices to break any one of these instances. (Strictly speaking, the multi-user setting gives you more freedom in choosing how many queries per user you can use, whereas here you're limited to 1 (encryption) query per user.)
The multi-user security of GCM was conveniently analyzed by Hoang, Tessaro, and Thiruvengadam in the ideal cipher model, which tells us in Theorem 3.1
$$
\begin{align*}
\mathbf{Adv}_{\mathtt{CAU}[H,E]}^{\text{mu-ae}} \le &\frac{d(p+q) + n(q + \sigma + p)}{2^k} + \frac{\sigma(2B + cn + 3)}{2^n} \\& + \frac{2q+1}{2^{2n}} + \frac{\sigma(\sigma + ncd) + 2pq}{2^{k+n}}\,.
\end{align*}
$$
Here we can set $n = 128$, $k = 256$, $d = q$ ($d$ is the number of nonce repetitions across users; since the nonce is fixed, this is equal to the number of queries), $c$ is a bound on the differential probability of $H$ (for GHASH, it can be set to $B/2^n$), $B$ is the maximum message size in blocks, $\sigma$ is the total number of blocks across queries (which can be bounded by $qB$), and $p \le 2^{n-2}$ is the number of offline AES evaluations (i.e., bruteforce of the key).
So, roughly speaking, as long as your messages are sufficiently short (to keep the $O\left(\frac{qB^2}{2^{128}}\right)$ term down), and the total number of queries remains well below $2^{128}$ (to keep the terms $2q^2/2^{256}$ and $O\left(\frac{q^2 + pq}{2^{256}}\right)$ down), as you suggested, this scheme should remain secure.


If you know the messages, and the results of HMAC(key, message) can you find the key?

Not, that should be not possible, at least if you have a good key.

All this is only valid as long as SHA-256 is still a secure hash algorithm and not broken. To be precise, as long as HMAC-SHA-256 is not broken.

Does the attacker have any informations about the messages (other than the length and that they are "random-noise")? If he/she doesn't: No, there's no way an attacker could get the key in real life conditions. They would have to brute force HMAC-SHA-256, and that's not possible if you use normal computers with non-ignorable probability. Every message has far higher entropy than anything possible to brute force.

If the enemy knows all messages: Well, it's all about your key. In the past, there was a need to have a key for hashes, but the common structures of hashes were not suitable to just put the key before the message. HMAC was invented to solve this problem. It has some nice security proofs which basically say "It should not be possible to get the key as long as the hash function is still secure and the key good enough." - the RFC 2104 has more explanations and some links for further informations.

Well, is your key good enough? If your key is anything under 64 bit long and at least one message known by the attacker, than you have lost. Brute forcing 64 bit is not easy, but doable. If your key is longer than 64 bit (something like 80 bit or better 128 bit or higher) then you have to think about entropy. If your key is fully random and an attacker doesn't know any pattern about it, than is the entropy as high as the length in bit, but if your password is something like "password1234", than it's pretty easy to brute force, despite having 96 bit (for 8 bit per character). Good passwords are alone a pretty complex topic, so I won't include them in this answer. If you need to know more about secure passwords, use the search engine you like the most for something like "good password" or "choosing secure password".


You don't specify your encryption method. To show you why that is important, I'm going to pick a really bad one. Let's say we use a stream cipher to encrypt. "stone" and "paper" have the same length, so we are good there, but "scissors" is longer. So, if Alice chooses "scissors", Bob can see the ciphertext length and know what she picked and choose "stone". Therefore, if Alice chooses "scissors", Bob always wins.

If you pick your encryption method so that the ciphertext lengths are always the same, this attack is mitigated.

Bob, once he knows whether or not he wins, could refuse to send $R_B$.

The major flaw, however, is, even if you pick a really good encryption method (say AES-CBC with a fixed length size), you are doing nothing for integrity checking when integrity is really the primary concern here.

The proper way to do this would be to have Alice and Bob each publish a commitment to their choice. Then they open the commitment publicly. This could be done, for example, with HMAC. Choose a random key $k$ and publish $HMAC(k,m)$ where $m$ is the choice. Once both have done this, they can each publish $m,k$. That way they can verify that the choice hasn't changed.


What is the security loss from reducing Rijndael to 128 bits block size from 256 bits?

Security issues related to block size boil down to the following: a pseudorandom permutation is not a pseudorandom function, and the difference becomes visible when you query the function too many times. Imagine a function which accepts as inputs, and offers as outputs, elements from a set of size $N$. For instance, the inputs and outputs are blocks of $n$ bits, so $N = 2^n$. If you feed this function with different input values, then you will first get as many different output values. However, with a PRF, you expect to obtain a collision at some point: a new input which yields the same output as a previous distinct input. On average, this should occur after about $\sqrt{N}$ queries. With a PRP, you will never get a collision, because permutations are, by definition, injective.

So when encrypting with a block cipher, using blocks of $n$ bits, you begin to have problems when processing more than $2^{n/2}$ blocks with the same key. 3DES has 64-bit blocks, so encrypting more than $2^{32}$ 8-byte blocks with 3DES can be troublesome: that's 34 gigabytes or so, a value which is not so huge nowadays. To avoid this problem, NIST launched an open competition for an "Advanced Encryption Standard" (the AES) with the following rules:

128-bit blocks.
Keys of 128, 192 and 256 bits.
Not slower than 3DES (many candidates turned out to be widely faster).

And that's what they defined. They did not really care that the selected candidate (Rijndael) had extended versions which could accept other block sizes; 128 bits were sufficient.

In all of the above, the important point is that the $2^{n/2}$ figure is related to the number of queries. It is generally estimated that, for an attacker, obtaining $x$ pairs plaintext/ciphertext is widely more difficult than trying out $x$ potential keys, since the former requires cooperation of the target system, while the latter requires only some computing power on the attacker's own machines. You'll have a hard time finding an "honest system" which needs to encrypt $2^{68}$ bytes with AES (that's close to 300 billions of gigabytes), and even more so an honest system where the attacker can get 300 billions of gigabytes of known plaintext while still being "locked out" (if the attacker can get the honest system to process that much data, then what left is there to attack ?).

Basically, the block size and the key size work on different scales, and it just happens, fortuitously, that "128 bits" is a nice level for keys (exhaustive search on $2^{128}$ keys is not feasible with current technology), and also a nice level for block size ($2^{64}$ blocks of 16 bytes of known plaintext is not a realistic attack scenario with current technology).

Notably, if a quantum computer ever sees the light, that computer would be able to break a 128-bit key in $2^{64}$ effort, but it would do absolutely nothing about the issues related to block size: 128-bit blocks would still be as good as they are today.

All of the above is for usage of a block cipher for encryption. When a block cipher is to be reused as a core element for something else, e.g. a hash function, then other constraints may apply. Typically, for the Skein hash function, the internal block cipher had to offer much larger blocks if the hash function was to live up to its promises (note that a hash function has no key, so we are far from the attack model of an encryption system). This is why Threefish, the block cipher in Skein, has big blocks. This is not because big blocks are good for encryption; this is because big blocks are necessary when a block cipher is turned into a hash function the way Skein does it.

A similar case is Whirlpool, which uses the "W" block cipher, which is a Rijndael derivative (with even larger blocks -- 512 bits -- and a revamped key schedule).

As for D-Wave systems, they are not "true" quantum computers; they compute a specific problem instance in a "somewhat quantumish way", but are not able to apply the nifty algorithms which eat crypto for breakfast. The difference is qualitative, not a question of mere tuning. See this for pointers.


Why Camellia paper declares that it is faster than Rijndael while it is actually much slower?

The paper says it is comparable in speed hardware and software to the AES finalists.

If we look at low end hardware performance, say cycles and resource bytes on a Z80 smart card:

Cipher         Keysched  Encrypt  RAM-KS RAM-ENC ROM-Total
----------------------------------------------------------
AES            10318     25494    32     34      980
Camellia       5146      28382    44     62      1698
Twofish        28512     31877    56     34      2808
RC6            138851    34736    90     124     1060
MARS           21742     45588    512    60      5468
Serpent        147972    71924    96     68      3937

AES is the fastest, but only about 11% faster than Camellia, all the other finalists are slower. Resource usage is also good, I would say their claim of being comparable is accurate, if not understated.

If we look at modern CPUs with hardware acceleration, what you saw was that AES is about 4 times faster. Without the hardware acceleration, Camellia is 2/3 of the speed of AES, slightly faster than Twofish, and faster than Serpent. I would say the claim still holds here, just not as strongly against AES.

For FPGA hardware from the Camellia paper in 2001, AES was clocked at 1540Mb/s using 1857 slices, whereas Camellia was clocked at 6750Mb/s using 9692 slices. Comparing rate/slice, they are within 20%. On other FPGA and AES with higher gate counts, AES will have a strong advantage, the Amphion CS5240X2 core on Xilinx Virtex2 clocks at 10Gb/s using only 2200 slices... and AES on Virtex4 clocks at 17.9Gb/s using 18400 slices, very very fast. AES is most likely more efficient on Virtex5, it can perform at 4Gb/s using only 350 slices, which 12 times the rate/slice of Virtex4. Camellia on Virtex5 using 132 slices operates at 85.4Mb/s, much slower. On a Spartan-3, AES does 2640Mb/s using 390 slices, and Camellia does 33Mb/s using 321 slices and half the clock speed.. or roughly 1/40th the rate per clock.

For ASIC, unrolled (1 cycle) on a 180nm process, Camellia performs at 25MHz using 355K gates, and an Amphion CS5240TK AES chip performs at 200MHz using 203K gates, a big difference, and a win for AES at 8 times the speed.

The closest looped ASIC frequency/area match is a 172Mhz 21 cycle Camellia implementation running at 1051Mb/s using 11.87K gates, vs the Amphion CS5220TK 200MHz 44 cycle processor at 581Mb/s using 14.8K gates, I call that one a win for Camellia since the speed per gate is more than double.

In the proposed Cryptoraptor configurable cryptographic processor, Camellia and Twofish run at half the speed of AES.

Considering that Camellia is a more complex cipher with more rounds, I consider their generalized claim of "comparable" to the finalists to be accurate, the AES winner Rijndael on the other hand does have an advantage due to its simplicity and low resource usage, based solely on the round count you would expect it to be 60% faster than Camellia in software table lookup, which it is. You can generally expect AES to be at least twice as fast in high end hardware, and about the same speed in low end hardware.


Is there any way to track if a ciphertext has been decypted?

Digital data can always be copied. So it is easy to see that such a seal would not work in general: you could just leave the original ciphertext where it is and decrypt the copy.

There are ways around this, but they need some other trusted party or device. For instance you could use a simple secret sharing technique where (information from) a trusted third party is needed to reconstruct the decryption key. Or the trusted third party could do the decryption themselves, but in that case they may learn the plaintext. There are also plenty of techniques where the trusted third party never knows the plaintext.

Obviously you don't know the other party actually learns the plaintext. It could perform the digital equivalent of looking away. You can just learn if they received the plaintext and had the opportunity to see it. It would be easy to require the other party to sign the plaintext to verify that information was received.

You can of course generate the digital variant of a sealed box in hardware. This lets you get around the fact that the ciphertext can be easily copied.