How to distribute system parameters in identity-based encryption

Public parameters (or system parameters as you call them) can be distributed however you want. Papers which introduce Identity-based Encryption schemes usually only present the scheme and not how it can be applied in the real world 1. The public parameters in IBE can be compared to the pre-shared data in the Diffie-Hellman key exchange protocol where both parties have to agree on a shared modulus and generator before starting the protocol. There are different ways to distribute such data. Here are two:

Bake (put into the application code) the public parameters into the application, so that every client has the same parameters and don't need additional trust negotiations. This will be a trust root.
Query the public parameters from some other party in a secure manner (signed and not necessarily encrypted). Each client has to have some trust root (certificate of the third party) for this to work.

1 If you see a commercial product which uses IBE/HIBE/ABE/PE/HVE/FE, please write a comment.


How any attack on a cipher carried out? Are these practical or only theoretical?

I'll answer your questions in order:

1. If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations?

By examining the mathematical properties of the algorithm and their attack.

2. Are these attacks only on paper or practically proven?

There is no practical way to perform any operation $2^{140}$ times, so they are only on paper. But note that mathematics is one of the few sciences where we can prove things without resorting to experimentation.

3. Considering super-computers owned by the government, which researchers don't have access, this time-frame may vary? Are these attacks taking into account super-computers computing power also?

$2^{140}$ is the number of elementary operations, usually 1 operation takes a constant amount of operations of the underlying primitive, e.g. 1 AES encryption/decryption operation. The number of operations required does not depend on computer speed.

But yes, faster computers will perform the operations faster. This is however of little importance as $2^{140}$ operations together take multiple universes of time and energy to complete. Only very disruptive technology such as quantum computing or breakthroughs in mathematics could make such attacks practical.

There is always the possibility that the attack itself can be improved upon. Attacks get better, never worse.

The results on 256 bit AES with relayed keys are mainly of importance when the block cipher is used within other constructions such as pseudo random number generators. AES encryption is still considered secure.


In which public key encryption algorithms are the private and public key not reversible?

Are there other public key systems that do not have this property?

A more cogent question might be "are there any public key systems other than RSA that does have this property?"

In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public and private keys, and you eschew the CRT optimization on the private key side).

I'm familiar with a number of proposed public key systems, and nothing comes to mind:

