Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?

Yes it is possible, and in fact, it has been done, with partial homomorphic encryption (for example in this paper) and somewhat homomorphic encryption (here and here).

The main difference is that a SNARG which uses these primitives instead of pairings is not publicy verifiable anymore. Indeed, suppose to simplify that you are supposed to perform a "multiplication" and some additions using a pairing, and that the verification should succeed if the exponent in 0 in the end. When doing so with the pairing, the final "zero test" can be publicly checked by everyone. When replacing it by a homomorphic encryption scheme, however, what you end up with is an encryption of zero. Checking that this does encrypt zero requires knowing the secret key of the scheme. For this reason, these SNARGs are restricted to being designated-verifier: they can only be verified by the owner of a specific secret key (and this secret key cannot be made public, since knowing it allows to forge a proof).


How to understand "homomorphically decrypting" in bootstrapping?

Does it mean decrypt to the plaintext first then recrypt again?

No. It doesn't. It just mean to run a "homomorphic version" of the decryption function. Since homomorphic evaluation just use homomorphic operations and these operations always return ciphertexts, the result of homomorphic decryption is also a ciphertext. And since the decryption removes the noise, this new ciphertext is fresh.

Think of evaluating homomorphically as a function, which we will call $Eval$.

So, homomorphically evaluating any function $f$ on arguments $m_0$, $m_1$, ..., $m_\ell$ means to execute $Eval(pk, f, [m_0]_{pk}, [m_1]_{pk}, ..., [m_\ell]_{pk})$, which returns $[f(m_0, m_1, ..., m_\ell)]_{pk}$.

