Are there known algorithms to compute that? Note that I can't simply concatenate the keys

No, you can't just concatenate them, but there are simple modifications to simple concatenation which does make it safe.

The easiest may be to simply prepend the length of every key in the concatination.  That is, if we have:

key1, key2, ..., keyN

we form the string

len(key1) || key1 || len(key2) || key2 || ... || len(keyN) || keyN

Where len(X) is a simple encoding of the length; it might be just an n byte encoding of the length (if you know that no key will be longer than $256^n$ bytes long), or you could go fancier and (say) reuse the variable length encoding from DER.

That way, if you introduce any other sequence of keys, you'll generate a distinct string, and so don't run into collision problems.

This is well known, but not greatly discussed (probably because it is assumed to be fairly obvious/trivial).

The only other thing is that you'd need a MAC that takes a variable length key.  Most don't; however one that does is HMAC.  The other possibility is to just use a collision-resistant hash function on the string (and use the result as the real fixed-length MAC key).


How many NVidia 3090 would you need to brute force a 1024 key in one day?

Brute force means running $2^{1024}$ operations. NVidia 3090 has $10496 \approx 2^{14}$ cores, each running at 1.70GHz which is approximately $2^{30}$ operations per second. Making the ridiculous assumption that a single clock cycle suffices for verifying a key, this comes to $2^{44}$ operations per second.
Before going to $2^{1024}$, let's consider 128-bit keys for AES. This would take $2^{84}$ seconds which is about $6 \times 10^{17}$ years. So, if I take a server farm of 1 trillion (about $2^{40}$) NVidia 3090 devices, then it would take "only" $2^{44}$ seconds, which is about 550,000 years. Of course, it would be much longer since you can't verify a single AES key guess in 1 clock cycle.
Let's now look at the entire power of the bitcoin network. This is estimated to run at about 150 million Terahash per second, which is about $2^{67}$ operations per second. That is absolutely huge! However, it means that it would take $2^{61}$ seconds which is 70 billion years. Just to reiterate - it would take 70 billion years for the entire bitcoin network to brute force a 128-bit key. (Of course, that network is computing SHA256 hashes and not AES computations, but you get the idea.)
Forget about 1024-bit keys and brute forcing. 128 is already too high for that.


FEAL-4 Linear Cryptanalysis - Prevention

By convention:

LC = Linear Cryptanalysis
DC = Differential Cryptanalysis

There are multiple ways to increase the security of a block cipher.

The first one (and usually applied) is to increase the number of rounds. In the case of FEAL, they switched from 4 to 8 rounds and then to X rounds. Therefore you would have to extend the equations for 7+ rounds before starting your brute force attack (see table below from Handbook of applied Crypto, note that the time indicated is not correct anymore due to the book being written in 1996...)

+---------------+------------------------+----------------+-----------------+
|               |                        |                |                 |
|  Attack       |    Data complexity     |   storage      |  procesing      |
|  Method       |                        | complexity     |  complexity     |
|               | known   |  chosen      |                |                 |
+---------------------------------------------------------------------------+
|   FEAL-4-LC   |   5     |              |    30K bytes   |   6 minutes     |
|   FEAL-6-LC   |  100    |              |   100K bytes   |  40 minutes     |
|   FEAL-8-LC   |  2^24   |              |                |  10 minutes     |
|   FEAL-8-DC   |         | 2^7  pairs   |  280K bytes    |   2 minutes     |
|   FEAL-16-DC  |         | 2^29 pairs   |                | 2^30 operations |
|   FEAL-24-DC  |         | 2^45 pairs   |                | 2^46 operations |
|   FEAL-32-DC  |         | 2^66 pairs   |                | 2^67 operations |
+---------------+---------+--------------+----------------+-----------------+

In the case of Linear cryptanalysis, the linear equations/approximations used to break the cipher holds with a certain probability. You just have to make sure that this probability stays low.

It has been shown by Joan Daemen and Vincent Rijmen in The Design of Rijndael: AES, chapter 7 that LC and DC share similarities by the Walsh-Hadamard transform. Increasing the DC resistance of an algorithm also increases the LC resistance.

The idea is therefore to find a good S-box, you need to prove that the Differentials don't go over a certain probability (the lower the better). In the case of Rinjdael (AES), they use a $8$ bit S-box. Therefore the table of the differentials has $2^8 = 256$ rows and columns. By analyzing such table, they made sure that no differential probabilities goes over $\frac{4}{256}$.

The bigger the S-box, the harder the differentials will be to exploit. However, it is also required from the designer to prove the security of his algorithm. So increasing the size of the S-box also make the proof harder. This is the reason why the $\chi$ function of keccak is similar to a 5 bit s-box.

Smaller S-box implies higher probabilities right ? Therefore, we add a diffusion layer. The goal is to propagate the differences and make them harder to track. There you have two kind of strategies: weak alignment or strong alignment... But that is getting too far.

I would suggest to have a look at this presentation Two ways of building round functions for block ciphers by J. Daemen.


Yes, this is possible.

The Bresson-Catalano-Pointcheval scheme (link) is a sort of hybrid of the ElGamal and Paillier encryption schemes. The upper-level user knows the factorization of the modulus. The low-level user does not know the factorization of the modulus, but he does know the Diffie-Hellman contribution. The upper-level user can perform decryption using the prime factors of the modulus. The lower-level user can perform decryption using the secret Diffie-Hellman value. Two distinct lower-level users cannot decrypt each other's ciphertexts but the upper-level can decrypt everything.

Also, checkout BIP32 (link). This proposed scheme allows a user to generate a tree of secret keys and matching public keys. He can communicate the secret key of one particular branch to another user who will be able to decrypt all ciphertexts encrypted using public keys from that branch. However, this second user will not be able to decrypt ciphertexts from other branches. The original generator of the larger tree retains the ability to decrypt anything (as long as the message was encrypted using a public key from that tree).


Paillier subtraction for negative result

In Pailler encryption, it holds for all messages $m_1$ and $m_2$, and whatever randoms[*] are used by encryption, that:
$$\begin{align}
(m_1+m_2\bmod n)&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
(m_1-m_2\bmod n)&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
where the modular inverse $E(m_2)^{-1}$ is computed modulo $n^2$, that is in $\Bbb Z_{n^2}^*$.

If $0\le m_2\le m_1<n/2$ then we have
$$\begin{align}
m_1+m_2&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
m_1-m_2&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$

When the sign of $m_1-m_2$ is unknown, we can define a modified Pailler cryptosystem. Encryption is unchanged, or/and we can compute $E(m)$ as $E(m\bmod n)$ when $m$ is negative. Decryption is modified to $D'(c)=[D(c)]_n$ with
by definition $[x]_n=((x+\lfloor n/2\rfloor)\bmod n)-\lfloor n/2\rfloor$.

Whatever random[*] is used by encryption, if $-n/2<m<n/2$, then $D'(E(m))=m$; and for all messages $m_1$ and $m_2$:
$$\begin{align}
[m_1+m_2]_n&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
[m_1-m_2]_n&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
If $-n/4<m_1<n/4$ and $-n/4<m_2<n/4$ then we have
$$\begin{align}
m_1+m_2&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
m_1-m_2&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
I fail to find who first extended Paillier encryption to subtraction, or/and to signed values with that variant $[x]_n$ of the $x\bmod n$ operator; but this is simple and natural enough that my guess is it has been independently rediscovered several times. The notation $[x]_n$ is often used in homomorphic encryption, at least since Craig Gentry and Shai Halevi Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011).

[*] Restrict the random integer $r\in\big[0,n^2\big)$ used by encryption to be coprime with $n$; that's overwhelmingly likely if $n$ is hard to factor.


SRP needs more than a group, it requires a field. See the specification: second user sends $B = v + g^b$. This requires two operations, addition and multiplication. You cannot trivially slap that onto a group which provides only one operation, such as elliptic curves.

Variants of SRP which use elliptic curves have been proposed, but do not seem to have reached wide acceptance or even substantial scrutiny yet. See for instance this proposal. Also, this article gives some details (e.g. it claims to break a previous proposal for an EC-based SRP variant).


Signing dynamic data on an embedded system

Signature algorithms of the ECDSA family are amenable to precomputations. Indeed, when you want to sign message m with ECDSA, the process goes thus:

We work in a curve (or a subgroup of a curve) of order $n$ (a prime integer). A conventional generator $G$ is given (a fixed point of order $n$). Private key is $x$ (a non-zero integer modulo $n$) and public key is point $Q = xG$.
Generate (for each signature) a new random non-zero integer $k$ modulo $n$. The integer MUST be selected uniformly in the whole range (this is important).
Compute the point $kG$, extract its $X$ coordinate, and reduce it modulo $n$; this yields the first half of the signature, $r$.
Hash message $m$ and truncate/reduce the hash value into an integer modulo $n$ (let's call it $h$).
Compute the second half of the signature: $s = (h+xr)/k \pmod n$

The point here is that the most expensive part, which is the computation of $kG$, does not actually depend on the message that is to be signed. It can thus be done in advance, before the message $m$ is obtained. A precomputing setup would pre-generate a bunch of values $k$, with corresponding values $r$ and $1/k \pmod n$, thereby reducing the online part of the signature to a couple of modular multiplications and a modular addition. This, however, calls for the following comments:

The process above requires a random $k$, produced with a random generator of cryptographic quality. This is a tough thing to get in practice, especially on embedded systems. Since a failure to use good randomness may expose the private key itself (and such blunders have happened in practice), another mechanism for generating the $k$ value has been defined, called derandomization. In the case of ECDSA, this is described in RFC 6979. However, while this removes the need for a random source, it makes $k$ depend on the input message $m$. As such, it prevents precomputations.
ECDSA, as defined by the relevant standards, operate on "classic" curves, which are not necessarily the fastest curves around. You might want to investigate EdDSA, and especially Ed25519 (application of EdDSA to a specific 255-bit curve). This can be done, but may run into some extra issues:

EdDSA is specified as derandomized, so no precomputations. It so happens that the signature verifier cannot actually know whether the signer was derandomized or not, so you could "re-randomize" the algorithm, which is totally heretic from a cryptographic point of view, and thus possible but fraught with peril.
The actual signature computation uses a hash function invocation, which is defined to be SHA-512. SHA-512 is reasonably efficient... on big desktop and servers, where 64-bit registers are available. Your 8-bit AVR won't like it.

Precomputations can help you only if you have time to precompute. The typical use case for precomputations is paying a toll on a highway or bridge: the signing device on a car has very little time to compute the actual signature (transaction should be completed while the wireless device is in range of the detection apparatus, and that does not last because the car does not slow down), but minutes if not hours to prepare the next signature. In your case, you have a long and potentially unbounded stream of signatures to compute, so it is not obvious whether you have enough time to do all precomputations.

To give some figures, the current record for elliptic curve computations on 8-bit AVR processors is described in this paper; they compute a point multiplication in Curve25519 in about 14 millions of clock cycles. This is substantially higher than your budget (at 0.400 millions of cycles per signature).

Here are some ideas that may help (or not):

"Modern" curves such as Curve25519 are designed under the essential premiss that multiplications are fast. This is true for the CPU in desktop and server systems, and also smartphones. But not on 8-bit AVR. Therefore, they are not necessarily a good choice in your specific case.
I suppose that the value of your signatures is not that high. I mean, you worry about fakes, but a fake log will not yield billions of dollars to attackers. As such, you could probably tolerate a slightly lower level of security. A 160-bit or so curve will provide a security level of about $2^{80}$, which is beyond the current public records in curve breaking. This is technologically attainable, but at a tremendous expense (we are talking billions of dollars here), so it is unlikely to be done merely in order to make fake GPS log (I assume you are talking about drone racing or something similar).
Under these conditions, I would say that among known curves, the fastest one will probably K-163, described in FIPS 186-4. This curve has a special structure that allows faster computations, provided that you apply some weird maths (the Frobenius endomorphism). However, even with the full power of the Frobenius, I fear that it would still not fit the per-signature cost in 400k clock cycles.
The human user is human; he is not that fast. By that, I mean that while you cannot predict when the user will pull the switch, you can still instruct the said user that pulling the switch may lose, say, the last two seconds of GPS logs. Therefore, you could compute one signature every 2 seconds, on twenty lines of logs in one go, instead of doing ten signatures per second. I have just multiplied your CPU budget by 20! And now, ECDSA with K-163 may become a realistic solution.
You might want to consider plugging in a better CPU. In a GPS receiver, chances are that the radio part uses way more power than the CPU, so you could use a more beefy CPU. The ARM Cortex-M0+, clocked at 48 MHz, would draw at most a few milliwatts (including the power for some RAM), and can compute an Ed25519 signature in less than 200ms.

Another, completely different idea, would be to use Lamport's signature scheme. It uses only hash functions and can be very fast. Its main issue is that it is a one-time signature scheme: if you sign two distinct messages with the same private key, then you reveal the private key, and forgeries become easy. However, in your specific case, you could apply it in the following way:

Before a flight, the GPS system generates a new public/private key pair, and exports the public key.
During the flight, the system regularly computes a new signature over the entirety of the log file, and replaces the previous signature. Thus, it only keeps a single signature in its storage system. This uses the fact that the private key is revealed only through showing two signatures; signature values that are never shown are thus not a problem.
The private key is held in RAM only, so it disappears when the system shuts down.

To ease usage, you could envision an hybrid system:

The system has a "permanent" key pair, to use in ECDSA or Ed25519 or a similar system.
When it boots up, it generates a new Lamport public/private key pair.
The public key is signed with the ECDSA/Ed25519/whatever key; the Lamport public key and the signature are then stored along in the log file header.
The running Lamport signature is computed every second or so, as described above.
The Lamport private key disappears upon shutdown.

Combining all of the ideas above makes me think that what you are looking for is possible, but certainly not commonplace. You are in for a big delve in arcane cryptography, and we know, out of experience, that such things are hard, in particular because there is no test for security (you can test for functionality, but you cannot easily know whether what you produced is secure).

So, a fun project, but don't build a business on it.


Can we use Bitcoin miner to break 2Key 3DES, if yes how long it takes?

First of all, 2DES is
$$\textrm{ciphertext} = E_{K_1}(D_{K_2}(E_{K_1}(\textrm{plaintext})))$$
The below from 19 September 2020 on the Bitcoin mining, Bitcoin mining is based on SHA256d calculations. All in all, ASICs, FPGAs, GPUs, and CPUs.
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in a hour} & \text{in a day} &  \text{in an Year} \\ \hline
\text{Bitcoin Miners on SHA-256D} & \approx 2^{67.9} & \approx 2^{84} & \approx 2^{84.3} & \approx 2^{92.8} \\ \hline
\end{array}
We can adjust the values if we can find 2DES implementation, however, the miners use various sources to mine, however, we can approximate with hashcat on Nvidia RTX 3080.
Hashmode: 14000 - DES (PT = $salt, key = $pass)
Speed.#1.........: 53585.1 MH/s
Hashmode: 1410 - sha256($pass.$salt)
Speed.#1.........:  6980.9 MH/s (81.18ms)

The DES is around 8 times faster ( not going into too many details of hash modes ) and 2 times for SHA256d that makes $2^4$-times faster. We call the DES 3 times so the speed is $2^4/3$. Make a little approximation it to $2^3$
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in a hour} & \text{in a day} &  \text{in an Year} \\ \hline
\text{Bitcoin Miner on 2DES adjusted} & \approx 2^{70.9} & \approx 2^{87} & \approx 2^{87.3} & \approx 2^{95.8} \\ \hline
\end{array}
So in a year, they can reach $\approx 2^{95.8}$  2DES calculations. Therefore they still need $112-86.8 = 20.2$ year that is $\approx 1048576$ years to execute brute force for a single target.
The above is a simple full brute force attack. In a more careful attack design (thanks to Poncho), the attackers can simplify some calculations
for key1 in KeySpace:
   c' = DESDec(k1,m)
   m' = DESEnc(k1,c)

   for key2 in KeySpace:
      assert m' = DECEnc(k2,c')

Now this totally calls $2^{56}( 2 + 2^{56}) = 2^{57} + 2^{112} $. The outer loop can also benefit from calling the key sechedule once. This can speed the brute-force attack 3 times.
One can go for better options. An interesting case is a multi-target attack. With a multi-target attack, you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{112}/t$. For a billion targets, the cost would be below $2^{84}$ and the time would be below $2^{54}$


Does this PBKDF2-SHA1 payload hint at a cryptographic security issue?

So lets take a look at this in hex:

626B3A C6AAF309F16C41A755679810A2732D9D 00000000000000000000000000000000 10270000 EBDB5836

This is bk: in ASCII, then 16 bytes of ciphertext, followed by an all zero IV, then a iteration count in hexadecimals : 10,000 (0x2710 in little endian), followed by what I presume is a 4 byte checksum or key check value.

So from a cryptographic standpoint this looks correct, unless an all zero IV is not acceptable.

Notes:

You cannot just start with character A when reading the IV. Byte boundaries for base 64 are within the characters for 3 out of 4 boundaries (or 5 if you count the one for the next byte). So you should always first convert the base 64 to hex.
Instead of 16 bytes of ciphertext I would expect 16 bytes of salt, used for the key derivation function. If those are random then it is alright to use an all zero IV, as the key would be different even if the same password is used; the random salt would make sure of that.


Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value?

Of course you can - but as to whether or not it's a practical or advisable idea, I don't think so.  It's not really prudent to implement crypto systems/protocols and assume that they'll be fine in 10 years.

Cryptography is a dynamic field that changes rapidly; algorithms get broken, hardware improves, governments try to undermine the field, and attacks only ever become more sophisticated.  The only way to ensure the security of your system is to stay abreast of what's happening in the crypto/security world, and to adjust your system/protocol accordingly.  For example, despite the recommendation of doubling PBKDF2 rounds periodically, many people in the community now recommend a memory-hard PBKDF like Scrypt instead, making PBKDF2 more or less redundant (although not quite, as it's used internally in Scrypt, and in systems where memory is not available).

Your proposal does have an upside though: a vast majority of security/crypto protocols get implemented and forgotten about.  Look at the linked-in fiasco for example - at the time of designing the system, the architect may have (however erroneously) thought that a saltless sha1 hash of the user's password would be sufficient security.  These days, the idea of a prominent website doing this is unthinkable (hopefully).  So in this sense, your proposal does at least attempt to stay up-to-date, which in lieu of a static system, is better than nothing.  However, I think that continuous scrutiny and a more "hands on" approach is preferable.


Will the non-colluding servers communicate in IT-PIR schemes ?

When the servers may collude then if they are all corrupted it's exactly the same as 1-server PIR. Thus, in information-theoretic PIR, it is always assumed that only some subset of the servers are corrupted.

It is unclear to me what you would gain by running MPC between the servers. One possibility is to simulate a single-server PIR with many servers. But this would just cost more.


Why using hash trees instead using a single hash value?

A Merkle tree is used for effective retrieving or sending data on the network that you can send/retrieve the data on any order and verify the current data with additional $O(\log n)$-data transmit and in $O(\log n)$-time. Actually, only the root hash is stored $O(1)$. While keeping the root hash any data retrieved/send verified.
\begin{array}{lcr}
 & \text{With Merkle Tree } &  \\ \hline
\text{receiver} & \text{data transmit } & \text{Databank} \\ \hline
\text{keeps the root hash} & & \text{keeps the files}\\
O(1)\text{-space} & & \\
& \xrightarrow{\text{request the ith file }} & \\
& \xleftarrow{\text{sends ith  file with the }O(\log n) \text{ siblings to the root hash}}\\
\text{Verification in} & & \\
O(\log n)\text{- time} & &
\end{array}
The above diagram that you are the owner of the data and outsourced it. If the client wants to upload the data, first they can transmit the root hash digitally signed to the server where the diagram continues.
If you use one hash, then to verify you need to send/receive all of the data and compute the hash all over it $O(n)$-data transmit and in $O(n)$-time. There are also parallel hashing like ParallelHash of the SHA3 or Blake3. This can decrease the hashing time of $h(x_1,x_2,..,x_n)$ if you have more than one core/thread. In theory, this is $O(\log n)$, however, in practice, it may not. Still, to verify, one needs to transfer all at once, i.e.  $O(n)$-data transmit.
\begin{array}{lcr}
 & \text{With Single Hash } &  \\ \hline
\text{receiver} & \text{data transmit } & \text{Databank} \\ \hline
\text{keep hash} & & \text{keeps the files}\\
O(1)\text{-space} & & \\
& \xrightarrow{\text{request the ith file }} & \\
& \xleftarrow{\text{sends all files } O( n) \text{-data transmit}}\\
\text{Verification in} & & \\
O(n)\text{- time} & &
\end{array}
Therefore the benefit is reduced hash time and reduced data transmission.