Other factoring-based systems: Rabin-Miller and Pallier - nope; although Rabin does come close, but with a fixed public exponent of 2, it can't really be used as a private exponent (and it's not quite reversible either).
Discrete log; nope.  They (in my experience) have a private key as an integer $e$ and a public key as the value $g^e$ (or $eG$, if you're using a group with additive notation).  Given that you can compute the public key from the private one, you can't swap them and remain secure.
Lattice based systems; nope.  They internally have more variants than the discrete log problems, however in general, the private key is some secret sauce that makes solving the lattice problem easy (at least in the cases that the system cares about), hence you can't swap them.
Code based systems; nope.  The private key is the secret sauce to make the error correction problem easy, hence you can't swap them.
Multivariate systems; nope.  The private key is the secret sauce to make solving the multivariate equations easy, hence you can't swap them.
Isogeny based systems; nope.  The private key in this case is a subgroup of the elliptic curve, while the public key is the isogenous elliptic curve that the isogeny maps the curve into (while mapping the subgroup to the neutral element).  Again, it doesn't make any sense to swap them.
Hash based signatures; nope.  In this case, the public key is a hash, while the private key is the series of values that are hashed together (generally in a big tree structure) to ultimately form the hash.  It makes no sense to swap the public and private keys.

I can't think of any other public key systems that haven't been broken...


How to generate a unique numerical value for an alpha-numeric string?

If you don't limit the length, there are infinitely many alphanumeric strings. The number of even 128-bit numbers is finite, so there's no way to assign a unique 128-bit number to every possible string.

That said, if you don't mind a very small risk of collisions, a cryptographic hash function like SHA-2 or SHA-3 truncated to your desired output length should be fine, as long as that output length is sufficiently large.  With e.g. a 128-bit output size, the average number of strings you'd need to hash before observing even a single collision is around $2^{64}$, probably far more than your software will ever see.  If you're really feeling paranoid, bump the length up to 256 bits.

(A point I should probably clarify is that hash functions like SHA-2 and SHA-3 output a fixed-length block of bits.  While this output is often represented in hexadecimal for convenience, it's really just a large binary number and could just as well be displayed in any other base, e.g. in the plain old decimal system we humans like to use.)


The Blum-Blum-Schub construction is a PRNG rather than a stream-cipher. (A stream cipher differs from a PRNG in that it provides for a loading mechanism for the key and an IV.)

There is a similar proposal for a PRNG based on the hardness of computing discrete logarithms by Blum and Micali (How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, 1984). The extraction from the internal state $x_i$ consists in a bit the value reflecting the outcome of the test $[x_i < {p-1\over 2}]$.

Please note that the construction you propose cannot be proven secure with the standard methodology in that the lowest significant bit of $x$ can always be determined given the value of $g^x\mod p$, so that it cannot be proven to be a hard-core bit for the corresponding one-way function — and even less so the simultaneous bits forming the least significant byte(s).

Gennaro (2000) proposes to extract a number of low significant bits from the state (starting from the second).

Now many authors proposed an analysis of the concrete security of this (or similar schemes), and of course, you can always take "another look" at it.


Number of affine points on an elliptic curve

The final code that worked for is shown below (published here)

# Returns number of affine points on the elliptic curve (wihout point at inf).
def countResidues(a, b, p):

    counter  = 0
    for x in range(0,p):

        # the curve in
        y2 = (x**3+a*x+b) % p

        # if x^3+ax+b = 0 (mod p), then there exists one point only.
        # i.e. the point is still on the curve even if there is no residue.
        if y2 == 0:
            counter += 1
            continue

        # if quadratic residues exists, two points are on the curve
        # i.e. the solutions to y^2 = x^3+ax+b (mod p)
        if isQuadRes(y2, p):
            counter +=2

    return counter

# Check if a curve is singular by checking that 4a^3+27b^2 = 0
# See p. 255 in course lit.
def isSingular(a, b, p):
    return ( -(4*a*a*a % p)-(27*b*b % p)) % p == 0

# Determines if there exists an x such that x^2=a (mod p), in other words,
# it will return true if the quadratic residue exists.
# Based on Euler's criterion, see course lit p. 180.
def isQuadRes(a,p):
    return squareAndMultiply(a,((p-1)//2), p) == 1

# Convert integer to binary representation
def intToBin(number):
    return '{:b}'.format(number)

# Computes number mod base
def mod(number, base):
    return number - base * (number//base)

# Calculate 'x^c mod n' using square-and-multiply algorithm.
def squareAndMultiply(x,c,n):

    # get the binary representation of c, the exponent.
    b = intToBin(c)

    z = 1

    # the main algorithm, adjusted from p. 177 from course lit.
    for i in range(len(b)):
        z = mod(z*z, n)

        if b[i] == '1':
            z = mod(z*x, n)
    return z

Course lit refers to https://www.amazon.com/Cryptography-Practice-Discrete-Mathematics-Applications/dp/1584885084


Ideal passphrase length: old diceware method (5 words) vs. your Bitcoin wallet.dat passphrase lenght (8 words) and doubling passwords?

I made a cool 5 word passphrase back then using the old Diceware
  method and use it as a master password. The question is as computing
  power increases will we need to add more and more words to our
  passphrases which we will eventually forget? I'm in my mid 30s, will
  passphrases be enough in my lifetime? :) So back then, Diceware
  suggested just 5 words, not the original Bitcoin QT client recommends
  8 words. Will theoriginal 5 words from the Diceware age will serve me
  in the Bitcoin age?

Bitcoin (well, the wallet software, anyway) is being a bit conservative. A 5-word passphrase might be a bit on the low side, but if your words have been chosen randomly from some dictionary with about 7.5k words, as claimed on the Diceware page, you should be safe, as this comes out at roughly $64$ bits of entropy. This should remain a strong passphrase for the next decade or two at least, but there's no real way to know. You'll probably be fine anyway if you're not a high-value target. Most attacks today are done against a large batch of weak (and weakly protected) passwords, not a single strong one.

  How effective is doubling a passphrase? Like I have now [passphrase]
  and simply doule it: [passphrase][passphrase]. So I don't really have
  more stuff to remember, just more stuff to type. That might serve me
  for a time.

It doesn't really help all that much. You're not adding lots of uncertainty to the new passphrase, you just doubled it. Now that this question is on the public internet, an attacker trying to target you might try every combination of 5 words, and then double them and try again, just in case you doubled your passphrase. This means the attacker will have to work twice as hard to obtain your passphrase, not very useful. Adding a single Diceware-grade word is considerably more effective.

  Oh, another interesting question as well: let's say I use one exact
  password on many similar forum pages. Will this generate the exact
  same hashes if they use the same forum engine? I know, you can't
  recover the password from the hash, but they may find same hash = same
  guy, right?

It depends. In an ideal world.. no. The hash functions would be different, and they would use a random salt anyway. But, in the real world, yes, it's quite likely that many forums out there are still using MD5(password) and in that case, the same hash will end up in multiple databases, which is bad.

But if a forum engine is well-designed, that should not happen - each user will be given a random "salt" to differentiate his password from other users', this means if you create the same account on two different forums (even using the same forum code) you will most likely be given different salts, which'll make the two hashes differ.

  I don't really want to mess around with a Yubikey. Heck, I Googled it
  and didn't really managed to find out what it is, what it does. Maybe
  I'm not the target market. I'm just a simple user. Carrying around a
  Yubikey would also be a red flag in my eyes. He has secrets!

Everyone has secrets, and people carry around authenticators already, don't they? :) Basically, it's a two-factor authentication token. When you log into a website, you usually only use one-factor authentication: you know your password. But in a two-factor authentication process, you need to provide what you know (password, passphrase) and something else, either of:

what you are (biometric fingerprint, retina scan)
what you have (a physical object, such as a security token)


Why does the TLS spec for TLS-PSK say not to derive the shared secret from a password?

Is the vulnerability of concern here that observing a handshake would allow an attacker to brute force the shared secret offline based on the PSK binder?

Sometimes; there are two ways for TLS 1.3 to negotiate with a PSK; with the PSK only, or with a PSK and an (EC)DH.  If an (EC)DH is used, the vulnerability of concern here is that a client (who does not initially know the PSK) would be able to attempt a negotiation with a server, and as a result of that exchange, run an offline test on a large number of possible PSKs.  On the other hand, if only a PSK is used, then yes, a passive attacker could go through and test the various PSKs (and then decrypt the encrypted data).
When (EC)DH is used, then what an attacking client would do is send the client hello (with the appropriate pre_shared_key identifier, and an honest DH key share, that is, one for which he knows the private value); the server would respond with a server hello, followed by "encrypted extensions".
This encrypted extension is encrypted with a key which is based on stuff the client knows (nonces, the DH shared secret), and the PSK.  What the client can do, for each guess of teh PSK, plug that into (with the inputs he already knows) into the TLS 1.3, and derive the corresponding session key, and then use that key to verify the authentication tag in the encrypted extension.
Once he finds a PSK that makes the authentication tag validate, he can then use that PSK to masquerade as either the client or the server in future exchanges (or do an active MITM).

Or would this only allow the attacker to compromise future streams (e.g. by spoofing the server and/or client as a man-in-the-middle?)

TLS 1.3 allows either PSK-only mode, or a PSK along with an (EC)DH exchange.  If a PSK-only mode is chosen, then the attacker can passively listen in.  If the client decides to do PSK plus (EC)DH, then the attacker cannot passively listen into future (or past) streams; this allows only active attacks.


Is GCM mode of authenticated encryption quantum secure?

Is AES-256-GCM considered quantum-safe?

For most common scenarios, yes.

Actually, it depends on your attack model.  If your attack model is that the attacker is allowed to perform entangled queries on your GCM implementation, and return entangled responses, then, no, GCM is known not to be secure against this model; the attacker can use Grover's algorithm on the decryption Oracle to find a second valid ciphertext/tag with a previous seen nonce with $O(2^{64})$ work.

On the other hand, the attack model is rarely appropriate.  Entanglement is quite delicate, and to make this attack model work, the decryption oracle would need to be implemented using quantum error correction.  Typically, implementations don't help out the adversary to that extent, and hence it would need to be implemented as a part of the quantum computer (so that the adversary can implement quantum error correction within the oracle).  About the only way this would be practical would be if you were attacking a white-box GCM implementation (so you couldn't trivially examine the implementation and extract the key).

In the standard scenario, where the attacker is allowed to make conventional queries to the oracle, and get the standard response, the standard proof of GCM applies; unless they can distinguish AES from a random permutation, they cannot generate a valid ciphertext/tag pair with nontrivial probability; using a 256 bit AES key means that Grover's algorithm would take $O(2^{128})$ time for this, which is generally considered infeasible.


Does an attacker gain an advantage if they have the initialisation vector?

No, they do not gain an advantage; part of the definition of IV is "information that is used to encrypt data which can be sent in the clear".

In fact, it is actually rather common to send the IV along with the encrypted message.  TLS version 1.1, IPsec, IKEv2 are all protocols that do that.

In CBC mode (which you didn't specifically ask about, but it is the most common), the argument that it can be sent in the clear is simple.   Here is CBC mode encryption:

As you can see, the IV is used as as input to encrypt the first block.  In exactly the same way, we use the first ciphertext block to encrypt the second block.  We send the first ciphertext block "in the clear", and hence the attacker can see it, and it does not cause a weakness.  Because we use the IV in exactly the same way, sending it in the clear also does not cause a weakness.  Now, there are some subtle points; the first ciphertext block is unpredictable to an attacker before he sees the message; it turns out that this is actually important, and so the IV must itself be unpredictable.

In Counter mode (the second most common case), the argument is different.  Here is counter mode encryption:

In this diagram, the IV is called the 'nonce'.  Now, the nonce is fed as input to the block cipher; since the block cipher is strong against known (actually, in this case, chosen) plaintext attacks, giving the attacker information about what the input to the block cipher is doesn't aid him.


Can I change the S-box and P-box in DES?

S & P boxes are not random permutations.
Changing them is not easy.
The position of each element of an such a box is chosen following principles such as Strict Avalanche criterion, Bit independence criterion, non linearity, xor table distribution and maximum expected linear probability.

Not following these makes it prone to differential cryptanalysis.

See Biham & Shamir's work on the cryptanalysis of DES S-Boxes.

Also check out "Comparison of random s-box generation methods" by Dragan Lambić for a different perspective.


How Does Prime Factorization Break ECDSA?

However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers.

Your understanding is incorrect. Shor's Algorithm is usable for both factoring integers and finding discrete logarithms.
Shor's algorithm works in two parts. First, it turns the problem (factoring or discrete log) into one of finding the period of a function. This first step is non-quantum. Then it finds the period using the Quantum Fourier Transform (QFT). Once you have the period of the function the first step can be reversed to find the solution to the original problem.
Shor's algorithm can be used without the Quantum part and simulating the QFT, though then it will be substantially slower than the best known classical algorithms. This python implementation simulates the QFT and may aid understanding.


The issue is, the message length is now longer than the modulus $p$ and $q$

That's not true.  In the $p$ track, you are raising $M \bmod p$ to the power $d \bmod p-1$; we have $M \bmod p < p$; that is, the value we are exponentiating is less that $p$, as results by Montomery multiplication.  In the same way, the $q$ track also satisfies the requirements on that side, and so everything works.


How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second?

That is a popular informal description of what a pseudo-random function is—a function constructed out of a random seed that, for any input, produces a pseudorandom output in a repeatable fashion (i.e., same input always gives you the same pseudorandom output).

The suggestion in the comments to use CTR mode is along these lines—CTR mode is the application of a PRF to a sequence of counter values.  I.e, if $f : K \to I \to O$ is a pseudorandom function family, $k \in K$ is a randomly selected secret key, and $i_0, \dots, i_n \in I^*$ is a sequence of distinct values in the domain of $f_k$, then the sequence $f_k(i_0), \dots, f_k(i_n)$ cannot be efficiently distinguished from a sequence of values drawn at random from $O$.

Some practical choices of PRF would be:

HMAC
Any block cipher (e.g., AES). These are pseudorandom permutations—bijective PRFs—which means that they cannot be distinguished from a general PRF unless the number of queries exceeds the so-called "birthday bound" (search for "PRF-PRP switching lemma").


Join Datasets While Protecting Anonymity

If you're okay with getting statistics that are not perfectly exact but noisy, a variant of randomized response could solve your problem. Instead of sending you real information about their usage, your users will send you noisy data. For a given user, you can't know for sure whether their answer to a particular question is exact or is just random (and you get a very solid property to quantify that, differential privacy). But when aggregating all responses, you can get statistics that are close to the real ones.

If you need more than binary questions, take a look at RAPPOR and the related paper — if you have enough users, you can get much more complex statistics (numerical, strings…) with a very decent precision and strong privacy guarantees.

Note that implementing such a system in practice is not trivial: you need to make sure that if you ask the same question twice to the same user (in your case, if the statistics are collected periodically) their randomized answer stays the same — otherwise, the noise cancels itself out over time and you end up learning sensitive information about them.


Is error propagation desired in modes of operation

It is neither desirable nor undesirable on its own.  Error propagation is not relevant to any modern cryptography.  The concept is a relic of an archaic school of crypto engineering that has been left to the junk heap of the previous century, but not all textbooks or instructors with job requirements to teach courses called Cryptography 101 have kept up with the state of the art.

What is relevant is authentication.  If there is any chance that an adversary might have the power to interfere with the channel between two peers—whether by intercepting packets on the wire or by compromising the server where messages or stored or what—then the peers should have a system for authenticating messages so that any changes an adversary makes have negligible chance of going undetected by the recipient.

If the peers already share a secret key that they could use with a block cipher, then, instead of picking a block cipher and a mode of operation as last century's school of engineering prescribes, they should pick an authenticated encryption scheme.  This is a gizmo that takes a key, a message sequence number, and an arbitrary bit string as a message, and turns it into a ciphertext which the recipient can use the same key to detect modifications in and, if unmodified, turn back into the message.

One example of an authenticated encryption scheme is NaCl/libsodium crypto_secretbox_xsalsa20poly1305.  Another example is AES256-GCM.  AES256-GCM happens to be built out of the block cipher AES-256, but this is an implementation detail—you should think of it as picking AES256-GCM as a unit, not picking AES and then a 256-bit key and then GCM as a mode of operation.  crypto_secretbox_xsalsa20poly1305 is not built out of a block cipher at all, and has some advantages over AES256-GCM—faster and safer in software, larger message sequence numbers so you can safely randomize them.


Are password salts equivalent to keystream?

No, they are not conceptually related.

A keystream is the output of a stream cipher and is of (effectively, for modern ciphers) infinite length. If you need to encrypt more plaintext, you use the cipher to produce more bytes of keystream.

On the other hand, password salts are of fixed size and their purpose is to make every password effectively unique. A simplification is that if two people have the passwords password but different salts, one password might be hashed as if it were passwordxSFsz8sl while the other is hashed as if it was passwordRsRb58yd. Without this protection, an attacker could (for instance) hash the 100,000 most common passwords and compare them to all of the hashes in your database. With salts, an attacker can't share this work between users in the database; to try those same 100,000 passwords, s/he must compute all 100,000 for every user in the database.

A much closer analogue of password salts is an initialization vector (or IV), used in encryption. Their purpose is very similar; they ensure that each instance of a cipher will encrypt the plaintexts differently so that even two identical plaintexts will encrypt to a unique ciphertext.


Computational Complexity: ECC multiplication vs Modular multiplication

If you only care about computational complexity, it's similar:

In ECC: the number of double-and-add steps is proportional to $O(|k|)$ (one double every bit, one add for each $1$ bit, in the non-windowed algorithm). Each double/add is a sequence of a constant number of field multiplications, squarings, additions and subtractions. Multiplication and squarings are the expensive ones, and using Karatsuba algorithm, they are $O(|t|^{1.58}$). Therefore the result is $O(|k||t|^{1.58})$.
Modular exponentiation is the same. Square-and-multiply is $O(|a|)$. Each square/multiply is $O(|p|^{1.58}$). Therefore the result is $O(|a||p|^{1.58}$)

Of course, if you need to be more precise, you'll have to decide on a specific point multiplication / modular exponentiations algorithms, since there are ones that use windows and precomputation tables; and in ECC, also specific formulas for point addition and doubling.


If I want to encrypt structured data composed of key-value pairs of strings, would it be an advantage to use an encoding that stores keys, values and their lengths, and is padded with random numbers?

Generally, no, this is not a good idea. A semantically secure cipher uses an IV or nonce (number used once, a unique number in a statically sized encoding) that randomizes the ciphertext in combination with the key used. There is therefore no need to randomize the data input (the "message") itself.
It very much depends on the mode of operation if the randomization of the message will actually fully randomize the data in the first place. In case of CBC mode a random block with the block size of an IV could be used as an alternative to a random IV. However, it would not really differ from using an IV in the first place; it will actually cost you one additional block to encrypt for no reason at all. On the other hand, if you consider the more modern CTR mode then the key stream will just be XOR-ed with the random input, and it won't influence the rest of the plaintext / ciphertext message. The random data would just be overhead without offering any benefit.
Modern authenticated modes just require a nonce, randomized or not. GCM mode for instance requires a 12 byte nonce. You can safely prefix the IV or nonce to the ciphertext (as the size is commonly known or configured in advance). Note that CBC mode requires an unpredictable (i.e. randomized) IV.


Multiple iterations of AES for key derivation?

One of the advantages of schemes like scrypt and bcrypt is that they are designed to be "hard" to brute-force. That is, the actual guts of the algorithm are designed to continuously use something that is difficult for a specialized implementation to speed up. For example, scrypt is based on sequential memory-hard operations, which makes sequential memory access a bottleneck of the computation process (meaning that the CPU is idle waiting on memory for some of the time).

This scheme doesn't leverage such a problem, and I would further argue that it's choke-point is pragmatically easy to brute-force due to the prevalence of AES-NI. For an attacker with AES-NI, a scheme like this would possibly the easiest type of scheme to brute-force because the choke-point uses the fastest cryptographic algorithm the attacker has access to.


How to add ciphered numbers under benaloh's scheme?

From here, it says that encryption in Benaloh's scheme takes the form:
$$E_r(m) = y^mu^r\bmod n$$
I'll actually write it as:
$$E_r(m;u) = y^mu^r\bmod n$$
Where $m$ is the message (in $\mathbb{Z}_r$) to be encrypted, and $u\in\mathbb{Z}_n^*$ should  be uniformly random. The other parameters $y, r, n$ are of course important for the scheme, but will not be important to discuss the additive homomorphic properties of the scheme.
The trick here is to note that messages are "in the exponent". So if we want to add the messages, we'll have to multiply the ciphertexts. If we do this, we'll see that:
$$E_r(m_0)E_r(m_1) = (y^{m_0}u_0^r)(y^{m_1}u_1^r) = y^{m_0+m_1}(u_0u_1)^r\bmod n = E_r(m_0+m_1;u_0u_1)$$
This will be a valid Benaloh ciphertext of $m_0+m_1$ (we technically should verify that $u_0u_1$ is distributed uniformly randomly over $\mathbb{Z}_n^*$, but this is not difficult).
Note that this homomorphic property is very similar to that of (unpadded) RSA, where ciphertexts take the form $E(m) = m^e\bmod N$. Of course there is the difference here that RSA must be padded to be secure, and this padding ususally removes the homomorphic property.


Any advantage of multiple salts/keys for single password when using PBKDF for multiple secrets?

Store a single pbkdf2 salt for the whole database, and derive a single
  AES key used for all the messages.

This is the better approach.
I'm confident to say that, because if you derive a new key using a proper password-based key derivation function (PBKDF) for each and every entry, you have to set the cost parameters for the PBKDF to not frustrate the user. But if you do this, then an attacker only needs to break a single one of the weaker password hashes to recover the password. So rather go with only one PBKDF operation, but make that one costly (maybe 100ms - 1s on the user's machine).

Additionally you can use a key-based key derivation function (KBKDF) to derive a new key for each entry from your master password-derived key. This KBKDF should be HKDF using most of its features (salt? key identifier? personalization string?), but if HKDF is impossible for you, simple HMAC should do as well.

There are a few gripes though with the choice of the primitives you mentioned, namely:

HMAC-SHA256 for PBDKF2. SHA-256 is based on 32-bit operations and thus performs best on 32-bit machines. If possible you should use SHA-512 because it is based on 64-bit operations and not only will perform better on 64-bit machines (your clients?) but will also be more costly for an attacker to implement in a parallel fashion because most of these devices can do 32-bit operations much more cheaply than 64-bit (especially GPUs are today always 32-bit processors)
Don't use PBKDF2 if possible, use Argon2, scrypt or bcrypt. The latter three PBKDF are modern successors to PBKDF2 and are more hardened to attacks by GPUs, FPGAs and ASICs than PBKDF2 ever could be. Also see the canonical answer on Information Security SE about this topic.
Use authenticated encryption. You have OpenSSL and as such you can use its authenticated encryption implementations, especially AES-GCM, which will give you better security than plain AES-CBC. Note though that plain AES-CTR provides less security than AES-CBC, because it is even more easier and targeted malleable, e.g. if you know where the data to change is you trivially flip the bits with CTR, with CBC you at least screw up the previous block.


If + means concatenation, then $H(A+B+C+D)$ doesn't help make verification easier. You still need all leaves in order to verify any leaf, whereas the point of Merkle tree is to be able to verify individual leaves with only logarithmic cost.

If + means XOR or addition, then $H(A+B+C+D)$ is not collision-resistant so the construction fails to authenticate the leaves.


In S/MIME, are the same certificates always used to sign and encrypt messages?

No, clients do not have to use the same certificates for signing and encrypting messages.
Actually, you already noted the reference yourself. Let me quote RFC 5751, section 2.5.3 on page 13:

2.5.3. Encryption Key Preference Attribute
The encryption key preference attribute allows the signer to unambiguously describe which of the signer's certificates has the signer's preferred encryption key. This attribute is designed to enhance behavior for interoperating with those clients that use separate keys for encryption and signing.  This attribute is used to convey to anyone viewing the attribute which of the listed certificates is appropriate for encrypting a session key for future encrypted messages.

(bold-italic emphasis mine)
As the reference states, clients can (but do not have to) use separate keys for encryption and signing.


I am currently hoping to find an answer to a similar problem, but maybe I can share some ideas. I would say that your problem is more standard than mine, and therefore it has the benefit that the existent options are relatively standard. However, my own question made me realize that key storage is an information security problem, as opposed to a cryptographic problem. With this, I mean that there is no provable best approach, but there are techniques and good practices that could help to mitigate risks, given some threat model.

Said threat model is, in fact, the most critical aspect to determine what is relevant. There are some approaches in terms of good practices, but they should be considered more as suggestions than as a checklist or a perfect answer.

One aspect that seems to be relatively agreed upon is that the encryption should happen within an environment separated from the normal processor (i.e. TPM, HSM, smart cards). I haven't looked into TPMs, but the other two seem to be the standard way to go.

Now, if additional hardware is out of the table, I can see that your approach makes sense in general. I would worry for the way in which each copy of the key is handled (encrypted and unencrypted, in RAM and in disk, in active usage and in backup), and the way in which the password is used for encryption. In particular, the less the key exists in plaintext, the better.

But mind the threat model. Knowing what you are concerned about is key to know whether your defenses are actually defending you.


If the computation is performed via an ordinary function call, then the caller and the callee live in the same address space. In this case, there is no concern about secrecy: the callee is not protected from the caller in any way. A malicious caller has access to the same memory as the callee and so they can access the key, they can inspect and modify the execution of the function, etc.

You should worry about accidental leaks, due to a buggy caller. It is standard good practice to wipe all memory that has been used for cryptographic computations after use. This way, even if the program later leaks memory, that's one secret that won't leak. For example, in this case, you should wipe the temporary variable on the stack. The basic idea is to call memset(buf, 0, sizeof(buf)) at the end of encrypt, but this actually doesn't work in practice, because the compiler is likely to optimize it away (what sense is there to write to an object that goes out of scope immediately afterwards?). CERT recommendation MSC06-C discusses this problem and some solutions (use memset_s if you have it, but it was only standardized in C11).

If the call is a cross-context call of some kind, for example a system call from a user program to a cryptographic service running in a more privileged CPU mode, or a call to a different process using shared memory, then the situation is different. In such cases, you need to be careful inside the cryptographic service to use the service's own memory for all key material and intermediate results that the client must not be able to access. Furthermore, in the service, you need to be careful when reading data in memory that is shared with the client, because the client might change the content of that memory: never read the same memory twice, or read back what you wrote. And you need to be careful when writing data to memory that is shared with the client, as the timing of these writes might convey information. The general rule for a data processing service running in a different context but communicating via shared memory (e.g. an operating system kernel) is: first copy the input parameters; then process the data in the service's memory; then copy the final output into shared memory. It sometimes makes sense to do this in several stages, but keep the data flow in mind and be aware of what the client might observe and perturb.


What is the difference between discrete logarithm and natural logarithm?

I will assume you understand modulo operation and the exponentiation.

First let's consider logarithm in $\mathbb{R}$.

You know that if we have $e^x = y$ then $x = \ln y$. The Napierian logarithm return values in $\mathbb{R}$.
You can have the same thing with another base. For example : $2^3 = 8$ and $\log_2 8 = 3$.

The simplified idea of the discrete logarithm is to return only the Integers ($\mathbb{Z}$).

In $\mathbb{R}$, we have $\log_2 5 = 2.321\ldots$. This is not interesting for us. Hard to manipulate... How does this translate into a Integer ?

Lets consider consider the integers where all numbers have to be below a certain prime number $p = 11$.
Lets also consider the only allowed operation is the multiplication : $\times$.

Therefore we have :
$3 \times 4 = 12 \equiv 1 \pmod{11}$
And so on.

This kind of structure is called a group of multiplication modulo the prime p. Its notation is the following $\mathbb{Z}_p^\times$. In this case we have $\mathbb{Z}_{11}^\times$

Let's consider $g=2$ and apply the exponent ($g^n = g \times  \ldots \times g$) :
$2^0 \equiv 1$
$2^1 \equiv 2$
$2^2 \equiv 4$
$2^3 \equiv 8$
$2^4 \equiv 2\times 2^3 \equiv 2 \times 8 \equiv 16 \equiv 5 \pmod{11}$
$2^5 \equiv 2\times 2^4 \equiv 10 \pmod{11}$
$2^6 \equiv 2\times 2^5 \equiv 9 \pmod{11}$
$2^7 \equiv 2\times 2^6 \equiv 7 \pmod{11}$
$2^8 \equiv 2\times 2^7 \equiv 3 \pmod{11}$
$2^9 \equiv 2\times 2^8 \equiv 6 \pmod{11}$
$2^{10} \equiv 1 \pmod{11}$

This is called a cyclic group of generator $g$ (here 2) : after a certain number of exponentiations, we have loop.

Now let's move back to our question : $\log_2 5 = ?$
In $\mathbb{Z}_{11}^\times$ as we have $2^4 \equiv 5 \pmod{11}$, therefore in $\mathbb{Z}_{11}^\times$, $\log_2 5 = 4$.

The discrete in discrete logarithm refer to the aspect that we are working in a discrete group and not any real numbers.


Encrypting between nodes that have RSA keys: Diffie-Hellman or random secret key?

If you're using RSA as a key encapsulation mechanism, then there is no need to use Diffie-Hellman to generate the shared secret.
Diffie-Hellman provides key agreement: Both Bob and Alice will end up with the same shared secret. No party a priori selects what that secret will be, it is determined by whatever $({g^a})^b \equiv ({g^b})^a$ happens to be.
If you did use Diffie-Hellman to generate the shared secret, then both Alice and Bob will already have the shared secret. Having Alice then encapsulate that and send it to Bob via RSA does not accomplish much.

How difficult is it to implement DH securely?

It's difficult - you are not expected to do so, and you should not need to do so. Perfectly good, free libraries that have already solved this problem exist.
Note
If it is at all possible, consider using an existing protocol and library such as TLS or libsodium instead of re-inventing this particular wheel.
If your current crypto library forces you to make these types of decisions, it's not a library you want to use.
A good crypto library will offer high level constructions that solve specific problems, rather then requiring you to combine low level constructs into a solution that you think/hope might work.

I believe this idea is pretty standard.

Quoth the bear, Nevermore
Actually, using RSA for this is not that great of an idea and is being phased out in general.

RSA-based key agreement (or transport, or exchange) with PKCS#1 v1.5 is vulnerable to Bleichenbacher attacks. OAEP (from PKCS#1 v2.0) is better, though it requires implementation to not leak partial information on failure causes, otherwise Manger's attack applies (which is like Bleichenbacher's, but more efficient). That's the first reason RSA key exchange is being discouraged.
The second reason is that RSA key generation is expensive (and hard to make constant-time)(there is a constant-time RSA keygen in BearSSL), so you don't want to make a new RSA key pair for each incoming connection. Reusing encryption keys goes contrary to forward secrecy, and forward secrecy has become a selling point (though it's a bit overhyped, in my opinion).
The third reason is basically performance, or at least performance perceived through the filter of microbenchmarks. An RSA private key operation is an order of magnitude more expensive than some ECDH.

Source: the Bear says so (excerpt from a private conversation)


How do I safely encrypt a file for transport and storage?

I'm however not very sure about how I would go about generating a suitable key from a password. Is using a simple hash function like SHA-256 secure?

No, you'd generally use a Password Based Key Derivation Function such as a secure version of Argon2. But preferably, you'd not use a password at all. It is only one factor that's required and passwords generally do not contain enough entropy for long term storage.
One trick is to use a public key for hybrid encryption, and store the private key on a separate device that is only connected when the file needs to be decrypted. That private key in turn can be encrypted.
If you use a password, I'd use a password manager with a very large password.

I'm assuming I'll have to store the IV along with the file. Is that correct?

Not necessarily. The input of a PBKDF always contains a salt value to protect against rainbow tables. From the password and salt (as well as the work factor) the output keying material can be calculated. It is possible to retrieve both a key from the output bits and the IV from other output bits.
Of course, now you'd have to store the salt value.
Full file names are also unique and could be used for a mode of operation by hashing the filename. However, that means that the file cannot be copied to another location, so generally we would try and avoid such brittle constructions.
There is of course nothing particularly wrong by storing a (random) IV, as long as it is unique with a high probability.

Would AES-256 in OCB3 mode be suitable for this sort of task or is there a better way of doing this?

It's not better or worse than any other AEAD cipher I suppose.

By the way, I am aware that it's quite easy to read the decrypted file from memory when it's decrypted at client-side, but I'm afraid there's not much I can do about it.

Well, you should harden your clients to the best of your ability. But yeah, in the end you need to access the data, and it is too large to fit into any kind of secure enclave in all likelihood.

Edit: Both server and client programs are written in c++. I also want to be able to encrypt and decrypt the files just in memory at runtime, so a lot of file encryption tools don't really fit the task.

Tools: possibly not. Higher level encryption libraries are however certainly available, and libsodium has already been mentioned.


Get IV from Key, Clear and Cipher text in AES-256 CBC

The IV is XOR'ed with the plaintext before encrypting the first block. You can get the input of the block cipher by decrypting the first block of ciphertext using the block cipher directly.

After that it is a simple operation to get the IV, of course, considering you know the plaintext and - hopefully - the mathematical properties of XOR.


Suppose the number of a set $S$ is denoted as $Card(S)$ (which is sort for cardinality if you didn't know), then

$Card($uppercase-letters$)+Card($lowercase-letters$)+Card($digits$)
=26+26+10=62$

To represent an element from a set of 62, you need a string of at least 6 bits, this is because $2^{6} = 64 \ge 62$

However I don't understand the title where it says "64 bits password = 13 characters" because $ 6 \cdot 13 = 78 $ which is way bigger here, than 64.

To achieve at least 64-bit entropy, you need to uniformly draw ${ {64} \over {log_2{62}} } \approx 11.00$ characters (10.749 to be more exact).


How to store keypair generated by RSA in a textfile?


Which is/are the strongest known Fully Homomorphic Encryption scheme(s)?

A recent paper: https://arxiv.org/abs/1804.06862 claims to be fully homomorphic with IND-CCA1. However it is a symmetric encryption scheme and I'm not sure if IND-CCA1 is an appropriate measure in this setting.

Besides this, I think security is based on the hardness of solving overdetermined systems of quadratic equation over $\mathbb{Z}_{(p\cdot q)^2)}$ rings, which then might not be Quantum-hard. If I'm not mistaken, there are sixteen quadratic equations and if we can factor $(p\cdot q)^2$ then these equations can be efficiently solved.

Otherwise the scheme is pretty efficient, in terms of key-length, decryption and encryption time, I think. It is noise free and based on ring-automorphisms for matrices with elements from the quaternion-ring over some $\mathbb{Z}_{(p\cdot q)^2)}$ ring.

However as the paper appeared only recently, an in-deep analysis, besides the argumentation auf the authors, is not yet availablabe as far as I know.


Suppose you have two message-signature pairs, $(m_1, s_1), (m_2, s_2)$, where $s_i = m_i^d \bmod n$. Suppose we also know the public exponent $e$—it is usually $65537$, $3$, $5$, $17$, or some similar small integer. Then we know that $m_i = s_i^e \bmod n$, or in other words $s_i^e = k_in + m_i$ and it follows that $\gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, k_2)n$, where $\gcd(k_1, k_2)$ is expected to be small.


