Does exponentiation by squaring work on Montgomery curves?

Yes, exponentiation by squaring can be applied to any associative binary operation with identity (that is, to any monoid, which includes groups like elliptic curves as a special case), independent of the particular representation.

However, the main advantage of Montgomery curves is that there is an improved algorithm (appropriately named Montgomery ladder) for point multiplication, which does not require the $y$ coordinate of the input point and achieves better resistance against side-channel attacks since it performs the same sequence of operations for all exponents of a given length (one addition and one squaring per bit), so you might want to use that instead if you are already going for a Montgomery curve.


Confused about Merkle Damgard Transform - short messages?

In SHA-256, the message is padded to a multiple of the block length by appending a single 1 bit and then as many 0 bits are needed to fill a message block to 448 bits; finally the 64-bit length is appended to make the input length an exact multiple of 512 bits.


The first thing to NOTE is that said by SEJPM in the comment, performance depends on the hardware - in both horizontal (core count, etc.) and vertical (clock speed, etc.) dimensions. The second thing to understand is that, although CSPRNGs and stream ciphers can share underlaying primitive, their security requirements are different.
So now, let's get started - what're some of the famous symmetric-key primitives?
There are 2 dimensions to consider when excluding the hardware parallism:

block size,

execution time per block.

Grades from slow to fast in: $$\text{Moderate} < \text{Fast} < \text{Very Fast} < \text{High} < \text{Very High}.$$ The grades are my personal opinion.

Primitive
Block Size
SW Performance Grading
HW Performance Grading

Gimli
384-bit
Very High
Very High

Keccak-p[1600,24]
1600-bit
Very Fast
High

Keccak-p[800,12] (not yet standardized)
800-bit
High
High

AES-128
128-bit
High
Very High

ChaCha20
512-bit
High
High

I haven't done systematic benchmarks on diverse hardwares and implementations yet, but the numbers are provided here for a quick reference. I used my own (hardly-optimized) MySuiteA library with ad-hoc benchmarking code written in a rush.

Primitive
Time of $2^{20}$ iterations of execution on Apple Silicon M1

Gimli
0.973sec

Keccak-p[1600,24]
16.495sec

Keccak-p[800,12] (not yet standardized)
8.143sec

AES-128
35.657sec(sw,unoptimized) 0.184sec(arm-neon-crypto)

ChaCha20
1.287sec

Next, we can consider implementation side.