(Here I'm using $[m]_{pk}$ to denote the encryption of $m$ under the public key $pk$).

That is, $Eval$ returns an encryption of the function evaluated in the arguments, given the function, encryptions of those arguments, and the public key used to encrypt them.

Now, let's say you have a pair of keys $sk$ and $pk$ and you want to refresh a ciphertext $c = [m]_{pk}$. Then, you have to homomorphically decrypt $c$. To do so, replace $f$ by $Dec$. Also, the arguments of $Dec$ are $sk$ and $c$, so, you should use $[sk]_{pk_1}$ and $[c]_{pk_1}$, for some public key $pk_1$. Then, we get:

$\begin{align}
Eval(pk_1, Dec, [sk]_{pk_1}, [c]_{pk_1}) &= [Dec(sk, c)]_{pk_1}\\
                                       &= [m]_{pk_1}\\
\end{align}$

that is, a fresh encryption of $m$ under the public key $pk_1$.

Note that this $pk_1$ may be a new public key, and in this case we will need a new secret key $sk_1$ to decrypt $[m]_{pk_1}$, or it can be equal to the original public key $pk$, and in this case we are supposing circular security...


The way a stream cipher works, traditionally, is that $E_k$ produces a pseudorandom bitstream (the keystream) based solely on the key $k$. The message is then encrypted by XORing the message with the keystream. This has a number of consequences, notably that if you know both the plaintext and ciphertext, it's trivial to compute the keystream (if $C=M\oplus K$, then $K=M\oplus C$). If you know the keystream, you can then encrypt messages of your choice up to the length of that keystream, even without the actual key.

For this method, it's actually far, far, far worse. The attacker doesn't even need m to do his attack; if you know the plaintext corresponding to some part of a ciphertext, you can then modify the ciphertext so that that part decrypts to whatever you want. For instance, if you know the first 32 bits are a timestamp and know the timestamp $t_1$ (so the message is $t_1||M$), you can then XOR the first 32 bits of the ciphertext with $t_2\oplus t_1$ to get a new ciphertext that decrypts to $t_2||M$.

The lesson is that stream ciphers don't hold up to active attack. That's OK; they're not meant to. To ensure that a ciphertext wasn't tampered with, you need a proper message authentication code like HMAC, which does verify that the person making the message had access to the key. The lesson for other uses of stream ciphers is that you want a message-specific initialization vector so that you don't have the same keystream on all messages encrypted with the same key; then the keystream is $E(k,IV)$, and the IV need not be secret (so you can just slap it on the front of the message). This isn't good to rely on for authentication, though; a MAC is what's made for message authentication.


In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic?

In the general case of for auxiliary-input zero knowledge, it is impossible for the prover to be deterministic; see Definitions and properties of Zero-Knowledge proof systems by Goldreich and Oren. In the random oracle model, everything is different, so I don't want to go there. However, I will say that it is not true that the prover is deterministic is Fiat-Shamir. Fiat-Shamir is a way of converting some honest-verifier ZK protocols to fully malicious ones. Almost all honest-verifier ZK protocols considered have a probabilistic prover, so the Fiat-Shamir version also has a probabilistic prover.


Technical feasibility of decrypting https by replacing the computer's PRNG

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels?

A strong stream cipher's output is random and unpredictable to anyone not knowing the key. See where this is heading? Just because something looks random doesn't mean it's random.

  2 - If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

If you can predict the PRNG you can basically predict the secrets used for key exchange, and from that deduce the shared secret. Then you can simply decrypt the communication.


How secure is AES in a critical situation?

In practice, because they will target the easiest/weakest/least expensive link in the chain, they would attack you.

It is infinitely easier to threaten to crack someone's kneecaps to obtain their password then to crack an AES key.

Supposing they wanted to attack the cryptography specifically, for practice or fun, they would probably extract the key via a timing attack. This is not technically an attack on AES, it technically is an attack against a simple/common/fast implementation of AES. This is one of the few arguments I can think of for using an algorithm other then AES. Either that, or ensure that you utilize a constant time implementation of AES.

If your data is that confidential, then it is probably wise to utilize an algorithm that is not as vulnerable to leakage of information via side channels. Additionally, it's probably not safe to trust just software anymore: You would want a hardware security module.

Then, you need to become concerned with attacks against the hardware. You might opt for an algorithm that has been design with advanced counter-measures in mind, such as one based on the Keccak permutation.


Maybe it doesn't help to recover the private key, but the private key is seldom the object of interest in a real application—instead, your private conversations, your money, etc., are the objects of interest.  Hashing the points is important for security of the composition of ECDH with another cryptosystem.  This is both for the benefit of the downstream cryptosystem, and for confidence in the DH security.

Standard encoding of uniform random curve points into bit strings is a bad way to get a uniform distribution on bit strings—so bad it was one of the first problems publicly reported about Dual_EC_DRBG in a comment by Gjøsteen[1] before everyone realized there was a back door.

Maybe the related-key attacks of Biryukov and Khovratovich on AES-256[2] don't specifically apply to the encodings of points satisfying $y^2 = x^3 + a x + b$ on your curve, but it's more confidence-inspiring to choose a distribution on keys much closer to uniform with a better hash function like HKDF-SHA512—you don't have to think about possible interactions.  For instance, what if you're using a curve over a binary field, and you use the key for a polynomial evaluation MAC over the same binary field?
Use of a standard hash function like SHAKE128 justifies using the standard argument of Bellare and Rogaway converting a decisional oracle into a computational oracle[3].  The cost of breaking the system can be studied by studying the costs of implementing the computational Diffie–Hellman problem of inverting $g^{x y}$ rather than the potentially easier decisional Diffie–Hellman problem of distinguishing $(g^x, g^y, g^{x y})$ from $(g^x, g^y, g^z)$ for uniform random $x, y, z$.

Maybe you don't believe in the random oracle model, but it is hard to imagine that the hashing step—whose cost is negligible compared to the elliptic curve scalar multiplication you just performed—could make the attacker's job easier; this argument suggests that it generally makes the attacker's job much harder.

E.g., Cheon's attack[4][5] (paywall-free) computes the secret exponent $x$ given $g, g^x, g^{x^2}, \dots, g^{x^d}$ in $O(\sqrt{p/d} + \sqrt d)$ group operations where $p$ is the order of $g$ and $d \mid p - 1$, or $O(\sqrt{p/d} + d)$ group operations if $d \mid p + 1$.  An oracle for $h \mapsto h^x$ can be used to find these powers of $g$ by iterating it, while an oracle for $h \mapsto H(h^x)$ cannot.

Consequently, the security conjecture of X25519 by Bernstein[6], for example, is that an adversary who knows everyone's public key $\operatorname{X25519}(n_1, 9), \operatorname{X25519}(n_2, 9), \dots$, and has oracles for $q \mapsto H(\operatorname{X25519}(n_i, q))$, can't do much better to generically break cryptosystems downstream of $H(\operatorname{X25519}(n_i, \operatorname{X25519}(n_j, 9)))$ than paying for the energy to compute $2^{125}$ curve additions needed by Pollard's $\rho$.


Designing a hash function from first principles rather than depending on heuristics

You should design your hash on the bit level.

Regardless how you design your hash, at the end of the day you have a $m$ booleans functions for each output bit from an arbitrary $n$ bits of input.

Some properties of boolean functions

All your output bits will be some boolean function of your input bits.

All boolean functions can be turned into the so called algebraic normal form (ANF), which means your input bits are combined using AND and XOR operators only.

XOR operator is just addition modulo 2. AND operation is just multiplication modulo 2. And these operations are usually denoted with multiplication and addition respectively. In modulo 2 arithmetic addition and subtraction are the same operation, so don't be surprised when I use + when talking about differences.

The modulo 2 arithmetic forms a field, which means all your usual algebraic identities you know are true.

So now the operation of your cipher is just a system of $m$ equations for $n$ bits of input.

Due to nature of modulo 2, a lots of things cancel. Powers cancel: $0^n = 0$, $1^n = 1$. Even coefficients cancel: $x + x = 2x = 0$.

This means the equations for the output is simpler: The only possible coefficient is 1 (or 0 which means a missing term). And all of them is on the first power.

Nonlinearity

If you try to make a cryptographic hash function that only uses XOR and shifting, the equations will be linear even after infinitely many rounds, now the analyst is just a single Gauss elimination away from solving it and now they have the ability to create arbitrary preimages.

In order to avoid that, you need to make your equations non-linear by using the AND operator. Hashes do all sorts of shifting and XOR-ing but this non-linear step is what makes them secure.

But having non-linear terms are not enough. You must make sure the attacker cannot effectively cancel out the non-linear terms out of your equations by fixing some inputs to 1 or 0. Also you need to make sure the terms will not cancel if the attackers takes the difference of two equations. If you have the formula $xy + x + y$ for one and another formula $xy + y + z$ for another bit. Adding these two will give $x + z$ which is now linear and allows the attacker to solve it to get the relationship between two out bits.
Every independent linear equation an attacker can create will reduce the security of your hash with 1 bit. One way to mitigate this is making sure all the functions for the output bits contain different terms. In the previous example if we replace the $xy$ to $xz$ to the second formula. Adding together will not yield linear equation then. But if the attacker fixes the $x$ to a constant value then it becomes a linear equation. This is probably the most challenging part of designing your hash.

Balance

Another thing to consider is balance. You want your hash behave like the so called random oracle. This is important if you want your hash useful as a cryptographically secure random number generator for example. You should make sure all your bits in the resulting hash have 50% chance to be 1. The XOR operator have a very good property that makes it possible: in $a + b$, if either term have 50% chance to be 1, the entire expression will have 50% chance to be 1. To prove this let's consider $A$ and $B$ the probability that $a$ and $b$ are 1 respectively. The probability that $a + b$ is 1 is: $A(1-B) + B(1-A)$. That is either $A$ is 1 and B is 0, or $A$ is 0 and $B$ is 1. If we expand this we have: $A + B - 2AB$. Substituting 0.5 for $A$ gives: $0.5 + B - B = 0.5$. So as long as you can ensure there is at least one term in the final equations that has 50% chance to be 1 independent from other terms, then that will ensure your function is balanced. The simplest way to achieve this, is making sure at least one first order input bit term appears in the functions of all output bits and it will anchor the 50% chance.

Strict avalanche criterion

The next thing to consider is the strict avalanche criterion (SAC).  This means if you change any bit (or more generally any bit pattern) in the input, all bits in the output must have 50% chance to change. Failing to do so can give information to the attacker about the input, and makes your hash vulnerable to differential cryptanalysis. Let $H(x)$ the original hash, let $H(x + \alpha)$ the hash of the changed input. In $H(x) + H(x + \alpha)$ the changed bits will be set. You must make sure this function is balanced too so any bit has 50% chance to be set. Let's se what it means. Let x be the bit we changed. Let $xy + xz + yz$ the expression we test. Let $\bar x$ be the flipped $x$. So the test expression will be: $(xy + xz + yz) + (\bar xy + \bar xz + yz) = xy + xz + \bar xy + \bar xz = (x + \bar x)y + (x + \bar x)z = y + z$. Basically terms that doesn't cointain $x$ will be removed, and $x$ will will be removed from terms that contain $x$. This implies that in order to reach SAC it's a necessary condition that  every output bit depends on every input bit. If there is an output bit that doesn't depend on some input bit, your hash will fail to demonstrate SAC if that bit is flipped.

So now how can you make sure that $H(x) + H(x + \alpha)$ is balanced? There is a class of boolean functions that ensure that. They are the so called bent functions. The simplest bent function is just $xy$ where $x$ and $y$ are independent bits. These bent functions can be combined together by adding them up, so $ab + cd + ef + gh$ will be a bent function too ($a$-$h$ are independent bits). There are other more complex construction too (but I didn't find good examples). So if you want to have SAC, use bent functions. But bent functions come with a drawback: they can't be balanced. There will be a $2^{-n/2}$ bias releative to the 50%.
But this bias approaches zero as the number of bits reaches infinite.

My summary is no way exhaustive.

As the time passes and more and more attacks are discovered so new hash designs need to satisfy more and more conditions, balance, SAC and nonlinearity is a good starting point but probably not enough (I don't know all attacks).


What's the difference between Trapdoor Functions and Encryption Functions?

Typically, trapdoor functions are used in asymmetric cryptography. For instance, if you have a RSA public key $(n,e)$, it is easy to compute a cipher text $c = Pad(m)^e\mod n$, but hard to get back to $Pad(m)$ from $c$ even if you have the public key. In order to easily reverse the operation you need the corresponding private key $d = e^{-1}\mod\phi(n)$. The reason RSA is a trapdoor function in this sense, is because it is based on the hardness of the Integer Factorization Problem. You can't calculate the private exponent $d$ unless you know $\phi(n)$, and you can't calculate $\phi(n)$ unless you know the prime factors of $n$.

AES and other symmetric ciphers are not trapdoor functions in this sense. You are only able to compute $c = AES_k(m)$ if you got the key $k$, but if you got this key it is equally easy to compute $m = AES_k^{-1}(c)$


What are the smallest possible RSA private and public keys?

Per the definition of RSA in PKCS#1v2.2

In a valid RSA private key, the RSA modulus $n$ is the product of $u$ distinct odd primes $r_i$, $i=1$, $2$, …, $u$, where $u\ge2$.

That makes $n=3\cdot5=15$ the smallest public modulus.

and the RSA public exponent $e$ is an integer between $3$ and $n–1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

That makes $e=3$ the smallest public exponent. $(n,e)=(15,3)$ happens to be a valid public key, since $\lambda(15)=4$ and $\operatorname{GCD}(3,4)=1$.

The RSA private exponent $d$ is a positive integer less than $n$ satisfying $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

That makes $d=1$ the smallest private exponent. It corresponds e.g. to $(n,e)=(15,5)$. Encryption (and decryption) with that key is identity, but there is no worded prescription against that.

If we prohibit $d=1$, then $d=3$ becomes the smallest private exponent, matching $(n,e)=(15,3)$. More generally, different definitions of RSA yield different lower limits. Allowing $u=1$, $e=1$, and removing the prescription that $r_i$ is odd, makes $(n,e,d)=(2,1,1)$ acceptable. For FIPS 186-4, the smallest $n$ is 1024-bit, likelyA $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; the smallest $e$ is $65537\,$; and the smallest $d$ isB $2^{512}+1$.

A: Under the plausible assumption that each of $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$,  $\lfloor2^{1023/2}\rfloor+2^{412}+430$ and $\lfloor2^{1023/2}\rfloor+2^{412}+432$ has a prime factor at least $2^{100}$, which I did not check.
B: Some valid matching public key $(n,e)$ exists with high likelihood. It's a mildly interesting problem to exhibit one.


Differences between methods of hardware random number generators

The Electrical Engineering SE would be a good resource for questions about specific sources of noise. Which method is best is not a a question for which you will find a good answer to. The "quality" of any method depends on which models of electronic components are used. They have different properties that don't make direct comparison easy:

Power use: Two sources that produce the same amount of "randomness" per second can have drastically different power requirements.
Price: How much you have to pay matters. Just because something is more expensive doesn't mean it's better at producing randomness. Even if it was it might not make a difference because things are either sufficiently unpredictable or they are not. Cheap components may work well enough. They may work better. They may be worse.
Rate: How much randomness can you extract from a single? How much per unit of time and how much per unit of power?
Unpredictability and Leaks: How much noise is known only to the HWRNG versus how much noise can be read by an outsider. (This is the reason you should not rely on atmospheric noise. Yes it is unpredictable, but two people in the same area on this planet will read somewhat similar noise signals.) What about side channel risks and protection? It doesn't do much good extracting noise from a random process if the HWRNG leaks information based on how much power it draws while generating random numbers. Or if you can literally hear part of the noise signal coming form capacitors.
Life-time and Stability - The behavior of some components change as they age. Some components may wear out the longer you use them. Some may change even without use. If you calibrate a system for producing noise as it is now, you might end up with a more predictable HWRNG sometime in the future.
Production - Variations between components of the same type means you might not be able to buy commodity components and use them interchangeably. Even if two components came from the same manufacturer. One should test the components and design a HWRNG that isn't too sensitive to variation.
Tamper-ability - Physical access is devastating but remote attacks can be too. I'm sorry I don't have links, but one method used in remote attacks is, I think, referred to as "illuminating" a device. It's when you "shine" an electromagnetic signal at a device. It can turn into a fault injection attack (making unpredictable behavior predictable) or a side channel attack (causing secret information to be bounced back.)

From a cryptography perspective the source of "randomness" or "unpredictability" does not really matter. We just need a signal that has entropy (a term for how much unpredictability there is in a signal) and a means of estimating how much entropy a system has. No one should be using raw readings from signals as their binary output.

Real HWRNGs typically output "whitened" noise. The raw signals from a noise-producing system do not necessarily (almost certainly don't) look like samples from a uniform statistical distribution. The input signals need to be processed to extract randomness. They're not 100% random so the bandwidth of the signal coming out will be less than the bandwidth going in. That's where the entropy estimate comes in. You do not want to emit 100 bits of random output if your un-whitened noise signal is only as unpredictable as 10 coin flips. (We say the input has only 10 bits of entropy in this case.)

Informally speaking the randomness is typically extracted by something like a cryptographic hash function. The signal going in is digitized and fed to the hash function. When enough data is processed, say an estimated 256 bits worth of entropy, the hash function is evaluated and the result is used as a seed/key for a deterministic random number generator. As long as the entropy estimator does not over-estimate the amount of entropy then this hybrid-system is a sound construction.

From this crypto-perspective what matters is efficiency (power use, bits per second, unpredictability) and security (unpredictability, stability, lack of side channels, difficulty with tampering). How we can get that out of hardware is a different type of problem in the realm of physics and electrical engineering.


Bilinear pairing arithmetic - cryptographic accumulators

This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.

First, if the prover knows $s$, it doesn't need to know the $e_i$'s to create membership witnesses.
It can simply raise the accumulator $\mathsf{acc}$ to $1/(e_k + s)$:
\begin{align*}
\mathsf{wit}_{e_k} &= \mathsf{acc}^{\frac{1}{e_k + s}} = {g^{f(e,s)/{(e_k + s)}}} =  g^{\prod_{i\ne k}{(e_i+s)}}
\end{align*}

This brings me to my second point: knowledge of $s$ allows the prover to create fake membership witnesses for any $e$ that was not accumulated. This is because the prover can compute $\frac{1}{e + s}$ for any $e$.

So, yes, computing $f(e,s)/(e_k+s)$ and then raising $g$ to it is one way to calculate the witness, but it's a bad idea: the prover can easily create fake witnesses for any non-accumulated $e$ if it knows $s$.
Computing witnesses in this way only makes sense when there's a trusted party that knows $s$.
This trusted party computes and outsources witnesses to an untrusted "prover" who merely relays these witnesses to verifiers (i.e., the 2- or 3- party models of authenticated data structures).

Requiring a trusted party that knows $s$ is unreasonable in many applications.
In practice, we want to prevent the (untrusted) prover from faking witnesses, by ensuring it does not know $s$.
We can do this via a trusted setup phase that gives the prover public parameters $\left(g^{s^i}\right)_{0\le i\le q}$ but does not give him $s$.
This trusted setup phase is run by some trusted "guy in the sky," which in practice can be implemented via MPC protocols (see Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model).
Here $q$ is a strict upper bound on the number of elements you will ever accumulate.

Now, in order to commit to a set $A = \{e_1, \dots, e_n\}, n\le q$ of items, you first have to compute the coefficients of the polynomial $f(e, x)$ using Lagrange interpolation in $O(n^2)$ time, Newton interpolation in $O(n^2)$ time or FFT interpolation in $O(n\log^2{n})$ time.

Note that you don't need to know $s$ to interpolate.
Consider $A = \{1,2,3\}$. Its polynomial $f_A(x) = (x-1)(x-2)(x-3) =
x^3 - 6 x^2 + 11 x - 6$, so its coefficients are $(1, -6, 11, -6)$.

Once you have the coefficients $\{c_1, \dots, c_n\}$ you can compute the accumulator $acc$ by raising the $\left(g^{s^i}\right)_{0\le i\le n}$ public parameters to the coefficients:
\begin{align*}
acc &= \left(g^{s^n}\right)^{c_n} \left(g^{s^{n-1}}\right)^{c_{n-1}} \dots (g^s)^{c_1} \left(g\right)^{c_0}\\
  &= g^{c_n s^n} g^{c_{n-1} s^{n-1}} \dots g^{c_1 s} g^{c_0}\\
  &= g^{c_n s^n+ c_{n-1} s^{n-1} + \dots + c_1 s + c_0}\\
  &= g^{f(e,s)}
\end{align*}

For example, for our set $A$ above, the prover computes its accumulator as $(g^{s^3})^1 (g^{s^2})^{-6} (g^{s})^{11} g^{-6} = g^{s^3 - 6 s^2 + 11 s - 6} = g^{f_A(s)}$.
Note that the prover does not need $s$ to compute $g^{f_A(s)}$ as long as it has the public parameters.
In my experience, most accumulator papers do not explain this step, partly because they only look at the two- or three-party models of authenticated data structures where there actually exists a trusted party that knows $s$.
(In other words, the "Hey, let's play with fire!" model.)

To answer your other questions,

  While computing $f(e,s)$, do I have to do modular arithmetic on $P$ where $P$ is a prime number representing the order of group $\mathbb{G}$?

If you know the trapdoor $s$ (i.e., insecure mode), then yes, computing $f(e,s)$ involves adding and multiplying things modulo $P$ as per its definition.

If you don't know the trapdoor $s$, then computing $f(e,s)$ involves adding, multiplying and inverting numbers (for Lagrange and Newton) modulo $P$. If you're using FFT interpolation, it also involves roots of unity in the field of order $P$ (i.e., the field "in the exponent").

  Also, one paper stated that it is impossible to create a witness for an element which is not accumulated into it. Will anybody please elaborate on it?

As I described before, the prover cannot fake witnesses only when the prover does not know the trapdoor $s$. I can't find the security proof in Lan Nguyen's original paper on accumulators, but it's a reduction to $q$-Strong Diffie-Hellman ($q$-SDH). The intuition behind why membership witnesses are secure is that without the trapdoor, nobody can compute any pair of the form $(e, g^\frac{1}{e + s})$.

  By dividing $f(e,s)$ by $(e_k+s)$ one can calculate a witness value.

Yes, but remember that this requires the prover to know the trapdoor, which is not secure (unless you're in the "Hey, let's play with fire!" model).

  Is there any way to distinguish between the witness (let me call it) values that where computed when $e_k$ is accumulated in $f(e,s)$ and when it is not accumulated $f(e,s)$?

Before I can answer this question, you have to clarify what element(s) these witnesses are for and what does the adversary know? Do they know the elements accumulated in the two accumulators?


Stream cipher vs OTP, with /dev/urandom and secure key exchange

Are there other factors to consider? (Note: I believe the staff can store their OTP securely).

The obvious issues are authentication of data and storage of keys.  I will presume the data being encrypted is personal to each staff member, and is not to be transmitted between staff.
You note that staff can store their OTP securely, on USB drives.  What happens if they get lost?  If the storage used for keys cannot be lost and is secure, you could just store the data there.
I think you have to question how secure a physical piece of storage can actually be.  It's certainly never close to being secure against unlimited physical power in a manner analogous to information-theoretic security.
Data authentication would need to be carefully implemented in order to not affect the security of the scheme, and would require using pad data.  Per Wikipedia:

Universal hashing provides a way to authenticate messages up to an arbitrary security bound (i.e., for any $p > 0$, a large enough hash ensures that even a computationally unbounded attacker's likelihood of successful forgery is less than $p$)

Per the helpful user Poncho:

you can do data authentication with an OTP (and preserve the informational security properties); for example, using an epsilon almost-universal hash function (with OTP providing both the UH keys and xoring the hash output)

Not using data authentication would mean that the data could be tampered with so it seems unlikely that this would be the case.


Can machine learning/AI lower the security existing cryptographic protocols similar to quantum computers?

No.  Machine learning and AI techniques do not fundamentally change the computational capabilities of an adversary like a quantum computer does, no matter how much hype is in the air around ML and AI.


AES-128 Decryption in Objective-C just slightly off

When you get the first part of the decryption wrong, but the rest correct, it almost always means that you got the IV wrong.

However, with CBC mode, what usually happens is that you get the first 16 bytes wrong; instead, you got only 6 bytes wrong; that may indicate that you got the first 6 bytes of the IV wrong (and the other 10 bytes correct).

In addition, I notice that, in your code, you're handing an 8 byte IV to the API; this is odd, because CBC mode takes a 16 byte IV.

I don't know the API you're using (and I certainly don't know the assumptions that the DSP has used), and so I'm at a loss at helping you any further -- however, you were looking for suggestions as to where to look...


How to identify RSASSA-PSS from rsaEncryption OID?

There are two different identifiers in a certificate, the algorithm of the public key for the certificate and the algorithm of the signature from the issuer.  The two don't have to even be the same algorithm family (e.g. RSA CA certs can sign ECDSA certs, and vice versa).

In the following certificate parse structure the algorithm identifiers starting at offset 24 and 529 (certificate.tbsCertificate.signature and certificate.signatureAlgorithm) identify that the issuing authority signed the certificate with RSA PKCS#1 with SHA-1 (id-sha1WithRSAEncryption).

The algorithm identifier at offset 371 (certificate.tbsCertificate.subjectPublicKeyInfo.algorithm) identifies that the public key contained within this certificate is an RSA key (id-rsaEncryption).

If the issuing authority had signed the certificate using RSASSA-PSS then the certificate.signatureAlgorithm and certificate.tbcCertificate.signature values would have the RSA-PSS object identifier (1.2.840.113549.1.1.10) and their parameters would convey the PSS data.

$ openssl asn1parse -in rsa384.cer -i
    0:d=0  hl=4 l= 591 cons: SEQUENCE
    4:d=1  hl=4 l= 521 cons:  SEQUENCE
    8:d=2  hl=2 l=   3 cons:   cont [ 0 ]
   10:d=3  hl=2 l=   1 prim:    INTEGER           :02
   13:d=2  hl=2 l=   9 prim:   INTEGER           :C42D621149D3EE63
   24:d=2  hl=2 l=  13 cons:   SEQUENCE
   26:d=3  hl=2 l=   9 prim:    OBJECT            :sha1WithRSAEncryption
   37:d=3  hl=2 l=   0 prim:    NULL
   39:d=2  hl=3 l= 146 cons:   SEQUENCE
   42:d=3  hl=2 l=  11 cons:    SET
   44:d=4  hl=2 l=   9 cons:     SEQUENCE
   46:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
   51:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :US
   55:d=3  hl=2 l=  19 cons:    SET
   57:d=4  hl=2 l=  17 cons:     SEQUENCE
   59:d=5  hl=2 l=   3 prim:      OBJECT            :stateOrProvinceName
   64:d=5  hl=2 l=  10 prim:      UTF8STRING        :Washington
   76:d=3  hl=2 l=  16 cons:    SET
   78:d=4  hl=2 l=  14 cons:     SEQUENCE
   80:d=5  hl=2 l=   3 prim:      OBJECT            :localityName
   85:d=5  hl=2 l=   7 prim:      UTF8STRING        :Redmond
   94:d=3  hl=2 l=  24 cons:    SET
   96:d=4  hl=2 l=  22 cons:     SEQUENCE
   98:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  103:d=5  hl=2 l=  15 prim:      UTF8STRING        :Microsoft Corp.
  120:d=3  hl=2 l=  32 cons:    SET
  122:d=4  hl=2 l=  30 cons:     SEQUENCE
  124:d=5  hl=2 l=   3 prim:      OBJECT            :organizationalUnitName
  129:d=5  hl=2 l=  23 prim:      UTF8STRING        :.NET Framework (CoreFx)
  154:d=3  hl=2 l=  32 cons:    SET
  156:d=4  hl=2 l=  30 cons:     SEQUENCE
  158:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  163:d=5  hl=2 l=  23 prim:      UTF8STRING        :RSA 384-bit Certificate
  188:d=2  hl=2 l=  30 cons:   SEQUENCE
  190:d=3  hl=2 l=  13 prim:    UTCTIME           :160302165904Z
  205:d=3  hl=2 l=  13 prim:    UTCTIME           :160401165904Z
  220:d=2  hl=3 l= 146 cons:   SEQUENCE
  223:d=3  hl=2 l=  11 cons:    SET
  225:d=4  hl=2 l=   9 cons:     SEQUENCE
  227:d=5  hl=2 l=   3 prim:      OBJECT            :countryName
  232:d=5  hl=2 l=   2 prim:      PRINTABLESTRING   :US
  236:d=3  hl=2 l=  19 cons:    SET
  238:d=4  hl=2 l=  17 cons:     SEQUENCE
  240:d=5  hl=2 l=   3 prim:      OBJECT            :stateOrProvinceName
  245:d=5  hl=2 l=  10 prim:      UTF8STRING        :Washington
  257:d=3  hl=2 l=  16 cons:    SET
  259:d=4  hl=2 l=  14 cons:     SEQUENCE
  261:d=5  hl=2 l=   3 prim:      OBJECT            :localityName
  266:d=5  hl=2 l=   7 prim:      UTF8STRING        :Redmond
  275:d=3  hl=2 l=  24 cons:    SET
  277:d=4  hl=2 l=  22 cons:     SEQUENCE
  279:d=5  hl=2 l=   3 prim:      OBJECT            :organizationName
  284:d=5  hl=2 l=  15 prim:      UTF8STRING        :Microsoft Corp.
  301:d=3  hl=2 l=  32 cons:    SET
  303:d=4  hl=2 l=  30 cons:     SEQUENCE
  305:d=5  hl=2 l=   3 prim:      OBJECT            :organizationalUnitName
  310:d=5  hl=2 l=  23 prim:      UTF8STRING        :.NET Framework (CoreFx)
  335:d=3  hl=2 l=  32 cons:    SET
  337:d=4  hl=2 l=  30 cons:     SEQUENCE
  339:d=5  hl=2 l=   3 prim:      OBJECT            :commonName
  344:d=5  hl=2 l=  23 prim:      UTF8STRING        :RSA 384-bit Certificate
  369:d=2  hl=2 l=  76 cons:   SEQUENCE
  371:d=3  hl=2 l=  13 cons:    SEQUENCE
  373:d=4  hl=2 l=   9 prim:     OBJECT            :rsaEncryption
  384:d=4  hl=2 l=   0 prim:     NULL
  386:d=3  hl=2 l=  59 prim:    BIT STRING
  447:d=2  hl=2 l=  80 cons:   cont [ 3 ]
  449:d=3  hl=2 l=  78 cons:    SEQUENCE
  451:d=4  hl=2 l=  29 cons:     SEQUENCE
  453:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Subject Key Identifier
  458:d=5  hl=2 l=  22 prim:      OCTET STRING      [HEX DUMP]:0414E451B61668BCEA124E09FE0A9E36B13865957515
  482:d=4  hl=2 l=  31 cons:     SEQUENCE
  484:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Authority Key Identifier
  489:d=5  hl=2 l=  24 prim:      OCTET STRING      [HEX DUMP]:30168014E451B61668BCEA124E09FE0A9E36B13865957515
  515:d=4  hl=2 l=  12 cons:     SEQUENCE
  517:d=5  hl=2 l=   3 prim:      OBJECT            :X509v3 Basic Constraints
  522:d=5  hl=2 l=   5 prim:      OCTET STRING      [HEX DUMP]:30030101FF
  529:d=1  hl=2 l=  13 cons:  SEQUENCE
  531:d=2  hl=2 l=   9 prim:   OBJECT            :sha1WithRSAEncryption
  542:d=2  hl=2 l=   0 prim:   NULL
  544:d=1  hl=2 l=  49 prim:  BIT STRING


How do I construct a 256-bit hash function from 128-bit AES?

HMAC is a specific construction which aims at providing a message authentication code. HMAC is defined over a hash function, something which AES is not.

So if your question is really about having HMAC, not just any MAC, and using an AES primitive, then your question becomes: how can we build a hash function out of a block cipher ? This is not an easy question, especially if the block cipher uses blocks which are smaller than the intended hash function output size. You could investigate ECHO, a former SHA-3 candidate, which received a reasonably fair share of analysis by many cryptographers, who found no actual problem in it. ECHO is built upon some constitutive parts of AES, and can benefit from most hardware accelerators for AES.

On the other hand, if you just want a MAC (not specifically HMAC), and have an available AES primitive, then I recommend CBC-MAC (just don't use the exact same key to encrypt data !). This will yield a 128-bit MAC. A 256-bit MAC is a weird requirement, since 128 bits ought to be enough to provide adequate security (if 128 bits are not enough, then the attacker is way more powerful than the whole of Mankind, including all governments, agencies, private corporations and mafias -- and at that point you probably have more trouble than a possibly weak MAC: for all practical purposes, the attacker is God).

One could imagine defining a 256-bit block cipher with a Feistel network where the confusion function is an AES instance, with enough rounds and distinct round keys -- like what the DEAL block cipher did with DES, during the AES competition. Then CBC-MAC on that block cipher would yield a 256-bit MAC. But custom building of block ciphers or other cryptographic primitives is not recommended at all since it is hard to get right, and you cannot test for the security of the result.


Differential Cryptanalysis for Hash functions

In the case of block ciphers, differential cryptanalysis aim to measure the changes between inputs and outputs with a probability. The goal is to predict what the result will be before the last round and try to extract the key.

For hash functions, your aim is to find a second-pre-image.

I will take Keccak as an example. It is a sponge construction interweaved with 24 iterations of a round function $\text{Keccak-$f$}$.

How does it work (very simple version)?

Analyse the round function and retrieve its differential probabilities or interesting properties (here $\text{Keccak-$f$}$ has some invariants). Consider $(a_0 \implies a_1)$ where [$a_0$/$a_1$] is the difference [before/after] the application of the round function.
Try to find a trail such as $(a_0 \implies a_1 \implies \ldots \implies a_n)$ which keeps an interesting probability and where $a_n = 0$.

In the case of SHA3-256, you will be looking for the 256 first bit of the difference state to be $0$ as they correspond to the output.

Once you get this characteristic (good luck with that!), you can try to find a collision by computing random inputs with difference $a_0$ and try to find two with the same hash. There you got a collision.

More information about the differential cryptanalysis of Keccak can be found here.


How do I calculate the private key in RSA?

The private key $d$ of RSA algorithm with public parameters $(N,e)$ is such that:

$ed \equiv 1\mod{\phi(N)}$. Since by definition $e$ and $\phi(N)$ are coprime then with extended euclidean algorithm you can find such $d$: $ed +k\phi(N)=1$

Consider that to compute $\phi(N)$ you should know how to factor $N$ since $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$

To see why this is correct imagine an encryption of the message $m$ to be $c=m^e\mod{N}$.
Then to decrypt you compute $c^d=m^{ed}\mod{N}=m \mod{N}$


Should HMAC or NMAC or plain Keccak be used for a secure MAC?

HMAC and NMAC make assumptions of the underlying hash function $H$ for their security proofs. Additionally they are designed to eliminate known flaws in other MAC constructions using MD type hashes.

NMAC is not $H(k1$ $||$ $H(k2$ $||$ $m))$, it actually uses the keys as the initial hash values, which require a higher level of access to the internals of the hash, meaning a large variety of implementations cannot use NMAC the same way they can use HMAC.

In response to your questions..

For HMAC, when the key length is shorter than the block length, there is no exploitable impact on security due to padding with null bytes. The maximum security will be the output length of $H$ or the input length of $k$, whichever is shorter.
NMAC is considered the stronger MAC, but because it requires modification of the initial hash value, it is less used in practice. Attacks on NMAC are applicable to HMAC, but not always the other way around. I would be concerned that there may be choices of IV that weaken $H$ with respect to it being a PRF, which could invalidate the security claims, however resistance against forgery in that case is most likely not compromised; this is only the case if the compression function is weak, and in that case there are other security issues with the hash.
Once again, since NMAC modifies the IV, you cannot have keys larger than the output length of $H$ for MD type hash functions. In HMAC, a key larger than the block size is hashed down to the output size, so the maximum effective size of the key is smaller.
Keccak can be used with HMAC but not NMAC, since the sponge construction security claim requires the state to be 0, and NMAC requires the state to be the key. The keyed sponge function $H(k$ $||$ $m)$ is likely more secure than HMAC for a given key length, due to the inner state being larger than the output length.

HMAC padding to the block size essentially allows a single iteration over that part of the message space to change the IV, making it closer to NMAC, since the next input to the compression function is the message. For HMAC, you will get the maximum security if the key length is equal to the blocklength, assuming that more security than the output length of $H$ can be achieved. The padding constants are there so the IV of both the inner and outer hash function are unique, but still related to $k$.

Keyed sponge functions gain security from capacity, with the bound being $min(2^{c-1}/M$ $,$ $2^k)$, where $c$ is the capacity, unless $M$ exceeds $2^{c/2}$. This means more security over large messages with a large enough capacity, since the security of HMAC starts to drop with every subsequent input block (correct me if I am wrong on that one), and is upper bound by $2^{c/2}$, where c is the digest size. This implies that a keyed sponge function can have a smaller capacity than is required for the security proof of HMAC, making it either more efficient or more secure given appropriate choice of $c$.

As fgrieu pointed out, HMAC and NMAC were not from NSA or NIST, but rather university research. The fact that NIST endorses it does not imply there is a weakness. The internal hash chain size is our limiting security factor here, as well as HMAC being constructed to make use of a hash function without limitation.


A patched SHA1 attempt for password verification

Short answer: don't. Use a password hash like PBKDF2, scrypt or bcrypt.

Also, if at all possible, use a library that takes care of the low level stuff like password database for you. E.g. passlib might work if you use Python. I'm sorry if that sounds blunt, but that's how it is.

To answer your actual questions:

  There is just only one thing which bothers us: what are the theoretical chances that two different passwords which give two different hashes after applying two different character removal algorithms (based on two different PINs) will give the same result.

The chances that two different password give the same final hashes are the same regardless of whether the PINs are different or not. The chance is $2^{-n}$ for an $n$-bit final hash. I.e. $2^{-128}$ for a 128-bit hash.

(To see why the PINs don't matter, consider the output hash as a random number. That's the best you can do. Different PINs would only matter if the password hashes are equal.)

You can instead just truncate the hash, including the PIN in the string to be hashed together with the password. Also, if you went this way, you might as well use SHA-256 which is believed secure, instead of SHA-1 which has theoretical attacks that truncation might make practical.

Again, you should not use just a normal hash to protect passwords. Further, your idea of hashing the password in the client is insecure:

  The browser gathers the user data, calculates a digest of the password and sends everything to the server side. We don't want to send the password over the network, it might not be safe.

This is a good instinct, but it doesn't work as you described it. Anyone who steals your password database will be able to use a hash to log in if you don't hash on the server side. (Your site/app may ask for a password, but the attacker doesn't have to use it.)

You can hash both on the client and the server, although that only protects the plaintext password in case the encryption is broken. That's nice for users who reuse passwords, but will not protect their accounts on your system any more than just hashing on the server.

(Unless the connection where you send the plaintext password over is encrypted, an eavesdropper can always just get the password/hash and log in!)

One more additional suggestion: if you really are limited to 32 characters in the password database, consider using base 64 encoding for the hashes if at all possible. That allows you to store 192 bits of the password hash. Binary would be even better, allowing the full 256 bits of scrypt or PBKDF2 with SHA-256.


Given a message and signature, find a public key that makes the signature valid (ECDSA)

Yes. We can easily generate the malicious public key as in DSS case.
The following attack was proposed in Section 4.5 of Blake-Wilson and Menezes: Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol (PKC 1999).

Let $(G,q,n,P)$ be the ECDSA parameters, where $n$ is the order of the group $G$ over the elliptic curve and $P$ is a generator of $G$.

Let $P_1 = d_1 P$ be the public key, let $M_1$ be the message, and let $S_1 = (s_1, r_1)$ be the signature as you noted.

Since $S_1$ is a valid signature under the public key $P_1$, it satisfies the following equaitons.
$$ s_1 k_1 \equiv e_1 + d_1 r_1 \pmod{n},$$
where $e_1$ is a digest of the message $M_1$, and $r_1 \in \mathbb{Z}_n$ is a $x$-coordinate of $k_1 P$ modulo $n$.

How to construct a malicious public key

Let $M_2$ be the target message.
We now virtually compute a malicious secret key $d_2$ as
$$ d_2 = r_1^{-1} (s_1 k_1 - e_2) \bmod{n}, $$
where $e_2$ is a digest of the message $M_2$.
We then compute a malicious public key $P_2 = d_2 P$, which is
$$ r_1^{-1} (s_1 k_1 - e_2) P = r_1^{-1} (e_1 + d_1 r_1 - e_2) P = r_1^{-1}(e_1 - e_2)P + P_1$$.

Validity of the public key $P_2$.

The public key $P_2$ makes the message $M_2$ and the signature $S_1 = (s_1, r_1)$ valid.
Let us verify the validity of them.

$r_1$ and $s_1$ is in the range $[1,n-1]$, because the signature $S_1$ is valid.
Let $X = u_1 P + u_2 P_2$, where $u_1 = e_2 s_1^{-1} \bmod{n}$ and $u_2 = r_1 s_1^{-1} \bmod{n}$.
By the construction of $P_2$, we have $X = (u_1 + u_2 d_2) P = s_1^{-1} (e_2 + r_1 d_2) P = s_1^{-1} (s_1 k_1) P = k_1 P$.
Therefore, $r_1$ is the $x$-coordinate of $X$.

How to prevent this attack

It is easy to prevent this attack.
We just use a digest $e' = \mathrm{Hash}(pk,M)$ instead of $e = \mathrm{Hash}(M)$.


How does a company like Apple keep its keys safe?

It is important and interesting to notice the different use cases you mention. You don't have millions of software updates you have to sign every day (or second for that matter). For SSL connections, however, you may have millions per second. Given the two use cases, it makes sense that the way you would protect the keys would be different.

We don't know (AFAIK) how apple protects their OS signing keys. But, one good way to do it would be to store them on a separate computer that is locked in a highly secure room and not connected to any network. Only a few select people have access to that room. When a new OS version comes out, you take it into that room on a USB drive (or something like that). Signing the software requires two or more passphrases to unlock the private signing key. That way no single person can do this by themselves. Once two people have entered their passphrases, the private key is decrypted, used to sign the new OS updates, then wiped from the machine.

For the SSL use case, that private key has to be used millions of times per second. It is a very different use case. At this point you must rely on the security of the software (hopefully no one can exploit services running on your system), OS provided protections (making the private key only readable to the users/groups that need it), etc. You can also use hardware to help. Things like hardware security modules. These systems store the private keys in hardware and only provide a well defined cryptographic interface to them. That way if an attacker breaks into the machine, they cannot extract the private key. These may be useful in both use cases, but I would argue that they are more useful in the SSL use case.


It's actually fairly straight-forward; the attacker knows $m_0$, $m_1$, and the challenge ciphertext $c = m_r \oplus s$, for an unknown bit $r$ and an unknown string $s$; his job is to recover $r$.

One thing he can try is selecting an arbitrary ciphertext $c'$ (which needs to be distinct from the challenge ciphertext, but can be anything else of the same length), and ask for it to be decrypted.  The decryption is $m' = c' \oplus s$; he can then recover $m_r = c' \oplus m' \oplus c$; he can then compare $m_r$ to $m_0$ and $m_1$ to deduce $r$.


The result of SHA-256 of an empty string is:

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Accordingly to this and this


Generally, named curves are used for DH and servers don't generate parameters themselves. These are configured using a specific number in the TLS protocol. The keys on the other hand are always re-generated preferably for each connection for TLS. This is assuming that an ephemeral key exchange is used, which can be identified using the postfixed letter E in the cipher suite for TLS 1.2 (DHE or ECDHE). Because of this the shared secret should always be specific to a TLS session.
RSA is a completely separate algorithm from DH. The RSA private key is used to authenticate the TLS handshake including the freshly generated DH public keys. RSA doesn't require any parameters (other than the key size). The color explanation of DH doesn't have anything to do with RSA. In principle you can use an entirely different key size for RSA and DH, although it makes sense to use a set that has approximately the same strength.
Let's Encrypt will never know about the DH parameters, they are specific to the TLS connection and are not included in a certificate.


Can you derive ed25519 keys from secp256k1?

No. They use different curves.

For each system the public and private keys of the same key pair are not independent. You choose a private key and that determines what your public key will be.

(Good thing it doesn't work in reverse. If you could derive someone's private key from their public key, then we wouldn't have an asymmetric algorithm.)

You can derive a private key from an old public key. (Wrong!) Or a private key from an old private key. But you cannot derive a public key directly from anything other than its corresponding private key.

Alternatively Alice can sign, using her old private key, a messages that informs others of her new public keys. When Bob wants to communicate with her, he can check the authenticity of that message using Alice's old public key. (Assuming the old private key has not been compromised.)

(Note that you should be using separate keys for signing and encrypting.)

As for Alice's private key, I recommend generating new (random) private keys. If her old private key were compromised then it would mean all new deterministically derived private keys would automatically be compromised as well.


Sketch.

Suppose you have an adversary against the composed scheme with advantage $\epsilon_3$. Observe that whenever you have a signature for the composed system, you have a signature for each of the three component signature schemes.

It should then follow that a forger for the composed signature scheme can be turned into a forger for each of the three signature schemes, and it will have advantage $\epsilon_3$. (This involves a few easy technicalities.)

With that proved, it follows that we can bound the adversary's advantage $\epsilon_3$ by the advantages $\epsilon$, $\epsilon'$ and $\epsilon''$.


Is there a guarantee that for each possible hash y there exists a number x such that with hash function H, H(x) = y?

TL;DR: there is no mathematical certainty that every output value of common cryptographic hash functions is reachable, but for most that's overwhelmingly likely. A notable exception is double-SHA-256 (SHA256d) used in Bitcoin mining, where overwhelmingly likely there are some unreachable outputs.

For an idealized 256-bit hash, it becomes likely that every possible hash value $y$ is reached by hashing some $x$ when there are about $2^{264}$ possible values of $x$, including all 33-byte $x$; then odds that some $y$ is not covered become vanishingly small: less than one in $2^{b-264}$ if there are $2^b$ possible values of $x$; so while there is never a guarantee, it is practically certain that all $y$ are covered when we allow say 40-byte $x$: odds of the contrary are less than $2^{-56}$.

Argument: a hash can be idealized as a random function. The problem of if a random function covers all its image set is the coupon collector's problem. If the destination set has $n$ elements, the expected number of elements in the source set to fully cover the image set is $E(n)=n\log n+\gamma\,n+{1\over2}+O({1\over n})$ where $\gamma\approx0.577$ is the Euler–Mascheroni constant; and odds of not covering the input set after hashing $E(n)/\epsilon$ elements are less than $\epsilon$. Changing $n$ to $2^b$ for a $b$-bit hash, we get $E(2^b)\approx2^b(b\log(2)+\gamma)$ and $\begin{align}\log_2(E(2^b))
&\approx b+\log_2\left(b+{\gamma\over\log(2)}\right)+\log_2(\log(2))\\
&\approx b+\log_2(b+0.833)-0.528766\end{align}$

SHA-256 is a Merkle-Damgård hash using a compression function built per the Davies-Meyer construction. The problem of if all $y=\operatorname{SHA-256}(x)$ are reached reduces, up to 55 bytes hashed, to if all $\operatorname{Enc}_x(IV)$ are reached for a certain constant $IV$ and a certain block cipher $\operatorname{Enc}$ where $x$ is the key, and key scheduling encompasses the block padding. For an idealized block cipher the same analysis as for an idealized hash would hold, so we'd cover all values with overwhelming odds. SHA-256 uses an ARX block cipher and I see no reason why it would significantly differ from an idealized one, but that's a weak argument.

We can be more positive that we get full coverage when we allow two rounds (say, 100-byte hashes), because the problem is now if all $\operatorname{Enc'}_{x_1}(y_0)\boxplus y_0$ are reached where $x_1$ is the 36-byte second block, and $y_0$ is allowed to vary among the nearly-full set of 32-byte values reachable with the first round ( $\boxplus$ is 256-bit addition without carry across 32-bit boundaries). Still, there is no mathematical guarantee.

In Bitcoin mining, what's computed is $y=\operatorname{SHA-256}(\operatorname{SHA-256}(x))$. We are, for the outer hash, much below the coupon collector's bound and overwhelmingly above the birthday bound, therefore it is overwhelmingly likely that there are some values of $y$ not reached.

I second Dave Thomson's comment below.


You are looking for a combination of homomorphic encryption and verifiable computation.

Homomorphic encryption plays a part in this, but it is possibly not the only tool that you need. Homomorphic encryption can preserve the confidentiality of your values, but it cannot ensure that the computation was performed as you specified. That is what verifiable computation does.

Depending on the nature of the operations that you need to perform, you may not require fully homomorphic encryption. If you only require the ability to add ciphertexts together, and you don't care about post-quantum resistance, then the Paillier cryptosystem is an option for you. It's not standardized to my knowledge, but it's older and has been used in other projects.

Otherwise, if you really want/need a standardized homomorphic encryption algorithm, you might opt to use one of the submissions that were recently submitted to NIST. These algorithms are not standardized yet, but they are on track to be, assuming that they are not broken before then. Many of them are based on lattice problems, which implies that may offer homomorphic encryption.

While verifiable computation doesn't have a standardized solution yet (that I am aware of), there has been work into implementing it: See Pinocchio and Pepper.


Which QKD schemes don’t utilize an authenticated classical channel?

None that can be trusted. All secure Key Distribution systems, quantum or not, require an authenticated channel at setup, before the distributed key can be trusted. This is typically a classical channel, like a person carrying (before the Key Distribution occurs) a paper with some secret scribbled on it in an opaque envelope, or (after the fact) a telephone line to compare a public value, with the tone of the voice expected to provide proof of origin.
A Key Distribution system not using an authenticated channel would allow Alice and Bob, who never met, to agree on a secret key. Alice would be using a gismoA, Bob a gismoB, both of public design. And when gizmoA and gizmoB are connected in some way (perhaps an optical fiber) not under scrutiny by Alice, Bob, or their delegates, the gismos would do their thing and output a secret key identical on both sides.
That can't be: the "public design" requirement allows an adversary to build gismoA2 and gismoB2 functionally identical¹ to the originals. The "connected in some way not under scrutiny" requirement allows the adversary to connect gismoB2 to gismoA and gismoA2 to gismoB. From the standpoint of Alice and Bob, nothing has changed: their gismoA and gismoB output a key. However gismoB2 outputs the same as gismoA, and gismoA2 outputs the same as gismoB, and the adversary knows these outputs. Thus the "secret" requirement is not met.
As Charles H. Bennett and Gilles Brassard put it in their "BB84" paper Quantum cryptography: Public key distribution and coin tossing generally regarded as foundational to KQD:

(QKD) achieves one of the main advantages of public key cryptography by permitting secure distribution of random key information between parties who share no secret information initially, provided the parties have access, besides the quantum channel, to an ordinary channel susceptible to passive but not active eavesdropping.

Accordingly, all serious articles on QKD, and companies selling QKD gismos, acknowledge they rely on an authenticated classical channel of communication. Many additionally require that channel to provide secrecy (that's a security requirement if that channel is used before QKD takes place). However, that channel needs only be used once at setup, or perhaps when the gismos get out of sync due to errors or attacks. For example, ID Quantique's 2020 whitepaper states that it is made

use of a pre-established secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

This is universal. All serious attempts replace the authenticated classical channel by another authenticated channel of some sort. One line of research DHL a Physicaly Unclonable Function, Fedex entangled photons, or UPS trapped smurfs. Another literally aims a single-photon/laser source towards a satellite, reasons that no other satellite can realistically get in there and play satellite-in-the-middle (per laws of physics unchanged since Kepler), discount the possibility of drone-in-the-middle² as too far-fetched, and hopes there's no fog.

¹ "Functionally identical" is not the same as indiscernible. There may be (e.g. quantum) PUFs that insure gizmos are discernible, but "public design" implies that how to make discernible gizmos functional and interroperable is public.
² That reportedly works against printers, but admittedly few use QKD.


What is the relation between the existence of a cryptographic hash function and the existence of a PRG?

There is a black-box separation between one-way functions and collision resistant hash functions. This was proven at Eurocrypt 1998 by Dan Simon, in the paper entitled Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?. Of course, this doesn't mean that it's not possible using non-black-box reductions, but no one knows how to do this.


Smart's attack for secp256k1 does not work

The question is referring to Nigel P. Smart's The Discrete Logarithm Problem on Elliptic Curves of Trace One, in Journal of Cryptology (1999) (earlier version). Quoting the intro:

(…) we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the finite field.

Trace of an Elliptic Curve: For an elliptic curve $E$ defined over $F_q$ with $\#E(F_q) = q+1−t$. The $t$ is called the trace of $E$.
In the specification of secp256k1 it is apparent that $n$ (the curve's order¹,²) is not equal to $p$ (the order¹,³ of the base field). In other words, the trace $t=p-n+1$ is not $1$.
Thus Smart's attack can't apply to secp256k1.

Off-topic note: assertions are there to stop execution before code does a silly thing. Removing an assertion without other code change working around the asserted limitation is seldom a good idea.

¹ The order of a finite group or finite field is how many elements it has.
² That order is the number $\#E(F_q)$ of points on the elliptic curve including the neutral "point at infinity".
³ That order is $p=q$, the prime modulus. The finite field considered is integers modulo $p$, noted $(\Bbb Z_p,+,\cdot)$, equivalently $F_q$.


In section 5.3 of this paper you can find a comparison between an accumulator and MHT. The complexity totally depends on the scheme.

In general, MHT is linear in the proof of exclusion (in the order of depth of the tree). Because the verifier has to check all the possible paths to convince a leaf is not in the tree.


Diffie-Hellman algorithm and MITM attack

The problem lies in the trust of the public key. If an attacker can simply replace one of the exchanged public keys with his own then an active MITM attack is possible. The attacker simply replaces both public keys with his own and proceeds to create two channels that rely on the shared secrets.  For ephemeral key pairs - as commonly used - the key pairs are short lived and the public key is not trusted so DH key agreement is then inherently insecure against MITM attacks.

This is the default for all TLS 1.3 cipher suites and all TLS 1.2 suites that start with DHE or ECDHE. These suites therefore have to rely on other methods of authentication to mitigate the MITM attacks.

So the common ephemeral-ephemeral Diffie-Hellman scheme does not protect against MITM attacks, and your premise is false.

Some DH protocols where both parties are authenticated may actually prevent MITM attacks. In static-static DH the public keys of both parties may be trusted and therefore the DH will provide entity authentication of both sides, rendering MITM impossible.

This is not a common method of operation at all. It seems TLS can offer static-static DH, but it seems a rare find. Because the key pairs are always identical the protocol relies on an additional nonce - applied during or after the key agreement - to make sure that the resulting shared secret changes on every execution of the DH key agreement protocol. The scheme where the nonce is applied during key agreement is not offered by many implementations.

If just one key pair is static and the public key is trusted then the party verifying the validity of the public key will see the invalid public key, and break off the handshake of the protocol used. Ephemeral-static DH is therefore also invulnerable against MITM attacks, even if just one party gets authenticated. Of course the party that accepts the ephemeral public key will still not have any idea who he's talking to. This is e.g. not a problem on internet sites as they don't care about who reads them - they offer additional password authentication where required.

Ephemeral-static key agreement is present in the TLS cipher suites starting with DH_ and ECDH_. This method of authentication is however not present in TLS 1.3 anymore. The authenticated DH protocol requires an DH-based certificate to be able to trust the public key. These kind of certificates are hard to come by. In practice only certificates that use RSA or ECDSA for authentication are used, rendering these suites useless.

Ephemeral means temporary, or fleeting. Ephemeral key pairs should be generated on each invocation of DH, and the private key should be destroyed to achieve so called forward secrecy. Some servers cheat - because key pair generation can be relatively CPU expensive - and reuse the key pairs for a longer time or even until the server is rebooted.


Encrypt data. Create 5 keys. Just 3 keys are needed for decryption

Yes, there is.  And it generalizes easily to requiring any $k$ out of $n$ keys, not just 3 out of 5:

Generate a random key for some symmetric encryption scheme (say, AES-SIV).
Encrypt your data with that random key.
Use a threshold secret sharing scheme such as Shamir's secret sharing to split the random key into $n$ shares, such that any $k$ of them are needed to reconstruct the key.

You can use those $n$ shares directly as the $n$ "keys" to be stored in different places.  However, if you'd instead prefer to use $n$ pre-existing keys, you'll need one more step:

Encrypt each share with one of the $n$ keys (using whatever encryption scheme you prefer, either symmetric or asymmetric) and store the encrypted shares alongside the encrypted data from step 2.

To decrypt the data, do the same in reverse: first decrypt at least $k$ of the shares (if needed), then reconstruct the random key from those shares, and finally decrypt the data using the random key.

Shamir's secret sharing is unconditionally secure, so the whole scheme is as secure as the encryption schemes you use in steps 2 and (optionally) 4.


Attacking CBC with predictable but encrypted IV

Generating the IV for CBC mode by encrypting a counter is one of the IV generation methods recommended in NIST SP 800-38A, Appendix C:

  "There are two recommended methods for generating unpredictable IVs.  The first method is to apply the forward cipher function, under the same key that is used for the encryption of the plaintext, to a nonce.  The nonce must be a data block that is unique to each execution of the encryption operation.  For example, the nonce may be a counter, as described in Appendix B, or  a message number.   The second method is to generate a random data block using a FIPS-approved random number generator."

This scheme is also endorsed by the classic paper by Bellare et al., "A Concrete Security Treatment of Symmetric Encryption" (2000):

  "To make a proper counter version of CBC, one can let the initialization vector be $y_0 = f(ctr)$ and increment $ctr$ by one following every encryption.  The scheme is capable of encrypting at most $2^l$ messages.  An analog to Theorem 17 is then possible.  The result is easiest (following as a corollary to Theorem 17) if the key used to determine $y_0$ is separate from the key used for the rest of the CBC encryption."

Alas, their proof is somewhat hard to follow for the casual reader, and frankly, the alternative proof given by Wooding in "New proofs for old modes" (2008) is not much better.1  At least the author is kind enough to summarize their conclusions:

  "We prove that CBC mode is still secure if an encrypted counter is used in place of a random string as the IV for each message."

Indeed, for a reasonably readable proof sketch, you could do worse than take a look at this answer by Seth right here on crypto.SE.

All of these proofs, however, assume that the counter sequence is predetermined.  If the attacker can choose counter values, things fall apart.

In particular, given a known plaintext/ciphertext pair $(P = P_1 P_2 \dots P_n, C = C_1 C_2 \dots C_n)$, an attacker can force the IV to equal any ciphertext block $C_i$ (for $i \ge 2$) by choosing $C_{i-1} \oplus P_i$ as the nonce.

Among other things, this allows the attacker to check whether a ciphertext block $c_j$ (and the preceding block $c_{j-1}$) in another message corresponds to a guessed plaintext $p_j$ by submitting the message $c_{j-1} \oplus p_j \oplus C_i$ for encryption, using the nonce $C_{i-1} \oplus P_i$, and checking whether the first block of the resulting ciphertext equals $c_j$.  This is exactly analogous to the attack based on predictable IVs that you refer to in your question.

1) Actually, the main issue with the Wooding paper is a profusion of notation.  If you can remember what all the variables and functions stand for, it's actually fairly clear.  Still, I'd like to know who (besides, obviously, the author) considered something like "$\scriptstyle \mathcal E\text-CBCH^{\mathcal P^\ell,c,V_0}_{n_L,0,n_E}$" a reasonable notation for an encryption scheme.


Using error-correcting codes for the bootstrapping procedure of Fully Homomorphic Schemes

I think not, because the two types of error correction are doing fundamentally different things.

Conventional error correction schemes, for instance Reed-Solomon codes, expect the value to be near some codeword.  To correct an erroneous value, they change it to the nearest codeword.  You can picture it as a space where some points in the space correspond to correct values, and each of those points is encircled by a region of incorrect values that belong to that point.  The assumption of error correction is that value started at a correct point and drifted a little, but stayed in the point's own region.

With LWE, you are mixing the correct value with a ton of error, and secretly you know some way to unmix it later (bootstrapping).  You can't use less error and still have security.  In terms of the point analogy above, the incorrect values have to be all over the space.  They can't stay close to their correct value in any obvious way.  Otherwise anybody could see what the correct value is - it's the nearest correct point.  I doubt that you can use any conventional error correction without having obvious regions of some kind.

Error correction doesn't do much for the bootstrapping either, I think, because once you unmix the value, you can just throw away the error part.


Why is RSA secure if I can solve the equations for it using a math solver?

The RSA problem, which is the underlying problem that makes RSA cryptographically secure, is currently considered as an unsolved problem. There exists no known algorithm to efficiently compute P, given the public key (N, e) and the ciphertext  C ≡ Pe (mod N).

But who cares about theory, right? You claim to have a solution, then try it! Here is an RSA public key:

    -----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEApjP/ml4yt/iLr3Kzt7yv
H+7zEdnJ04xCTeW+Vx9CBRQukRdkVoMYntP6RHx6mZSeMKTXtOt87LHVxOoNi2Bf
efoQAxB1ehXW4h8F1tnmSruKt87U9YDe0W8Z9GOC63vq5eu95zqDvWQ6s42P4Gga
eZGXD6RKaw6TcYqfl7MWR6I21lOgFUKojNb0+LD4wdaES1L7pOlbCLstaQO91Dea
3HyD1h+NKEDrVT2goVnTbsF9AZf8xHmEHhWAZNRpsskiXlG6PKdlzuBbt1q+5b4J
0Kimw01mwgKt/2k4LkPa6PaM2PoiXisfDeaRLFV5F3INokhwaYNTolzEaz7y+Tyr
OhBwrcvMK+/1iMPzNgSk0qsnObX0+fn9e/RZvzxz8hdlWqVGVb4sswWt+bJnn1Bv
zZ58Q+NlQG7kQb58i+zHuBqvbunbMWT9osmbS4W+PVKG0nGrusRlTc3lY10HfoPE
hX3r1L4rYQUO1wdukkdfKOL0lcITu1A8Wv6olFpQna8u/hIW0dY0qdqiHO/kSLjJ
zCJNX/hzx3Cy1oUSrEaIjs5Lv6Nuu0r2mFwS6f8kgg5rXPI97homStro8bmwQQF8
EcyPlq9OXS2Ide/F6IxY/HzkpOlbwzoSsqyjoJCC9mwd+67ItShKUQdx/1c4aZme
6+9s50KyK5Pna5dVi+CVrEkCAwEAAQ==
-----END PUBLIC KEY-----

Here is a ciphertext, encrypted with said public key and encoded in base64:

mFrcsgt06GQ8xAK60D5iMBMc/oDTj/MwvG/obnS6pDl3svhlde4aOfkAIUPlawfl2uDYuX2TD3VB
L5iJYCDRsCoGcxbnQ1kS6Q2zXevBzs33RQg5sanXVt8Jic+OWWVPPwN3JPDuS3Ot4ljgs8eB7LTR
hvmeyVMfT6iue3AMU+B1EOnMpij5I9HQs6eUGO29ROU6WJk7PFYIY6M0FrTVyYXHoSwl+zukQzdu
kYPcj0ST4NsjR93h7drPeyo7y/LVI5mCIp+kPD2SXH1BAzxGAcZLA85MZFHypbqiU+7eO4iBmYPD
BJDU02PiTyB6YGFrsQFZWeVeycdniuCfbQeaGH6eb4qZxHsNhosCEdyxQRF8c4Nh2+q8LwqrPwid
kKcoEqh4/HbBqgXQ/UXLTvUCucowDtW4sDFlT1nsup3Tod0xd3Ea3hEf9qZJnVKe/puHxEB6cwf1
5SbEBBRBCusJ8o6MhmWa2U14dBuO4J+YDJiCiL6PMJ2sCjeTEsKdegx0O82Bvs4sMbbTFZUb/T0u
oC1P0o4MHAFHwNkl85rkgih2d15lyOSsYiZ6TEQ41EE7wckIV/48rjL1JoXIFsxVDsuihXhSOpR4
/LKhXv0OdkrPOeZpjPwNq9eo/DgiCTVwtxWYxvk5UKT+64fefqpyqwM9YOqWEQfJkeh/niVlsrc=

Of course, since you have the public key, you can make as many ciphertexts as you want with it. I just thought I'd include a little message for you when you are done.

Good luck!


You don't have to use XOR, but rather, it tends to be convenient.  One of its convenient properties is that it is its own inverse.  Also, XOR implements addition in $\mathbb F_{2^n}$, making XOR a key component of working in finite fields of characteristic $2$, if you want to use them in an algorithm.

The "one-time pad" is usually defined as taking a random key the same size as the input and XORing them together to produce the ciphertext.  If you changed XOR to addition, whether $\mod 256$ or considering the entire input to be one large number, it would still be perfectly secure.  It just wouldn't be its own inverse - decryption would require subtraction instead of addition.

RC4 was considered secure for years, and though somewhat broken in modern times, it can serve as an example.  RC4's algorithm revolves around swapping bytes in an S-box, then determining a byte to XOR with the plaintext.

If you modified RC4 to do $\mod 256$ addition instead of XOR, it would have the same security as standard RC4.  However, it then wouldn't be its own inverse; decryption would require an RC4 that uses $\mod 256$ subtraction.


For Coppersmith's method to work on $n = p\cdot q$, you need to know $\frac{1}{4}\log n$ bits of $p$.  It would take an amazingly badly botched random number generator in your key generation procedure to reveal that to an adversary.  There have been two high-profile cases of this: low-quality hardware RNGs Taiwan's national identity smart cards in 2013 (summary), and the ROCA vulnerability in Infineon's RSALib library for smart cards in 2017.

Unless you are trying to use the cheapest possible hardware RNG (as seems to be the case with Taiwan's national identity cards), or trying to be clever about generating keys as efficiently as possible (as seems to be the case with ROCA), you don't have to worry about Coppersmith's attack.  There are various ways to generate RSA moduli, and they're all basically fine except insofar as they are distinguishable from one another and enable fingerprinting of RSA key generation procedures.

Safe primes, i.e. primes of the form $p = 2q + 1$ for prime $q$, are not really relevant to RSA.  Strong primes, which are similar but with a few more criteria, were once suggested to be relevant but no longer—the costs of the attacks that they thwarted are much higher than the costs of the best modern attacks on >=1024-bit moduli.  None of these attacks—from the old Pollard's $p - 1$ or William's $p + 1$ to the modern elliptic curve method or general number field sieve—are related to Coppersmith's method, which is about known fixed bits in the factors.


Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

As far as I am aware, all the recent progress on discrete log algorithms which derived pseudopolynomial efficiencies took place for the case of small characteristic fields $GF(p^n)$ with a structured exponent $n$. So the best complexity is still exponential in $\log N$ where $N$ is the size of the subgroup under consideration. So nothing better than generic DL complexity seems to be known.

You may find the following interesting. Bernstein and Lange have shown advances for generic discrete logs for the case that preprocessing is allowed, e.g., for curves in standards.

Even there, the online phase complexity seems to be $\geq (\log N)^{1/3}.$ See this paper for a discussion. Here is a quote:

  In practice, however, an adversary may have access to the description of the group $G$ long before it has to solve a discrete-log problem instance. In particular, the vast majority of real-world cryptosystems use one of a handful of groups, such as NIST P-256, Curve25519, or the DSA groups.


Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG?

A hash function is a "public" function. If some bad guy knows what the input might be then they are able to evaluating the hash function themselves and get the same output the good guys do. The only way that won't be a problem is if the input has really high entropy.

Insecure PRNGs only appear random to the human eye, but their output might follow enough of a pattern to make brute-force guessing of hash input possible. (Their output definitely has low entropy if their state space is low or if they're seeded with a 32 or 64-bit number.)

You can address the fact that hash functions are public by using a PRF (pseudo-random function) instead. PRFs can be built from hash functions. See the HMAC and SHAKE (SHA-3) algorithms. If the input to your PRF is non-repeating and your secret-key is not predictable then this is a secure PRNG based on the definition of a PRF.

If you do something like outputBlock = PRF(secretKey, rng.getRandom32Bits()) then the construction is not secure. Even if rng allowed you to sample from an ideal uniform random variable, this method would start repeating outputBlock(s) after around $2^{16}$ samples. (Due to the birthday problem, but even if that weren't a problem you would get repeats within $2^{32}$ blocks.

The improbable occurrence of repeated long outputBlock(s) would be a problem for meeting the requirements of a secure RNG. It might also be possible to perform a stronger attack (full state recovery) with knowledge of the insecure RNG's patterns by observing the pattern of repetitions.

However it is really easy to avoid the problem of repetition. Just use a $n$-bit counter for input and use less than $2^n$ blocks of output. A PRF, by definition, must produce output (on non-repeating input) indistinguishable from random (Even if input doesn't look random!) and, by definition, doesn't permit key recovery attacks no matter what the input is.

That gets you a secure RNG (potentially using just hash functions). But you then don't need the weak RNG.

Of course there are many faster secure PRNG algorithms out there. (Like using ChaCha20 key-stream output or the output produced by repeatedly encrypting a counter with a block cipher.) If you can use a hash and a few extra bytes of executable is acceptable then I don't see why you wouldn't want to base an RNG off of ChaCha. Hash functions implemented in software (compared to a dedicated CSPRNG algorithm) are going to be slow, require a large executable size, or both.

Large executable size meaning large for embedded systems. On a PC with GB of RAM it's neglible.


How can we add real values using GF field?

As stated by CodesInChaos in comment, what's asked can't be done with the same $+$ operation for the binary field $\operatorname{GF}(2^4)$ and the desired $+$ operation for common integers. Proof: in $\operatorname{GF}(2^4)$, $a+a=b+b$ for any $a$ and $b$, and that does not hold for any useful subset of integers.

However, we can map the elements of $\operatorname{GF}(2^4)$ less zero (0000) to $\{0,1,2\dots,13,14\}=\mathbb Z_{15}$, with multiplication in $\operatorname{GF}(2^4)$ mapping to addition modulo $15$ in $\mathbb Z_{15}$ . We take any generator $g$ of $\operatorname{GF}(2^4)$, e.g. 0010; map 0001 to $0$,  $g=$0010 to $1$, $g^2=$0100 to $2$, $g^3$=1000 to $3$, $g^4$=1001 to $4$, and more generally $g^n$ to $n$.

Now, the operation in $\mathbb Z_{15}$ defined by getting back to $\operatorname{GF}(2^4)$ per the inverse of the above mapping on both arguments, multiplying the results in $\operatorname{GF}(2^4)$ , and getting to $\mathbb Z_{15}$ again by applying said mapping, is simply addition modulo $15$, and thus works as asked for small non-negative integer values.

Analogy: we can perform addition in the set $\mathbb R$ (the reals) as $x+y=\log(e^x\times e^y)$.


Fibonacci LFSR, recovering previous bits

Yes. just run the lfsr backwards, so if you have $$s(t)=s(t-2)+s(t-7)$$ use $$s(t-7)=s(t-2)+s(t)$$ all mod 2 with $$(s(-6),\ldots,s(0))=(1,0,1,0,1,0,1)$$ your initial loading.


Side-channel attacks against ECDH for Weierstrass normal form curves

The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves.

Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for exponentiation using textbook formulas for addition and doubling), then anyone can basically take the smart card, perform power analysis while the scheme is running, and directly read off your secret exponent from the power trace because additions and doubling produce quite different patterns on the trace.

See e.g. J.-S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", CHES 1999, for some of the basic attacks and countermeasures.

Using appropriate countermeasures, you can certainly implement elliptic curve cryptography on Weierstrass curves in a way that is largely secure against side-channels. The argument of proponents of other curve forms (such as Montgomery curves if you want ECDH, or curves with unified arithmetic like Edwards curves for signatures and other applications) is that, as you say, implementations are easier to get right with those other forms (and as a side benefit, they tend to have better performance characteristics as well). See also this related answer by Thomas Pornin.

For example, the Montgomery ladder, which is the standard way in which you would implement exponentiation on a Montgomery curve, is safe against simple power analysis without having to add in any other countermeasure. Of course, if you want to protect against stronger physical attackers, you may still need to add other countermeasures to your implementation (against DPA, fault attacks, etc.), but the basics are covered, so the situation is really a bit better than with Weierstrass form, where the most standard exponentiation algorithm is leaky and countermeasures tend to be costly.

Side note: the idea that on Montgomery curves "the same algorithm can be used to do both point addition and doubling" isn't entirely correct. Typically, people use Montgomery curves for the very efficient x-only differential-addition and doubling operation that can be used to do efficient, SPA-secure exponentiation up to sign (the Montgomery ladder). But you can't really do point addition at all (certainly not x-only point addition, since it's not well-defined, and if you're going to use two components, you might as well use a better suited curve form).

It's twisted Edwards curves (among others) that admit addition formulas that can also be used for doubling. Now it turns out that any Montgomery curve is birationally equivalent to a twisted Edwards curve and vice versa (you can use any such curve in one form or the other depending on the application) so the distinction might sound a bit academic, but all of these curves can also be put in Weierstrass form as well, after all, so the difference certainly matters as far as implementations are concerned.


What is the difference between a digest and a hash function?

The digest is the output of the hash function.

For example, sha256 has a digest of 256 bits, i.e. its digest has a length of 32 bytes.

That's it really.


TLS-conformant ciphertexts and SSLv2-conformant ciphertexts for Blechenbacher attack for DROWN attack

(background) It wasv mentioned in the paper that for TLS, RSA PKCS#1 v1.5 is used to encapsulate the 48-byte premaster secret exchanged during the handshake. Does means that a random padding string PS is prepended to the 48-byte premaster secret to this formatted massage
  ([00] || [02] || PS || [00] || pms)
  before the actual RSA encryption is done?

Yes, with the correction that PS is random nonzero. (I'm sensitive to this because I once had to interop-test with a system that didn't correctly exclude zero from PKCS1-type2 padding, resulting in several percent of cryptograms causing spurious test failures.)

  (1st question) How does the decryption oracle in the SSLv2 server differentiate between TLS-conformant ciphertexts and SSLv2-conformant ciphertexts, since the padded TLS plaintext also contains ([00]||[02]) as the 1st 2 bytes?

As described in 2.2, for SSLv2 the PKCS1-encrypted value is $mk_{secret}$ whose size depends on the ciphersuite selected.

As described in 3.2, the SSLv2 oracle (server) checks "$m$ starts with
0x00 02 followed by non-null padding bytes, a delimiter
byte 0x00, and a master_key $mk_{secret}$ of correct byte
length $k$" where k depends on the ciphersuite; examples given are 5 to 24.

48 is not equal to the k value for the selected SSLv2 ciphersuite, or indeed any of them.

3.3 confirms this: "But since no SSLv2 cipher suites have
48-byte key strengths, this means that a valid TLS ciphertext
is invalid to our oracle O." The rest of 3.3 explains the (clever) process used to find a mathematically-related and SSLv2-conformant ciphertext.

  (2nd question) Why is it that one has to transform a RSA PKCS#1 v1.5 TLS conformant ciphertext to RSA PKCS#1 v1.5 SSLv2 conformant ciphertext before being fed to the Blechenbacher oracle?

Because the SSLv2 oracle only gives a distinguishable response for an SSLv2-conformant ciphertext. For all TLS-valid ciphertexts it gives a randomized response from which no information can be extracted -- but the entire purpose of an oracle is to leak information.


Why is the security level defined by $\log _{2} \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$

The value $t/\epsilon$ is the expected amount of time required for an attacker to "win". E.g., if he has a 50% $(\epsilon = 0.5)$ probability to guess a key in $t = 10$ seconds, then the expected length of time for him to guess the key is $t/\epsilon = 10s/0.5 = 20s$

The example you provided is a bit unspecified, and it's not clear to me that $A_3$ is a "trivial modification" of $A$, what a "trivial modification" means, or why we would expect a "trivial modification" to retain the security of the original.

To be more concrete consider two examples:

First, a blockcipher $E$ with 128 bits of security (for simplicity, 128-bit keys and 128-bit blocks). Then $E'_{k1,k2}(x) = E_{k1}(E_{k2}(x))$ could be considered a "trivial modification" of $E$ and has, as you say, pretty much the same security level --- in this case, 129 bits due to a meet-in-the-middle attack.

On the other hand, if you view the blockcipher $E$ as a PRF, then the "trivial modification" $E'_{k1,k2}(x) = E_{k1}(x) \oplus E_{k2}(x)$ has significantly more security --- we've gone from ~64 bits of security (generic birthday-bound attack) to ~85 bits of security (c.f "The sum of PRPs is a secure PRF" by Stefan Lucks).

So in the absence of more specific information about your $A_3$, it's entirely reasonable that $A_3$ may have either about the same, significantly more, or even significantly less security than $A$.

A final note I don't know what text your definition comes from, but although it's a completely reasonable definition for "bits of security" --- a term often used informally --- it's a bit incomplete since it doesn't account for possible limits to the number of queries an attacker can make, or the amount of pre-computation he could perform before being provided with oracle access.


When making public key fingerprints - is a sha1 hash still a good idea?

I understand that in 2005 SHA-1 was found to have a security flaw and the now recommended standard for this kind of thing is SHA-2 (256 or 512).

This post may be of some use:
https://stackoverflow.com/questions/3897434/password-security-sha1-sha256-or-sha512


For AES CBC, can I encrypt the IV with AES ECB and the same key and include it with the message?

It actually leaks information. You are sending:

Encrypted IV: $AES(k,IV)$
First ciphertext block of CBC: $AES(k, M_1 \oplus IV)$

Eavesdropper can observe whether the two blocks are equal, which happens iff $M_1$ is all zeroes.


Building a 4-bit S-box with a 4-uniform DDT

Yes. All $4\times4$ bit S-boxes have been classified. It is possible to reach a maximum differential of 4 as well as optimum nonlinearity.
SERPENT used optimal $4\times 4$ S-boxes with respect to differential cryptanalysis. So does PRESENT, to the best of my knowledge.
Some links

2011 - Markku-Juhani O. Saarinen, Cryptographic Analysis of All 4 × 4-Bit S-Boxes

2015 - Zhang et.al., A New Classification of 4-bit Optimal S-boxes and its Application to PRESENT, RECTANGLE and SPONGENT

SAGE is a good way to learn about and experiment with S-boxes.

Sage: S-Boxes and Their Algebraic Representations

Edit: None of the optimal Sboxes' representatives from Saarinen have the property of all 4's you want. I have no time, but I believe it can be proved using Theorem 1

in Blondeau-Nyberg which originally appeared in Eurocrypt 94  Chabaud-Vaudenay that such a DDT pattern would yield weak S-boxes against linear cryptanalysis. Here $n=m=4,$  $cor_x(a\cdot x \oplus b\cdot F(x))$ is the correlation bias of the corresponding linear characteristic, and $P[\delta \stackrel{F}{\rightarrow} \Delta]$ is the diferential probability.


When NIST put together the table A.1, they accidentally used a 96 character alphabet for that last column, not a 94 character one.  One way to see this is looking at the bottom most entry; they list that $log_2(b^{40}) \approx 263.4$, where $b$ is the alphabet size they used.  If we solve for $b$, we get $b \approx 96.002...$.


Does an information-theoretically secure hash function exist?

The Gilbert-MacWilliams-Sloane MAC referred to by @SqueamishOssifrage in the comments is information theoretically secure "for single use", at the cost of having hashes that have length $2\ell$ for fixed length messages of length $\ell.$

Poly1305 is not information theoretically secure.

It is much more flexible, can take essentially arbitrary length inputs, and has a low probability $p$ of being spoofed which depends on four factors, $\delta,C,D,L$ and which is essentially $\delta$ plus a tiny correction factor, so $$p\leq \delta+f(L,D)2^{-106}.$$ See the original paper by Bernstein (Springer LNCS vol. 3557, also available at his site https://cr.yp.to/mac/poly1305-20050329.pdf) :

One can have up to $C\leq 2^{64}$ authenticated messages
Messages are of maximum length $L.$
One can attempt up to $D$ forgeries
$\delta$ is the probability of distinguishing AES output from a random permutation

To start with, we don't know what $\delta$ is. AES could be replaced if it was found to be weak, but the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution, which would enable one to define information theoretic security, which depends on entropy, a well defined functional of a probability distribution.


Finding non-zero coefficients in 8 bit polynomial LFSR

Berlekamp Massey algorithm does this for you.

See Dilip Sarwate's nice answer


Invalid curve attack: finding low order points