Secure way to derive separate encryption and MAC keys from a single master key?

Yes, this should be secure, as it is largely compatible with KDF1 and KDF2 which basically use a 4 byte big endian encoding of the counter instead of a direct ASCII conversion to a byte. Note that this construct works fine for master keys (short length, high entropy) but may be vulnerable to length extension attacks if larger input is allowed.

However, if you want to use the latest and greatest, you could use HKDF, possibly even augmented with a salt for session keys.

HKDF and the KDF's in NIST SP800-108 typically have a better security proof and supply methods of expanding the amount of key material after extracting the key material from the input. They also incorporate methods of supplying an explicit label and other information (using "enc" and "mac" instead of '1' / '2'). Unfortunately they are not often present in cryptographic libraries, they are harder to implement, they are badly defined and they seem to offer relatively few benefits over simpler schemes such as KDF1 and 2.


PKI Validation - Usefulness of the public key with the identity certificate

I may have found an answer here: https://devcentral.f5.com/questions/difference-between-root-cert-intermediate-cert-and-ssl-cert

  One more thing one the public key of your server certificate. There is
  the same mathematical relationship as described above between the
  public key and private key of your server certificate.

  It will be used during the SSL handshake. The client encrypts some key
  material servers public key (retrieved by the client out of the server
  certificate) and sends it to the server. It can be decrypted by the
  server using the private key. If the server does not have the matching
  private key it cannot decode the key material and the handshake
  brakes.