Double randomised HMAC verification to prevent timing attack

Will this successfully prevent a timing attack?

Strictly speaking you should be checking if openssl_random_pseudo_bytes happens to be returning cryptographically strong numbers or not. If not, an attacker could guess be able to launch a timing attack practically as easily as without the extra HMAC.

(Got to love PHP... Even the function name: random "pseudo bytes"...)

You should also, if possible, HMAC the raw output rather than the base64. The base64 encoding function might itself even allow timing attacks (probably not but who knows), so you would be better off using the raw values. It is also faster.

  Am I doing anything unnecessary? Could something be improved?

The $random_salt is actually a key, so you should call it and treat it as such. You could reuse it across function calls, if you are after performance.

There is no advantage to generating a random-length key. You should be using a key size that matches the overall security strength you are aiming for, but e.g. 256 bits would be plenty.

The security of this relies on the security of HMAC. As long as the key is secret, no one will be able to learn anything about the original hash even if the final comparison leaked the value. And if the key is long enough it cannot be brute forced. Randomness does not help beyond generating a secure key.


Using platform-level RNGs for key derivation with hash functions like BLAKE3?

Would it be safe to use an architecture-level instruction like RDRAND or RDSEED (x86) or RNDR (ARM) to generate this key material, and then derive a key that way?

Would you need to derive the same key twice (for example, you're using the key to encrypt data from Alice to Bob, so both Alice and Bob need to derive the key; or if you're using the encrypt stored data, so you need to derive the key both when you store the data and when you retrieve it)?
If so, then RDRAND won't give the same data twice, hence you won't derive the same key.
If not, that is, you are generating the key only once (and storing it if you need to refer to it later), then it should be safe.  On the other hand, there may be little reason to bother with a key derivation function at all; just invoke RDRAND, and use that as your key...


I think that you missed a pivotal point in the concept, which is the small blocks that are used to compose a secure PRF (or PRP), i.e. when you permute one bit, you actually change the value of the small block of that bit, i.e. the whole small-block is effected and thus prepared to be confused in the next round, this way you will reach a confusion of the entire big-block very fast.