SBox Modern cryptography wisdom says this: avoid SBox if it has to be implemented using look-up table (because it's a cache-memory side-channel), so AES is the most dangerous here;

Block Size AES is also dangerous due to its small block size - 128-bit is too small a space for nonce and counter. ChaCha20 also has only 128-bit space for nonce and counter, but it has larger state and a side-channel-resistant non-linear layer.

ARX vs Binary Polynomial ARX stands for Add-Rotate-Xor, which is a traditional paradigm for obtaining non-linearity (ChaCha20 follows this). It has the implementation disadvantage of requiring somewhat more complex circuit when doing a hardware implementation, and this is where ones without arithmetic addition - those based on binary polynomials have a win (Gimli, Keccak).

Word Length It was a surprise for me to see that my software AES implementation is actually very bad, but anyway, it's a byte-oriented algorithm anyway. What I want to note here is that, Keccak-p[800,12] out-performed Keccak-p[1600,24] not because of smaller block size, but because the fewer number of rounds - using 32-bit words on a 64-bit machine is actually a drawback when compared with using native word lengths. It is for this reason, SHA-512 outperforms SHA-256 on 64-bit computers.

Side information:
Gimli had a full-rounds distinguishing attack last year: https://eprint.iacr.org/2020/744 . Gimli isn't the only 384-bit permutation though, Xoodoo is also a good 384-bit permutation, and is authored by the same group of people invented Keccak, but I haven't implemented in my suite for benchmarking yet.


Is it possible to prove that I have half a key to decrypt file, to someone who has other half, without disclosing my part?

This is similar to problems in Multi-Party Computation, but in this case I don't know how its possible if there is no trusted third party, and no corollary data accompanying the secret keys.

However if you relax the scenario, and allow the distributor to convey an extra piece of information to both parties, then this can be achieved. Have the distributor distribute a second piece of information to both parties, for this example let it be Hash(First Half) XOR Hash(Second Half)

So both parties know the hash of their half, and the XOR of the hashes of both halves. They can easily figure out the hash of the other parties data. So effectively, they both have a password which they can authenticate each other with. So then use a secure verification protocol that isn't subject to replay attacks (perhaps Password-authenticated key agreement algorithms such as SPEKE) Then they can both verify each other, and that they knew the Hash of their block of half of the key, which we now assume means that they knew that data.


How would an attacker perform an exhaustive key search on a block cipher using ECB mode?

I think the attack models establish constraints on the cipher parameters that allow you to confirm guesses in a brute force or probabilistic search.

A simple way to look at it is that they let your write equations involving the cipher parameters. For example, in $c = enc(p,k)$, you can fix two of the parameters and solve for the third. Clearly $c$ (ciphertext) must be obtainable from $\lbrace p,k \rbrace$ (encryption of plaintext $p$ under key $k$), and $p$ obtainable from $\lbrace c,k \rbrace$ (decryption), but $k$ should not be obtainable from $\lbrace c,p \rbrace$ (secure against known-plaintext attacks).

If all you have is ciphertext samples, then you have no means to verify a guess for the key. From an algebraic perspective, you cannot set up an equation using $c$ alone that will allow you to derive anything about $p$ or $k$. However, if you are running in ECB mode, then solving $k$ for one block under known-plaintext gives you $k$ for every other block, including blocks where only $c$ is known.

Sure, you can set up the equations corresponding to a particular attack model, but ciphers are designed so that the equations are not solvable by any means other than exaustive brute force search.


Can CBC ciphertext be decrypted if the key is known, but the IV not?

With CBC (Cipher block chaining) mode, before encryption, each block is XOR-ed with the ciphertext of the previous block, to randomize the input to the block cipher (and avoid encrypting the same block twice with the same key, as this would give the same output, and tell the attacker something about the plaintext).
As the first block has no previous block, here the initialization vector will be used instead.

On decryption, we will apply the block cipher to each ciphertext block, and then XOR the result with the previous ciphertext block (or the initialization vector, for the first block).

As all ciphertext blocks are known, and we have the key, we can reliably decrypt everything other than the first block, even if no or a wrong initialization vector is given.

For the first block, we actually have no information at all, without the initialization vector, other than that it has the same length as any other block (16 bytes for AES): Every 16-bytes plaintext can be reached by supplying the fitting IV. Fortunately (or unfortunately, depending of your point of view), in many file formats the first some bytes are fixed (or almost fixed, or can be guessed based on the rest of the file).

So, with CBC-mode, a secret initialization vector gives almost no protection, if the key is known to the attacker.

This applies generally: Protocols rely on the key being secret, while an initialization vector can usually be public, and often is even transmitted together with the ciphertext.

In CTR mode, a secret initialization vector (there called "nonce") will actually help a bit more to keep the plaintext secret - but if the attacker can guess even one plaintext block (and has the corresponding ciphertext block), he can (given the key) calculate the corresponding counter value, and from this the nonce. Don't let the attacker have the key.


It's unlikely that you'll be able to prove unforgeability from Discrete Log alone. You might need a new assumption altogether on bilinear maps.

Also, in the bilinear world, assuming discrete log is usually not enough to prove security. You need stronger assumptions such as Bilinear Diffie-Hellman or XDH, or the bilinear generic group model (see Appendix A of BBG05).


Does AES-CTR require an IV for any purpose other than distinguishing identical inputs?

Well, no, in your case, a constant IV is not a problem.  With counter mode, the rule is that you cannot reuse the same IV with the same key.  However, it is perfectly fine to use the same IV with different keys, and that's what you're doing.

One minor correction to what you have (that doesn't directly relate to your question): you state that there are problems if "a key is used with the same (or a numerically-close one).  Actually, as long as the IVs are different, "numerically-close" IVs are not an issue.  In fact, it is actually pretty common to select counter mode IVs using a message counter (e.g. the first message gets IV 0, and second one gets IV 1, etc.)

However, I do have one question: how do you expect someone to decrypt the ciphertext?  If what you're doing is generating a hash of the plaintext, why don't you just go with the SHA-256 hash of the plaintext?


How does DJB's nistp224 manage to fit compressed points into 224 bits?

That's because you can do ECDH by exchanging only the X coordinates of your public value; as long as the shared secret depends only on the x coordinate, everything works out.

Here's the fundamental property of elliptic curves that makes this work, the x coordinate of $nP$ is only a function of the x coordinate of $P$ (and $n$); it does not depend on the y coordinate of $P$.

So, if the two sides select their secret values as $a$ and $b$, they both compute $aG$ and $bG$.  They then exchange the x-coordinates of those points to the other.  What both sides can do is then compute the x-coordinate of $a(bG) = b(aG) = (ab)G$.  This x-coordinate is the same value on both sides.  Now, neither side knows the y-coordinate of the common point; however, the x-coordinate is sufficient for a shared secret.


An example of an appropriate use case for AES-CBC encryption without authentication?

Full disk encryption is only an example of encryption of data at rest. For that kind of usage CBC could suffice if only confidentiality is required. This is often the case if the user just wants to hide something, say an illegally downloaded movie. In that case you don't care if anybody can change the ciphertext, you just want to make sure that nobody finds out what is encrypted (possibly leaking the size of the file, which can be pretty unique for such large files, by the way).

The same goes for ransomware. If ransomware encrypts a file then the rightful owner can muck with the encrypted file as much as he wants; the data just gets further mangled. In this case I assume that there is no padding oracle attack, I suppose that the victim simply gets an application with the private key to decrypt files instead of the victim sending files over for decryption. That's one way to implement it anyway.


Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key?

With RSA, there is no known way to deduce the private key based on chosen ciphertext; that is, even if the attacker has oracle access to the private operation, the key is still safe.

However, this doesn't mean that it's safe to give an attacker this access; he can't deduce the key, but he can use this access to decrypt anything he wants (and this is the nonobvious part) he doesn't have to reveal what he's decrypting to the RSA implementation.  That is, even if you design the implementation to attempt to not tell him the decryption of a specific message, he can decrypt that message anyways.

The technique he would use is called 'blinding', and here is how it works; assume that the attacker has a ciphertext $C$ that he wants to decrypt; what he does is pick a random number $r$ and compute: $C_{blind} = r^e C$ (where $e$ is the public exponent).  He then presents $C_{blind}$ to the Oracle for decryption.

Now, $C_{blind}$ is effectively independent of $C$; the Oracle cannot deduce any information about $C$ (because for every possible $C$ value, there is a value of $r$ that makes it work).

The Oracle then returns $P_{blind} = C_{blind}^d = r C^d$.  The attacker then computes $P = P_{blind} r^{-1} = C^d$, which is the decryption he is looking for.

As for your second question; whether it is possible to deduce the public key, no, from a single plaintext/ciphertext pair, it isn't possible.

However, from two plaintext/ciphertext pairs, it is (as long as the public exponent $e$ is sufficiently small).  Here is how it works: if we have a plaintext/ciphertext pair $P_1, C_1$, we know that: $$P_1^e - C_1 = k_1N$$ where $e$ is the public exponent, $N$ is the modulus, and $k_1$ is some integer.  If we have a second pair $$P_2^e - C_2 = k_2N$$ we can then compute $$gcd( P_1^e - C_1, P_2^e - C_2) = gcd(k_1N, k_2N) = N gcd(k_1, k_2)$$ $gcd(k_1, k_2)$ is almost certainly a small integer; allowing us to recover $N$.

If we don't know $e$ apriori, we can just search through the various possibilities (we're assuming $e$ is small, hence there aren't that many)


I see no reason why that would not be secure.  If you want to play it safe, though, you could always go with a standardized key derivation function, such as HKDF (RFC 5869) or one of the other KDFs listed in this draft standard.  (The draft itself seems to be expired, but it's the most convenient list of standardized key derivation functions I could find.)


Does sending the same message with 2 different keys in OTP leak information?

As long as the keys $K_i$ are only used once, this is semantically secure.  To see it, observe that if $K_i$ is a uniformly random value in $\{0,1\}^{|M|}$ then so is $C_i = M \oplus K_i$.


Question about the definition of a perfect cipher

Since this is homework, I'm not going to give the answer, but will hopefully point you in the right direction.

You are correct when you say for a perfect cipher, the probability should hold that $\mathbb{P}(P=m|C=c)=\mathbb{P}(P=m)$. In words, this means that given that you see the ciphertext is $c$ what is the probability of the plaintext being $m$ (note, I'm using $P$ for the plaintext space and $C$ for the ciphertext space). If being given the ciphertext does not help the adversary at all (i.e., the probability of any plaintext does not change at all given the ciphertext), then the cipher is said to be perfect. Almost all modern ciphers that we use today we cannot prove this property. For the cipher you are studying, however, it is possible.

By applying bayes rule, we get
$\mathbb{P}(P=m|C=c)=\frac{\mathbb{P}(C=c|P=m)\mathbb{P}(P=m)}{\mathbb{P}(C=c)}$ and we want to show that this equals $\mathbb{P}(P=m)$. Therefore, if the other term on top cancels out the term on bottom, we would get what we want.

To help a little more, think about what the two terms are. On bottom we have $\mathbb{P}(C=c)$. In other words, what is the probability of each ciphertext (independent of plaintext). The ciphertext space is $\mathbb{Z}_p$ so the size of it is $p$.

The other term is $\mathbb{P}(C=c|P=m)$, meaning, given a plaintext message $m$, what is the probability that the ciphertext is some $c$. So, given a plaintext $m$ if all ciphertexts in $C$ are produced by the same number of keys, then $\mathbb{P}(C=c|P=m)$ would simply be $\mathbb{P}(C=c)$ in which case the two terms would cancel as we want.

I'll leave that up to you to show.


Is SHA1 secure with such many inputs Z that Z = constant secret X + variable public Y?

Answering the question as worded in its body: NO, $\mathrm{SHA1}$ is not designed so that the proposed construction is secure under the stated conditions. The design objective of the $\mathrm{SHA1}$ and $\mathrm{SHA2}$ hashes, as explained by NIST, is that

  it is computationally infeasible to find a message that corresponds to a given message digest, or to find two different messages that produce the same message digest.

and this does not lead to the conclusion that the proposed construction is secure, under any reasonable definition.

In order to answer the (different) question as worded in its title, we need to define "secure". The question is about a construction $F: (X,Y) \to F(X,Y) = \mathrm{SHA1}(X||Y)$. One possible definition of "secure" could be that $Y \to F(X,Y)$ is computationally indistinguishable from a random function for an attacker not knowing $X$ (which implies that $X$ does not leak from examples).

With this wide definition, NO, $\mathrm{SHA1}$ is not secure. It is vulnerable to a length-extension attack, a classical weakness of the Merkle–Damgård construction used in $\mathrm{SHA1}$. An adversary knowing $\mathrm{SHA1}(X||Y)$ can compute $\mathrm{SHA1}(X||Y')$ for some $Y'\ne Y$, on the conditions that $Y'=Y||P||E$; and he knows $E$ and the length of $X||Y$; and $P$ is a specific 65-to-576-bit string depending only on that length. Having many examples of $(Y,\mathrm{SHA1}(X||Y))$ helps the adversary, in that it widens the choices for $Y'$.

To perform this length-extension attack, the adversary can choose $P$ as the 65-to-576-bit string constituting the padding for $X||Y$ when computing $\mathrm{SHA1}(X||Y)$. Then, $\mathrm{SHA1}(X||Y||P||E)$ is computed by starting the normal computation where the block with $E$ starts, with the 160-bit hash state $\mathrm{SHA1}(X||Y)$ rather than the constant specified in $\mathrm{SHA1}$. The attack has very low cost, lower than if the adversary had computed $\mathrm{SHA1}(X||Y')$ directly with knowledge of $X||Y'$.

When the conditions for the length-extension attack are not met (including if the length of $Y$ is fixed, exactly or with a small leeway of +64 bits), or when the objective of the adversary is finding $X$, the construction proposed has considerable cryptanalytic resistance. Up to some limit on the size of $X$, we know no attack much better than brute-forcing $X$. A security argument could be given based on the assumption that the cipher used in the $\mathrm{SHA1}$ round function is secure; but we know that this assumption does not hold at all, if only because of some near-practical attacks on the collision-resistance of $\mathrm{SHA1}$. Therefore I can't quantify the level of resistance better than "AFAIK unbroken for practical purposes", which is not strong enough for a recommendation.

Fortunately, there is a recommendable construct based on $\mathrm{SHA1}$ that is designed to be secure (in the wide definition we considered); this is HMAC with $\mathrm{SHA1}$ as the hash function, $X$ as the key, $Y$ as the message. This construction has a security argument that is not directly harmed by a collision-resistance attack on $\mathrm{SHA1}$. Although the absolute confidence we can have in this argument is the subject of debate and some controversy, it is still very reassuring to me about the security of HMAC, and I am not alone.


generating prime p and q, with alpha of element of order q

There are generated the primes $p$ and $q$ such that $q | (p-1)$

What that means is that we search for two prime numbers $p$ and $q$, with the constraint that $q$ is a divisor of $p-1$.  That is, $kq = p-1$ for some integer $k$.

In practice, this is easy to do; we first pick a prime $q$ of an appropriate size, and then search for the value $k$ values of the appropriate size until we find a value $p = kq + 1$ which is also prime.

  and $\alpha \in \mathbb{Z}_p^*$ ...

$\mathbb{Z}_p^*$ is the multiplicative group modulo $p$; its elements have an obvious identification to the between 1 and p that are relatively prime to $p$ (and since $p$ is prime, that means the values $[1, p-1]$), and

  an element of order $q$.

What this means is that the smallest positive value $\lambda$ for which $\alpha^\lambda \equiv 1 \pmod p$ is $\lambda = q$.

It turns out to be a lot easier to find such a value $\alpha$ than you'd expect; you pick an arbitrary value $\beta \in [2, p-2]$ and set $\alpha = \beta ^ {(p-1)/q} \pmod p$.  As long as $\beta \ne 1$, then $\alpha$ will have an order precisely $q$.

We know that $\alpha^q = (\beta ^ {(p-1)/q})^q = \beta ^ {p-1} = 1$ by Fermat's Little Theorem (and because $p$ is prime)
We know that $\alpha^r \ne 1$ for any $0 < r < q$, because if $\alpha^r = 1$, then we could show that $\alpha^{\gcd(q, r)} = 1$, and as $q$ is prime, $\gcd(q, r) = 1$, and so we'd have $\alpha^1 = 1$, which we had verified is not the case


Which is better when the secret is leaked, RSA or Diffie-Hellman?

Neither one is secure if the private key is leaked; if the connection data is kept by and adversary then the adversary could decrypt the connection data if the private key of either DH or RSA key pair is lost.

The idea of ephemeral Diffie Hellman is that you create two new key pairs for each connection. Then you can throw away the key pair(s) after the connection has been set up and authenticated. Even if the private key is factored or otherwise retrieved then you could only attack a single connection. If the server is found by anybody then the private key would already have been destroyed, so this makes it impossible to decrypt the data when the server is found. This is what forward secrecy offers you.

RSA is not very useful when it comes to generating ephemeral key pairs. RSA key pair generation is one of the slowest algorithms that exist, and the time it takes to find two or more primes is indeterministic as well. In principle you could generate a new key pair at one side and use it to agree on a master key, just like with ephemeral Diffie-Hellman.


Does blinding work against side channel on RSA?

Blinding protects against some side-channel attacks in RSA: those that target variations in the timing or other side-channel information as a known function of $C$ (or $C^d\bmod n$ should that end up to be available).

As noted in the question, blinding is pointless against the most basic (Simple) Power Analysis attack, which determines the bits of the private exponent $d$ (or the CRT exponents $d_p$ or/and $d_q$) by finding from power traces if binary exponentiation is performing a multiply or not. Protection against such attacks must be by other ways (e.g. using a Montgomery ladder, a randomized exponentiation algorithm, or/and making square fully indistinguishable from multiply from a hardware standpoint, including when measuring execution time between these operations).
However, blinding is useful as a countermeasure against some timing attacks, which operate differently. In essence, they correlate variations of execution time (for the same unknown $d$ ) with the particular value of $C$ being deciphered or the deciphered result. The original idea is in Paul C. Kocher's Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, in proceedings of Crypto 1996. With blinding, the attacker is deprived of direct information about what the exponentiation has as input or output, which both are masked with random secret $r$. Some implementations do not even care to make the computation of $r^e\bmod n$,  $C\cdot r^e\bmod n$, or $r^{-1}\bmod n$ constant-time, or/and make $r$ much smaller than $C$.
Even when exponentiation is inherently constant-time (as many carefully written or/and hardware implementations are), blinding can also be useful against other side-channel attacks, in particular, those targeting variations in power consumption / electromagnetic emission according to known $C$ .

Details per comment
One of the reason that the execution time of the computation of $C^d\bmod n$ depends on $C$ can be that modular reduction modulo $n$ sometime needs to fix a bad estimation of quotient. For example, the HAC's algorithm 14.28 for classical modular multiplication uses algorithm 14.20 for multiple-precision division, which step 3.4 reads

if $x<0$ then set $x\gets x+y\,b^{i−t−1}$ and $q_{i−t−1}\gets q_{i−t−1}-1$

with the condition $x<0$ rare (enough that it won't occur for most parameters to algorithm 14.28, but still frequent enough to be observable for random inputs), and the conditional computation lasting a significant time ($x$ and $y$ are vectors of machine words).
In the following, we'll assume that modular multiplication takes sizably varying time according to parameters; that the time it takes is predictable as a function of the two inputs to be multiplied; that the adversary measures the execution time of the computation of $C^d\bmod n$ for many values of random $C$ (no power analysis involved); and that this computation is per left-to-right binary exponentiation, as:

$S\gets C$
for each bit of $d$ from high order to low, except the highest one

$S\gets S^2\bmod n$
if the current bit of $d$ is set

$S\gets C\cdot S\bmod n$

The attack tests if overall execution time conclusively correlates positively with the (computable!) execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^2\bmod n$. That computation occurs if the bottom step of the algorithm is executed on the first iteration of the for a loop. If such correlation is found, the attack concludes that the second-highest order bit of $d$ is set; otherwise, clear. While there are other sources of timing variation than those in the particular $S\gets C\cdot S\bmod n$ targeted, and they are cumulatively much larger, correlation of enough measurements cancels out these other sources because they occur practically independently of the tiny variation targeted.
The attack can then proceed and test if overall execution time conclusively correlates positively with the execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^4\bmod n$ (if the previous detection found the bit clear), or $C^6\bmod n$ (otherwise). This will reveal the third-highest order bit of $d$.
All bits of $d$ can be found this way (though only some fraction is enough to mount a factorization). The attack can be improved, in particular, leverage timing variations in the next $S\gets S^2\bmod n$ step; guess several bits of $d$ simultaneously to get an even stronger correlation, and recover from an accidental wrong decision (no later correlation is observed). There's a trade-off between the number of available measurements, and the post-processing cleverness/effort necessary to find $d$.
Reference for essentially that attack: Jean-François Dhem, François Koeune, Philippe-Alexandre Leroux, Patrick Mestré, Jean-Jacques Quisquater and Jean-Louis Willems; A Practical Implementation of the Timing Attack, in proceedings of CARDIS 1998.
Blinding prevents this archetypal class of timing attacks very well. It is also effective against some power-analysis variants, which test if power traces varying according to $C$ best correlate with this or that hypothesis on early-tested bits of $d$.

[Note following other comment: the attack does not directly target the timing variation caused by the guessed bit of $d$ being set or not (it can't because that bit is fixed, thus there is no such variation). Rather, the attack targets the timing variation caused by $C$. The attack determines if the overall computation time is correlated with variations that would occur, or not, depending on if the guessed bit of $d$ is set or not.]


Can poly1305 be used as an error-correction code?

what is the minimum amount of bitflips on the message that can be corrected

Zero bits, Poly1305 doesn't provide error correction (at least Bernstein doesn't claim that property in the original paper).

  (or at least detected) by someone who knows the corrupt message, the mac code, and the key?

One bitflip is already detectable, it will change all bits of the resulting hash with a 0.5 chance.

Of course, there is always a negligible chance that the data does result in the correct hash (a chance of 1 in $2^{128}$ for the full MAC output). However, that's not dependent on how many bits are flipped.

Generally, it is recommended to keep the full output of the MAC calculation as an authentication tag.

If you also want error correction against changes, you could include a block of error-correcting code over the message + authentication tag. That way both are protected against non-malicious changes. Or you could use a specialized MAC algorithm as indicated within your own comment.

Personally I don't see a direct way to add error correction capabilities to the Poly1305 calculations, but I'm not the best person to indicate if that's possible.


Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction.
That is, $y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where $h$ is a universal hash function.

At TCC 2012, Jain, Pietrzak, and Tentes gave another technique to reduce the number of calls with preserving hardness by using t-wise independent hash functions. See their paper for details.

Leonid A. Levin. One-way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. Levin87

Abhishek Jain, Krzysztof Pietrzak, Aris Tentes: Hardness Preserving Constructions of Pseudorandom Functions. TCC 2012: 369-382. JPT12


If key revocation is a requirement, that is, if Alice no longer works for BigCorp, her keys no longer is able to decrypt email to BigCorp, then it either becomes impractical or easy.

That is, you will need to do one of two things:

Either you need to update the master public key when Alice leaves.  This is likely to be impractical.
You require Alice to work with some central body to do the decryption; the central body would verify Alice's employment as a part of the decryption process.

In the latter case, where we can assume a trusted central body, it becomes easy; have the central body hold the private key; it would either decrypt the message for Alice, or alternatively (for example, with RSA or IES), the central body could do a blinded decryption (and so the entity won't be able to track the message)


Yes, it's invertible. Consider:

$(E \oplus A \oplus B) \oplus (B \oplus C \oplus D) \oplus (C \oplus D \oplus E)$

to get the value of $A$. The values of $B, C, D$ and $E$ can be calculated in a similar manner.


Since the output of the configuration of Skein is 1024 bits, we would expect to get 512 bits correct just by random hashing. So the question is, what is the probability of getting 640 bits correct? From that we can figure out how long it would take for that to occur.

There are ${1024 \choose 640}\approx 4.16\cdot 10^{292}\approx 2^{972}$ ways this can happen out of $2^{1024}$ different outputs. If we assume the probability of each output is $1/2^{1024}$, then the probability of getting one of those outputs with 640 correct bits is approximately $2^{972}/2^{1024}=1/2^{52}$. So, perform $2^{51}$ hash function calls and you have a $.5$ probability of getting one of those outputs. That sort of work factor should be do able with lots of hardware (supercomputer, GPUs, etc) in 24 hours. As Paulo said, the problem is embarrassingly parallelizable.


Is there a counter mode of encryption where the key is being changed for every block of data?

There are some ciphers which do this, most notably E0, a 128-bit stream cipher based on four LFSRs that is used in older versions of the Bluetooth protocol. As vulnerabilities have been found in E0, a scheme was devised to reduce the security impact called two-level E0. Normally, the cipher encrypts 2745 bits (one Bluetooth frame) at a time. With two-level E0, every 128 bits of the keystream is used to seed another instance of E0 which generate only 2745 bits of keystream from that key.

Note that this is not a special mode of encryption, but the use of true stream ciphers. This difference is minor, as counter mode is merely a way to convert a block cipher into a stream cipher. Most block ciphers (and many stream ciphers) have a key schedule, which is an expensive setup phase whenever a new key is used, making it impractical to frequently switch keys. The stream cipher E0 does not have a complicated key schedule. The 128-bit key is used directly as the cipher's inner state (specifically, it is split up into 25, 31, 33, and 39 bits, each of which is used as the initial state for each of the cipher's four LFSRs). This allows it to change keys frequently without a significant performance impact.

Please note that E0, even two-level E0, is not a particularly secure cipher. The key must be changed very regularly or known-plaintext attacks can allow for key recovery. These weaknesses stem from both problems in the design of two-level E0, as well as the fact that E0 is built off of LFSRs, which are non-cryptographic algorithms. Using AES in CTR mode will be far more secure than any type of E0.


How re-encryption can be done through RSA

Both RSA and elGamal have homomorphic property. So both can re-encrypt the cipher text

That doesn't follow.

Re-encryption means being able to take $E_{a}(m)$ and $F(a, b)$ (that is, a function of both private keys), and being able to generate $E_{b}(m)$ (that is, the encryption of the same message under a different private key), but (and this is the critical part) it not being able to recover $m$ from those two.  That is, $F(a, b)$ is a key that allows you to "switch keys", but is not sufficient (without the private keys $a$ or $b$) to allow you to decrypt.

What the homomorphic property of RSA is allow you to take $E_{a}(m)$ (and the public key), and allow you to generate $E_{a}(G(m))$ (for certain functions $G$).

That doesn't allow you to switch RSA keys (which would imply changing modulii), and there is no obvious way to do so...


In Shamir's secret-sharing scheme, the secret and the shares of the secret all are elements of a finite field, and so necessarily have the same size. In the Reed-Solomon code based variant of Shamir's secret-sharing scheme proposed by the late Bob McEliece and myself (R.J. McEliece and D.V. Sarwate, "On sharing secrets and Reed-Solomon codes", Communications of the ACM, v. 24, Issue 9, Sep 1981), the $n$ shares are $\frac 1k$-th the size of the secret, but these schemes don't have the perfect information-theoretic security of Shamir's scheme. See this answer.


There are two cases to distinguish: The attacker issues the revokation or the owner issues the revokation.

Attacker revoking the cert. In this case the attacker has the private key and uses this to issue a revokation. He thus effectively takes any use out he could get out of theh certificate and the certificate is revoked as it should be in such a situation."Thank you attacker, you just did my job  without me having noticed the breach!"
Owner revoking the cert. The owner wants to prevent missuse of the cert and thus revokes it. This stops the attacker. Everything as it's supposed to be.


How to prove that finding a cycle in a cryptographic hash function is hard?

In a uniform random function on a space of $n$ elements, the distribution on the length $s$ of a chain starting at any $x$ before it repeats, i.e. the smallest $s$ such that $h^s(x) = h^{s - q}(x)$ for some $q < s$ or equivalently the number of distinct elements in $\{x, h(x), h(h(x)), \dots, h^{n - 1}(x)\}$, is $$p(s) = \frac{(n - 1)! \, s}{(n - s)! \, n^s},$$ whose expectation grows with $\frac 1 2 \sqrt{2 \pi n}$ (Harris 1960, Eqs. 3.2, 3.4, 3.11; paywall-free).*
Standard collision search algorithms work by following such a chain with a tortoise–hare algorithm to find the point where a non-cyclic initial chain coincides with a cycle.  But your black box somehow finds just the cycle without any initial chain.  Although the distribution of cycle sizes is weighted more toward smaller than larger cycles with expectation $\frac 1 4 \sqrt{2\pi n}$ (Harris, Eq. 3.11), the number $q$ of elements that are themselves on cycles has the same distribution as $s$ (Harris, Eq. 3.12).
For, e.g., a 256-bit hash function as you need for the standard 128-bit collision resistance, the expected probability of stumbling upon an element on a cycle by chance is about $2^{-128}$.  Even for a 128-bit hash function like MD5, although the expected probability of stumbling upon an element on a cycle by chance is about $2^{-64}$, the expected cost of confirming that it is on a cycle is $2^{64}$ steps, for a generic algorithm, although maybe there's a clever way to speed this up in batch or in parallel like the van Oorschot–Wiener collision search machine.
If, for some particular $b$-bit hash function aimed at random oracle applications like SHA3-256, you found a way to find an element on a cycle with substantially higher probability than $2^{-b/2}$, or a way to confirm whether an element is on a cycle or not with substantially lower cost than $2^{b/2}$, it would likely be worthy of publication and cast serious doubt on the security of the hash function.

My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial time, such that applying $h()$, $r$ times gives $x$:
$$ h(h(h\ldots(h(x))) = x $$
Can this be used to prove the function is not collision resistant or pre-image resistant?

It is not a priori clear that this black box is helpful for finding collisions or preimages: clearly it does not itself find a collision, and it's not parametrized by an image for which it could find a preimage.
Of course, the field of generic collision search is a black art underlying a surprising array of cryptanalytic attacks including the usual hash function collision search, Pollard's $\rho$ for factorization, Pollard's $\rho$ for discrete logarithms, hash function preimage search including AES key recovery, and so on.
So it would not surprise me if a black box with this capability could be fruitfully used to accelerate a generic collision search, or if it could be proved not helpful, but it would be an interesting theorem either way!

* Harris 1960 is an excellent compendium of probability distributions for various quantities in various important types of random mappings.  Read it!


Concerns about using a hash to determine if specific input data has already been encrypted

Instead of using a hash function, use a pseudo-random function (PRF). Unlike hash functions, which are publicly computable, PRFs use a secret key. HMAC-SHA256 is a widely supported PRF (although usually it's used as a MAC, which is a bit different). Use a different key for the PRF then you use for encryption.

Another possibility is to use a deterministic encryption scheme, such as SIV. These ensure that the only information leaked (asside from plaintext lengths) is plaintext equality: the same plaintext results in the same ciphertext each time, but close-related plaintexts don't result in similar ciphertexts. Unless you're crunched for space in the database, though, there's no real advantage to this approach for your purposes, and implementations may not be as widely available.

To address some of your other questions:

A salt would prevent the use of pre-built rainbow tables, but, depending on the length of account numbers, this may not be sufficient.

Suppose you use 10,000 rounds of a SHA256. If there are 8 digits of an account number that an attacker cannot guess beforehand, bruteforcing all the account numbers requires 10^8 * 10,000 = 10^12 SHA256 calculations. A modern GPU can do 10^9 SHA256 calculations a second. This would result in all the account numbers in your database being broken in 10^3 seconds, which is under 17 minutes.

You might be able to play with the numbers a bit to make things more reasonable, but my advice would be to go with the PRF. Then you don't have to worry about this sort of thing.

I'm assuming that anyone who could steal the PRF key could also steal the encryption key, and therefore am not worrying about this possibility. But you could certainly combine the PRF with a large number of hash rounds to provide some measure of defense-in-depth. If you opt to go this route, consider using bcrypt rather than, e.g., SHA256. Bcrypt is less easily bruteforced on a GPU. Some experts also recommend scrypt for this purpose, but scrypt is new enough that I would be hesitant to rely upon it.

Edit: There's another related (but distinct) disadvantage to using repeated hashing: An attacker who obtains the hashes can easily answer the question, "Does account #XYZ exist in this database?" Depending on what these account numbers and database are used for, this might be a real concern for your users. A PRF does not allow this attack, provided the key remains secret.


Verifying authentication by just using the root of a Merkle tree

If you need to verify all the data, you are going to have to recompute the entire tree, and compare your root with the root you were given. The power of the Merkle tree comes into effect when you only need to verify a subset of the data.


FHE - Brakerski's "Scale Invariant" Scheme

I think arguments could be made for either, but I would still call BGV the state of the art for FHE for the following reasons:

A public implementation exists
We have benchmark info
Other protocols have successfully applied it with real world use and analysis here and here (though presumably the scale-invariant system could replace BGV in this work)

All of this could change though. Someone could release an implementation of the cipher and benchmark the benefits. Recent papers are beginning to mention the scale-invariant system. The authors list a number of potential benefits of their system. And a recent blog post details the simplistic nature of the cipher.

There are reasons to believe that the scale-invariant system will not become state of the art though. This system uses rationals (fractional ciphertexts modulo 1) which is different and I'm not sure how that affects implementation. The blog post talks about this and mentions using reals, truncated and that this does not affect correctness. But what about performance?

One popular optimization to FHE ciphers is ciphertext packing (putting multiple plaintexts into a single ciphertext). This allows SIMD like computations on encrypted data. The authors of the paper you mention do not mention packing in $\S$4.2-Implications and Optimizations. Though it appears to be at least an option (see comment by Chris below). Multiplication in the scale-invariant cipher appears to be less efficient too.


Using the OTP and RSA compared to only using the OTP itself

It depends on what you would use the RSA algorithm for since a one-time pad (assuming you implement it correctly) should achieve perfect secrecy, which means its ciphertext cannot be cracked. RSA is one of the first public-key cryptosystems that can also be considered as secure when you are using large enough primes.

So to answer your question, it cannot be more secure than using OTP only since it simply provides the perfect secrecy. But OTP does have its limitations and that's why we have other encryption schemes and algorithms so that we can choose the most suitable one in different situations.


1) Is it correct to assume that in this scheme there is only one public key? Private keys are generated based on one's attributes that I do understand, by the authority.

No, each attribute is a public key. When you are encrypting a message, you form the access policy using the public keys of the various attributes needed from your policy.

  2) If above holds true and there is only one global public key based on a global secret then I assume there's no way for message originator to sign his message under this scheme. So that a recipient could verify that the message originator is really the one in possession of a given attribute (such as Id). I'm thinking of ways of implementing authentication under this scheme.

The above does not hold true, but I wanted to comment. Researchers have developed other primitives for attribute based signing. There has also been research published on attribute based signcryption, which combines the two.

  3) If one encrypts a message under specific access structure parameter values are these values in plaintext? I mean if one encrypts a message under attribute ID value '11' is everyone else able to see who the recipient actually is? I mean are they able to read the value '11'.

Under the original constructs, the access policy was public. So if you got a hold of a ciphertext and the policy, you could determine what attributes are necessary for decryption. Since then, researchers have developed methods to allow you to hide or keep private certain attributes in an access policy.


Total anonymity against malicious agents

Dining cryptographer networks are information theoretically secure to the anonymity set size. This is ultimately a traffic analysis question; however, it's very closely related to, and somewhat hard to delineate from, cryptography. In practice a DC-net is, in numerous ways, a lot like a one time pad. Primarily useful in theory and some niche cases. Anonymity is very much dependent on having a large anonymity set size, and DC-nets aren't very scalable.

Constant rate cover traffic is something else for you to read about.

Not just the semantics to be concerned about in this area. Malicious party will delay packets and create a watermark in interpacket arrival timings, then do end to end correlation analysis looking for that actively created pattern. This rapidly explodes into the massive complexity of mix theory. Pynchon gate is the state of the art in mix theory; it uses PIR for message retrieval from nymservers.

Traffic analysis still is largely successful even if all traffic is encrypted and impossible to decrypt. The goal is maintaining -- across all of myriad dimensions -- invariance from the anonymity set. Anonymity is at least typically severely degraded by any variation from the set, other than if there is variation in the form of randomization per hop (i.e. layers of encryption being removed at each hop still has variance of ciphertexts across the anonymity set, but the variance is made statistically independent from itself at each hop by the adding or removing of a layer of encryption).

Interpacket arrival timings are far from the only thing. Need the packets all padded to the same size, or else the packet sizing disparity across streams of packets creates a variance from the anonymity set that can be followed throughout the network.

Traffic analysis is extremely meta. It isn't about the communications, it's about the signals carrying them.

Check out freehaven.net bibliography.

Almost all experts say that Tor is the best bet for anonymity, and that this will not stop being the case any time soon. There is a big disconnection between theory and practice in this area. Plethora mix network designs, and things like DC-nets, are technically much stronger and -- arguably, perhaps anyway -- more sophisticated than Tor is. It's just they have such significant constraints on them, and oftentimes such poor scalability, that in the real world Tor blows them away even though it has major variance in terms of things like stream byte counts for example.


Generating S boxes that satisfy Coppersmith's criteria?

For each of the $2^6$ possible inputs, there are $2^4$ possible outputs. Thus, there are $(2^4)^{2^6} = 2^{256}$ possible S-Boxes mapping 6 bits to 4 bits: you cannot exhaust this many possibilities.

You need to construct S-Boxes which satisfies all the criteria directly, in contrast to looking at all S-Boxes and then testing for the criteria.

You may have a look at "affine equivalence" to divide the search space (see e.g. [1]) and at DESL [2], a variant of DES which uses a unique S-Box satisfying most of the Coppersmith criteria as well as other ones [2].

[1] On the Classification of 4 Bit S-Boxes, Arithmetic of Finite Fields (2007)
[2] New Lightweight DES Variants, Fast Software Encryption (2007)


ElGamal is a scheme, that can be applied to any kind of group structure. The only requirement is that DDH has to be hard (e.g. not $(\mathbb{Z}_p,+)$).

If you use the most common construction with multiplicative groups $(\mathbb{Z}_p^*,\cdot)$, then you need larger groups, due to attacks like index calculus.

If you use elliptic curves, you can use smaller groups instead, because algorithms like index calculus are not known.

Elliptic curves with pairings are not suitable to be used, because in that case the DDH problem is not hard. Therefore, you can not design protocols with efficiently computable pairings.

One property of ElGamal is, that it is (semi-)homomorphic w.r.t. the group operation. If you see that as an unwelcome property, you can also call that malleable. If you consider this property useful or a security risk, depends on your point of view and your actual goal.


Anonymous Multi-Receiver Identity-Based Authenticated Encryption with CCA Security?

As always there is only one system public key (also called "public parameters" or simply "parameters"). In IBE, the identifiers of users are publicly known which can be used in conjunction with the public key to compute temporary group elements.

If you look into the scheme you're linked to, you should see that there is only one set of "params" which represent the public key with all of its configurations.

Of course, the user identifier must be kept authentic in the same way that RSA public keys of all of the recipient users must be kept authentic. If an attacker makes you believe to encrypt some data to their own identifier, then you have lost, but that doesn't have anything to do with a scheme and more of an issue with fully designed systems.


For a given x there are only two possible y coordinates figuring that out is just a matter of solving the curve equation for y.

Afterwards  you just end up with a regular DLOG problem which is hard (if your x is for a point with large enough order order your curve order is prime).


That should be possible yes. It's probably ECB or CBC mode encryption. If it is CBC mode encryption then the first 8 bytes (16 hex characters) may be the IV. Otherwise it is likely to be a vector consisting of 8 zero bytes (or eight 00 hex characters of course).

I presume here that you can distinguish the result from random of course. If that's not the case you'll have to guess the encryption mode & IV used to encrypt.

If you can only decrypt the later part of the ciphertext then you are using an incorrect IV.

In the worst case you also have to try CFB or OFB or even CTR, but that's relatively unlikely.

Note that you first have to decode the hexadecimals to bytes. The key is probably already the same as the ASCII characters when viewed as bytes.


Key establishment from secret answer to a question using Socialist Millionaire Protocol

I have read this as telling that two parties sharing a low-entropy
  secret (such as a secret answer to a question) can use it to establish
  a high-entropy shared secret key across a classical insecure channel,
  with help of the Socialist Millionaire Protocol.

First, I think this isn't usually done, because SMP protocols tend to be not faster than key exchanges and because you can build an SMP protocol out of a password-authenticated key exchange (PAKE) by simply afterwards comparing whether the resulting keys are equal (eg by using them for a symmetric transport layer and sending a pre-agreed value both directions).

  Quantitatively, what's the probability for a MitM attack to succeed at
  least once in $n$ attempt?

I would suppose any such protocol enjoys similar security properties to your standard PAKE protocol, that is, if you break into one of the parties it's game over, but you don't learn anything about the password from the transcript and you can only test one guess for the password per connection attempt. So if the process of picking the password has entropy $E$, your chance of getting it right (per online connection attempt) should be $2^{-E}$.

  How is that achieved?

One protocol, I just came up with goes as follows:

Run un-authenticated Diffie-Hellman between the two parties $A$ and $B$ to get the shared secrets $m_A,m_B$. Note that if there is an active MitM attacker $m_A\neq m_B$.
Let $p$ be the password the two parties share. Formulate $\langle p,m_A\rangle$ and $\langle p,m_B\rangle$, e.g. as $\langle x,y\rangle=\operatorname{HMAC-SHA256}_y(x)$, i.e. pair them up somehow, so that the result of $\langle\cdot,\cdot\rangle$ may only be learned by somebody knowing both inputs.
Run a SMP protocol between $A$ and $B$ and have them compare $\langle p,m_B\rangle$ and $\langle p,m_A\rangle$ for equality. If the result is 1, output $m_A=m_B=m$ as the shared secret, if the result is $0$, output $\perp$, that is an error.

The idea is that attacks on DH result in both parties seeing different shared secrets which the SMP protocol should unveil while at the same time ensuring that if the parties actually arrive at the same DH secret, they also both know the same password and are thus authenticated by knowledge of the password.

Of course the above does not constitute a formal security analysis and thus this (inefficient) protocol should not be used without prior formal protocol analysis in production!


Encryption of plain text using stream cipher algorithm

The stream cipher generates 128 key stream bits per iteration. Usually these bits are buffered internally. When the encryption or decryption (identical operation, encryption = decryption) takes place then the bits are taken out of the buffer and the plaintext at the same location is xorred with it. When the keystream buffer is exhausted the next iteration takes place, making another 16 bytes of key stream available to the user.

Some implementations do wait for the full block to become available. This should however be the exception rather than the rule. The last (possibly incomplete) block just takes as many bits out of the buffer as necessary. The other bits are simply discarded.

Note that this is entirely the same scheme as used by e.g. AES in counter mode. One possible performance enhancement is to enlarge the buffer and generate more 128 bit blocks of key stream in one go. This may have benefits if the generation of larger amounts of keystream is less CPU or CPU-cache intensive.


Can reduced-round ChaCha be used as non-cryptographic fast PRNG to produce output indistinguishable from random data?

As cypherfox had correctly pointed out during our chat, two rounds is not enough to reliably diffuse a single changed bit throughout the entire output.
My question appears to have been answered directly by Bernstein's page on diffusion for Salsa20 (note that ChaCha has better diffusion).
Quoting https://cr.yp.to/snuffle/diffusion.html

The following pictures show how quickly changes in one byte of Salsa20 input spread through the entire Salsa20 array. Here's a typical Salsa20 input array, with a superposition of 256 possibilities for the first byte in the third row:

After one round:

After two rounds:

After three rounds:

After four rounds:

…

Additionally, the paper on Salsa20's security gives an example of diffusion:

Consider computing the second block of the Salsa20 stream cipher with nonce 0 and key (1,2,3,...,32). Rather than displaying the arrays produced by the second-block computation, this section displays the xor between those arrays and the corresponding first-block arrays, to emphasize the "active" bits—the bits where the computations differ.
The Salsa20 hash function starts with a 4×4 input array who's only difference from the first block is the different block counter, as shown by the following xor:
0x00000000,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
By the end of the first round, the difference has propagated to two other entries in the same column:
0x80040001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x0000e000,0x00000000,0x00000000,0x00000000
At this point there are still just a few active bits. The difference depends on a few carries but is still highly predictable.
The second round then propagates the difference across columns:
0xedc5e0a9,0x020000c0,0x381f830c,0x304888dc
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00006000,0x800c0001,0x00000000
0x0000e000,0x01c00000,0x040000d8,0x01200f00
By the end of the third round, every word has been affected:
0x39545d5e,0x0cc160d8,0x301fb030,0xa05208dc
0xa240cc8b,0x24e0120c,0x2a030dc7,0xabeeb94e
0x39ea409b,0x0000000f,0xcf3bb828,0x1c205f6d
0xc6612ba5,0x01c06a00,0x02000018,0x6745c36b
A substantial fraction of the bits are now active, although two words still have stretches of bits that were not (and were unlikely to be) active.
By the end of the fourth round, those last two stretches of inactivity have been eliminated:
0xf5eebb6a,0x79a3e194,0x52e3644f,0x28fc33dd
0xcbfe2c2e,0xa0ce9f57,0xfa23cf02,0x2f549d35
0x2b1af315,0x7af4976b,0xa100a15f,0x86f420f1
0x2900cc14,0x8dcbf124,0x90611242,0x61fdabbe
That's just 4 out of the 20 rounds in Salsa20. In every subsequent round, there are hundreds of active bits, for a total of more than 4000 active bits. Each of those 4000 active bits interacts with carries in a random-looking way, producing random-looking differences, not shown here.

Clearly, no less than 4 rounds can be used to safely achieve full diffusion. At this point, Salsa20/4 is no longer competitive with other fast PRNG alternatives. I'll additionally update my answer with the results from Dieharder tests later, when I have time. I will also test ChaCha.


Is it safe to encrypt a public key alongside a message with AES?

Probably not in this case, although not for the reason you gave.

As @Sadeq points out in the comments, AES is resistant to known-plaintext attacks. This means that by simply knowing M+P or P (the entire plaintext you've encrypted) it should not be possible to recover the AES key.

However, key recovery isn't the only attack and it raises a deeper question: authentication.

This design which sends the signer's public key along with the message seems to imply that the recipient doesn't already know what key the message should be signed by.

If the recipient doesn't know exactly what key the message should be signed by in advance, then he probably shouldn't just accept any random public key for the signature. Even when the AES key is negotiated perfectly securely, the CBC and CTR modes suggested by @sadeq can allow an active attacker to manipulate the decrypted plaintext in well-controlled ways. An attacker could possibly anticipate the signing key and replace it with his own, or selectively corrupt bits of it and observe the recipient's timing and behavior to identify the actual signing key.

It also raises the important question of how the AES key was negotiated securely. How do the sender and recipient know they're not talking to a man-in-the-middle? Maybe you've already addressed that somehow, I don't know.

Of course, there are systems which enable one to securely accept a new public key. For example, if it is signed by a trusted third-party like a certificate authority. But these systems are usually not optimized for anonymity and they raise additional complications for your goal. Address issues of key enrollment, revocation, expiration, etc. from the beginning.

As usual, the strong authentication problem is the harder one here. Solve the authentication and then come back and think about the encryption. It will be much easier to identify and prevent the active attacks that way.


How to decode Playfair when only a small part of key is available?

Playfair key grids are often generated by filling in the letters of a key phrase, then completing the grid with the remaining unused letters of the alphabet.
It looks to me like the partial grid you provided has been created in this way. If so, you can fill in several more letters straight away (assuming there is no J):
? A ? D ?             ? A ? D ?
? ? ? B C             ? ? ? B C
G ? ? K L     -->     G H I K L
N Q ? ? ?             N Q ? ? ?
V ? ? ? Z             V W X Y Z

Furthermore, the three cells between Q and V are most likely to be RST, RSU, RTU, or STU. For each of those four possibilities, there are now only six cells remaining to be filled. With a computer, it wouldn't take long to test every possible combination (4×6! = 2880). You could probably even solve this with pen and paper by attempting a partial decryption with the parts of the key you already have, then working back from the plaintext to figure out the others.
I think it's safe to assume that TXT2 is the Playfair encrypted message. It has an even number of characters, no digits or punctuation, and no letter J. Also, when split into pairs, there is no pair in which the same character appears twice (something that cannot happen in Playfair encryption).


The current status as of the time I write this is: There are no known attacks on second pre-images for truncated SHA-256 that are faster than brute force.


Type of values that can be accumulated in bilinear map (multiplicative) accumulator reg

If the group order $P$ is prime, then you can accumulate any integer in $[0,P)$.


Why is a HMAC using a 32bit tag not prone to birthday attacks?

"Birthday attacks" relate to the mathematical phenomenon colloquially known as the birthday problem, which states that if you generate random value in a space of size $N$, you expect to hit your first collision, i.e. generating a value that you already generated previously, after having produced about $\sqrt{N}$ values. This can lead to actual attacks in some contexts. It so happens that the normal usage context of HMAC is not one of these contexts.

HMAC is about checked integrity: it is a keyed function that is computed over a given message. In the most generic model, the attacker is allowed to submit $n$ messages $m_i$ of his own choice, and obtain the corresponding HMAC value $h_i$; and his goal is to achieve a forgery, i.e. a new message $m$ distinct from all submitted $m_i$, and the corresponding HMAC value $h$.

HMAC being what it is, it operates as a random oracle: from the point of view of the attacker, every time he submits a new message $m_i$, the obtained HMAC value $h_i$ is indistinguishable from a newly generated random value. Thus, when considering an as yet unsubmitted message $m$, the attacker's chances at predicting the HMAC value are essentially $1/2^r$, where $r$ is the length (in bits) of the HMAC output. In your case, $r = 32$, so anytime the attacker tries to predict the HMAC output for a message, then either he already submitted that exact message, and thus he can predict with probability $1$, or he did not submit that exact message previously, so his prediction will be true with probability $2^{-32}$ only.

The birthday problem, here, says that once the attacker has observed (or submitted) more than about $2^{16}$ messages, he can expect collisions, i.e. two distinct messages that map to the same HMAC value. But this does not change anything for the attacker, in that he still has no clue about what will be the next HMAC value for any given (new) message.

In fact, one can say that the birthday problem really incarnates how much collisions do not help the attacker. If you imagine a MAC system that takes care never to produce the same MAC value as previously (e.g. by remembering all produced MAC values in a database), then, message after message, the space of remaining possible MAC values get thinner. Ultimately, with such a system, once $2^{32}-1$ message+MAC have been obtained, the attacker could predict the next MAC value with probability $1$, since that would be the only MAC value not produced yet. But HMAC is not such a system, and will produce collisions just like it was a random source, thereby not incurring this "thinning space" effect.


Such a block cipher would be completely unusable in any of the standard modes of operation, presuming you want at least IND-CPA security. Say, for instance, that you are using it in CTR mode. A chosen plain text adversary looking at a cipher text consisting of only two blocks (i.e. 2 times 32 bits), would have a non-negligible probability (higher than $2^{-32}$) of guessing if the cipher text is produced by your block cipher in CTR mode, or a random function.

This matters in so far that a block cipher in CTR mode is only secure up to the bound where the block cipher might still be modeled as a PRF, as defined in the security proof. If you are able to distinguish the block cipher from a PRF, CTR mode is no longer IND-CPA secure. This applies to all other standard modes as well.

If one of the CTR mode cipher texts is 16 GB, you will have revealed the entire code book, and the adversary will not need the key.

If you have a hard time seeing this, consider a 2-bit block cipher in CTR mode that has produced the ciphertext stream 3-1-0. If Eve has tricked us into encrypting 0 three times, then the next CTR value must be 2 with probability 100%. Real plaintexts are nearly that predictable, so exhaustion of the ciphertext space is a practical limit. 32 bits is just too tight.

Edit:
Please also note that it would be a mistake to assume that failure to meet IND-CPA security, would only be relevant in scenarios where the exact CPA game can be played out. Suppose, for instance, that you encrypt only a single message (in CTR mode) with each key, and that this message is $l$ bits long. If $l \le 32$ you are safe, but if it is longer, you are not. Suppose $l=64$. In such case the plain text $m$ might be divided into two blocks $m=m_0|m_1$ and the cipher text $c$ into two blocks $c=c_0|c_1$. Now, the attacker might immediately deduce that $m_1\ne m_0\oplus c_0 \oplus c_1$ (because $m_i \oplus c_i = E_k(i)$ and $E_k(0) \ne E_k(1)$) and has learned $32/{2^{32}}=2^{-27}$ bits of information about $m$. The more that is known of patterns in $m$ and the greater the length $l$, the more information about $m$ might be deduced even in a cipher text only attack.


Can a compressed checksum be considered unique

TL;DR: The zlib output is at least as unique as the SHA-256 output.

Compression libraries like zlib have to encode the data in such a way that it is recoverably, which implies that they can not reduce the uncertainity (entropy) of the data.

Because of this logic, the entropy of the encoded hash has to be the same as the one of the hash. Now as hashes tend to have near-perfect entropy, this means that the the encoded data has the at least same entropy and thus must be at least as unique as the hash itself. Additionally, the compression may work non-deterministically when encoding data and thus even add entropy resulting in multiple unique encodings of the same hash (thus "increasing" the uniqueness).


Simply put, what does “perfect secrecy” mean?

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is plaintext to encrypt. In terms of probabilities, it means that the probability distribution of the possible plaintexts is independent of the ciphertext.
We contrast this with semantic security, which I define by quoting the seminal 1984 paper of Goldwasser&Micali:

Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext.

For two examples, I quote my answer to this related question:

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (eg by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.
To illustrate this, consider what happens if one tries to brute force OTP? Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the appropriate plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to ever possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0,1,2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.
Most cryptographic methods we use now are computationally secure. There are lots of different ways to do this, and I'll just sketch at a few of them. We might come up with a reduction to a problem conjectured to be hard (eg the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve [hard-problem]", meaning our problem is at least a difficult to solve as [hard-problem]. So, if the problem is indeed hard to solve, so must cracking our encryption be.


Other than brute force, are there any attacks on Threefish-512 using only a single known plaintext block?

According to Schneier,
there is an attack on 42 rounds of ThreeFish-512, but if you check out the analysis, it relies on multiple plaintext values.

Wikipedia lists no singular known plaintext attack, only a boomerang attack, which also depends on multiple known plaintexts.

So given these sources, it would seem there is not a well known and effective attack on three fish 512 with only one plaintext block.

Generally speaking, given only an encryption of a single plaintext block it would be difficult to use cryptanalysis to break a cipher. Even block cipher modes of operation which are deprecated, such as ECB, will operate securely for single block-key encryptions.

The Known-Plaintext-Attack seems to utilize single blocks of plaintext in some situations. That wiki site lists its usage on a cipher used during WWII, so technically Yes, there do exist ciphers which have been susceptible to a single known plaintext block at some points in history. But for modern ciphers, No, it does not seem to be an effective means of attack


The cost of finding collision for SHA-1 is currently estimated as $2^{61}$ SHA-1 calls. To understand how much  (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or $2^{61}$ hashes in three seconds.


What is the difference between TRNG and CSPRNG?

A True Random Number Generator uses a physical phenomenon not known to be fully deterministic as origin of the discrete values (bits or integer numbers) that it outputs. That phenomenon can for example be a dice throw, thermal noise, disintegration of a radioactive substance… What detects this phenomenon can be followed by a conditioning stage to turn the output into an (at least, near) ideal sequence of random bits. The conditioning is often an integral part of the TRNG.

The archetypal conditioning stage is the Von Neumann debiaser: it groups the values at its input (such as dice values, binary output of a clocked comparator, count of clock cycles between events…) into pairs, and outputs 0, nothing, or 1, depending on if the first element in the pair is less, equal or more than the second. If the input was consisting of independent values, the output (if any) would be independent random bits with 50% probability for 0 and for 1; that is, truly uniform independent random bits (hereafter: ideal randomness).

Unless otherwise stated, a TRNG can be imperfect to some degree: it is to be expected that a statistical test distinguishes its output from ideal randomness.

A Cryptographically Secure Pseudo Random Number Generator is a deterministic (hence the pseudo) computational method to turn an input (typically short or low-throughput, and explicit unless otherwise stated) into a (typically arbitrarily long or/and high-throughput) sequence of bits that are indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary not knowing the input, assumed secret and not reused.

In a cryptographic context, a CSPRNG can be abbreviated PRNG or PRG. But in other contexts, not all PRNGs are cryptographically secure. The Mersenne Twister is an example of PRNG that is not cryptographically secure.

A Cryptographically Secure Random Number Generator (not Pseudo) is a random generator with no explicit input, and which output is indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary assumed able to attack multiple instances of the CSRNG and obtain multiple output sequences (the adversary can use one CSRNG to attack another; restart the CSRNG, in some attack model s/he can attempt to exploit side channels, inject faults in the calculations made, or/and shutdown power at any time).

The archetypal deterministic CSRNG is built from a CSPRNG and a random secret seed that is not reused (perhaps, with help of permanent memory surviving a power cycle). That is essentially the only way to build a CSRNG without some form of TRNG.

The archetypal non-deterministic CSRNG is built from a CSPRNG, and a TRNG which output is used as input of the CSPRNG at start of each sequence (including power-up). The idea is that the cryptographic strength of the CSRNG comes mainly from the CSPRNG, and the unpredictability across multiple sequences and instances comes from the TRNG.

Note: there are more complex constructions, where the TRNG's output influences the CSRNG continuously, so that hopefully, security will eventually be recovered  after a compromise of the CSPRNG state. A Unix /dev/urandom typically uses this strategy.

A TRNG can be a CSRNG. Any CSRNG must include a TRNG, or must have made use of one as the origin of some secret value at an initialization stage (otherwise, knowledge of the CSRNG structure would allow to predict its output).

It is notoriously difficult to make a good non-deterministic CSRNG even by applying the above principle and using a good CSPRNG. One reason is that in practice, TRNGs often fail, spontaneously or under adversarial influence (for example, an adversary can reduce thermal noise by putting the device in cold condition using evaporation of some liquefied gas, or remotely feed controlled events to a sensor of disintegration). If that goes undetected, the output of the TRNG can become highly predictable, and knowledge of the PRNG will allow to predict its output. Thus a practical non-deterministic CSRNG must test its TRNG, and somewhat prevent any output when it does not operate properly.

On the other hand, a deterministic CSRNG must permanently keep its state secret. Due to the possibility of side channels attacks that's difficult when the adversary has physical access, and it turns out that methods to guard against side-channel attacks require random numbers in vast quantity! Also, there is understandable prevention against fully deterministic RNGs. This adds up to make fully deterministic CSRNGs a rarity in modern high-security cryptographic designs.

Summary of terminology:

A TRNG is not deterministic. Unless otherwise stated, that's its only defining characteristic.
A CSPRNG is deterministic, has an explicit input (unless otheriwse stated), and, with cryptographic certainty, its output is indistinguishable from ideal randomness by a computationally bounded adversary if its input is random, secret, and not reused.
A CSRNG has no explicit input, at least appears not deterministic, and its output is computationally indistinguishable from ideal randomness by a computationally bounded adversary. It can be deterministic, or not. In the former case, it's a CSPRNG with a random secret key that is not reused. In the later case, it includes (or perhaps is) a TRNG.
In a cryptographic context, PRNG or just PRG is synonymous with CSPRNG, and RNG might be synonymous with CSRNG (especially when using a RNG in another construct, rather than discussing its properties). But in non-cryptographic contexts, don't assume any security property from the acronym PRNG: in many programming languages, the default implementation is not cryptographically secure.

  If they (TRNG and CSPRNG) are both non-deterministic are they not the same? Are they not both producing unpredictable outputs?

A CSPRNG is deterministic, and never is a TRNG; and vice versa.

  Do we not use both TRNG and CSPRNG to produce sessions keys?

Often we use a CSPRNG initialized with a shared secret and some other element (like a nonce) to initialize session keys, so that the session keys needs not be transmitted secretly.

If we use the output of a CSRNG or TRNG as a session key, we need to encipher the value produced on one side to transfer it to the other side, which has no way to produce the same session key independently. Further, it we use a TRNG directly, we must use one that is close enough to a CSRNG that the key can't be guessed (that's an issue for short keys).

Another practice is to use a CSRNG or TRNG (often, one on each side) as input to an asymmetric key exchange protocol (like Diffie-Hellman) to produce a shared secret session key.

  Can we (do we?) use TRNG to produce CSPRNG?

No. But we often use a TRNG and a CSPRNG to produce a CSRNG.


The function $L_a(x)=\langle a,x\rangle=a_1 x_1+\cdots+a_n x_n$ is a linear multivariate function of $(x_1,\ldots,x_n)$.

The function $$f(x)+\langle a,x\rangle=f(x_1,\ldots,x_n)+a_1 x_1+\cdots+a_n x_n$$
equals $0$ mod 2 if $f(x)=\langle a,x\rangle$ and $1$ mod 2 otherwise.

The sum
$$
\hat{f}(a)=\sum_{(x_1,\ldots,x_n) \in \mathbb{F}_2^n} (-1)^{f(x)+\langle a,x\rangle},
$$
is equal to $2^n-2 d_H(f,L_a)$ and computes the correlation between the function $f$ and the linear function $L_a$. Here $d_H(f,L_a)$ is the Hamming distance between those two functions as $x$ varies over $\mathbb{F}_2^n.$ Each one of these $2^n$ correlations (for different $a$) can be obtained by a matrix multiplication.

Since the mapping is invertible, a $2^n\times 2^n$ Hadamard matrix appears as below: $$\left[(-1)^{\langle a,x \rangle}\right]$$
where $a$ indexes rows and $x$ indexes the columns in the standard order.

Due to the kronecker structure of the Hadamard matrix, a fast transform and inverse transform exist. The functions that have the maximum hadamard coefficient $\hat{f}(a)$ minimized are called bent functions and are important in coding theory and cryptography. By Parseval's relation, $$\sum_{a \in \mathbb{F}_2^n} |\hat{f}(a)|^2 =2^{2n},$$
and bent functions have $|\hat{f}(a)|=2^{n/2}.$ Note $f(0)=0$ means a function is balanced, bent functions are not.


Security proof of FO(Fujisaki-Okamoto) hybrid encryption

Intuition

The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext.
In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a valid ciphertext without querying to the random oracles is negligible.

How to answer a decryption query

Lemma 11 is the core of the proof. The knowledge (or plaintext) extractor without a secret key but with the tables of the random oracles successfully simulates the real decryption oracle with the secret key following the above intuition. In Appendix B, the knowledge extractor is described.

A ciphertext of the converted PKE is of the form $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)).$$
The knowledge extractor has the tables $T_G, T_H$ of the random oracles $G, H$.
The table $T_H$ contains $(\sigma_j,m_j,h_j)$, where $h_j$ is a returned value on the query $(\sigma_j,m_j)$. The table $T_G$ contains $(\sigma_i,g_i)$, where $g_i$ is a returned value   on the query $\sigma_i$.

the knowledge extractor, given a ciphertext $(C_1, C_2)$, picks up consistent pairs $(\sigma, m)$ from the tables $T_G$ and $T_H$, which satisfy the equation, $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)),$$
by re-encryption with $h$ and $g$ in the tables.
If discovered, the knowledge extractor returns $m$. Otherwise, it returns $\bot$.

You can find the proof in Appendix B of the paper.


Is collision resistant hash enough for one-block counter mode?

It depends what you mean by collision resistance.
If by collision resistance you mean that the output of $H(.)$ cannot be distinguished from a stream with full collision entropy (i.e. a $H_2=\ell$) then by Jensen's inequality we cannot distinguish from a stream with Shannon entropy at least this large and so the conditions for a one-time pad are met.
If by collision resistance you mean that hash function collision cannot be found without less work than $n$ hash function evaluations, then no. Let $n=2^{256}$, let $\ell=1024$ and define $H(x)$ to be SHA3(x)||SHA3(x). Collisions in $H(x)$ are in one-to-one correspondence with SHA3 collisions and so cannot be found with fewer that $2^{256}$ hash evaluations (with the proviso that SHA3 remains strong). Thus there is a 256-bits of collision resistance, but the encryption function is now horribly weak as the every other 512-bit block of key stream is a repeat of the previous.


How to hide multiple types of information in the same file?

One simple steganographic technique is to just use the comment structure of a mark-up language to embed plaintext messages. For example, the html code
<!-- ATTACK AT DAWN -->
<img src="lolcat.jpg">

inserted in a web page and opened in a browser will render as an image (presumably of an amusing cat), but if opened in a text editor the comment line can be read (and the cat picture can not be examined).
In particular the jpg format allows COM segments which are preceded by the bytes 0xFF 0xFE and a length field which then allow insertion of ASCII text.
Note that this is pretty trivial to detect and provides only steganographic protection (vice cryptographic).


How to achieve identity authentication without revealing credentials

The primitive you are looking at is called anonymous credentials. It deals exactly with your scenario, and there are dozen of papers on the subject. The introduction of this paper provides plenty of references to the literature on this subject.


Proving security of an encryption scheme

If you are working in an order $p$ prime order group which is generated by $g$, and $a$ as well as $r$ are drawn uniformly random from $\mathbb{Z}_p$, you can prove this secure under the decisional Diffie-Hellman (DDH) assumption (what you sketch here, is often referred to as modified ElGamal in the literature).

Informally speaking, under DDH you can show that $c_1$ looks like a random value. Now, once you have shown that $c_1$ looks random, you can view $g^r$ like a one-time pad on the message.

See Section 3 of this paper for an excellent formal treatment.


Does classifying an integer as a discrete log require it be part of a multiplicative group?

The discrete logarithm $\log_b a$ is an integer $x$ such that  $b^x = a$. Similarly to the logarithms, we need a base, here $b$.

If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.

Take a generator $g$ of a multiplicative group $G$ with order $n$, and then  take $g'=g^k$ where $\gcd(k,n) \neq 1$. Now the $g'$ will generate a subgroup $G'\leqslant G$, not the full group. Then any element of the full group $ a \in G$ and $a \not\in G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.

When we consider the non-zero elements of a field $F\backslash\{0\}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.


Demonstrating Diffie-Hellman key exchange using only p, A, B;

I guess the problem is to find the generator $g$.

Denote the factors for $p-1$ to be $p_1 =2, p_2 =2,p_3 = 37, p_4 = 709$.

With $p$, and the factorization of $\phi(p)$ you can find a generator in the following way:

Randomly choose an element $x$ from $Z_p$ and test whether $x^{\phi(p)/p_i}$ mod $p \ne 1$ for every $i =1,2,3,4$. If this is the case, $x$ is a generator. Otherwise, just select another element to run the test. You should find one soon. (Please refer to wikipedia for the method.)

Since $5^{2\times 37 \times 709}$ mod 104933 = 104932, $5^{2\times 2 \times 709}$ mod 104933 = 45751, $5^{2\times 2 \times 37}$ mod 104933 = 92770. Then 5 is a generator.

Next steps are basic algebra, I will stop here.


1-2 Oblivious Transfer - Can the recepient obtain both secrets by manipulating v?

Can I send Alice a v value that, by knowing the m'0,m'1 received, I can crack both m0 and m1?

One would hope not; if Bob can, this would show that the proposed protocol does not meet the security requirements of an OT protocol.
However, in this case, selecting such a $v$ value would appear to be difficult.  What Bob would need to do is find two values $y, y'$  that map to two values with an Alice specified difference, that is, $y^e - y'^e = x_1 - x_0$.
If Bob can do that, we can learn both values (by setting $v = y^e + x_0$.  Conversely, if he knows a value $v$ for which he can learn both secrets, he can compute such a $y, y'$ pair, hence this reformulation of the problem is tight.
However, the mapping $x \rightarrow x^e$ acts unpredictably (if you don't know the factorization); there is no known way to find such a pair for a random difference $x_1 - x_0$.


AES-128 as compression function in Merkle-Damgard construction

This short thesis describes some of the basic ways in which to use the Merkle-Damgård construction based on block ciphers. The construction that is commonly used in MD5 and related constructions is in fact an instance of the Davies-Meyer construction. This could be directly applied to your construction (you have to add length padding and a length field to get a secure hash function of course) as follows: let $E_k(m)$ be a block cipher (like AES) with key $k$ and message block $m$, then we take $f(W_i) = E_{m_i}(W_{i-1}) \oplus W_{i-1}$ for $i=1,\ldots n$. This way we get a secure hash function, provided $E$ is a secure block cipher in the appropriate sense (essentially indistinguishable from a random permutation).


identify if the functions are pseudorandom generator?

$G'$ is a PRG. Proof sketch: by assumption, $G(x)$ for a uniform $x$ is indistinguishable from a uniform string. This means that $y_1$ and $y_2$ (the halves of $G(x)$) are also indistinguishable from uniform strings, and finally that so are $G(y_1)$ and $G(y_2)$.


Is constructing IND-CCA2 public key encryption schemes particularly easy with the KEM/DEM approach?

If I understand the question correctly, you are asking whether it's really needed to have the KEM be CCA secure, and maybe in the random oracle model it would suffice for it to just be an invertible one-way function.

This would not be CCA2-secure. Specifically, let $f$ be any invertible one-way function, and construct $f'$ so that $f'(x)=0f(x)$ for every $x$. In addition, the inversion function works by ignoring the first bit of $y$ and then inverting the rest using $f^{-1}$. Note that $f'^{-1}(0y) = f^{-1}(1y)$ for every $y$. Thus, it is possible to change a single bit in the ciphertext, and the encrypted value remains untouched. Since the CCA2 experiment allows the adversary to query a decryption oracle on anything but the challenge ciphertext, this would allow it to obtain a decryption (by changing the appropriate bit of the ciphertext). I know that this is a stupid counterexample, but this is exactly the point of these counterexample: it demonstrates that additional properties are needed.

If we ask the same question for a trapdoor permutation then this seems more promising. The same KEM proof when using RSA (see Section 11.5.5) may go through in this case. I'm not guaranteeing it, since sometimes proofs fall on strange things, but it's my intuition. I suggest writing out a proof to make sure.


Selection of the noise application position in differential privacy

Noise addition is not the only thing that needs to be done to obtain differential privacy: you also need to bound the contribution from each user's gradient update, and calibrate the noise accordingly.
If a user can have an arbitrarily large influence on the ML model, because the gradient update from this user is unbounded, then you can't know how much noise needs to be added afterwards to hide this arbitrarily large contribution. So no, you can't add noise to the model after training is completed and obtain DP, or at least not in a straightforward way.
Alternative approaches to DP-SGD exist, like PATE, which kinds of corresponds to your idea of "adding noise after the training is completed", but that method involves multiple "teacher" ML models "voting" in a private way to train a "student" model, so it's more complicated than simply adding noise to the model.


Proof that the cardinality of the cipher text set is greater than or equal to the cardinality of the plaintext set for a symmetric cryptosystem

The start of the proof, concluding $e_k$ is injective for all $k$, is fine. Only the ultra picky would add that $d_k$ is the left inverse of $e_k$ by definition of a cipher, and that the rest of that part considers $x$ and $y$ elements of $P$.
By my taste, the rest using proof by contradiction is on the overly complex and circular side, and less than rigorous: the "Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$" is not crystal clear (at least it it does not follow from a stated definition or theorem).
I would change the whole second part to: The cardinality of the destination set of an injection is at least the cardinality of it's source set, by definition of cardinality.
Or, if cardinality is not yet formally defined in the academic context: The size of the destination set of an injection is at least the size of it's source set, by a counting argument. The notion of counting argument is often invoked in crypto, in the context of hash collision, or proof of existence.
If we do want to make a proof by contradiction, one could invoke the pigeonhole principle, also common in crypto, on the tune of: $\lvert C\rvert<\lvert P\rvert$ and $e_k$ injective would contradict the pigeonhole principle.


Most of this was already explained in the comments but let me summarize this.

a) SPHINCS+ as SPHINCS are stateless signature schemes like RSA or (EC)DSA. You can use the secret key to sign a virtually unlimited number of messages. In practice, you can sign up to $2^{64}$ messages with SPHINCS+ ($2^{50}$ for SPHINCS) without allowing any kind of forgery.

b) Your idea of a one-time signature is wrong. A one-time signature scheme is a signature scheme which allows the user to sign a single (arbitrary) message securely. The resulting signature is a standard signature as you know it from RSA that can be verified by everyone and as often as you want. The limitation of one-time signature schemes is just that you can only use your key pair to sign one message. As soon as you sign two different messages, security drops almost instantly to zero (depends a bit on the setting, but lets ignore this). So, a one-time signature is no interactive protocol. Just think of it as an RSA signature where you are only allowed to use your secret key once.

c) SPHINCS (with and without +) is no one-time signature scheme as a) already states. It internally uses a one-time and a few-time signature scheme. So, you can use it like RSA / (EC)DSA.

[Details]
If you would use a key pair more than $2^{64}$ times (which is almost impossible if you don't rent a massive server farm that does nothing else than signing messages with the same key pair for the next 20 years or so) security will slowly degrade as the probability of using a few-time signature key pair too often increases.
[/Details]

d) There are no specific caveats involved. As stated above, you can use it like any other signature scheme. (Actually, it follows the NIST call so you can see the requirements there...)

e) As there also seems to be some confusion about stateless vs stateful: The difference between stateless and stateful signature schemes is that stateful schemes require the secret key to change after every signature. So, we should rather talk about a secret key state than a static secret key. The crucial point is, a secret key state must not be used twice. This means, you have to make sure that you do not accidentally reuse it (e.g., back-ups are a problem in this case if you cannot recover the last used state somehow). Stateless schemes are actually the "standard setting", i.e., RSA, (EC)DSA are stateless. For hash-based signatures stateless schemes are not trivial to build. They avoid all this trouble with state handling at the cost of worse performance.


Security implications of storing an ssh passphrase

(..) encrypting an ssh key with a passphrase (..and..) storing the passphrase in the MacOS key chain or Gnome key-ring (..) encrypted using my login password (..)If I backup both my ssh key and my key-ring, have I reduced the complexity of cracking my ssh key from guessing my passphrase to guessing my password?

Yes for competent attackers (as posited in cryptography), and as long at the key-ring does not use dedicated hardware to limit the number of (consecutive) invalid login password presentations (like for the PIN of Smart Cards).

Further, if the login password is short and the passphrase long and good, "reduced" implies "lowered" for all reasonable parametrization of the key stretching for the password and passphrase (key stretching use purposely slow computations in order to slow down dictionary search, and is becoming increasingly critical to any competent use of password, except perhaps with dedicated hardware to limit the number of password presentations).

Rationale for yes: with the methods used by the key-ring and login assumed known, finding its password allows to recover the passphrase (or perhaps, with tight integration of the ssh key encryption with the key-ring, perform anything that knowledge of the passphrase allows; but this is both unusual, and ineffective in the situation).


Break El-Gamal Algorithm by knowing the value of the random k

Yes, this does break the security for that particular message.  If the attacker somehow recovers the value $k$, he can recover the message $m$ by computing $m = C_1 \cdot A^{-k} \pmod{p}$ (where $A^{-k}$ is the multiplicative inverse of $A^k$; one way it can be computed is by $A^{-k} = A^{p-1-k}$)


Assuming

that in the question "with public key" describes encryption under the intended recipient's public key;
secrecy of the corresponding private keys;
that by some external mechanism public keys are securely bound to the legitimate parties;
the parties have some unstated convention to define which is Party 1, defining who transmits first and order in "concatenated"

then yes,

the "Shared key" is the same on both sides absent alteration by an active adversary
an adversary (even active) can't predict any characteristic of the "Shared key" that one of the legitimate party uses.

Notice undesirable characteristics:

There's no forward secrecy: from past communications passively eavesdropped, an adversary later learning the two private keys can find the "Shared key". Modern key exchange protocols are safe from this.
[Edit: The simple/standard/best method for forward secrecy is DH, with some independent authentication mechanism (e.g. using the PGP keys in signature mode). I know no way to turn generic encryption or/and signature into forward secure key exchange without some other asymmetric crypto primitive.]
The party that transmits second can weaken the "Shared key" to some degree; e.g. choose it's random so that the top 32 bits of "Shared key" are zero, or some function of the other bits. However, each additional bit of weakening doubles the effort.
The parties have no insurance that their "Shared key" is shared with anyone; the only assurance is that it could be shared only with the legitimate holder of the private key matching the public key alleged by the other party.


Are there order-insensitive, constant-space MAC constructions?

Yes.  Let p be a large prime that's also bigger than 2$^{\text{output_length_(innerMAC)}}\hspace{-0.03 in}$.

If innerMAC "Uses constant space independent of" message length, then

outerMAC$_p\hspace{-0.03 in}\big(\hspace{.16 in}$k$_{\hspace{.02 in}outer}$ || k$_{\hspace{.02 in}inner}\hspace{.08 in}$,$\hspace{.09 in}$multiset$\hspace{.15 in}\big)$
$=$
PP-MAC$\left(\hspace{-0.07 in}k_{\hspace{.02 in}outer},\left(\hspace{-0.08 in}\left(\displaystyle\sum_{\operatorname{string} \in \operatorname{multiset}} \operatorname{int}\hspace{.02 in}\hspace{-0.04 in}\left(\operatorname{innerMAC}\left(k_{\hspace{.02 in}inner},\hspace{-0.03 in}\operatorname{string}\right)\right)\hspace{-0.08 in}\right) \operatorname{mod} p\hspace{-0.08 in}\right)\right)$

will give such a privacy-preserving MAC.

If additionally PP-MAC is a PRF, then outerMAC$_p$ will also be a PRF.

Since [having a composite affects neither order-independence nor space-usage] and

[security is only computational anyway], it's enough for $p$ to be probably prime.  Rather than being hard-coded, such $p$ can be efficiently generated using an additional part of the key, falling back on any large-enough odd number if finding a probable prime takes too long.