But the above may be referring to using RSA for symmetric key transference, which like I posted earlier is generally done by ECDHE these days.

I imagine you'd just be able to take the certificate and use it to spoof a site if you successfully hijack DNS without any validation of the identity certificates public key. Surely it's validated in some way.


How much data do I leak if I use the first bytes of a file as AES-CBC IV?

The danger I see with using the beginning of a file as the IV is that the beginning of files tend to be fairly predictable.  For example. Linux shell scripts tend generally have a first line of "#!/bin/bash" - 11 characters (12 counting the Linux end-of-line LF character). If each file has a separate key this isn't much of a risk, but if the same key is used for multiple files then the IV reuse can result in problems (see this question or this question, or this question for examples)


Are there any symmetric cryptosystems based on computational complexity assumptions?

Finding uniform random $x$ given $x^3 \bmod{pq}$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $\operatorname{AES256}_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.

That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 \bmod{pq}$ is much costlier than the computation of $\operatorname{AES256}_k(92187681)$.  In other words, RSA-2048 is much more expensive for less security than AES-256.

You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’.  But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks.  In reality, AES is a much harder problem than RSA!

There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM.  Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.

The term ‘provable security’ means nothing more than there is a theorem.  These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA.  So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.

* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier.  There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard.  Hence not even the RSA problem has ‘provable security’ relative to factoring.


Proof that a given function is not a OWF

The attacker is given $y = f(v,w)$ and must find $v$ and $w$. The attacker can generate a random $v_0$ and calculate $g(v_0)$; then they can simply calculate $w_0=y⊕g(v_0)$ and then return $(v_0,w_0)$, for which $f(v_0,w_0)=y  \implies \Pr[\mathit{Invert}=1]=1>\mathit{negl}(n)$.


Why can't NORX produce intermediate auth tags like Keyak can?