I attach a good explanation of the concept as described in Lindell-Katz Book

  In addition to his work on perfect secrecy, Shannon also introduced a
  basic paradigm for constructing concise,random-looking permutations.
  The basic idea is to construct a random looking permutation $F$ with a
  large block length from many smaller random (or random-looking)
  permutations $\{f_i\}$ with small block length. Let us see how this
  works on the most basic level. Say we want $F$ to have a block length
  of $128$ bits. We can define $F$ as follows: the key $k$ for $F$ will
  specify $16$ permutations $f_1,\ldots, f_{16}$ that each have an $8$-bit
  ($1$-byte) block length. Given an input $x\in\{0, 1\}^{128}$, we parse
  it as $16$ bytes $x_1,\ldots,x_{16}$ and then set (equation 6.2)
  $F_k(x)=f_1(x)||\ldots||f_{16}(x_{16})$. These round functions
  $\{f_i\}$ are said to introduce confusion into $F$. It should be
  immediately clear, however, that F as defined above will not be
  pseudorandom. Specifically, if $x$ and $x'$ differ only in their first
  bit then $F_k(x)$ and $F_k(x')$ will differ only in their first byte
  (regardless of the key k). In contrast, if $F$ were a truly random
  permutation then changing the first bit of the input would be expected
  to affect all bytes of the output. For this reason, a diffusion step
  is introduced whereby the bits of the output are permuted, or “mixed,”
  using a mixing permutation. This has the effect of spreading a local
  change (e.g., a change in the first byte) throughout the entire block.
  The confusion/diffusion steps—together called a round —are repeated
  multiple times. This helps ensure that changing a single bit of the
  input will affect all the bits of the output.

  As an example, a two-round block cipher following this approach would
  operate as follows. First, confusion is introduced by computing the
  intermediate result $f_1(x_1)||\ldots||f_{16}(x_{16})$ as in Equation
  (6.2). The bits of the result are then “shuffled,” or re-ordered, to
  give $x'$. Then $f'_1(x'_1)||\ldots||f'_{16}(x'_{16})$ is computed
  (where $x'= x'_1,\ldots,x'_{16}$), using possibly different functions
  $f'_i$, and the bits of the result are permuted to give output $x''$.
  The $\{f_i\},\{f'_i\}$, and the mixing permutation(s) could be random
  and dependent on the key, as we have described above. In practice,
  however, they are specially designed and fixed, and the key is
  incorporated in a different way


Deniability properties of the X3DH Key Agreement Protocol

I think, using of signatures means something like STS protocol (https://en.wikipedia.org/wiki/Station-to-Station_protocol).
In STS, for the purpose of mutual authentication,
each party must send a signature of ephemeral keys.
So, in terms used in https://signal.org/docs/specifications/x3dh ,
Alice should sign EK_a || SPK_b, and Bob should sign the same.

In X3DH, authentication provided by signatures is substituted by
the fact that for getting the key (SK) each party should execute DH exchange using his identity key (say, ID_a) and counter-party's ephemeral key (say, SPK_b). So, in fact, signing of SPK_b with private key of ID_a (in STS) is substituted with just running of DH for ID_a and SPK_b (in X3DH).

So, what's the difference for deniability? Very simple: signature is evidence of communication and knowing of ephemeral keys, and hence knowing of SK. While running of DH is not an evidence, because it's even impossible to know wether Bob (or Alice) run DH and get SK or not.
If Alice will want to prove to some judge that Bob communicated with her,
and Bob knows some SK (and hence - he could create or at least decrypt some cypher-texts provided by Alice to judge), she can't prove it:
it's obvious that Alice could simulate DH with any EK_a key she wants. There's no evidence that Bob was running DH with EK_a and even know about existence of such EK_a.


Is there an asymmetric algorithm that can perform double encryption?

No.  For semantic security, the encryption of a known plaintext with a given key must be overwhelmingly likely to have high entropy so for most plaintexts and keys, there must be lots of possible encryptions of the plaintext with the key.

So for most keys, the ciphertext space must be significantly larger than the plaintext space.

You might be interested in trapdoor permutations. The only candidates I'm aware of for [such permutations with domain not depending on the public key]
come from multi-variate crypto.

On the other hand, it's easy for symmetric schemes to satisfy the deterministic version of CCA-security.


I believe it seems similar to random and urandom function in unix/Linux system. Once the physical entropy/seed is not enough, one would block and the other would generate the seed based on current ones. From security point of view, pure random entropy should be better choice, but in practical, I don't see the problem with seed generation. It should be indistinguishable to some extent if your initial seeds are pure random.. like from physical entropy.


Why is RSA easily cracked if N is prime?

Is this correct?

Sadly no.

First here's a simple counter-example: $n=11,e=3\Rightarrow d=7\neq 3$, also note that $(5^3)^3\equiv 9\not\equiv 5\pmod {11}$ and $(5^3)^7\equiv 5\pmod {11}$.

Concretely the mistake in the calculations is finding the order for exponent (e.g. the totient function of the modulus), which the calculations hard-code to $\varphi(pq)=(p-1)(q-1)$ which is only true for $p,q\in\mathbb P$.
The fix is to use the proper formula which obviously is $\varphi(1\cdot q)=q-1$. Now you can proceed normally in calculating $d$ as solution to $e\cdot d\equiv 1\pmod{q-1}$.


How are initialization vectors used in TLS 1.1?

You might be somewhat confused by the term 'record'.

In TLS, a data to be encrypted is divided into a series of fragments; each fragment is encrypted as a record, with each record being encrypted and integrity protected independently [1].  Such a record can hold up to 16kbytes of data. This 'record' is standard TLS terminology and is what you are referring to as a 'message'.  If you use a block cipher, then the amount of data that is processed by that block cipher at a time is referred to as a 'block' (not a 'record'), and in TLS, we generally don't talk about it that much, as there is generally little need to deal with the lower levels of how the crypto is done.

In TLS, each record is encrypted separately.  If you use TLS 1.1 and CBC mode, when you encrypt a record, you pick an unpredictable IV, and then use that IV to CBC-mode encrypt all the data (and the HMAC of the data).  You use CBC-mode in the standard way, and so CBC mode uses the IV the encrypt the first block (16 bytes for AES), and then uses resulting initial 16 bytes of ciphertext to encrypt the second block, and so on.  It's just like TLS 1.0 CBC mode, except instead of using the previous ciphertext as the next IV, you use the value that appears immediately before the ciphertext.  Hence, your first diagram is more accurate.

[1]: In addition, TLS sometimes sends messages between the encryptor and decryptor, to do the original negotiation, or to do rekeys.  This data is also sent within records.


Among several aspects of the question, I'll cover only protection against replay of commands.

A common technique (among several) is to have commands tied to a nonce, that somewhat is accepted only once by the slave device receiving the command. The nonce is included in the input of a MAC or public-key signature algorithm that protects the integrity of the command.

When two-way communication is possible, a nonce can simply be a true random value wide-enough to most likely not repeat (say, 16-byte), generated by the slave device and sent to the master before it sends a command. The slave then receives the command, checks the MAC or signature included in the command (prepared on data including the nonce, as a prefix of the data in the actual command), and executes the command only if the MAC or signature checks. The slave then no longer accepts to execute another command until it has generated another nonce.

This is safe from the standpoint of pure replay. However an adversary may be content to defer execution of a command (rather than execute it a second time). Think of a garage door: an adversary waits for the home owner returning home and sending an open command; the adversary captures that command until the middle of the CRC at the end, and starting from that instant jams the radio channel. The command is ignored by the slave for wrong CRC, and does not get executed. Long after the attacker stops the jamming, then retransmits the command with recomputed CRC; abracadabra the door opens! Amazingly, some complex secure channel protocols put no time limit on how much an active adversary can delay a frame (perhaps inserting dummy requests for repetition to keep some link active), and are vulnerable to that attack. There's a simple countermeasure: we can put a time limit to the validity of a nonce, like seconds, enforced by the slave, counted from the sending of the nonce; and the nonce needs to be unpredictable (rather than only unique) to block some variants of the attack.

This is fine, but the nonce requires two extra frames (to the slave asking for the nonce; from the slave with the nonce). One option to reduce at least the number of overhead frames is to embed a fresh nonce in every frame sent, applicable to the next frame if received within delay; so that in a burst of commands, the overhead is two initial frames, plus the size of the nonces added to other frames. With great care, that later overhead can be eliminated using precise conventions on how the nonce evolves when there is authenticated activity.

Caution: the problem of making the nonce unpredictable, or even not repeating itself, is notoriously difficult if the adversary has access to the power supply of a slave device with no reliable TRNG (that was the situation in early Smart Cards). The solution of enciphering a counter held in EEPROM with a local secret key superficially seems to work (and even allow to use a nonce twice narrower with increased assurance against reuse); but there are the issues of making a counter that does not go backward on power loss during change; limited endurance of EEPROM to repeated writes to the same location; and the basic difficulty of keeping a secret key secret despite side-channels.


Character frequency graph for cipher text

In each language there is an expected distribution of characters so you can use this to make reasonable estimate as to characters.
For example, E is by far the most common letter in English words, followed by T, then A then O etc. So in your substitution ciphertext, the most common letter is probably E.
From pi.math.cornell.edu:


RSA key normalization is merely the convention that when comparing public keys we view them as two numbers where the first number is the public exponent and the second is the public modulus. Now in the case of RSA if you're given the public key as two numbers then the big composite one is the modulus and the smaller one which is often 65537 is the exponent so it's pretty obvious which is which.

The need for normalization is more obvious with DSA keys which involve four numbers of which two (the generator and the public value) would be impossible to distinguish if $h$ was chosen at random when the generator $g=h^{(p–1)/q)}$ was calculated). In all cases with DSA if you're just given the four parameters in any order you have to do a bit of extra calculation to make sense of it and normalization takes care of the whole issue.


Only allow specific types of data to be transmitted via an end-to-end encryption service

One (very generalized) solution would be to use a general ZKP solution like libsnark.

In libsnark (and other tools like it), you would write a function that accepts both public and private inputs, and outputs a proof that the inputs satisfy the logic of the function. This proof can then be verified, at a much lower cost than it took to generate it.

E.g., you might have:

public_inputs = { encrypted_string, regex, length }
private_inputs = { plaintext_string }

function(public_inputs, private_inputs)
  s = encrypt(plaintext_string)
  check1 = (encrypted_string == s)
  check2 = (length(plaintext_string) == length)
  check3 = string_fits_regex(plaintext_string, regex
  return (check1 and check2 and check3)

Libsnark gives you one algorithm for "prove" and one for "verify".

The sender would then call "prove", which would generate the proof, and then send the proof along with the encrypted string.

Then you (or the receiver), could call "verify" with the same public inputs and it would say "yes" or "no".

There's a lot more details, check the references at the end of that repo's README page. Here's a good illustration from a (somewhat related) blog post.

I bet there are other, even better (less computationally intensive) solutions as well.


Pencil & paper encryption, some thoughts on polyalphabetic techniques

What you seem to be describing is similar to a single-letter book cipher, but using the solution to a crossword puzzle instead of a book as the reference source.
While this might have some merits as an ad hoc hand cipher — after all, book ciphers have also been successfully used as such in the past — it also shares most of the drawbacks of book ciphers.  In particular:

It has no secret key, other than the choice of which crossword puzzles to use.  Anyone who can guess that, and has access to those puzzles, can decrypt the messages.  This is a violation of Kerckhoff's principle.

It cannot encrypt letters that don't occur in the reference crossword.  No Q or Z in today's puzzle?  I guess you'd better not use those letters in your message.

Its security is strongly dependent on the encryptor's skill at choosing letters uniformly at random from the reference source — something that people tend to be bad at, especially if they're tired or in a hurry or just feeling lazy.  In particular, if the encryptor keeps reusing the same coordinates for repeated letters, or tends to choose nearby coordinates for successive plaintext letters that happen to occur close to each other in the puzzle (e.g. in the same word!), or even just generally favors a particular corner of the puzzle, the security of the scheme may be substantially weakened.

Some of those problems could be remedied; for example, superencrypting the ciphertext with a simple substitution cipher with a secret key (or, perhaps more simply, just using the secret key to somehow scramble the row and column labels) could make this scheme significantly harder to crack.  But other weaknesses, like the reliance on operator diligence, are harder to patch.


Is it ok to transmit an IV as a custom HTTP header?

From a cryptographic standpoint, it doesn't matter how you transmit the IV. You can send it as a header, in the message body, as the path in the request method, or even the URG pointers in a few TCP packets. From the perspective of the encryption process itself, it doesn't care how it got the IV, no matter how silly the transmission method used, as long as it got it in the end.

From a web development standpoint, it's bad practice to include data that is applicable to the payload in the headers. Sending an IV in a custom HTTP header slightly increases overhead when compared to simply prepending it to the ciphertext and sending it all. You don't even need an elaborate serialization format. Just prepend the fixed-size IV and call it a day. This has the additional benefit of not breaking the HEAD method, which requests the HTTP headers but not body. I can't think of any reason why you could possibly want the IV sans ciphertext.


Brute forcing the secret key in Elgamal encryption

Given $p$ and $p_e \equiv p^e \pmod{n}$. You need to calculate $p_e$. Propose $e$ is small enough to brute-force. The simplest way would be to calcute $p^e \pmod{n}$ for values $e \in \{1,2, ..., n-1\}$ until you find $p_e$.

So all you need would be something like this:

static int findE(int n, int p, int pe) {
    int base = p;
    for(int e = 2; e < n; e++) { // also it suffices to start at e=2
        p = p * base % n;
        if (p == pe) return e;
    }
    return -1;
}

Even though you are doing to much calculation (for every value of $e$ you recalculate all values of $p^{e-1}$), right now i do not see why your code would'nt work.
Update: forget all i said about modular exponentation, that was bullsh*t.


Importance of round complexity in determining the efficiency of an MPC protocol

First note that all polynomial-time functions can be securely computed with a constant number of rounds (Yao and BMR families) and all can be securely computed with protocols that have rounds dependent on the depth of the circuit computing the function (GMW families). The question is when is one type better than another.

The answer to this question is not straightforward, and depends on many parameters. Clearly, if you are on a slow network (Internet with 30ms round-trip time), then any protocol that has many rounds will be very very slow. However, if you are on a fast network, then many rounds has less of an influence (except in very extreme circumstances of incredibly deep circuits). It turns out that the constant-round protocols that we know of have much higher bandwidth than those that have complexity that depends on the depth of the circuit. Thus, in a very fast network, many-round protocols often out-perform constant round ones. As I mentioned, this is NOT the case in a slow network.

There isn't too much published that directly relates to this question. However, for semi-honest adversaries there is one paper that comes to mind by Schneider and Zohner, titled: GMW vs. Yao? Efficient secure two-party computation with low depth circuits that appeared at Financial Crypto 2013. This is a good place to start reading.


Finding Linear Redundancy by counting the number of distinct frequency distributions of absolute walsh transform

Given $S:F_2^n\rightarrow F_2^n$, define the (generalized) walsh transform coefficient as $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x + b \cdot S(x)}.$$

Looking at your array, $b=0$ which gives  $$\hat{S}(a,b)=\sum_{x\in F_2^n} (-1)^{a \cdot x}=0,$$ should result in a zero sum for all $a\neq 0$ and a sum of $2^n=2^4=16$ giving a row or column with 15 $0$s and one $16.$ You have omitted one column, which I shall assume corresponds to $a=0.$

Otherwise, what is observed from your array is that the multiset of absolute values for nontrivial linear selections of the sbox bits ($b\neq 0$),i.e., the multisets
$$
M_b=\{|\hat{S}(a,b)|: a \in F_2^n\}
$$ where we count frequencies of occurence of distinct transform values are invariant with respect to different values of $a,$ which is a kind of uniformity. I wouldn't call it "minimal redundancy" without a definition of what that term might mean. Moreover, due to the absolute value, this is equivalent to the following multisets
$$
M_b=\{|\hat{S}(a,b)|^2: a \in F_2^n\}
$$
begin invariant. In general, from Parseval, we would have
$$
\sum_{a \in F_2^n}|\hat{S}(a,b)|^2,
$$
be a constant, and maybe the maximum redundancy would correspond to these magnitudes all being the same, i.e., $\pm 2^{n/2}$ which could occur only with $n$ even. In any case from Parseval we can deduce that the omitted values in the other rows are $$\sqrt{2^{8}-2\times 8^2-8\times 4^2}=0$$ which could also been directly inferred but this means that your other values are admissible as walsh coefficients so it's useful.
But I fail to see why the multiset of values you exhibit (including the missing one)
$$
\{8(2~times),4(8~times),0(6~times)\}
$$
are in some sense minimally redundant, without some kind of result on divisibility properties (by some $2^i$) for walsh coefficients of Sboxes (which I assume are permutations). Such properties are usually deeply algebraic in nature.


On CPA & KPA security of $\boxplus$-Feistel

In term of CPA and KPA security, does $\boxplus$ replacement add security over 3 rounds, with proof?

No. There's nothing special about $\oplus$ in the Feistel struture. In fact any group operation $\boxplus$ over $\{0,1\}^n$ will do just fine. The main point of these random functions is to "blind" the previous rounds' other halves and for that a group operation is sufficient.

In fact Maurer and Pietrzak proved the more general security bounds for the Feistel construction beyond 4 rounds using an arbitrary group operation $\oplus$.

  If   $\boxplus$-Feistel structure have better security bounds that  $\oplus$-Feistel, why do not we see it common?

Well, as any group operation is sufficient, we usually choose the operation which can be computed fastest on most hardware. In particular you can evaluate XOR on your whole arbitrary-width block without having to consider carries and the like on any word-size. Also it's way easier to construct XOR in hardware than it is to construct any other group operation I can imagine right now. Also it's hard to beat 1 cycle / word with no inter-bit dependencies.


Building a pad for OTP on-the-fly with Diffie-Hellman

Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad?

No, since that is not how a one time pad works. You can use your idea to create cryptographic material to encrypt plaintext using XOR, what you are describing is an asymmetric stream cipher of some sorts.

A one time pad requires an "offline" exchange of key material. A one time pad when used properly is unbreakable, whereas a DH exchange can be broken or potentially maliciously interfered with. Using this idea may potentially expose a weakness in the PRNG used to generate the private keys, but that same problem is applicable to whatever is generating a true OTP. I this case however, the public key exchange may expose this weakness much earlier than an offline key exchange, as no ciphertext would be needed.

This idea may be significantly faster than an offline key exchange, but that depends on how much key material needs to be created. In your example, the shared secret would generally be passed through a hash function to distribute entropy more evenly over the bits, or possibly reduce the size of the shared secret so the entropy per bit is higher.


Double permutation patterns for transposition ciphers, how to crack

While transposition ciphers may move bits around, they are entirely linear; and effectively perform substitution... except the data positions are substituted, instead of the values.
Let's say I have the ciphertext
raspberry
and I encrypt it to get
bsapryrre
Statistical analysis becomes even easier than with a substitution cipher: I simply look for a word or set of words with the same count of each letter. Once I have a set of possible plaintexts (there won't necessarily be only 1 match) I effectively have a reduced set of possible plaintexts, one of which forms a known plaintext.
If I have the next ciphertext block as
ip
I can perform the same attack on the next block, effectively creating a series of anagrams. In fact, this attack is so simple that it's already been implemented on every online anagram solver.
I might find multiple choices choices with meaning:

raspberry pi
raspberry ip

Since one makes more sense than the other, you know what your message is. This principal can be applied indefinitely to break transposition ciphers without even needing to break the key.


A private key with multiple public keys?

Here's an idea:

Alice's private key is an AES key $k$, which Alice picks randomly.  Yes, we're using an AES key as a private key; bear with me a moment...
To generate a new public key, Alice picks a random value $r$, and generates the pair $(\text{AES}_k(r), rG)$, which she publishes, and which I will refer to as $(b, H)$.  Alice can optionally forget the value $r$ she picked.  Alice can generate and publish as many public keys as she needs...
To encrypt a message $m$ with this public key $(b, H)$, Bob selects a random value $s$, computes the point $sG$ and the AES key $KDF(sH)$, and outputs the triplet $(b, sG, \text{AES}_{KDF(sH)}(m))$
To decrypt $(b, sG, \text{AES}_{KDF(sH)}(m))$, Alice first decrypts $\text{AES}_k^{-1}(b) = r$, (and if that decryption fails, the message wasn't meant for her).  Then she computes $r(sG) = s(rG) = sH$, computes $KDF(sH)$, and then decrypts $\text{AES}_{KDF(sH)}(m))$, giving her the message $m$.

Two different public keys from Alice are unlinkable, as the only connection is that they contain the encryption of two different values with the same AES key, and that's indistinguishable from random.

And, all operations take time independent of the number of public keys Alice generates...

(Note: you'll use some authenticating encryption mode of AES, such as AES-GCM...)


How to force non-negative int64_t output for blowfish encryption with int32_t input?

One option is to encipher each number as follows:

concatenate one 0 bit, the index for the number to encipher (or a random value) on 31 bits, and the 32-bit number to encipher, to form a 64 bit value with the leftmost bit at 0
encipher with blowfish (and a fixed secret key)
if the leftmost bit of the result is set, loop to 2
output the 64-bit result (which matches the desired condition of having its leftmost bit clear)

Decryption is as follows

check that the input value matches the desired condition of having its leftmost bit clear
decipher with blowfish (and the same fixed secret key)
if the leftmost bit of the result is set, loop to 2
optionally, if the index is known: check that the leftmost 32 bits of the value match the intended index; that gives you a free Message Authentication Code with odds less than one in two billions of forgery!
extract the deciphered 32-bit number as the rightmost 32 bits of the result

That's cycling, a classical technique of Format Preserving Encryption. The average number of Blowfish encryptions is 2, and odds are about $1/2^n$ that more than $n$ Blowfish encryptions are necessary to encipher a number. It is not possible that steps 2/3 of encryption or decryption enter an infinite loop (including if the ciphertext was altered, thanks to the check made at step 1 of decryption); however it could be that we encounter by accident an input which requires 50 loops or slightly more, or (with a determined attacker knowing the key and giving us a rogue ciphertext) perhaps next to 100; and the only firm upper bound we have ($2^{63}+1$ iterations) is entirely impractical.

Other methods are possible that take bounded time, and can reduce the cryptogram size (at the expense of MAC robustness); but all the secure ones I know will have one of the following drawbacks:

they will require significantly more Blowfish encryptions on average (as if we build a 63-bit block cipher from Blowfish and a Feistel structure);
they will provide no integrity insurance (as if we encipher a 31-bit incremental index with blowfish, truncate the 64-bit result to 32 bits, XOR that with the 32-bit number to encipher, and form the cryptogram by prefixing the 32-bit result with a  0 bit and the index).


There are two possible ways (I can think of) an attacker could mess you up here, but they both stem from very poor design. So I don't know how realistic they are.

Note: the following figure assumes a 64-bit blocksize

CFB is only self synchronizing against insertions/deletions of a specific length. The length is determined by the shift register. If the attacker can insert symbols that don't follow this length, then they can throw everything off in effect causing a DoS. Thus, when designing the system, you have to take into account the # of symbols that can be accidentially or maliciously inserted (deleted). If an attacker can inject down to a single symbol, then you'll have to set $k=1$ in the figure.
Another possible attack came to light in your comment about forcing CFB to behave like ECB. This can happen if you use the same instance of the block cipher to encrypt and decrypt. This is not how I would design the system. I'd use two separate instances of the block cipher, one for encrypting my messages to you and one for decrypting your messages to me. Furthermore, I would use different keys for each direction. If you do it this way, what the attacker injects will only mess up your decryption instance (which thanks to the self-synchronizing nature of the mode, is a problem from which you can recover).


Yes, with some more ciphertext.
The CFB mode encryption equations;
\begin{align}
I_0 &= \text{IV}\\
I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\
C_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus P_i\\
\end{align}
and decryption equations;
\begin{align}
I_0 &= \text{IV}\\
I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\
P_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus C_i\\
\end{align}
As you can see, to read one value one needs more than one ciphertext and that is defined by the CFB mode is used. NIST has CFB-1, CFB-8, and CFB-128. The $s$ in the CFB-$s$ represents the encryption size per block cipher encryption/decryption.

CFB-1 needs to read 129 ciphertexts block, one can be IV, to decrypt one block
CFB-8 needs 9 to read 129 ciphertexts block, one can be IV, to decrypt one block
CFB-128 needs 2 to read 129 ciphertexts block, one can be IV, to decrypt one block

The good is that if you read sequentially then the need is not linear, for example, 2 sequential ciphertext blocks will need only 3 on CFB-128, 10 in CFB-8, and 120 in CFB-1.
Actually, even in the reduced sizes like CFB-1, this is not really a problem, since the 128 ciphertexts are bits and that is only two reads if the data can be access 128-bit per reading. The memories can handle this and harddisk has wider read access. This, however, has a drawback on the decryption time. AES-CFB-1 needs 128 decryptions, AES-CFB-8 needs 16 decryptions.
Note that we don't use CFB or CTR on-disk encryption, we rather prefer XTS or XEX modes.


Hash Function to get same value for different messages

For cryptographic hash functions, there are the 3 definitions of collision resistance, (first) preimage resistance and second preimage resistance.

Number 3 is collision resistance, and it is quite different than No. 1 and No. 2, which is due to the birthday problem (also see birthday attack).

In No. 1 and 2, the resulting hash value is fixed (once directly and once indirectly due to a fixed element as input to the hash function). In No. 3 however, you just have to find two elements with the same hash value. So you start by hashing two elements and the hash value has $n$ bits. The chance that they are equal is $1/2^n$. Now you hash a third value. The probability that it is equal to either the first or second value is $2\cdot(1/2^n)=1/2^{n-1}$, the next element has a chance of $3\cdot(1/2^n)\approx 1/2^{n-1.6}$, and so on.

In average (and this is a very rough estimate) you can find a collision after $2^{n/2}$ hashed values. For No.1 and No.2, you need to test in average $2^{n-1}$  values.

Btw, No.1 is (first) preimage resistance and No.2 is second preimage resistance. The difference between these two is less obvious, but you can create toy examples with preimage resistance but no 2nd preimage resistance. For example:

Why doesn't preimage resistance imply the second preimage resistance?

Pre-image resistant but not 2nd pre-image resistant?

The second thread also lists a function which is 2nd preimage resistant but not fully preimage resistant, but that is a very specific example and probably goes too far for your questions.


RSA: least significant bit position in key

Because (if $C=P^e$ where $P$ is the plain text): $2^e C= (2P)^c \pmod{N}$ so multiplying the ciphertext by $2^e$ modifies the plain text by a multiplication of $2$, which is a bitshift to the left of $1$, so we get 1 new zero bit at the end. To get $m$ zero bits, we need to multiply by $2^{em}$ (modulo $N$), of course.


How to generate a nonce for ChaCha20 Poly1305?

The RFC 7539 describe your needs.
The uniqueness:

The most important security consideration in implementing this document is the uniqueness of the nonce used in ChaCha20.  Counters and LFSRs are both acceptable ways of generating unique nonces, as is encrypting a counter using a 64-bit cipher such as DES.  Note that it is not acceptable to use a truncation of a counter encrypted with a 128-bit or 256-bit cipher, because such a truncation may repeat after a short time. (The bolds are mine)

LFSR's and counters are very efficient. Use a 96-bit binary counter or 96-bit length LFSR with a primitive polynomial. One must be careful during system reboots and especially system and power failures since you have to store the nonce somewhere to recover correctly. You need to make sure that when a failure occurs either do a long-jump on the counter/LFSR or generate a fresh new key.
Randomly generating:
You can also generate it randomly while considering the birthday bound $\mathcal{O}(\sqrt n)$. You should stop way before generating $2^{48}$ nonces under the same key to hit a collision. You can adjust the advantage of the adversary with the birthday calculations.
Combining Both
One can also combine counters/LFSR with random generation. For example, use a 48-bit binary counter and 48-bit random. For each nonce generation increment the counter/LFSR and generate a new 48-bit random.
This is more reliable than single counter/LFSR or random based one. During a failure, if the system did not correctly write the last step/stage of the counter/LFSR, then the random part would be helpful to mitigate the repeat of a previous nonce.
Consequences of repeating a nonce:

If a nonce is repeated, then both the one-time Poly1305 key and the keystream are identical between the messages. This reveals the XOR of the plaintexts, because the XOR of the plaintexts is equal to the XOR of the ciphertexts.


PSI protocol reveals only one element of the intersection of two sets

In fact, one possibility is to use the generic garbled circuit protocol that implements a PSI circuit + a filter circuit such that the result (intersection) from the PSI is filtered and only one randomly chosen element in the intersection is output at the end of the protocol. However, I cannot say much except this is feasible.

Below is a custom protocol for your purpose, assuming $|A\cap B|$ can be leaked and semi-honest adversaries. It can be further optimized.

You need 3 building blocks:

A PSI with data transfer protocol (see below references [1,2, 3]). A PSI with data transfer protocol is a PSI protocol such that at the end of the execution, Bob gets nothing and Alice gets for each element $a_i$ in her set, a piece of data $d_i$. If we just want PSI, then if $a_i$ is not in the intersection $d_i$ is a random string, otherwise if $a_i$ is in the intersection $d_i$ is $a_i$ itself. So that after running the protocol, Alice gets the intersection. The trick we will use relies on the fact that it is entirely possible to let $d_i$ convey other information than just the set element.
A semantically secure encryption scheme $(\mathcal{G},\mathcal{E},\mathcal{D})$ in which the ciphertext can be efficiently re-randomized. Here $\mathcal{G},\mathcal{E},\mathcal{D}$ are the key generation, encryption, decryption algorithms. One example is Paillier. For any ciphertext $\mathcal{E}_{pk}(m)$, one can re-randomize it by generating a fresh encryption of 0, $\mathcal{E}_{pk}(0)$, and use the homomorphic property to get a new ciphertext $\mathcal{E}_{pk}(m)*\mathcal{E}_{pk}(0) = \mathcal{E}_{pk}(m+0)= \mathcal{E}_{pk}(m)$. The new ciphertxt encrypts the same plaintext but looks totally different.
A sementically secure symmetric block cipher $(G,E,D)$.

In the protocol, Alice has a set $A$, Bob has a set $B$. Bob also generates a key pair $(pk,sk)=\mathcal{G}(\lambda)$ ($\lambda$ is a security paramter). Bob gives $pk$ to Alice. Then they do the following:

Bob generates a random key $k_1=G(\lambda)$, then use the block cipher to encrypt all his elements $E_{k_1}(b_1),\ldots,E_{k_1}(b_n)$.
Bob and Alice run the PSI with data transfer protocol, such that Alice uses her set as input, and Bob for each his element $b_i$, send a data payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_i))$,  -- note that each $\mathcal{E}_{pk}(1)$ must be generated using fresh randomness.
In total, Alice will receive $n$ pieces of data in the form of $(c_1^i,c_2^i)$. If Alice has an element $a_i =b_j$ (i.e. $a_i =b_j$ is in the intersection), Alice will receive the payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_j))$, otherwise, Alice will receive a piece of random data which can be parsed as $(\mathcal{E}_{pk}(r_1),E_{k_1}(r_2))$ where $r_1,r_2$ are random. However, Alice cannot tell whether each $(c_1^i,c_2^i)$ she received is "good" or random because it is a pair of ciphertexts.
Alice generates a new key $k_2=G(\lambda)$. For each $(c_1^i,c_2^i)$ pair, Alice re-randomizes $c_1^i$ to get a new ciphertext $(c^i_1)'$, and encrypts $c_2^i$ to get $(c^i_2)'=E_{k_2}(c_2^i)$. Alice puts all pairs $((c^i_1)',(c^i_2)')$ in a set $A'$, randomly permutes $A'$, and then sends $A'$ to Bob.
Bob generates a new key $k_3=G(\lambda)$. For each element $((c^i_1)',(c^i_2)')$ in $A'$, decrypts $(c^i_1)'$, if the result $\mathcal{D}_{sk}((c^i_1)')=1$, puts $E_{k3}((c^i_2)')$ in a set $B'$. After all pairs have been processed, permute $B'$ and send $B'$ to Alice. (If $B'$ is empty then stop because the intersection is empty).
Alice randomly chooses one element $e \in B'$, sends $e$ to Bob. Bob decrypts and sends $e' =D_{k_3}(e)$ to Alice. Alice decrypts and sends $e''= D_{k_2}(e')$ to Bob. Bob decrypts and sends $e'''=D_{k_1}(e'')$ to Alice. Now $e'''=D_{k_1}(D_{k_2}(D_{k_3}(E_{k_3}(E_{k_2}(E_{k_1}(b_l))))))$ is a random element in $A\cap B$.

1 Efficient Private Matching and Set Intersection, Michael J. Freedman, Kobbi Nissim, Benny Pinkas, EUROCRYPT 2004 (link)

2 Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity, Emiliano De Cristofaro and Gene Tsudik, FC2010 (link)

3 When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol, Changyu Dong, Liqun Chen, Zikai Wen, CCS 2013 (link)


Recovery of private key in AES-CBC from two ciphertexts with different IV, but identical plantext

To give a short answer, if an attacker knows ($P$, $IV_1$, $M_1$) and ($P$, $IV_2$, $M_2$) such as :

$M_1 = E_K(P, IV_1)$

and

$M_2 = E_K(P, IV_2)$

where $E_K$ is the AES-CBC encryption function with the key $K$ then he doesn't learn anything about $K$ because AES is resistant to known plaintext attacks. As long as the $IV$ is randomly chosen, encrypting the same message with the same key $K$ do not reduce the security of AES-CBC.

Here is a longer answer : Why is AES resistant to known-plaintext attacks?


Offline Complexity of the garbling scheme

From The Foundation of Garbled Circuits

  A garbling scheme is a five-tuple of algorithms $G=(Gb,En,De,Ev,ev)$.
  The first of these is probabilistic; the remaining algorithms are
  deterministic. A string $f$, the original function, describes the
  function ev$(f,\cdot): \{0, 1\}^n\rightarrow \{0, 1\}^m$ that we want
  to garble where $n$ and $m$ are the input and output size resp.  On
  input $f$ and a security parameter $k\in \mathbb{N}$, algorithm $Gb$
  returns a triple of strings $(F, e, d)\rightarrow Gb(1^k, f)$. String
  $e$ describes an encoding function, $En(e,\cdot)$, that maps an
  initial input $x\in\{0, 1\}^n$ to a garbled input $X=En(e, x)$. String
  $F$ describes a garbled function, $Ev(F,\cdot)$, that maps each
  garbled input $X$ to a garbled output $Y = Ev(F, X)$.  String $d$
  describes a decoding function, $De(d,\cdot)$, that maps a garbled
  output $Y$ to a final output $y = De(d, Y )$.

Thus, taking an FHE $(Gen,Enc,Dec)$ scheme (see this)which takes an encoded input $X=Enc(x)$, applies the function $C$ to it to get $Y=C(X)$ and then decode the output by $y=Dec(Y)$ we get that $y=C(x)=Dec(C(Enc(x))$ (since the scheme is fully homomorphic. In this example the garbling algorithm, the one you denote by $CC.Circ$ just do nothing and its complexity is $O(1)$, which is optimal.

This example shows that you must restrict your arguments when you refer to the optimality considerations of a garbling scheme. This topic is currently under an intensive research.


It is easily seen that the value of $q$ is invariant modulo $e$.  As a consequence, we always have $q \equiv p\cdot (p-1)^{-1} \pmod e$ and thus $q(p-1) \equiv p \pmod{e}$.  So, the resulting modulus $N = pq$ is such that $N \equiv (p+q) \pmod e$.

Example: With $p=10598342506117936057$ and $e=5004898192290387253$, the proposed construction yields the prime $q = 106091356957242239963$.  One can check that $p\cdot q \bmod e = 1577041040681269201 = (p+q) \bmod e$.


Decrypt a public encrypted message and Sign a signature, how the math is different?

The simplistic view that signing uses the same math as decryption is descriptive with textbook RSA; has some relation to practice in safe use of RSA; and is just wrong with most other common asymmetric cryptosystems, beside the commonality that a private key is involved.

In textbook RSA, the math to decrypt an encrypted message and compute a signature is the same: it is applied the textbook RSA private key function $x\to y=x^d\bmod N$, with $(N,d)$ the private key, and $x$ the encrypted message in decryption, or the message to sign in signature. Problem is, textbook RSA is unsafe for both encryption and signature.

When we move to secure use of RSA, the math becomes different:

To decrypt we check the bound of the cryptogram $x$, apply the above textbook RSA private key function, then

Extract the encrypted message from the result $y$, in a certain way that removes random padding that was added at encryption (and perhaps checking certain fields). There are at least two common classes of RSA encryption padding and corresponding decryption removal, defined in PKCS#1, and several implementation variants (not all are safe). That can be enough for very small messages (like few hundred bytes).
And/or what we really obtain is a secret key, which is then used to decipher the bulk of the message using symmetric-key cryptography (that's hybrid encryption).

To generate a signature we typically hash the message to sign then add redundancy in a certain way, then apply the above textbook RSA private key function to obtain the signature $y$ (in some variants we further keep $\min(y,N-y)$ ). There are at least three common classes of RSA signature padding: two in PKCS#1, and ISO/IEC 9796-2, which comes with several variations.

When we move to asymmetric cryptosystems other than RSA, one thing remains: the private key is involved in decryption, and/or computing a signature. Other than that, there is typically profound disjunction between decryption and computing a signature (one notable exception is the Rabin cryptosystem, which can be seen as a variant of RSA with even public exponent); and very often, one of the two features is just not offered by a particular cryptosystem.

For example, we have DSA, ECDSA, and Lamport signatures, but these cryptosystems do not offer encryption.

The converse can be true: we have Pailler encryption, but no useful signature analog. We have NTRUEncrypt, which latest versions are unbroken; but it is quite different from the related NTRUSign, and last time I checked work on the later stopped in the broken phase of multiple break/repair cycles.


Does a stream cipher require a KDF when it's key is variable length?

One problem with RC4 is that, while it does take a variable length input (up to 256 bytes), it's known not to be great at mixing those bytes together.  Specifically, we see correlations between the RC4 key and the RC4 output stream.

My first recommendation to you would be to use something other than RC4.  About the only advantage RC4 has over most other ciphers is that it is simple enough to be memorizable; for example, if you are going someplace where you don't want to carry any programs with you, if you can get access to anything programmable, you can type in an RC4 program, and have a good chance at having it work properly.  If you don't care about that (and you probably don't), then there are better options available.

My second recommendation (assuming that you ignore the first) is that you ought to obscure the relationship between your password and the RC4 key (as RC4 doesn't do a great job of obscuring the relationship between the RC4 key and the keystream).  Using a KDF to process the password would work; at the very least, you should use a hash function.  Now, I don't know whether the weaknesses in the RC4 key setup logic would be a concern to you; I also don't know that it's not; covering that potential weakness would appear to be a prudent step.

As for a single character password, well, that's going to be weak, whether you use a block cipher or RC4....


Breaking Truncated Linear Congruential Generator with known parameters

According to the paper Freize et al, for the most significant bit case which is discussed at length in the link,the modulus M must be odd, the addend I assume can be any number between 1 and the modulus, and the increment must be zero. So given:
a*x(i) + b ~ mod M
M is odd
0 > a < M
b = 0

Because both a and $M$ are known n we obtain high order bits y(i). Then $x = y + z$
where $y$ is the high order bits $n$, $z$ is the lower order bits.
Lx ~ 0 mod M
Taking B the reduced basis of yields.
Bx ~ 0 mod M
Substituting x = y + z gives
B x + By ~ 0 mod M which yields the equation
Bx + By = km for an unknown vector k of integers.

From this point, its easy to find the lower order bits $z$. (see the link above)
In the case where we are give the lower significant bits $z$ instead of the higher bits $y$, the paper suggests substituting $x = 2(s0)* y + z$. And they talk about finding the inverse of $2(s0) \pmod M$ which is guaranteed to exist since M is odd.
But that's where I get completely lost.


Under which conditions would it be OK to use “H(pass||data)”?

I think the attack by Preneel and van Oorschot (MDx-MAC and Building Fast MACs from Hash Functions, CRYPTO'95) in Proposition 4 applies. It was cited by PulpSpy in reply to my question about H(pass||length(data)||data). With fixed-length data, that amounts to a known suffix for the key.

Proposition 4 states in a nutshell that for a generic construction which generally covers H(…||data||…) where H is an $n$-bit hash function, there is an attack that allows the attacker to replace some trailing blocks. The attack does however require about $2^{n/2}$ known text-MAC pairs, which is not feasible with a 256-bit hash. So this 20-year old result exhibits a theoretical attack. I don't know if there are more recent results that show a more practical attack.


Can one hide a text in an image and then hide that image in another image?

Yes!

For bitmap images, if you use all the pixels of the image (bad idea, it's very detectable) you need a first image 8/3 times bigger than the size of the text you want to hide (you can compress it).

8 because you need 8 pixels to hide one byte (one bit per pixel).
1/3 with color images, because you can hide a bit per channel/pixel.

After this, you can hide this image into another image 8 times bigger (again, 1 byte into 8 pixels).

For JPEG images the approach is different, because you are hiding information into the DCT coefficients. But it's the same idea.


Does a stream cipher provide perfect secrecy?

First, do not ever use RC4.

Second, it depends on how you use that stream...

If you use AES-CTR as a stream cipher (see more here), you will specify a key $K$ (and a nonce $IV$). The CTR mode of AES will generate a stream of bits, whose length matches the messages. All that is required is to XOR it with the message.

In order to decipher. One will require the key $K$ (or nonce $IV$), regenerate the stream and XOR to retrieve the plaintext.

If a brute force attack were to happen, it would be on the nonce + key (its size is smaller than the message).

On the other hand, if:

you were to generate a really long stream of truly random bits in advance,
send it to your partner through a secure way and
use parts of that stream to encrypt messages for him only (without any reuse of the generated stream).

Then what you are doing is a Vernam Cipher, not a stream cipher (unless I am wrong). This was the way they exchanged message between USA and URSS (exchanges disks of random bits for single use).
And yes it would be perfectly secure.

One of the requirement of the Perfect secrecy is the key space has to have the same size as message space. Hence the key and the message must have the same length. In the OTP or Vernam Cipher, this is the case. In a Stream cipher, given that the key is used to generate a stream, whose length is greater, it does not meet the Perfect Secrecy requirement (while still being reasonably secure).


What effect does a salt have on attacks against hashes's fundamental properties?

I'm no security expert but I'll take a stab at this since it hasn't been answered.
Also, I'm answering as if you're asking about a Rainbow table or Dictionary attack for preimage and second-premiage attacks. Preimage being the rainbow table attack and second-preimage relating to getting similar encrypted values (cipher text) from the same password.
If you actually mean preimage and second-preimage, these attacks have nothing to do with password protection and more to do with the hashing algorithm's robustness.
Basic Salting Info
In the most basic sense, salting increases the amount of time and effort needed to crack passwords.
Salts are:

Unique
Random (GUIDs are not necessarily random. Look up CSPRNG)
Public (at least, it doesn't need to be a secret)

Also, make your salts robust. This doesn't mean that the password should be weak. The password itself should also be robust.
How Salting Effects Hacks
Unique salts ensure the same password will be hashed to a different cipher text.
Attack 1: Salting will increase the time needed to find other user's passwords. Because, the attacker would need to create a Rainbow Table for every salt used because salts change the output in unpredictable ways. Cracking the hash for one user wouldn't be much harder but cracking the hash for all users would be exponentially harder (I'm not sure if that's literally exponentially harder or if it just seems that way).
Attack 2: If the salts are unique then there is no matching input (idealistically. I know there's collisions). So, if you know the plain text (and salt) for one user, then that doesn't mean you'll know the cipher text for all other users with that password.
Side Note: I suppose if you had the whole database and knew every salt that was used then you could hash the known password against all the known salts and compare all of those hashes to all the values in the database. However, this is still a win for salting because that takes more time then being able to query the database with one value. Also, I think key stretching can be used to increase the amount of time needed to hash while increasing the entropy of the algorithm. All of these little things make it that much more impractical to try and decrypt large databases.
Attack 3: I don't think you need to worry about collision attacks. In a collision attack, the attacker is in control of the input. An example, the attacker presents Document 1 to Person A to sign. Person A signs it. Then the attacker puts Person A's signature on Document 2 and gives it to Person B. I think this mostly has to do with TLS (SSL) security. Salting has no explicit effect on a collision attack.
Conclusion
Salting will make Attack 1 and Attack 2 more difficult to complete by increasing the amount of time and/or resources needed to execute the attack. This is assuming the attacker is hacking to get information for many users as oppose to just one.
Don't forget, strong salts should be used in conjunction with strong passwords.


Finding the n-th root of unity in a finite field

In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.

Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).

To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^{(q-1)/n})^n = x^{q-1} = 1 $$
Therefore, $x^{(q-1)/n}$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.

Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j \neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:

Get a random $x \neq 0$ in your finite field.
Compute $g = x^{(q-1)/n}$.
If $g^{n/2} \neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.

This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).

Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.


Can you tell me why doing scalar multiplication of a point on a Elliptic curve over a finite field gets to a point at infinity?

The points on the Elliptic Curves $E$ over a finite field $K$ are forming a commutative additive group ( Abelian group) with the point addition as the group operation. The group needs an identity element and usually represented as $\mathcal{O}$. In most curves, this is the point at infinity and also notated as $P_\infty$. In the Edwards curves, the identity is an affine point $(0,1)$.
The scalar multiplication $[k]P$ this actually means adding the $P$ itself $k$-times. More formally;
let $k \in \mathbb{N}\backslash\{ 0\}$
\begin{align}
[k]:& E \to E\\
&P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}
and by being identity $[0]P = \mathcal{O}$, and $[k]P=[-k](-P)$ for $k<0$.
Since $\#E(K)$, the number of points, on Elliptic curves over a finite field is finite if you add a point $P$ itself many times eventually you will get the identity $\mathcal{O}$.
$$\underbrace{P+P+\cdots+P}_{\text{$t$ times}} = [t]P= \mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge since the attacks. If we consider the  expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, i.e. we need to double the point size.
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $\mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
The order $n$ of the base point
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
is
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field ($K$) are same then the discrete logarithm on this curves runs in linear time.


Finding differentials and space complexity

If such a large Sbox with no structure were to be analysed you'd treat the analysis as a one-off precomputation.

Considering only classical differential cryptanalysis as an example, after the precomputation you'd only need to keep track of the highest probability differentials since if you combine a high probability differential with a low probability one, you've already lost quite an edge and over multiple rounds your attack will fail.

As for FEAL, there is lots of structure in the 32x32 round function and divide and conquer is the way to go.

If there was a randomly chosen huge Sbox, life would be difficult, but it is also difficult for the designer who'd have a hell of a time proving the strength of his/her randomly chosen Sbox, with any kind of guarantee. Blowfish Sboxes which are key dependent, for example, are only 8x32 (thanks @J.D.) and this helps by limiting the number of input differences that need to be considered.


As long as you ensure that $n_1\leq n_2$ is guaranteed, the value $r^em\pmod {n_1}$ can be treated as an element in $Z_{n_2}$ and the "outer blinding" and "outer unlinding" in $Z_{n_2}$ does not change this value. Consequently, if you compute the "inner unblinding" in $Z_{n_1}$ after the "outer unblinding" your proposal works.

Remarks from the previous comments:

fgrieu – in his comment – also provided a trick for cascading signatures when working with different RSA moduli. This, however, does not apply to your setting since you are not cascading signatures (maybe you want to do that?)

Your application scenario:

As CodesinChaos noted in his comment in response to your desired application, your approach still raises some questions.

A simple eCash protocol on blind signatures does not really require you to do that. There, you can assign different values for coins by setting up different signing key pairs for the bank (one for each value) and the coin (value $m$ in your case is simply a random element). If the merchant blacklists the unblinded value and signature pairs, then you can prevent doublespending. Although you will not achieve anonymity revocation in case of this event.

It is not clear for what purpose you want to include customers identites into the coins - maybe you want to have something like anonymity revocation? (why you therefore require another modulus $n_1$ - as well as use blinding without signing this part)? I think there is still potential for discussion.


PhD in cryptography using elliptic curves

If you want to end up in the industry, I strongly doubt a PhD is a good investment of your time, regardless of the rest of this discussion.

I believe a general purpose quantum computer, the kind that will send us all to relearn all our algorithm theory, is far from certain in 20 years. I won't even be surprised if someone publishes tomorrow a serious proof it can't be built. 10-20 years ago people were making similar predictions, and though quantum annealing seems to have moved forward, general quantum computers have not advanced much.

In the industry, people won't want to hire you because of your specific thesis and maybe not even because of your field of study. A PhD shows you are intelligent, capable of independent research, capable of finding and reading the latest literature, etc. These are marketable skills.

I read many PhD resumes on a daily basis. And though we do machine learning and artificial intelligence work, I won't throw out a cryptography PhD resume. However the real question with any PhD resume is: can they build production grade software? I believe our own requirements are common in the industry.


difference between leveled FHE and normal FHE scheme

FHE should be able to evaluate any circuit. Leveled FHE can evaluate circuits which have a bounded depth.

BGV was, I believe, the first to offer leveled FHE. The gain was in performance. By restricting to only certain depths (where the depth is calculated by looking at multiplication gates), they were able to remove the bootstrapping operation of Gentry's construction (which was very expensive) or at least spread out the bootstrapping.

Another benefit for leveled schemes is that you can remove the assumption of circular security, i.e., that you can safely encrypt your private key with your public key. We don't know (as far as I remember) how safe this is. Note that we can convert a leveled-FHE to an FHE scheme if we assume circular security though (see footnote 1 in the BGV paper).


If I understand your question correctly, you want to generate a short value $v(T)$ from a table $T$ such that if $T_1$ and $T_2$ have the same size and the same elements in each corresponding cell, then $v(T_1) = v(T_2)$, and if the tables have different sizes or different elements then $v(T_1) \ne v(T_2)$.

What you need for that is two ingredients:

A unique representation for tables.
A cryptographic hash applied to said unique representation.

“Unique representation” means that distinct tables have different representations. For example, if your table cells don't contain the character |, then | + T[0,0] + | + T[1,0] + || + T[0,1] + | + T[1,1] + | (where + is string concatenation) is a unique representation of a 2x2 table, and the representation generalizes to arbitrary-size tables with no collision. However, if your table cells can contain the character |, this representation is not unique: you cannot distinguish T[0,0] = a|, T[1,0] = b from T[0,0] = a, T[1,0] = b.

If you can't assume anything about the content of table cells, a convenient and secure method is to take a cryptographic hash of each cell independently, and build the hash of the table by hashing a string made up of hashes. (This is a special case of a Merkle tree.) Don't forget to include the table geometry in the representation. One way to do that is by putting the number of lines and columns at the beginning of the string:
$$v(T) = H(m + \mathtt{|} + n + \mathtt{|} + H(T[0,0]) + H(T[1,0]) + \dots + H(T[m,n])$$
where $+$ is concatenation, $m \times n$ is the table size, numbers are represented in decimal and hashes in hexadecimal. Another possible representation is to hash a row by hashing the concatenation of the hashes of the cells in that row, and hash the table by hashing the concatenation of the hashes of the rows.

Moving on to the question of how likely duplicate keys are, there are three cases to consider. Suppose that $H$ is a $k$-bit cryptographic hash.

All the data is essentially random. In this case, the chance that two tables have the same hash is negligible as long as you have significantly fewer than $2^{k/2}$ entries in the list of tables. This figure comes from the birthday problem. For example, a 128-bit hash lets you have several billion billion entries before the chance of a collision becomes high; with a billion entires, the probability is less than $10^{-18}$.
An attacker can choose some of the contents of the table, for example one of the fields is a free-form string, and the objective of the attacker is to craft two distinct tables with the same hash. This is an attack on the collision resistance of the hash. Breaking collision resistance can allow an attacker to inject a harmless record into your database, then substitute a bad one for it. When it comes to attacks, you can no longer reason in terms of probability, because attackers don't behave randomly. MD5's collision resistance is broken: there are cheap ways of generating strings with the same MD5 and with some content in common. Hash trees may be fine, but that depends on the exact structure of your data. So you must use another hash. SHA-256 is the standard hash nowadays.
An attacker wants to craft a table with the same hash as another table that is already in the database and not chosen by the attacker. This is harder than the previous attack; it's an attack on second preimage resistance. MD5 is not broken in this respect; however it would be a bad idea to use it because there is a risk that the attack on collision resistance could be improved to an attack on the second preimage.

TL;DR:

Encode the data in your table such that the representation is unambiguous.
You can take a hash of each piece, then take a hash of a sequence of hashes and other data: such hash trees are fine.
Don't use MD5. Use SHA2-256 (or SHA2-512).
If implemented correctly, not only is the probability of a collision too small to worry about (it's less than the probability that your processor will flip a bit at the wrong time), but better than that, there is no possibility for an attacker to arrange a collision.


How to encypt/decrypt messages after ECDH key agreement

You can't encrypt a message with ECDH alone, because all it gives you is a shared secret that you can't really control. Rather, you use that secret in a symmetric scheme like AES (generally after passing it through a KBKDF to convert from an ECDH result to a proper-length and less-structured symmetric key, which you then use as the key for symmetric crypto).


Are there any symptoms of a side channel attack on the target chip?

Side channel attacks are variably understood as excluding or including fault attacks. Let's start with the excluding definition, where side channel attacks monitor a device running some security-critical process, without deliberately attempting to alter its normal operation.

The most straightforward and perhaps earliest form of side channel attack is probing the internals of the circuit using contacts on the physical traces (e.g. of a PCB); that's called micro-probing when done directly on an IC. The archetypal goal of probing is capturing the data bus of a microprocessor system, letting one examine all that it manipulates. Some devices have dedicated sensors to detect probing; see e.g. figures 2 and 3 in Ross Anderson, Mike Bond, Jolyon Clulow, Sergei Skorobogatov Cryptographic Processors - A Survey, in proceedings or IEEE, 2006. On occasion, micro-probing indirectly cause misbehavior and can be detected as some fault attacks are in software, see last 5 bullets.

Many side channel attacks (including most with the keyword Differential) require many cryptographic computations to be performed. Counting the number of computations (with a carefully implemented power-loss-resistant counter in EEPROM or Flash) and limiting that number is a from of detection, and is effective if a small enough limit is functionally acceptable. Alternatively, the key can change regularly (e.g. every 100 uses), but typically that must be integrated in the specifications, and recovery in case of protocol errors can be an issue; and that's prevention rather than detection as asked.

In the special case of Power Analysis, it conceivably could be detected that a test setup inserts a resistor on Vcc or Gnd (the simplest option for a Power Analysis setup), and thus that the power supply voltage (which the device can measure) changes with DC power consumption (that the device can change by turning on or off some circuits, or changing a frequency divider). The effective series resistance of the power supply could thus be estimated to some degree, and attack suspected above some threshold. However, doing this has a risk of false positive (e.g. if the power contacts are dirty); and it could be circumvented by a better attack setup. I do not know that this line of defense is used.

Other forms of side-channel attacks seem basically undetectable to me. One can not hope to test if something is timing execution, monitoring EMI emission..

Fault attacks are detectable, high-security ICs (like those in many Smart Cards) have sensors for that, and high-security software has countermeasures trying to block these attacks by performing redundant checks. There are things like:

Vcc out-of-range or/and rapid change sensor.
Light sensor, to detect optical flash or laser pulses, as well as careless use  of the IC in lighted environment after epoxy removal or de-passivation.
Clk frequency out-of-bounds detector (glitching Clk used to be an effective fault attack in early Smart Cards; but the trend is internally generated clock).
Temperature-out-of-bound sensor.
Mesh(es) and associated sensors: one ore more mesh(es) (a long wired forming a regular pattern) is/are added on top of the IC or circuit, and it is hopped that probing will interfere with the mesh, activating some sensor: mesh-has-been-opened, meshes-have-been-shorted, capacitance-between-meshes surveillance (which has a chance to detect de-passivation). See this archived FlyLogic blog, read after Mesh Comparison.
Internal self-test: like stuck TRNG detector, parity check on bus or memory, or even dual CPUs performing the same operations concurrently with their result matched.
Checking results of cryptographic computations; the archetypal one is checking that $x\equiv y^e\pmod N$ after having computed $y=x^d\bmod N$ in RSA (especially if the computation of $y$ was using the CRT).
Redundant implementation and testing of critical states, like are the access rights granted by a proper PIN presentation.
Checksums on critical variables or code.
I imagine, much more..

Note: I have not much touched prevention (rather than detection) of Side Channel and Fault attack, which is a much wider subject.


Why does NaCl's crypto_secretbox for xsalsa20-poly1305 require the first 32 bytes to be zero?

The first 32 bytes of XSalsa20 output are used as key for the one-time-mac Poly1305. Poly 1305 needs a new 32 byte key for each message, using part of the key-stream is a natural way to obtain those.

Requiring those empty bytes makes implementing the API easier. The implementer only needs to call XSalsa20 on the zero padded input buffer once, receiving both the Poly1305 key and encrypting the message.

Without a padded input it's necessary to split the call to XSalsa20 into several calls, one to HSalsa, two to Salsa20 and a bit of copying. This is a bit annoying and incurs a minor performance hit.

IMO requiring zero padding is bad API design. This is an implementation detail that shouldn't be exposed to the user. APIs should be designed with the consumer in mind, not the implementer.


Why can ssh-keygen export a public key in PEM PKCS8 format?

What you have here is indeed a structure called SubjectPublicKeyInfo. It's usually part of an X.509 certificate, but it is often also used separate from a certificate. It's, for instance, the default encoding for RSA public keys in Java and - if I'm not mistaken - OpenSSL.

You can view the complete structure here and compare it with the SubjectPublicKeyInfo structure defined here. Of course, you'll only see it up to the BIT STRING. The BIT STRING itself contains the structure defined as RSAPublicKey here. That the BIT STRING contains the RSAPublicKey structure is identified by the 1.2.840.113549.1.1.1 (RSAEncryption) object identifer (OID).

It's certainly not PKCS#8. That's indeed for private keys.

Note that what you are currently showing is the PEM encoding of said SubjectPublicKeyInfo. The PEM structure, sometimes also called "ASCII armor", makes it possible to send binary data over text interfaces, e.g. mail. It consists of the header, the footer and the base 64 encoding of the binary contents.


Calculating differentially private average of a dataset

Welcome to Crypto.SE, and thank you for your interest in our open-source DP tooling! To implement BoundedMean, we actually use Algorithm 2.4 from Differential privacy: From Theory to Practice, not Algorithm 2.3.
The reason is because Algorithm 2.3 is not actually differentially private. To the best of my knowledge, the reference that exists for this fact is a footnote in my PhD thesis (at the bottom of this HTML page, or on page 211 of the PDF version). When implementing BoundedMean, we also tried some of the others algorithms proposed in this book, and Algorithm 2.4 was the one that seemed to work best empirically.
Now, to answer your question about adding noise directly: when building DP algorithms, you are only allowed to make decisions based on differentially private data. Even something as simple as "what is the scale of the noise we are adding" can actually leak more information than expected. In your question, $N$ is a private quantity, since it can go up or down by one if a user is added or removed to the dataset. This means that you can't use it as an argument to the noise without adding noise to it first, to make it differentially private as well (and count it towards the privacy budget).