The NORX documentation does not specify how to use it for intermediate tags, but I agree with Richie Frame that it could easily support them. Using intermediate tags in sponge-based authenticated encryption was considered by Bertoni et al., SAC 2011, see Section 2.1. Since NORX's mode of operation is derived from the same construction, I see no obvious obstacle.

Note that, on the other hand, Keyak explicitly specifies the concept of a session with intermediate tags, its implementation readily supports them and its security analysis takes them into account.

About the second part of your question, i.e., that Keyak "seems to be slow in the absence of hardware acceleration", there is no objective reason to believe so, since Keyak with its 12 rounds and full-state absorbing should be at least twice faster than SHAKE128. For instance, our current benchmarks confirm the comment of Biv, as Ocean Keyak takes about 1.8 cycles/byte on Haswell on a single core.

Disclaimer: I am one of the co-designers of Keyak.


Why is proof-by-reduction needed (for Elgamal proof of security, for example)?

Why is proof-by-reduction needed?

In general, reduction proofs are a very common thing in computer science. Specifically in cryptography, the reasoning goes something like this:

  The general cryptographic community believes that problem $X$ is very difficult to solve. I have designed a new cipher $Y$ and want to convince the community that it would be hard to break. So, I assume that someone could efficiently break $Y$, then I show that using an efficient break of $Y$, someone could also solve problem $X$. Therefore, we can conclude that breaking $Y$ is at least as hard as solving $X$. Since general consensus is that $X$ is really hard to solve, $Y$ must be a secure cipher.

That is not the only way to prove security of a cipher. If I remember correctly, the proof of security for the one-time-pad does not follow this paradigm. It has, over time, however, proven to be a very good way to prove security of a cipher and has worked well in practice.

  Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?

See Maeher's comment.


I've figured it out.  The Message schedule is 64 words in length where as the chunk is only 16.  The schedule contains a copy of the chunk in the first 16 words then smears the original 16 words in the chunk to the remaining 48 words.


How can public key not reverse encryption if the algorithm is known?

I will give you the simplified answer.

The public key encryption does not prevent adversery from computing private key from public key. It just makes it very very very hard. The algorithms use math that allows simple private->public calculation, but public->private has no good mathematical "shortcuts". It would take adversery more time to calculate this, then for him to walk in front of every home on Earth, and beat every occupant inside with a rubber hose while asking about content of Your message.


$\ell_2$-norm vs canonical embedding norm on ring-lwe

I think you are mixing up some concepts... There are two things here: the embedding and the norm.
Those schemes are defined over polynomial rings, but for several reasons (e.g. to relate them with lattice problems, to have some geometry) we want to analyze them in vector spaces.
So, representing those ring elements as vectors is what we call embedding. There are several ways to embed them. For instance:

"The naïve way": just represent a polynomial $p(x) = \sum_{i=0}^n a_i$ as a vector $\vec{p} = (a_0, a_1, ..., a_n)$;
The canonical embedding: For $1 \le j \le n$, define the isomorphism $\sigma_j$ from $\mathbb{Q}[x] / \langle \Phi_m(x) \rangle$ to $\mathbb{C}$ as $x \mapsto \zeta^j$, where $\zeta$ is an $m$-th root of unity in $\mathbb C$. Then for any polynomial $p(x) = \sum_{i=0}^n a_i$, associate the vector $\vec{p} = (\sigma_1(p), \sigma_2(p), ..., \sigma_n(p)) \in \mathbb{C}^n$.

Once you have an embedding, you can just use the norms as usual, because you are working on a vector space. And that is what papers usually do: they use the $\ell_2$ and the $\ell_\infty$ norms after choosing one method to embedding elements.
Therefore, what you are calling canonical norm is just the usual $\ell_2$ or $\ell_\infty$ on vectors obtained by the canonical embedding.
Maybe what is tricking you is "why to use the canonical embedding instead of the naïve one?". If this is the case, I suggest that you read at least the introduction and the section 2 of A Toolkit for Ring-LWE Cryptography.


Difference between HMAC-SHA1(key, msg) vs SHA1(key + msg)

Right off the bat, SHA1(key + msg) is vulnerable to length extension attacks. That is, if I know SHA1(key + msg) I can use that to compute SHA1(key + msg + anything I'd like to add here) without having to know the key.


Scrypt KDF cipher (scrypt CLI) - known vulnerabilities and cryptanalysis?

scrypt
scrypt is actually a password-based key derivation function (PBKDF *) created by Colin Percival; Stronger Key Derivation via Sequential Memory-Hard Functions. We want slower PBKDF functions since it will slow the attack times. The below is from hashcat performance;
scrpyt                         1172.8 kH/s (16.61ms)
PBKDF2-HMAC-MD5               18059.2 kH/s (69.72ms)

It is slower and designed against large-scale custom hardware attacks (ASIC,FPGA, and GPU) by requiring a large amount of memory. Internally uses PBKDF2 and Salsa20/8.

Any known cryptanalysis for scrypt / vulnerabilities?

The attackers cannot reverse the scrypt to find a pre-image. The only meaningful way is the password cracking by trying all possible passwords up to some length, checking the common password list, and trying combinations, or various other methods. If you want to mitigate this, you need to use a password with good entropy. You can generate one using diceware ( also EFF has a nice diceware page) or Bip39 or some other system that generates password with good entropy.

is scrypt considered in the community as a secure (comparable to sha256) cipher?

SHA256 is not a cipher, it is a hash function. You can also use SHA256 for KDF however not advised. The KDFs are designed for these purposes. For hash functions, we consider the pre-image, secondary pre-image, and collision resistance. For KDF functions the collision resistance or the collision attacks are not related.
There are no attacks on scrypt except for the first item.

How collision-resistant is it?

Collisions are not related to password hashing, the pre-image is requried

Is it easily breakable by quantum computing attacks?

Hardly, since the number of q-bits will be much higher than AES. The main reason will be a large memory. If ever built, it will use Grover's algorithm.
scrypt CLI program.
In short, scrypt CLI program uses AES256-CTR for encryption and HMAC_SHA256 for integrity and authentication. Little details;

AES with the key size 128 bits resisted attacks even after nearly 22 years and practically still secure [1] [2] but vulnerable to multi-target attacks. From the code, as we can see, they use a 32-byte key, i.e AES256. That is even secure against Grover's quantum search [3].
CTR mode requires a nonce (number used once), and should not be repeated. Once reused, it will be vulnerable to the two-time pad.
HMAC is Hash-based Message Authentication Code here initiated with SHA256. It's security proven by Bellare, Mihir (June 2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance under the assumption that the compression function is PRF.

* : don't confuse with PBKDF1 in rfc 8018


How can we build a ZKP simulator for “Were is waldo?”?

I think that it would be more suitable to model this as witness hiding, meaning that after the proof it should be still be "computationally hard" to find Waldo. The best place to learn about witness indistinguishability and hiding is either in Oded Goldreich's Foundations of Cryptography (volume 1), or in Uri Feige's PhD Thesis.

In general, witness indistinguishability is a property that just says that it's not possible to distinguish which witness the prover knows. It is not hard to show that zero-knowledge implies witness indistinguishability, but it gets more interesting. For example, parallel repetition of witness indistinguishable proofs preserves witness indistinguishability and reduces soundness. Thus, it is possible to construct 3-round witness indistinguishable proofs for any language in NP (something that is not possible for zero knowledge, at least not for black-box zero knowledge).

Feige also defines witness hiding, which means that if a language is hard and one cannot extract a witness, then even after the proof the verifier cannot extract a witness. For example, consider a randomly sampled tuple $(g,h,g^x,h^x)$. Then, a prover could prove that this tuple indeed is of this form (what we call a Diffie-Hellman tuple) using a zero-knowledge proof. Alternatively, in some cases it may be enough to just prove that it is of this form in a way that ensures that a cheating verifier cannot learn $x$ (or any other witness to this fact). As such, witness hiding is the "one-way function" analog of zero-knowledge; it is much weaker, but makes sense in some cases. Feige showed that any witness indistinguishable proof with two "computationally independent witnesses" (meaning that one cannot learn one witness without the other) is witness hiding.


Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

let $a=g^{k_1} \pmod n$ and $b=g^{k_2} \pmod n$. We want to prove that $a^{k_2} \equiv b^{k_1} \pmod n$. By congruence definition, $\exists t_1 \in \mathbb{Z}/\,a=nt_1+g^{k_1}$ and $\exists t_2 \in \mathbb{Z}/\,b=nt_2+g^{k_2}$. We want to prove that $(nt_1+g^{k_1})^{k_2} \equiv (nt_2+g^{k_2})^{k_1} \pmod n$. By binomial theorem, we have $(nt_1+g^{k_1})^{k_2} = \sum _{i=0}^{k_2} \binom{k_2}{i}\times(nt_1)^i\times(g^{k_1})^{k_2-i}$ and $(nt_2+g^{k_2})^{k_1} = \sum _{j=0}^{k_1} \binom{k_1}{j}\times(nt_2)^j\times(g^{k_2})^{k_1-j}$. The only time where $nt_1$ and $nt_2$ disapear is when $i=0$ and $j=0$, otherwise the two sums are $\equiv 0 \pmod n$. Thus, $(nt_1+g^{k_1})^{k_2} \equiv \binom{k_2}{0}\times(nt_1)^0\times(g^k_1)^{k_2-0} \equiv g^{k_1k_2} \pmod n$ and $(nt_2+g^{k_2})^{k_1} \equiv \binom{k_1}{0}\times(nt_2)^0\times(g^k_2)^{k_1-0} \equiv g^{k_2k_1} \pmod n$. Hence, $g^{k_1k_2} \equiv g^{k_2k_1} \pmod n$.


Difference between Asmuth-Bloom and Shamir's Secret Sharing

As has been commented, Asmuth-Bloom is does not always give a perfect scheme.  The original paper gives a condition on the primes to maximise "sharpness", which is what they call their measure of closeness to perfection.

A recent paper at Asiacrypt 2018 gives fairly detailed analysis of the differences, and they also construct a new scheme using similar techniques.  In the introduction they remark:

  In  a  word,  Shamir’s  scheme  is  ideal  and  easy  to  construct
  while  Asmuth- Bloom’s  scheme  is  not  ideal,  hard  to  construct
  but  more  natural  and  neat  in constructing  weighted  SS  scheme.

So while Shamir's scheme is very good for threshold schemes by most metrics, if one wants to construct secret sharing schemes for weighted threshold access structures then Asmuth-Bloom, these authors claim, has a more "natural" generalisation.  (Weighted threshold schemes are defined in the same paper, and are basically a way of fine-tuning the qualified sets of the access structure.)


Well, assuming that you have a fixed block cipher (that is, you don't change the block cipher as the length of the message increases), then given a message of length $N$:

Both ECB and OFB take $O(N)$ time for both encryption and decryption.
Both ECB and OFB take $O(1)$ space in addition to the space to hold the encrypted/decrypted message (which is $O(N)$).


Is it actually possible to secure data with gpg DSA keys?

Why does The Digital Signing Algorithm encrypt data [...]?

You can't encrypt data using DSA.
However gpg supports ElGamal encryption, which is an encryption scheme which can be quite naturally derived from the Diffie-Hellman key exchange and typically gpg pairs "DSA signing" with "ElGamal encryption". Why is it paired like that? Because (in theory) you could use your DSA public key for ElGamal encryption and both scheme's security is strongly related to the discrete logarithm problem, so it makes sense pairing them.

  Why is this even an option in gpg ?

Back in the day, the dark ages of crypto, RSA was patented. That is you needed to license it from RSA (the company) to use it. This is one of the reasons why DSA was developed and as established above pairing ElGamal with DSA makes sense. Now of course gpg was also affected by the patent issues surrounding RSA which is (I could imagine) why they originally offered only DSA / ElGamal. The RSA patents have expired in the 2000s which is why we have now RSA for everything and DSA / ElGamal mostly is left in for backwards compatibility and to let users a choice on factoring vs discrete logarithm based security.

  Is with DSA "encrypted" ( if it even is ) data secure ?

As this means that the data is actually encrypted with ElGamal and only used to encrypt the key for hybrid encryption, I'm very confident that this is actually secure.


Example of a PRP that is not a strong PRP

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP.

A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$, where $f$ is an element of a pseudorandom function family.  This PRP will be keyed with three keys $k_1, k_2, k_3$, which will be used to key a PRF $F$ differently each round.

We define $E_{k_1,k_2,k_3}$ to be a three-round Feistel network:

$E_{k_1,k_2,k_3}(L \| R) = \operatorname{Concat}(P_{F_{k_3}}(P_{F_{k_2}}(P_{F_{k_1}}(L, R))))$

Assuming $F$ is a PRF, $E$ will meet the definition of a weak PRP.  I believe this proof is originally attributed to Luby, Rackoff (for details of the proof, see here, starting on page 11).  Similarly, the inverse $D_{k_1,k_2,k_3} = E^{-1}_{k_1,k_2,k_3}$ is also a weak PRP.

Interestingly, though, $E$ is not a strong PRP.  When given simultaneous access to both a "forward" oracle and a "backward" oracle, an adversary can distinguish between $(E_{k_1,k_2,k_3}(\cdot), D_{k_1,k_2,k_3}(\cdot))$ and $(\Pi(\cdot), \Pi^{-1}(\cdot))$, where $\Pi$ is a randomly selective permutation on the same domain.

Here is an adversary that distinguishes the two with high probability:

Query the decryption oracle with two strings of zero bits: $(a\|b) \leftarrow D(0\|0)$
Query the encryption oracle: $(c\|d) \leftarrow E(0\|a)$
Query the decryption oracle again: $(e\|f) \leftarrow D((b\oplus d)\|c)$
If $e=c\oplus a$, then return $1$, else return $0$.

Here's why this works:

By expansion, we see that $D_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_3}(R))$

$y=L \oplus F_{k_3}(R) \oplus F_{k_1}(R \oplus F_{k_2}(L\oplus F_{k_3}(R)))$
It follows that the first oracle query will result in:

$a=F_{k_2}(F_{k_3}(0))$

$b=F_{k_3}(0) \oplus F_{k_1}(a)$
By expansion, we see that $E_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_1}(R))$

$y=L \oplus F_{k_1}(R) \oplus F_{k_3}(R \oplus F_{k_2}(L\oplus F_{k_1}(R)))$
It follows that the second oracle query will result in:

$c=a \oplus F_{k_2}(F_{k_1}(a))$ and

$d=F_{k_1}(a) \oplus F_{k_3}(c)$.
Note that $b$ and $d$ both contain the term $F_{k_1}(a)$.  When we compute $b\oplus d$, the terms cancel:

$b\oplus d=F_{k_3}(0) \oplus F_{k_3}(c)$
Finally, in the third oracle query, the specifically crafted $L$ and $R$ cause the following simplification:

$e=c \oplus F_{k_2}((b\oplus d) \oplus F_{k_3}(c))\\=c \oplus F_{k_2}(F_{k_3}(0))\\=c \oplus a$
The adversary finds that $e=c\oplus a$ as required, which would only be expected with low probability for a truly random permutation.

The basic idea is to set things up so that $F_{k_2}$ receives the same input in two different queries.  This causes the left oracle output to be masked with the same value, which can be detected by the adversary.

Crucially, this attack would not work without the ability to query the permutation in both directions.


Malleability of ElGamal and Hashed ElGamal

There are different crypto-systems that have been called Hash-Elgamal. The one your exam refers to is likely whatever was included in your course. Without knowing that, we can't necessarily answer your question.

The most common is the Elgamal variant defined with encryption function: $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$

This is still a malleable encryption function, except that the adversary must xor in the amount they want to change the encrypted message by. So strictly speaking, it may protect against the exact attack of multiplying in constants, but it does not prevent the broader attack of being able to manipulate a message under encryption (without knowing the message).

Hash Elgamal could also refer to the Fujisaki-Okamoto heuristic applied to Elgamal. This prevents malleability but can also lose the CPA-security of Elgamal. Other Elgamal variants that use a hash function are Cramer-Shoup (mentioned by @jalaj) and DHIES. These are both secure against any malleability (they are CCA-secure) however they aren't typically referred to as hash Elgamal.


Are any attacks / compromises possible if a server sends its public key $(n,e)$ in the clear to a client?

Nope, it's a public key; it's designed to be public. Shout it out loud, tell the world, there's no risk.

That said, you want to be sure that a Man In The Middle attacker can't intercept the message and replace your public key with their own and then pretend to be you. The only real way to prevent this in to get your public key embedded into a Public Key Certificate tying that public key to your server in some unique way (IP, or domain name, or email address, etc) by a Certificate Authority that both you and the other person have in their trust store. (I'll leave out further details from this post.)

  Suppose a server is using the same public key $(n,e)$ for all the clients in a LAN. Does this pose a threat?

Yup, that's fine.


How to compute the discrete logarithm of Diffie-Hellman with a composite modulus?

I think the problem is that you are trying to recompute the result in $(p-1)(q-1)$ instead of $n$ and that is why you don't find the exact $x$.

Your question is:

  I can compute the discrete logarithm of $y=g^x \mod n$ by computing
  the discrete logarithm of $y$ modulo $p$ and $q$. But then how to
  recompute it?

As I understand, you want to find the discrete logarithm of $y$ modulo $n$, not modulo $(p-1)(q-1)$.

Let be $x_p$ the discrete logarithm modulo $p$ and $x_q$ the discrete logarithm modulo $q$. So to recompute the result we have to solve the system
$\left\{
\begin{array}{l}
  x \equiv x_p \mod p \\
  x \equiv x_q \mod q
\end{array}
\right.$

If $gcd(p,q) = 1$ then you can apply the chinese remainder theorem by using the Gauss algorithm (check also the Garner algorithm which is more efficient) without having to consider $p_1$, $p_2$, $q_1$, $q_2$ and you will find a unique solution.

  What about when $lcm(p−1,q−1)$ is way smaller than $(p−1)(q−1)$?

If $gcd(p,q) \not = 1$ but $gcd(p,q) \text{ | } x_p - x_q$ the system can still be solved but there exist several solutions.

Otherwise, you will not be able to recompute the solutions modulo $p$ and $q$ into the modulo $n$.


Modes of operation that simply uses the tweak of a tweakable block cipher

Many people want a "seekable cipher", which implies that they can't use chaining modes.(a) (b)
So far I've seen 3 ways to build such a cipher:

XTS: "XEX-based tweaked-codebook mode with ciphertext stealing (XTS)" is used in most modern "full-disk encryption" systems. (c)
CTR: "Counter mode (CTR)" (d)
OCB "Offset Codebook Mode (OCB)" (e)


Message mapping to elliptic curve in BLS signature

It depends on whether the pairing is a type 1 pairing or some other type of pairing. In a type 1 pairing, $S$ is a multiple of $P$. In any other type of pairing, $S$ is not a multiple of $P$.


How do mix networks work with server downtime?

It depends on your choice of mixnet, as to whether a mixnet is resilient in the case that C doesn't participate (for whatever reason, including system failures and adversarial behavior by C).

For onion routing, where the ciphertext is of the form

$enc(pk_A,enc(pk_B,enc(pk_C,enc(pk_D,m))))$,

the mixnet is not resilient, because $enc(pk_C,enc(pk_D,m))$ cannot be decrypted without participation of C.

By comparison, for a re-encryption mixnet, where the ciphertext is of the form

$enc(pk,m)$,

the mixnet works, since B can skip C and send directly to D. The resulting reduction in anonymity corresponds to reducing the number of mix nodes from four to three.


Clarification of Advantage vs Probability/Success of an Adversary

There is nothing special about advantage versus probability of success, and they should be used where it makes sense and improves readability. When considering distinguishing games (like for encryption, PRG, and the like) advantage has the benefit of simplifying notation. Also, it "behaves nicely" in the sense of being able to add advantages and the like (although this should always be checked formally via the distinguishing probability equations). Note that in distinguishing tasks, it is always possible to succeed with probability 1/2. So, it is only interesting to know how much the adversary can succeed beyond 1/2, and this is the advantage. This makes things nice since we can just talk about a negligible or non-negligible advantage.
When considering computational and not distinguishing tasks, advantage no longer makes sense. Here, if the adversary can succeed with non-negligible probability then it's broken. As such, the success probability is all you need to talk about.


How close is AES to random oracle model?

Like all PRNGs (pseudo random number generators), there can be no guarantee of randomness, so therefore no statement to that effect can exist. However, reasonable randomness for a given application can often be demonstrated.

Following up on Daniel Lemire's work: I used 254 p-values (30 corrected) obtained from each of over 512 TestU01 BigCrush results on high and low 32-bits (forward, reversed and byte reversed) of the 64-bit output to perform a (work-in-progress) meta-analysis of AES in counter mode (seeded using SplitMix). I find no evidence that suggest any issues with AES, however BigCrush (thus my meta-analysis) has its limitations.

I believe others (perhaps Vigna/Blackman) have performed Hamming Weight Dependency analysis on it to over a petabyte, but cannot find documentation.

Wikipedia has an AES article with information on security, which is a related topic.


Russian spy Reino Häyhänen, code name VICTOR;
https://en.m.wikipedia.org/wiki/VIC_cipher


Choosing good entropy $g$ and $p$ for a classic Diffie-Hellman Key exchange

The most commonly used values are in this RFC; it includes groups that range from 1536 to 8192 bits; the size 2048 is actually the most common.

The properties of these groups include:

The modulus is chosen using a 'nothing up my sleeve' method (and hence is unlikely to be specifically chosen to be especially vulnerable)
The modulus has the high 32 bits and the low 32 bits all set; this can be useful for some modmul algorithms
It has $g=2$; this can make the initial computation of $g^x \bmod p$ rather more efficient
The order of the subgroup generated by $g$ is a prime of size $(p-1)/2$; a size which is quite sufficient for security

DannyNiu's reference to the IANA TLS groups (actually, the groups 256-260; the others are various elliptic curves which aren't what you are asking about) are another set; they're actually generated using the same procedure (and share the above properties), but are deliberately slightly different (to avoid potential factor-based style attacks against the original group)


You forgot step 4:

  $m$ and $s$ should each be primitive roots mod $p$ and mod $q$

$m$ is not a primitive root mod $p$.  We can easily deduce that (without the bother of actually performing any nontrivial math) from the relation you gave:

$$s^{e_p} = m \bmod p$$

for $e_p$ even; hence $m$ must be a quadratic residue, and hence cannot be primitive.

As $e_p$ is even and $e_q$ is odd, there is no solution to the CRT...

For your reference, $m$ will be a primitive root of a prime $p$ if, for every prime factor $r$ of $p-1$, we have $m^{(p-1)/r} \not\equiv 1 \bmod p$


What exactly is a negligible (and non-negligible) function?

In perfectly secret schemes like the one-time pad, the probability of success does not improve with greater computational power. However, in modern cryptographic schemes, we generally do not try to achieve perfect secrecy(yes governments may use the one time pad, but this is generally not practical for the average user). In fact, given unbounded computational power, all of our non-perfectly-secret schemes are insecure(also note that for public-key cryptography, perfect secrecy is unachievable using classic cryptography so all schemes are insecure against unbounded computational power). Instead, we  define security against a specific set of adversaries whose computational power is bounded. Generally, we assume an adversary that is bounded to run in time polynomial to $n$, where $n$ is the security parameter given to the key generation algorithm(more precisely, the key generation algorithm is given input $1^n$ so that $n$ will be its input size and its output--the key--will be polynomial in the size of its input.)

So consider a scheme $\Pi$ where the only attack against it is brute force attack. We consider $\Pi$ to be secure if it cannot be broken by a brute force attack in polynomial time.

The idea of negligible probability encompasses this exact notion. In $\Pi$, let's say that we have a polynomial-bounded adversary. Brute force attack is not an option. But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one. In this case, we define security using negligible functions: The probability of success has to be smaller than the reciprocal of any polynomial function.

And this makes a lot of sense: If the success probability for an individual guess is a reciprocal of a polynomial function, then the adversary can try a polynomial amount of guesses and succeed with high probability. In sum then, if the overall success rate is $1/poly(n)$ then we consider this a feasible attack and the scheme is insecure.

So, we require that the success probability must be less than the reciprocal of every polynomial function. This way, even if the adversary tries poly(n) guesses, it will not be significant since it will only have tried:

$$\mathit{poly}(n)/\mathit{superpoly}(n)$$

As $n$ grows, the denominator grows far faster than the numerator and the success probability will not be significant.

Edited to add Here is an informal argument that may make this clearer: To see that the notions of superpolynomial brute force attack and negligible probability guessing are equivalent, consider a scheme with $K$ possible keys.

Brute force attack on the key set runs in $K$ time. Moreover, the probability of choosing a key at random and it being the correct key is $1/K$. Now, if $K$ is polynomial in $n$, (the security parameter), then this scheme can be brute forced in time $K = \mathit{poly}(n)$. Moreover a random guess succeeds with probability $1/K= 1/\mathit{poly}(n)=\text{non-negligible}$
and the scheme is by both definitions insecure.

To secure the scheme then, we want to make brute force run in superpolynomial time. In other words,$K$ must be superpolynomial in $n$. Well then, the probability of guessing correctly on a single guess is $$1/K=1/\mathit{superpoly}(n)$$ and this is by definition negligible probability.

Although informal, I think this last part motivates the use of negligible functions in security proofs.


Self-synchronizing cipher recovery from dropped bits

First, when the textbook talks about 'dropped bits', they are not referring to bits that are received incorrectly; instead they are talking about transmission errors where certain bits are deleted.

One example of this would be if the sender sent the pattern:

$$0123456789$$

and the receiver received:

$$012456789$$

That is, the byte containing the value 3 has disappeared, and the 4 immediately follows the 2.

Furthermore, the textbook is referring to a rather older understanding of CFB.

  This is the equation for CFB:
  $$ C_i = E_K (C_{i-1}) \oplus P_i $$

Actually, in the original design of CFB, it was a bit more complex; it was:

$$ C_i = \text{Trunc}_k(E_K (C_{i-1} || C_{i-2} || … || C_{i-n/k})) \oplus P_i $$

where:

$k$ is a value selected by the designer
$\text{Trunc}_k$ is a function that returns only the first $k$ bits of its argument
$P_i, C_i$ are $k$ bit values (rather than the full block size of $n$)

This is equivalent to the modern understanding of CFB if $k=n$; however we can also consider smaller values of $k$.

Now, why would we do that (especially considering that CFB becomes less efficient with smaller $k$; we perform one block encryption for every $k$ bits)?

The answer is because of error recovery; suppose that we have a communication channel that could, by accident, add or delete blocks of $k$ bits (as explained above).  If we look at, for example, CBC mode, if we had a long encrypted stream, and deleted 8 bits from the ciphertext, the blocks that the decryptor used to decrypt would not line up with the blocks that the encryptor used, and so the decryptor would get gibberish; and they would never sync up (until a multiple of block size bits were deleted).

In contrast, if we used CFB mode with $k=8$, then deleting 8 bits from the ciphertext is not a major issue; the next 8 bytes (assuming a 64 bit block size; given the historic context we're talking about, this is appropriate) will be gibberish, but after that, things would sync up, and (assuming that the communication channel didn't get more errors) everything would decrypt correctly.

This is what the textbook was referring to; that even after add/delete errors, CFB mode (with an appropriate $k$) will resync.

And, yes, back in those days, we had communication channels that could add or delete blocks of bits as a common error; RS-232 could delete or (more rarely) add bytes (and so $k=8$ would be appropriate in that case); I believe that bisync could add or delete individual bits (and so $k=1$ would work there).

Now, all that is historic; in the modern error, we are rather more sensitive to the issues an attacker could do if he could modify the text.  Hence, we are less interested in self-synchronization properties of CFB, and are considerably more concerned about detecting when any error has occurred (either by accident or by maliciousness).


Bijective encryption function in Paillier cryptoststem

How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece?

You do realize that this would make encryption insecure, don't you?  After all, someone who knows what an encrypted 1 looks like can subtract 1 until he gets one; this immediately reveals what value the original ciphertext stood for.

If security is not a requirement, might I suggest using the identity function as your encryption mechanism.  It is deterministic, it can be implemented quite efficiently, and for that matter, it is fully homomorphic.


What’s the difference between a secret key and a seed?

I suspect that what you're referring to is the operation of a pseudo-random number generator (PRNG).  It takes a seed as input, and produces a random-seeming series of outputs.

If you derive a cryptographic key from the outputs of the PRNG, then the key chosen depends on the seed.   If an attacker knows the seed, they may well be able to (much) more efficiently guess the key.

If the seed is created using a source of randomness (as compared with a source of pseudo-randomness), then, at least in part, it is not predictable, and the resulting outputs of the PRNG are not predictable.  If you then throw away the seed (so that it can't be stolen after the fact), you should be able to use the key with some confidence.

You ask specifically:

  So, is the secret key just typically an expanded version of the seed?
  If so, via some key derivation algorithm?

I would say that while it is worded a bit oddly, you could probably look at the secret key as an "expanded version of the seed."  The process is slightly more complicated than just via the key derivation algorithm, because you omitted the PRNG.  So: seed -> PRNG -> key derivation algorithm -> key

  Also, if you can easily obtain the key when you have the seed, why
  don't we just use the seed as the secret key instead?

The short answer is that the seed has a small amount of real randomness that takes time and effort to acquire.  By contrast, the PRNG changes that seed into significantly more pseudo-random output very quickly / cheaply.

You can definitely use the seed (or, a series of seeds, presumably, since you probably need more data than just one seed contains) as a data source to generate your key.  (seed1 + seed2 + seed3 + ... + seedN) -> key derivation function -> key, omitting the PRNG.

The reason it isn't done that way is because:

True random (as distinct from pseudo-random / PRNGs) sources are much much slower and more expensive
Key derivation functions are potentially very sensitive to any predictable information in the input data.  That means that input data (e.g. your seed) that is even partially predictable is dangerous.  So you would need the seed to be generated completely from a slow, expensive, true random source rather than just having a fraction of the seed be truly random.
You need a significant amount of data, so you need more than just one seed.  See above about each one being expensive by comparison to PRNG output.


There are only two messages from the client before TLS permits the server to send

Application Data; ClientHello and the other one, in that order.  Furthermore, the client does

not keep any secret randomness between ClientHello and that other message from the client.

Thus, the third party can use the following strategy in an attempt at breaking deniability:

Before the connection starts, the third party generates ClientHello, chooses a PRF key, and gives Andy that ClientHello and obfuscated code implementing [apply the PRF to the server's initial response, and use that output and randomness to generate the next client-to-server message].

Andy sends the ClientHello from the third party, applies the obfuscated code to Selma's response, sends that code's output to the server, gets authentincrypted Application Data from Selma,

and then sends both of the Selma-to-Andy messages to the third party.

Since the third party knows the PRF key, the third party can

verify-and-decrypt the alleged authentincrypted Application Data from Selma.

By this answer's first two sentences and the security of the to-be-obfuscated-code's PRF

and the fact that TLS's MACs are stateless, regardless of the Level #, just rewinding isn't

enough, so if the obfuscation was Virtual Black Box then, without Selma's cooperation,

Andy couldn't get the third party to accept any Application Data other than

that actually sent by Selma, even when Andy has oracle access to the third party.

Of course, Virtual Black Box obfuscation is impossible in general, but other than Level 4+ and the +s of higher levels implying a secure signature-with-message-recovery scheme for which TLS's symmetric part is the signing algorithm, I'm not aware of any arguments that there shouldn't be an obfuscation scheme that's good-enough at obfuscating the relevant things from this answer.

(On the other hand, I also have very little idea of what such obfuscation schemes might look like.)

Level 1:
If instead the obfuscated code took a ClientHello message as another input (rather than the third party giving Andy a specific ClientHello message) and used a perfectly invoker-randomizable PRF, then for all obfuscated-programs which it's possible for an honest third-party to generate

(but otherwise chosen by the server), the server would have exactly zero ability to distinguish Andy's first two messages (with the latter generated via the obfuscated-program) from a normal client's first two messages.  (weakPRP-based constructions of invoker-randomizable PRFs

result in the perfect invoker-randomizability property holding unconditionally.)

Level 2:
Level-1 code could be extended to authentencrypt Application Data from the client and

decrypt authentincrypted Application Data from the server.  In this case, under the same

assumption on the obfuscated-code, the only way for the server to distinguish Andy

from normal clients will be sending invalid allegedly-authentincrypted Application Data.

Level 3:
Level-2 code could be extended to [come close-enough to verifying the

authentincrypted Application Data from the server] that, under the same assumption

on the obfuscated code, it will be hard or [information-theoretically impossible]

for the server to distinguish Andy from a normal client.

Level 4:
Level-3 code could be modified to verify the authentincrypted Application Data from the server

in the same way as a normal client, so that under the same assumption on the obfuscated code,

the server will have zero ability to distinguish Andy from a normal client.

The + of a Level:
There could be [a specific simply-efficient obfuscation scheme achieving the Level] for

which it is infeasible for Andy to have a non-negligible chance of fooling the third party.

(rather than [the scheme just being fast-enough to break deniablility]

or [there just not being an efficient way to reliably simulate])

Level 5:
Level-4 code could be modified to output [signatures from a standard signature scheme] on structs encoding [the relevant parts of the protocol's first three messages] and [the plaintext Application transcript].  In that case, the third party would only be needed to securely generate

the signature verification key and obfuscated code, rather than also to check Andy's claims.

Level 6:
There might even be canonical "obfuscated code" that breaks deniability at Level 5,

in which case there wouldn't even need to be a designated third party

- Everyone could check without needing to trust anyone.


I need a pathway for studying Lattice-Based Cryptography

Katz and Lybushavesky just (yesterday) released a book on lattice based cryptography. My particular copy is still shipping, so I can't mention whether it covers what you are in particular interested in, but as:

Lyubashevesky is a co-author of both the KYBER and DILITHIUM finalists

Katz's prior book (with Yehuda Lindell) Introduction to Modern Cryptography is widely praised for its excellent writing (and Katz is a co-author of the non-lattice Picnic round 3 alternate signature scheme)

It seems quite possible this could be the "goto" recommendation for learning lattice-based cryptography generically, and potentially even have exposition on the NIST candidates --- I won't know until my copy arrives though.
These slides by Daniel Apon (at NIST) regarding why NIST made the particular round 3 selections may also be useful for discussing the "design space" of lattice-based NIST candidates. You can find this kind of exposition elsewhere, for example in this paper of Dan Bernstein --- although I should mention that Dan often disagrees with certain "consensus" viewpoints within lattice cryptography.
The paper is still useful of course, but if I recall Dan in particular has slightly non-consensus views on:

The underlying choice of ring for RLWE (in particular, the size of its Galois group)
Particularities of the definition of security often used in lattice cryptography (the "core-SVP" count)
Certain potential patent issues with various RLWE-type techniques

One can read more about these disagreements on the NIST pqc google group, but I don't know of some short summary of them.


Why don't parameters generated by dhparams conform to `(2^p) mod (p-1)/2 == 1`?

OpenSSL prefers groups where $g$ (in this case, $2$) is a generator, that is $2^x \bmod p$ can take on $p-1$ distinct values (depending on $x$).  Because of this, $2^{(p-1)/2}$ can't be 1, as if it were, $2^x$ could take on, at most, $(p-1)/2$ values.

In the $g=2$ case, and where $p$ is a "safe prime" (that is, $(p-1)/2$ is also prime), then there's a simple rule; if $p \equiv 3 \bmod 8$, then $2$ will generate the entire group (and so $2^{(p-1)/2} \not\equiv 1$); if $p \equiv 7 \bmod 8$, then $2$ will generate only half the possible elements (and so $2 ^{(p-1)/2} \equiv 1$.  A quick examination of the last hex digit of $p$ (B) gives us $p \equiv 3 \bmod 8$.

The obvious question would be "what does this matter for security"?  Well, this observation allows the attacker to deduce the lsbit of each side's DH private exponent; however it doesn't do anything other than that.  Some (including me) would question why it's necessary to reveal anything at all about the private exponent; the OpenSSL people thought that minor leakage was acceptable.

Now, if you're proposing to use the group for something other than DH, this may matter to you; however it's hard to complain that a tool doesn't work for a use it was never designed for.  On the other hand, if you need a $g$ which generates the subgroup of size $(p-1)/2$, there's always $g=4$


How do you find a cheater in Shamir Secret Sharing?

Shamir's secret-sharing scheme has $n$ shares of a secret.  The shares are of the form $(x_0,f(x_0)), (x_1,f(x_1)), \ldots , (x_{n-1},f(x_{n-1}))$ where the $x_i$ are $n$
distinct nonzero elements of a finite field $\mathbb F$, and $f(x)$ is a polynomial of
degree $k-1$ with coefficients in $\mathbb F$. One coefficient, say $f_0$, of
$f(x)$ is the secret being shared and the remaining $k-1$ coefficients are chosen at random.  Note that the while the $i$-th share is constructed as $(x_i,f(x_i))$,
what the owner of the $i$-th share  sees is just a pair $(x_i,y_i)$ of
elements of $\mathbb F$, that is, while the owner knows that $y_i = f(x_i)$,
the owner has no other knowledge about $f$.

Given any set of $k$ shares $\{(x_{i_j},y_{i_j}) \colon 1 \leq j \leq k\}$,
there is a unique polynomial $g(x)$ of at most degree $k-1$ that interpolates through these $k$ points, that is, enjoys the property $g(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, and
this polynomial can be found, for example, through Lagrange interpolation.
Since $f(x)$ is of degree $k-1$ (or less if the random choice of $f_{k-1}$
resulted in $f_{k-1}=0$) and also has the property that $f(x_{i_j}) = y_{i_j}$
for $1 \leq j \leq k$, it follows that the $g(x)$ that has been interpolated
is the same as $f(x)$, and thus $g_0$ is the secret.  If fewer than $k$ shares
are available, the $g(x)$ that is recovered is not the same as $f(x)$.

If $m > k$ shares are available, we can interpolate through any $k$
of them and recover the secret.  For the application on hand, if it
is known that there is one (or at most one) cheater, and the
cheater's share  may have the wrong value for $x_i$ or $y_i$
or both, proceed as follows.

If two shares are identical, one of the two shares belongs
to the cheater but it is not possible to
determine who is the cheater. Fortunately, the secret is
recoverable if at least $k+1$ shares are available (that is,
$k$ distinct correct shares are available).  Of course, in
a different scenario, the reconstructor may know the identity
of each share owner, and so know that the $j$-th owner should
not be "turning in" a share in which the first symbol is $x_i$,
and thereby identify the cheater right away.
If there are two shares $(x_i,y_i)$ and $(x_i,y_j)$, then
one of them belongs to the cheater.  If $m \geq k+2$, interpolate
through a set of $k$ shares excluding these two to recover $f(x)$.
Calculate $f(x_i)$ and check which of the two possible cheater
shares matches $(x_i,f(x_i))$: the other belongs to the cheater.
Again, in the different scenario,  $(x_i,y_j)$ could be identified
right away as the cheater's share since the $j$-th owner should not
be turning in a share with $x_i$.
If all $m \geq k+2$ shares have different (and correct)
$x_i$ values, interpolate
through the $\binom{m}{k}$ different subsets of $k$ shares.
$\binom{m-1}{k}$ of these subsets will not contain the cheater's
share and all these interpolations will recover the same $g(x) = f(x)$.
The other interpolations will be through the cheater's share and
will give different interpolating polynomials.  It can be shown
that fewer than $\binom{m-1}{k}$ of these interpolations can
result in the same (but incorrect) $\hat{g}(x)$, that is,
in the $\binom{m}{k}$ interpolating polynomials resulting from
the $\binom{m}{k}$ different subsets, the correct polynomial
$f(x)$ will occur most often (win by a plurality but not
necessarily a majority).  Having found $f(x)$, simply reconstruct
the $m$ shares $(x_i,f(x_i))$ and compare to the ones "turned in"
to identify the cheater.  Alternatively, the union of the
$\binom{m-1}{k}$ subsets of shares that gave $g(x) = f(x)$
is the set of $m-1$ correct shares, and the complement is the
unique cheater's share.

More generally, if there can be as many as $t$ cheaters
it can be shown that the secret can be recovered and
the cheaters identified if $k+2t$ shares are available for
reconstruction.  Note that as many as $t$ of these $k+2t$
shares might be cheaters' shares.  Put another way, if
there can be as many as $t$ cheaters, we need at least
$k+t$ honest shares available (in addition to the $t$
possible cheaters) to be able to recover the secret and
identify the cheaters.

The proofs of assertions about plurality can be found
in the paper I.S. Reed and G. Solomon, "Polynomial
codes over certain finite fields,"  SIAM J. Appl. Math.,
v. 8, pp.300-304, 1960.  The original application of
Reed-Solomon codes to secret sharing (and suggestions
for more efficient recovery than multiple Lagrange interpolations)
can be found in R.J. McEliece and D.V. Sarwate, On sharing
secrets and Reed-Solomon codes, Communications of the ACM,
v. 24, Issue 9, Sep 1981.