Before we get into the key storage and management issues, I wanted to clarify the scheme that is proposed in the linked article, to make sure it is clear what we are talking about.
Let's assume we get pw for authentication from the user and retrieve salt and tag from the database and we get sk from the storage method (see below) being a secret key. We then only accept the password pw if and only if tag=hmac(sk,salt||pw||salt) holds. The prototype of hmac looks as follows: MessageAuthenticationCode = hmac(SecretKey,Message), where the input SecretKey is implicit for trusted devices which provide a parameter for designating a specific secret key stored inside the device.

I really only see three options you have for storing the key if you want to use to do the password verification on a server that reboots:

Use a trusted device connected to the server. This includes smart cards (they may be too slow), trusted platform modules (TPMs; which may also be too slow) and hardware security modules (HSMs; which may be too expensive)
Store the encrypted key and hold the clear one in RAM and require user interaction for unlock. This may work by sending the server a secret password that allows for decryption of the HMAC key if it's at rest or may use this protocol (with EC-ElGamal) for smart card / TPM / HSM based / software based remote unlock.
Store the encrypted key temporarily, hold the clear one in RAM and use a trusted device. This means you let the server generate the secret HMAC key which is only held in RAM until a reboot happens and use a trusted device on reboot only. You may combine this with the second approach.

Now for the details and trade-offs of each method.
Trusted Devices
You can get yourself a smart card and install it in the server. You then send the password to be checked to the card, which holds the key, and receive the corresponding password hash which you compare to the stored value. This may not be suitable for mass-authentication as smart cards tend to be slow  but is the (second) cheapest option among the trusted devices.
You can get a server mainboard featuring a trusted platform module (TPM) and use it like the smart card in the above paragraph. However the TPM suffers from the same problems: While it tends to be cheap it usually is rather slow and not suited for a larger service (handling more than ~10 requests per second).
The "best" solution from this category is the hardware security module(HSM). It would be used just like the other two. Whatsoever those modules tend to be very fast and would very-well be capable of handling many requests in very short times. Furthermore HSMs tend to also have better security certifications then smart cards and TPMs. The downside of course is that HSMs are very expensive, with the cheap ones starting at several hundred dollars and the better ones going up to several ten-thousand dollars, whereas smart cards are within the price range of a few dollars to a hundred dollars per piece.
TL;DR: So overall, while they provide the most security, I don't think trusted devices would solve your situation, because of API, speed and price restrictions.
User Interaction
Here there are basically four different options. A combination of in-place or remote password-based or public-key based key unlock. I'll quickly describe each.
But first I need to describe the overall concept of this approach. You let the server generate the HMAC key in RAM and store an encrypted copy on the hard drives. Every time the server reboots, the HMAC key gets wiped from the RAM and the encrypted copy needs to be unlocked in order to verify passwords. This is where the user interaction comes into play.
The first version of this would to simply enter the password while being directly and physically connected to the server. This is arguably the most secure solution of those requiring user interaction but on the other hand also the most time-intensive solution, as you have to plug-in a monitor and a keyboard, every time your server restarts, so you won't want to do this.
The second version is nearly identical to the first, but this time you'd connect a smart card reader (with a pinpad) to the server, enter the PIN and let the card (asymmetrically) decrypt the stored HMAC key. While this is even more secure than the first approach it suffers from the same problems and thereby usually isn't an option.
The third version improves upon the first, by establishing a TLS (or otherwise) secured channel to the server and handing the password over this way. While this is obviously less secure than the first version as there's the risk of intercaption and man-in-the-middle attacks it is also a lot more scalable.
The fourth version improves upon the second. You'd establish a secured channel (TLS, IPSec, local network, whatever) to the server and then run this protocol on it. This will allow you to decrypt the stored key without the key (or the ciphertext) ever having to leave the server. Yet only the correct smart card / private key can unlock the HMAC key. This is the most secure and most scalable solution among the remote-solutions that require user interaction at boot.
TL;DR: This may be an appraoch that is suitable for your needs, but may require too much user interaction to scale well. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
Trusted devices on Reboot
Full disclosure: I didn't invent this approach, but observed it first at Jetico's BestCrypt VolumeEncryption.
You can let the server generate the key in RAM. Now you let the key stay there until a scheduled reboot happens where the TPM will encrypt the HMAC-key and store it onto the drive. Now the server reboots and after the reboot the TPM will unlock the key and afterwards delete it. This allows for unattended reboots but has the problem that if an unexpected reboot happens the key will be lost and no passwords can be verified. The positive side is of course that this will scale extremely well and will allow for fast software based verification while using powerful hardware protection when necessary.
TL;DR: While this solution will scale quite well, it has the issue of key-backup in case the server shuts-down without a warning. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
The optimal solution (?)
This approach will work the same as the previous one with the small exception that one makes an encrypted backup of the HMAC-key to the drives. Most of the time the server will operate as in the above approach (using software-based HMAC for verification), but in the case of reboots the TPM will kick in and temporarily make the back-up copy for the reboot. Now the weakness of the "old" approaches was that there's no backup for the case of unexpected reboots. In such cases the user interaction appraoch could kick in and allow for decryption of the back-up key. This would even fix the problems of the "blind-decryption" protocol as the user now would very rarely use this method and only in cases where it was sure what happened, allowing for stronger key protection (like a smart card in a vault) and where the user can directly see the result (successful unlock). Furthermore the backup copy of the HMAC-key could be moved to a physically secure location (like a CD inside a vault) which was one of the problems of the stand-alone protocol.
TL;DR: This approach fixes the issues with the previous one, so there's a solid back-up, allowing for unexpected reboots and for unattended planned reboots. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
Note: Drives may be directly attached to the processor / mainboard or may be at a physically different location.


How do different block sizes affect the throughput of GPU implementations of AES?

Remember, a GPU consists of a large number of computational engines, all controlled by the same instruction stream.  That is, there might be 64k processors, and all those processors can work on different pieces of data, but they must all do the same thing to all of them.  We refer to this as SIMD parallelism.

With that in mind, how can they encrypt and decrypt a large amount of data quickly?  That depends on the mode they use.

If they use ECB mode, well, ECB mode applies the AES transformation to each 16 byte section independently.  So, given a 1 Megabyte plaintext, then hand off each 16 byte section to a separate computational engine, and then have all the engines perform the AES encrypt operation on the 16 bytes they were given.

A similar trick works for CBC mode decryption.  In that case, the transform is doing an AES decryption on each 16 byte block, and then exclusive-or'ing the result with the previous ciphertext block.  Similar to the ECB mode case, all that can be done in parallel by the GPU computational engines.

However, if you're asking about CBC mode encryption, well, that can't be parallelized.  There, to encrypt block N, you first exclusive-or in the ciphertext of block N-1, and (unlike the decryption case) you don't have that until the computation of block N-1 is completed.  Hence (as mentioned on the web page), you can't parallelize it, and the web page doesn't give any results there (because the GPU is actually slower than just having the main CPU do the computation).


secret sharing with 3 parties under constraint

This problem is known as conditional disclosure of secret in cryptography. There have been many nice recent works on the subject, I suggest having a quick look at this one for example.

In you exact scenario, can $r$ be of length $2n$? If so, here is a simple solution: call $(r_0,r_1)$ the left and right parts of $r$, each of length $n$.

Alice sends $s + r_0x - r_1$
Bob sends $r_1-r_0y$

Because of the mask $r_1$, these two values only leak $(s + r_0x - r_1) + (r_1-r_0y) = s + r_0(x-y)$. If $x=y$, this discloses $s$; otherwise, $r_0(x-y)$ perfectly hides $s$ (addition and multiplications are performed over $\mathbb{F}_{2^n}$).

Regarding your second questions, yes, there are results on conditional disclosure of secret for arbitrary functions. The best result we know of for arbitrary predicate $f:[N]\times[N] \mapsto \{0,1\}$ has communication $2^{O(\sqrt{\log N \log\log N})}$. For predicates represented by a boolean circuit, I think we can have communication linear in the circuit size, but I would need to check this.


Why are MACs in general deterministic, whereas digital signature constructions are randomized?

One rationale for avoiding randomized schemes in general, and in MACs in particular, is that the random in such schemes tends to increases the size of cryptograms or reduce the size of the payload. An example is scheme 2 in ISO/IEC 9796-2 RSA signature with message recovery, where the size of the random/salt field is directly antagonist with the amount of data recoverable from a signature.

Also, a randomized scheme typically opens a "subliminal channel" backdoor that can't be detected in a black-box testing of an implementation, and could funnel out sensitive information. E.g an RSA (SSA-PSS or ISO/IEC 9796-2 scheme 2) signature blackbox could leak a factor of the private key, CBC-encrypted with random IV and a backdoor-key in the field supposed to be random.

Given that MACs do not seem to need to be randomized to be secure, the above is reason enough that most MACs are deterministic in their definition. Notice however that in practice, the MACed message itself often contains a random component, or/and that (in order to resist side-channel attacks on implementations) the key could be a random session key, in effect randomizing the MAC.

If the random source in a randomized digital signature scheme is bad, that often weakens the scheme. The best example might be [EC]DSA and the PS3 signature fiasco, see this, including comment #2.


One Time Pad Low Bandwidth Doubt from the book

For an OTP you need to distribute the OTP key stream out of band. That can be performed by e.g. bringing a data storage device to the other side. Let me explain.
The problem with an OTP key stream is that you cannot transport it over a secure transport channel without removing the claim of theoretical security. Similarly, you cannot simply distribute a seed for a PRNG, because the PRNG would have similar security as a stream cipher.
Because you cannot distribute an OTP without compromising its security it is limited to the amount of information that you distributed out of band.
How limiting this is depends on the application of course. Nowadays you can store several TB in a tiny flash disk. That's enough for many, many hours of video. Still, securely distributing such a disk would be troublesome; just sending it by regular post is obviously not a good option.
Another option would be to use quantum key distribution. However, implementations of quantum key distributions are not necessarily secure, and the speed may be a severe limit.
Fortunately, we've got a lot of ciphers that we don't know how to break, key ratchets and whatnot to give us practical security even for much smaller key sizes.


Adversary to Any Collision Resistance Hash Function

CF is a randomized algorithm with input $K$. As a randomized algorithm, it is allowed to do random decisions in its calculations – this can be thought of flipping a coin. The results of these coin-tosses (i.e. a list of heads and tails) – can be thought as another "input".

For each key $K$ and each list of coins, the algorithm either finds a collision or doesn't.

Now we assume some random distribution of both (usually a uniform distribution of the keys, and an uniform distribution of each of the coin tosses), and can determine the probability of the success.

This probability is what is meant in your definition.

For example, if you have a hash function family $F_K$ with $2^{50}$ keys, a (quite dumb, but fast) algorithm would be to toss 200 coins to generate two 100-bit strings and output them. They either are a collision or are not, and it depends both on the key and the tossed coins whether it works. Calculate the number of combinations of "good" keys and tosses on one hand, divide by the total number of keys times the total number of possible coin toss results (this is $2^{50} · 2^{200}$). Assuming that for half of the keys exactly one collision (of 100-bit inputs) exists (and for the other half of the keys there is none), we would have $$P(\text{algorithm finds collision}) = \dfrac{2^{49} · 2 }{2^{50} · 2^{200}} = \frac{1}{2^{200}}.$$ (This is 2 instead of 1 in the first fraction, because if $F_K(a) = F_K(b)$, we also have $F_K(b) = F_K(a)$, and the algorithm could find any of them.)


Diffie-Hellman (and variants such as ECDH) protect against passive eavesdroppers, but not (at least by themselves) against active man-in-the-middle attacks. An active MITM can substitute his own keys for Alice and Bob's keys during the initial exchange, something like this:

Alice -> Bob (intercepted by Mallory): Hi Bob, I'm Alice and here's my public key: [Alice's public key]

Mallory -> Bob: Hi Bob, I'm Alice and here's my public key: [Mallory's public key]

Bob -> Alice (intercepted by Mallory): Pleased to meet you Alice, I'm Bob and here's my public key: [Bob's public key]

Mallory -> Alice: Pleased to meet you Alice, I'm Bob and here's my public key: [Mallory's public key]

Alice then computes a shared key based on her private key and "Bob" (actually Mallory)'s public key, and uses that to encrypt data to/from "Bob" (actually Mallory). Similarly, Bob computes a shared key he thinks is shared with Alice, but is actually shared with Mallory. Mallory uses the two public keys and his own private keys to compute both shared keys, and uses them to decrypt and reencrypt the messages passing between Alice and Bob.

This is why it's important to couple DH key exchange with some sort of authentication. For instance, in TLS's ephemeral DH and ECDH modes, the server signs its DH parameters (including its DH public key) to insure that they haven't been tampered with.


Suppose I capture encrypted data that I want to decrypt. Could I use a server farm to decrypt?

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have my array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the work load of hacking this encrypted data to get through it in about 37 days? Why or why not?

The answer depends entirely on what cryptanalytic problem you're hoping to solve.

Worst case: No.  For example, if you have to compute $2^{2^t} \bmod pq$ without knowing $p$ or $q$ (large random primes of sizes beyond the reach of ECM or NFS) where $t$ is very large, throwing more computers at it doesn't help (without a novel cryptanalytic breakthrough); only making the computer itself run faster—e.g., by designing an ASIC that computes it and running it at a high clock rate cooled with liquid nitrogen—will give you an answer faster.

This is because we don't know of any algorithm to compute $2^{2^t} \bmod pq$ other than starting with $x_0 = 2$ and then computing $x_i = {x_{i-1}}^2 \bmod pq$ sequentially $t$ times: except for vectorization attainable in the squaring operation, parallelism doesn't help.

Best case: Yes.  For example, if you have a password hash and you want to find a password among a large space that a single computer can search in 1000 years to search, and if you have 10 000 you can afford to run, then sure, you can divide the space into about 10 000 subspaces—for instance, all those passwords starting with aaa, aab, aac, etc.—and get a factor of 10 000 speedup by searching the subspaces independently.

Actually, if you have a collection of password hashes and you're content to find one of the passwords, you can get an even better speedup than a factor of 10 000 by a multi-target attack.

In general, you are limited by Amdahl's law: if the fraction of time spent a sequential program that can be parallelized is $P$, then the best possible speedup attainable by parallelism is a factor of $S = 1/(1 - P)$; that is, if it previously took time $T$, then with parallelism it can take at best time $T/S$.

For computing $2^{2^t} \bmod pq$, $P$ is essentially 0—the problem is, as far as we know, inherently sequential (short of factoring $pq$), so $1/(1 - P) = 1$ meaning that parallelism doesn't change the time at all.

For searching among keys $k$ to find one matching a given hash $H(k)$, $P$ is essentially 1—the problem is embarrassingly parallelizable, so $1/(1 - P) = \infty$, meaning that the time can be made arbitrarily small with parallelism.

Will this matter for serious cryptography?  No.
Serious cryptosystems are generally chosen so that the cost of an attack is higher than you can ever afford.  For example, you will never find one of any plausible number of AES-256 keys by brute force, because the cost will far exceed $2^{128}$ evaluations of AES, which you don't have the pocket change to pay for the energy to do, no matter how much you parallelize it.  The same goes for finding any Curve25519 private key by the best known discrete logarithm algorithms given all the Curve25519 public keys in the world.

Note that even with Amdahl's law, trading parallelism for time doesn't necessarily reduce cost: the energy to power 365 computers for a day is about the same as the energy to power one computer for a year.  In some cases—like parallel rainbow tables or distinguished points in a multi-target attack—it does reduce cost!  But you're not guaranteed a cost reduction just by parallelizing a computation.  In other cases—like Grover's algorithm on a (hypothetical) quantum computer—parallelizing the computation may raise the cost!


Is there more than one public key for a private key?

Does deriving the public key from an RSA private key always yield the same result?

Well, if $e$ is the correct public exponent, then any value of the form $e + k \cdot \text{lcm}(p-1, q-1)$ (for any integer $k$) is also a correct public exponent (in the sense that it would function equivalently when used with the same modulus).

Of course, we usually select $e$ to be small; the alternative public exponents are huge (and hence much slower).  In addition, publishing two different public exponents of that form would allow someone to efficiently factor the modulus, and hence taking advantage of it might not be that great of an idea...

  And if so, does this generally apply to all asymmetric cryptosystems?

Not in general.  Another example where it doesn't apply would be NTRU; the private key is a polynomial $F$ (that meets certain properties); the public key is another polynomial $pF^{-1}G$ (where $G$ is a sparse polynomial); we can select a different $G$ and obtain a different public key that works equivalently.


Need literature or link to family of cryptographic invertible polynomials which has distribution similar to inverted bell curve

These requirements are impossible. If $p_k$ is a permutation, then the distribution induced by "choose $x$ uniformly in $\mathbb{Z}_n$, output $y=p_k(x)$" is also uniform in  $\mathbb{Z}_n$. It can't follow a normal distribution. For every possible $y$, there is exactly one $x$ that makes it happen, and that $x$ is assigned probability $1/2^n$.


Multiparty millionaire problem where members only know if they are the richest one

Edit:

As the comment of Mikero correctly points out it is quite easy to make the outputs differ for most MPC protocols (for example in the 2PC case at YAO's protocol, you can tell the evaluator that output key X1 means 0 and output Y1 means 1 while you don't say anything about X2 and Y2 and make the evaluator send X2 and Y2 to the garbler, who knows the meanings of them).

In this case you just need to output 0 or 1 to every party if they are the richest or not.

Old answer:

My best idea to solve the problem is to use YAO's protocol (or any other common MPC protocol), make every party additionally input a random identifier and make the function output the identifier of the richest party. Then the richest party knows being the richest while the other parties don't know who is the richest party.

To avoid the problem that two parties input the same identifier I would think about the following (combining these ideas also makes sense):

Make the identifier large enough so that the likelyhood that two parties input the same identifier is negligible.
Expand the function such that the function outputs a fixed identifier 0 (which must not be chosen by any party) if two parties input the same identifier. If that happened, repeat the MPC computation with another random identifiers.


Iterated AES encryption under a fixed key

Under a fixed key, $E_K$ is a permutation in the symmetric group of permutations on $2^{128}$ elements. Thus its order divides $(2^{128})!$.

If AES is modelled as a random permutation, for a randomly chosen fixed key, the order $N$ of $E_K$ is likely to be near $2^{127}$ as explained in the comment under the question, and indeed $E_K^{N-1}(x)=E_K^{-1}(x)$ for all $x\{0,1\}^{128}$.


What is the name of this public key encryption cryptosystem?

Maybe I miss something, but after some quick thoughts about that algorithm, I think it is not secure. Therefore it may not be used and be more like an example for teaching (with no name).
The problem with the algorithm is that you can derive the secret key q from the public key. When you have two integers a and b, where both are a multiple of q (like all q*z_i in your case), then a - b is also a multiple of q, that is much smaller.
So the private key q can be reconstructed within a fraction of a second for primes with few thousand bits. All you have to do it to take two q*z_i from the public key and compute the greatest (only) common divisor.


Now, you highlighted key generation - no one really cares about key generation time (unless you are generating ephemeral keys, that is, a fresh key pair for each connection - we generally don't).  Instead, we might generate a fresh key pair maybe once a day or once a month (usually far less frequently), and so we don't care whether it takes perhaps a second (RSA) or submillisecond (ECC).

Now, while the key performance delta between RSA and ECC is the most extreme, ECC still outperforms RSA in most other measures, just not by as wide of a margin.  You can still ask "why do people still use RSA in spite of those other metrics by which ECC is better":

Inertia (we've been using RSA for decades, why should we switch?); this lends itself to trust.  And, this is not a spurious concern - we generally like to use crypto which has been published a long time ago, and vetted by a number of crypanalysts - the more, the better, and it's really hard to think of something more vetted than RSA.
RSA is easier to understand; it's not difficult for someone with a little bit of mathematical background to get the basics.  In contrast, to understand ECC, you need to dig into more number theory than most people have encountered.  This ease of understanding also lends itself into trust.
Backwards compatibility; there are a number of people running older browsers that just don't understand ECC certificates; if you're a server and all you have are ECC certificates, you've just disqualified those people from talking to you.  Now, you could have both an RSA certificate and an ECC certificate (TLS 1.2 and on allows you to select the certificate based on client capability); however if you have an RSA cert, why do you need a second cert?
Performance (which sounds like it contradicts what you read - it really doesn't).  For TLS, clients generally don't care about the performance of RSA vs ECC - they usually make a handful of connections per second, and either is fine for that.  For servers (which may need to make thousands of connections per second), they often have crypto accelerators.  And, at least in my limited experience, RSA crypto accelerators are rather more common than ECC ones, and RSA with a crypto accelerator does go faster than ECC in software.
Intellectual property; not that long ago, there was a company (Certicom) which claimed to have patent rights over most of ECC, and threatened lawsuits against companies which used ECC without paying them (and did file in at least one case).  Now, that was several years ago, and people are not concerned about them now.  However it did delay things, at least for those companies large enough to be concerned about Certicom suing them...


How Hermite Lattice reduced basis implies LLL reduced basis?

Ignoring the trivial case $j = i$, for which the second condition is automatically satisfied, the conditions for Hermite-reduced bases can be formally written as:

For all $1 < i \leq n$ and for all $1 \leq j < i$: $ \qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.
For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}\leq} \ j \leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$.

The conditions for LLL-reduced bases can be slightly rewritten as:

For all $1 < i \leq n$ and for all $1 \leq j < i$: $\qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.
For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}=} \ j\leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$ .

The only difference in the definitions, highlighted in red, is on the values $j$ for which the second condition must hold; for Hermite-reduced bases it must hold for all $j \in \{i+1, \dots, n\}$ while for LLL-reduced bases it must hold for $j \in \{i + 1\}$ (provided $i + 1 \leq n$). Since $\{i + 1\} \subset \{i+1, \dots, n\}$ this means Hermite-reduction is a stronger notion than LLL-reduction. So Hermite-reduction implies LLL-reduction.

As for your last questions:

  What about the other inequalities? Does other inequalities are satisfied? If not, how does it output nearly orthogonal basis?

For the case $n = 2$, the sets $\{i + 1, \dots, n\}$ and $\{i + 1\}$ are equal for $i = 1$, while for $i = 2 = n$ the second condition does not apply. So for $n = 2$, both notions of reducedness are equivalent. (Many other notions of reducedness also collapse to the same definition in case $n = 2$.)

For $n > 2$, setting $i = 1$ shows that the conditions are not necessarily equivalent. I am not sure whether already for $n = 3$ there are examples of LLL-reduced bases which are not Hermite-reduced, but certainly for larger $n$ there are many such examples - by the second condition, the vector $b_1$ of a Hermite-reduced basis must be a shortest non-zero vector of the lattice, while for LLL-reduced bases the vector $b_1$ is only known to be at most a factor $2^{O(n)}$ longer than a shortest non-zero vector in the lattice. In high dimensions, an LLL-reduced basis will look quite skewed compared to a Hermite-reduced basis, so in that sense it does not really output a "nearly orthogonal basis" - only a "somewhat orthogonal basis".


Using pairings to verify an extended euclidean relation without leaking the values?

Well, assuming the equation holds, $\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ must also hold, due to the bilinearity of $e$. (Conversely, the equation only holds mod |G_1|.)

To see why, recall that the fact that the mapping $e$ is bilinear translates into $e(g^a,h^b)=e(g,h)^{a*b}$ for all elements $g$ and $h$ in $G$ and for all integers $a$ and $b$. Thus, we always have $e(g^{q_i(s)},g^{P_i(s)})=e(g,g)^{q_i(s)*P_i(s)}$ and by multiplying all these equalities together we get that $$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) =e(g,g)^{q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)}.$$
Now what you want to check is if $q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)=1$: if it is true, we can replace the expression in the left-hand side of this equation in the pairing equation above by 1 and thus get
$$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$
as stated in the beginning.

For $e(g,g)$ is a group element of $G_1$, it must hold that $e(g,g)^{|G_1|}=1$, as for any other element of $G_1$.

For the actual value of $e(g,g)$ itself, we can only say it is an element of $G_1$ (by definition of $e$). It can be the neutral element of $G_1$ in which case $e(g^a,g^b)=1$ for all $a$ and $b$ and thus does not provide you with a way to check the extended euclidean equality, since you'll basically get $1=1$ for all possible values of $q_i$ and $P_i$.


Generalization of the DL-assumption in bilinear group pair

Usually the point of working with a Type 3 pairing is exactly to have
  such a tuple, and use the pairing to decide if the fourth element
  indeed equals $zQ$ or some other element. So if this problem is not hard
  and $z$ is private, then you're in trouble.

From your explanation, I don't think you require a Discrete Log-like assumption. You are saying that the pairing is used to check if some element is indeed $zQ$ or some random value. This seem to imply that $P$, $zP$, and $Q$ are known to an adversary, and you want to ensure that an adversary cannot produce a value that passes the check you make with the pairing.

Assuming I understood this right, then this seems to be a fit for the Computational co-Diffie Hellman problem (co-CDH): given $P$, $zP \in G_1$, and $Q \in G_2$, the co-CDH problem is to output is $zQ \in G_2$. This output is what you are checking with the pairing, so it seems to me that the co-CDH problem is what you are looking for.

In this case, a Discrete Log-like assumption may be overkill, since an adversary wouldn't need to find $z$. It suffices to compute $zQ$.


Who provides prime numbers for cryptographic protocols?

Let's have a look at how these are implemented:
RSA
RSA is probably the example, showing how prime numbers are used in cryptography. In order to calculate a private key, two prime numbers, $p$ and $q$ are "chosen". What that means in practice is that your computer will generate a random number (and set a few bits) and then check whether or not the generated random number is a prime.
Well...not exactly. Actually, the generated number is a "pseudo prime number", which is a number that is probably a prime number, but we can't know for sure. In order to be certain, we would have to divide the number by every prime number up to the square root of the prime candidate.
Why isn't this check done? As you can imagine, checking whether or not 13377216267221394781281321803240685565647633863945354245591337480581850892718220086347852930388186839929611014777408043323753186115505611255512212061593047 is a prime factor of  168581487233807662095985877892466382655984504887588184273878566402288131033127314863556248166230176818735604347430473403376658381900826700241919315590165489510028586594896744589808921429729412701596114362546978418049726172509111051384159129475101054095614648000575426731420406552789078218487162756487172295557 is a computationally expensive task. Especially if our current tests run magnitudes faster and can give us a $4^{-k}$ chance of a non-prime passing the test, with $k$ being the number of runs of the Miller-Rabin test.
You can even try this yourself by running openssl genrsa. You will see output like this:
Generating RSA private key, 2048 bit long modulus (2 primes)
................+++++
...............+++++
e is 65537 (0x010001)

Each . means a potential prime candidate was generated, and each + means a round of Miller-Rabin was passed. According to this answer, even three rounds of Miller-Rabin will be enough to make it very unlikely that a randomly generated non-prime passes the Miller-Rabin test. So as you can see, OpenSSL stops after five passed rounds and moves on to generating a new number.
Diffie-Hellman Key Exchange
In order for DH to work, there needs to be a public prime $p$, which can be a known default value. These can be generated on-the-spot by either the client or the server, but publicly known default values can be used. Since these are just transmitted over plain text, an attacker can intercept them.
It should be noted that you want to pick a $p$ for which $p-1$ has a large prime factor $q$.
The secret keys $a$ and $b$ generated in DH don't need to be primes, so any random number will suffice.
Are they supplied by the user?
Yes and no. Many protocols require a user's private key, which they supply in form of a key file. Nothing stops a user from generating their own key file with any prime number of their choosing.
However, most users won't do that, as there is really no benefit to that. Even an attacker has no benefit of supplying something like a semi-prime (a number that is the result of two prime numbers, e.g. 15), since that would not give them any advantage.
Definitely, no serious program will ever ask the user to enter a prime number, which is then used for cryptographic purposes, aside from demonstration tools.


Ciphertext packing for bandwidth optimization

If $m_b$ has size $n_b$ bits, then there are $2^{n_b}$ possible messages $m_b$; and they MUST be all "possible" in the eyes of outsiders (including Carol). Similarly, there are $2^{n_c}$ possible messages $m_c$. Thus, there are $2^{n_b}\times 2^{n_c} = 2^{n_b+n_c}$ possible inputs to your problem.

If you have a system that can encrypt all such inputs into a sequence of $t$ bits, then there are $2^t$ possible output messages, and, from each such message, Bob and Carol can unambiguously extract $m_b$ and $m_c$, respectively -- if they work together, they will get both $m_b$ and $m_c$, unscathed. This implies that the encryption system must be injective: if $(m_b, m_c) \neq (m'_b, m'_c)$ (the message for Bob, the message for Carol, or both, are different), then they must encrypt to a different sequence of $t$ bits. Otherwise, it would not be possible to decrypt the result unambiguously.

Therefore, $2^{n_b+n_c} \leq 2^t$. This means that you cannot do really better than concatenation, in all generality.

Now, if you suppose that your messages are "real world data" with a lot of internal structure and redundancy, then you can use data compression to reduce the size of the plaintexts. Data compression, on average over uniformly random input bits can only increase data length, but on "meaningful" data it can be quite successful. Unfortunately, data compression makes data length depend on data contents, and encryption, as a rule, does not hide data length, so compression is a recipe for data leakage.

In your specific case, you could also envision a compression scheme that exploits the similarities between Bob's and Carol's messages: split $(m_b, m_c)$ into three parts $(s_b, s_c, d)$ where $d$ is the part which is common in $m_b$ and $m_c$, $s_b$ is the part specific to $m_b$ and $s_c$ is the part specific to $m_c$. Then you can encrypt $d$ only once with a symmetric key $K$, and encrypt $K$ with the public keys of both Bob and Carol. Depending on the structure of your messages, this may save a lot of space. However, it also reveals to Carol a chunk of the the message sent to Bob; and even outsider can know how much data is shared between the two messages.


First use the TID as input for a KDF to generate one or more tag specific keys, using a static, symmetric master key stored in the initialization software and gadget.

Use one of these keys to obtain access. Use another for verification of the tag.

During initialization derive and set the access key (s). Then create a HMAC over a static value (or multiple static values) within or outside the memory of the tag, and store it within the tag.

During read out by the gadget use the keys to gain access and to verify the HMAC value over the static value(s).

This symmetric solution can of course be complicated by several patches with regards to key management (roll over to different keys and such, possibly storing multiple hash values).

That's for a symmetric solution. If you're brave you may consider an asymmetric solution. As you don't have enough room for e.g. RSA signatures you may want to go for a small size signature. The obvious advantage is that you don't need to distribute the private key to the gadgets. These kind of schemes do however require more cryptographic capabilities from your side.

Don't forget to store a version number or something similar in your tags so you have an upgrade path.


You want to hash the existing generator $g$ then coerce that hash to a curvepoint. This will result in a generator which is uniformly independent of $g$ (well, in the random oracle model anyway) and also commits to $g$ so that neither generator can be changed (say, to introduce a correlation) without changing the other.

The "obvious" way to avoid correlations, which is deriving $h$ from a nothing-up-my-sleeve (NUMS) number, suffers from the problem that the SECG generator $g$ does not have a clear origin -- it is not NUMS -- so it is possible that somebody knows the discrete log of $g$ with respect to some NUMS point. (Thanks Adam Back for pointing this risk out to me.)

To coerce a hash function to a curvepoint you can use functions from this paper (thanks Greg Maxwell for this link), for example... or you could just take the hash as the $x$-coordinate of your point and keep incrementing it by small integers until you are able to produce a valid curvepoint.


CBC mode works well for input greater than "b" bits. What is that "b" bits?

There the $b$ bits mean the block size of the Encryption and that is 64 for DES and 128 for AES.
Therefore you may need more than one block for the encryption of your plaintext (message). If your message size is $\ell$ than you need $$\lfloor \frac{\ell}{b} \rfloor + 1$$ blocks to encrypt.
The block nature of the CBC mode like any other, not like CTR, requires padding to fill the empty bits of the last block. Usually, the PKCS#7 padding is used for this.  PKCS#7  can increase the number of blocks by one if $b|m$.
Note that if the CBC mode is used with servers like in TLS, then it is vulnerable to padding oracle attacks that work like decryption oracle. In this case, you may need to get rid of the CBC as TLS 1.3 did and use paddles mode like CTR. The better is using authenticated encryption modes like AES-GCM which internally uses the CTR mode and provides integrity and authentication with GMAC.
Keep in mind that, Wikipedia is the first source to look at those, not any other site.
If you really want to use CBC mode then
Your obligations

You must Generate a uniform random 256-bit secret key, and keep it secret all the time;
For each message that is going to be encrypted under the same key choose an Initialization Vector (IV) that must be unique and unpredictable. You can send the IV prepended to the ciphertext
Make sure that the message size is multiple of 128 with proper padding.
The message size must not exceed $2^{60}$.
The key must not be used more than $2^{45}$ due to the IV collision due to the birthday attack. This will produce $$(2^{45})^2/2^{128}/2 = 2^{90 - 128-1} = 1/2^{39}$$ probability of collision instead of $1/2$ probability of $2^{64}$

In return : CBC guarantees

CPA security; that is the adversary cannot distinguish two ciphertexts with the same length, and thus cannot read the message sent.
That is all you get from the CBC mode if used properly. To achieve authenticated encryption use HMAC with CBC in encrypt-than-MAC as a recommendation.


Salsa20 expands a 256-bit key and a 64-bit nonce into a 2^70 byte stream - where did the 2^70 come from?

Salsa20 is a PRF working in Counter-mode. That is it generates the keystream as $K_i=F_k(N,\text{Counter}_i)$.
This Counter is a 64-bit value - not the nonce - thus allowing $2^{64}$ invocations of the PRF before repetition. Each PRF invocation yields 64 bytes, so in total $2^{64}\cdot 64=2^{70}$ bytes.

Salsa20 generates the stream in 64-byte (512-bit) blocks. Each block is an independent hash of the key, the nonce, and a 64-bit block number; there is no chaining from one block to the next.

The above is the relevant quote from the paper, about five lines below the quote in the question.


You have to understand how the modulus operation works. When we say $a=b\mod c$, what we mean is that $a-b$ is a multiple of $c$. Now, since for any positive integer $n$, $a^n-b^n$ is a multiple of $a-b$, we can usually raise both sides to the same power in a modular equation, keeping $c$ intact. However, if $a-b$ is a multiple of $c$, there is no guarantee that $a^n-b^n$ is a multiple of $c^n$. Hence, raising $c$ to the same power makes no sense. I hope this answers your question. For a better understanding of elementary number theory, you can go through the initial chapters of a high-school text (like Burton's).


Do all forms of symmetric encryption require multiple pieces of information? (nonce, iv, etc)

The way I see it is that I can store the iv in a second location from the encrypted text or I can generate the iv predictably every single time.

Actually, if you don't mind the ciphertext being longer than the plaintext, we can just include the IV/nonce in with the ciphertext.  What we typically do is place the IV/nonce at the front of the ciphertext, and place the output of the block mode right behind it.  This means that the ciphertext is 8 to 16 bytes longer; for most use cases, we can live with that.  We generally also want to store some sort of integrity tag as well (so that if someone modifies the data, we can detect it); that extends the ciphertext a bit more.

Of course, there are some use cases where the ciphertext must be exactly as long as the original plaintext (for example, if we're storing the encrypted data somewhere that was originally intended to store the plaintext, and so the space available to store data is limited to the expected size of the plaintext; this comes up both with encrypted databases and encrypted disk drives).  We could, in this case, store the IV/nonce (and the integrity tag) elsewhere, however (in my experience) that's rather rare.

There are specialized modes that are designed to work with the constraint that the ciphertext is exactly the same length as the plaintext, such as XTS (generally used for disk sector encryption) and Format Preserving Encryption modes (designed for encoding small pieces of data, such as a credit card number); unless you require something that needs to live with this constraint, this is typically not the correct solution.

  I can generate the iv predictably every single time.

Modes that use IV/nonce are typically badly behaved if you encrypt two plaintexts with the same IV/nonce; with EAX mode, you allow the adversary to deduce the XOR of the two plaintexts; with CFB mode, you allow the adversary to deduce how many blocks the plaintexts agree and on the block they first disagree, the XOR of those two blocks.  Hence, generating the IV predictably every single time is generally not the correct solution.


Do Korea and Japan have their own national hashing standard?

Korea has its own standard for hash and block cipher, such as LSH (for hash) and ARIA (for block cipher). Source code can be found in here. I cannot find the English page, but google translator seems to work well. You can find information about standardization and other documents on the website, e.g. here.
The above-linked site KISA is itself authoritative and a public institute. If you want a much formal standard document, you could find them from TTA or KSA. The standard is as follows.

LSH hash: KS X 3262 KS Link, previously TTAK.KO-12.0276 (expired)
LEA encryption: TTAK.KO-12.0223 TTA Link but the document is mostly in Korean. Source code is available here but its manual is also in Korean.
ARIA encryption: KS X 1213-1 KS Link

The documents on KS site are not free, and they are also written in Korean.


Encryption through multiplication of encoded key

It is insecure in the sense that anybody with a calculator can reverse it (and a large set of people without one).

According to the Kerckhoff principle you should tell everybody the algorithm. So there is no security there.

After that an attacker will receive multiple ciphertext (ciphertext only attack). This attacker will quickly find a common divisor for the ciphertext. This common divisor is the key.

Furthermore, there are special values in your plaintext. In principle you don't want to have these in a cryptographic algorithm. Say for instance that you send a single space. In that case you would send bit string 00100000. As you can see there is only one bit set. Multiplication will result in a binary representation of the key "Hi", shifted 5 bits to the left. So an attacker can simply read the key straight from memory. If you can think of such a value, then your cipher is already considered broken.

Finally, a good cipher is a random permutation; a 1:1 mapping of the key to the ciphertext. That's the case in your algorithm, but the permutation is from $N$ to a set $key \times N$. Now you would have to encode this ciphertext efficiently or you end up with very large ciphertext values. This is why most cryptography uses modular arithmetic and XOR (which can be thought of as addition modulus 2).


ECDSA public key recovery is discovered by whom?

Update: in a footnote of his paper Generic Groups, Collision Resistance, and ECDSA (online since 2002-02-27), then published in Designs, Codes and Cryptography (2005), Daniel R. L. Brown wrote that

In ECDSA, the public key can be recovered from the message and the signature.

Then, acting as editor of the SEC 1 standard, he put there how such ECDSA public key recovery can be made. In this version v1.99 of 2009-05-21 with changes since v1.5 visible, that section appears as a late addition.
Thus it seems possible that Daniel R. L. Brown of Certicom came up with ECDSA public key recovery circa 2002. At least he knew about its feasibility. That vastly predates Bitcoin.


The system can be viewed as a complete graph, in which each vertex is a user and each edge represents a different symmetric key.

Thus for 100 users (vertices), you need (100*99)/2 keys (edges). This is roughly 5,000.

To help visualise, consider the image below from Wikipedia. It demonstrates a complete graph with seven users. Hence 21 seperate keys would be required.


EC: How to prevent discovery of base point after commutative operation

If you're not tied to EC, here's one easy method: let $N$ be a composite number of unknown (secret) factorization; then:

$$f(x, B) = B^x \bmod N$$

is both uninverible, and commutative.  If $f$ needs to be a permutation (that wasn't specified), then we can select the factors $p, q$ of $N$ s.t. $p-1, q-1$ have no small odd factors (and restrict the allowable values of $x$ to small odd values $>1$).

If you absolutely have to do EC, well, the obvious approach would be to actually use a pseudocurve (that is, do the EC operations in the standard way, but work on a ring rather than a field), with the ring being (yes, you guessed it) the integers modulo $N$ (where the factorization of $N$ is secret).  Yes, an operation may fail, but if the factors of $N$ are large enough, this will practically speaking never happen.  $N$ needs to be large enough so that directly factoring $N$ is infeasible (which means it's much larger than moduli we normally do EC in), however it would appear to meet your requirements.  Note that point counting on a pseudocurve doesn't work (or so we hope; if it did, then we could factor), and hence the standard way of inverting point multiplication (which involves finding the multiplicative inverse modulo the order of the curve) is unusable.


How to distribute session keys in public key cryptography?

Normally, the client sends the session key.  This means that clients cannot decrypt other session keys.

Although this approach ensures each session is safe from information gathered in other sessions, it doesn't guard the session against an attacker later acquiring the server's key and retrospectively decoding all recorded sessions.

To guard against that threat is termed Perfect Forward Privacy.  This can be achieved using ephemeral Diffie-Hellman (EDH,DHE) key exchange.

There is an excellent blog explaining recent improvements in Perfect Forward Secrecy which is well worth reading.


Incorporating known ciphertext into new message

Not sure if this fits your requirement, but, here goes.

Using the homomorphic properties of ElGamal, you could turn $E_{pk}(b_0),E_{pk}(b_1),E_{pk}(b_2),E_{pk}(b_3),E_{pk}(b_4),\cdots,E_{pk}(b_n)$ (where $b_i\in\{0,1\}$, i.e., individual bits), into $E_{pk}(b_0||b_1||\cdots||b_n)$ (where $||$ is concatenation). This is done by using homomorphic scalar multiplication and addition (multiply by 2 then add the next bit, repeat as necessary).

This could be generalized to larger messages (not just individual bits) if Trent is told the lengths of the messages.

Any cipher that is homomorphic with respect to addition could be used.


Size of a MAC for a quickly checked message?

If the MAC is well designed and there is no better attack than guessing, the attacker can choose at least two attacks:

a. Find the key for MAC and be able to sign any message.

b. Guess (maybe randomly) a MAC of an arbitrary message. (If unsuccessful, maybe retry the attack.)

The feasibility of attack a depends on the size of the key, but not on the size of the MAC itself. (Well, smaller MAC means potentially less information leaked about the key, but this is rather a minor effect.) Small MAC thus does not increase the probability of the key being cracked.

The important point: Attacker without the key can't just bruteforce a MAC for an arbitrary message, even if the MAC length is 1 bit. Since MAC is symmetric and key is kept in secret (there is no public key), attacker with a valid pair of message and its MAC can't verify it offline.

None of these facts, however, mitigates attack b. The attack b may be a real threat with a short MAC. Feasibility of the attack will depend on details that are not available. (It, however, does not much depend on the time window between message sent and message recieved.) If the MAC does not protect anything very valuable and the attacker is likely to be traced and killed after the first unsuccessful attempt to forge a message, one bit MAC might be very sufficient. If the attacker can do many unsuccessful tries without any problem, then the MAC must be much longer in order to resist such attack. How much long? It depends on the feasible online attack rate. Plus, you are likely to want a safety margin, don't forget about that.

There is one more issue. Where would you get a MAC function that outputs a shorter MAC? When you take an obsolete MAC function, there might be some serious issues (e.g. short key). When you use an existing MAC function and shorten the output from it, it is not guaranteed to provide desired level of security. For example, a MAC function with 128b  output might provide signifficanty less enthrophy in the output due to some redundancy or probability characteristics. This should not be an issue with HMAC, which is hash-based.

I hope you question is rather theoretical one (i.e. you are curious if this is safe) and you don't wan't to implement such system. The MAC overhead should be usually negligible and there should be no serious reason for using a short MAC. The benefits of slightly smaller MACs are usually not worth of a serious reasoning about security of that system.


How can I show that the DDH problem is self-reducible?

What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary
(worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an efficient algorithm for the
average case implies an efficient algorithm for the worst case. You already have outlined how this is technically done in your question and I'll show you a construction for the computational version of this problem.

Example CDHP

Let $G$ be a group (w.l.o.g. of prime order $p$) generated by $g$. The CDH is given two elements $g^a$ and $g^b$ and to
compute $g^{ab}$.

Lets say we have a solver $\cal A$ for CDHP in $G$, then we can construct an algorithm $\cal B$ that uses $\cal A$
as an oracle and $\cal B$ solves any instance of the CDHP in $G$ with the same probability as $\cal A$ and only
requires "a little" more time than $\cal A$ (see below the time required for the sampling of the elements and the
extra arithmetic that has to be done).

It goes like this:

$\cal B$ receives $(u=g^a,v=g^b)$ as input and does the following:

Choose uniformly at random elements $x,y$ from ${\mathbb Z}_q$
Compute $u'=ug^x$, $v'=vg^y$ and run $\cal A$ on $(u',v')$
Take the output $w'$ of $\cal A$ and do the following: compute $w=w'\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}$
Output $w$ as solution to the CDHP for instance $(u,v)$.

Observe that if $\cal A$ solves the CDHP then also $\cal B$ solves the CDHP, since then

$w'=g^{(a+x)(b+y)=ab+ay+xb+xy}$ and thus

$$w=g^{ab+ay+xb+xy}\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}=g^{ab+ay+xb+xy-ay-xb-xy}=g^{ab}.$$

Note that due to the "blinding" in step $2$, the instance for $\cal A$ is uniformly distributed and independent from the original instance to the CDHP $(u,v)$, i.e., a "fresh" random instance.

I only have argued informally and let the exercise to write the analysis down formally to you.

DDH

Having this example it should not be too hard to devise such a reduction for the DDH.


Meta: although both are reasonable, I'd actually consider this Q a better fit for security than crypto. Be that as it may ....

In https://security.stackexchange.com/questions/81597/in-psk-tls-how-is-the-key-used-for-encryption-derived (suggested by RoraZ) the steps from premaster to master to working are applicable, but the premaster step (even for DH_PSK) differs from normal DH keyexchanges, plus TLS1.0 is out of date.
What is the purpose of pre master secret in SSL/TLS?  and What is the purpose of four different secrets shared by client and server in SSL/TLS? similarly focus on the later steps although the former does mention (EC)DH.

So to lay it out:

the publickey and privatekey values for the two peers are just keys. TLS specs use the notation where X is the privatekey and Y = G^X mod P the publickey, plus an identifier of the party owning the key: dh_Ys is the server publickey and dh_Yc is the client publickey.

Although TLS isn't careful about it, there is actually a distinction between on the one hand parameters P,G which must be shared between TLS peers and can be shared on a larger scale (such as an organization or community), and on the other hand key(pair)s X,Y which should be unique to one peer and not shared and for ephemeral DH (the preferred kind) should further be unique to one session and not stored.

In TLS to date (although draft 1.3 proposes to change this) the server selects the group (parameters) and for ephemeral generates the server keypair in that group; the client generates its keypair in the same group for ephemeral.
the DH agreement value is used as the premaster secret; see RFC5246 sec 8.1.2. With the TLS notation this is Ys^Xc (computed at client) or Yc^Xs (computed at server).
This step is (very) different for other keyexchange methods.
the premaster secret plus the two nonces (client_random and server_random) are used to derive the master secret per 8.1 and then the master secret and the nonces are used to derive the working keys per 6.3. In case of renegotiation, the second derivation (from master secret to working keys) is repeated using the new nonces from the second handshake, see F.1.4. These steps are the same for all keyexchange methods.

Both key-derivation steps use what is now called the 'pseudo-random function' PRF. Unlike the other steps, this varies between protocol versions: SSL3 used nested MD5 and SHA1 (and didn't label it PRF), TLS1.0 and 1.1 use doubled both HMAC-MD5 and HMAC-SHA1, and TLS1.2 uses doubled HMAC of a hash that can be selected for each ciphersuite but so far is always SHA-256 or SHA-384.


It's safe to store a known value (for checking) next to the actually encrypted values

Yes, it is secure to do this. Any cipher should be secure against known plaintext attacks after all.

However, if you're using RSA then the RSA decryption routine will already throw an exception during the PKCS#1 v1.5 unpadding, so storing the 'lorem ipsum" data is not necessary: the padding already acts as the "lorem ipsum" data.

If you still somehow require "lorem ipsum" for the symmetric encryption (in case Android loses track of the AES key as well) then you might as well use the "lorem ipsum" as Additional Data for the GCM algorithm. This data is included in the authentication tag but not in the ciphertext. If it is constant then you do not have to include it at all.

Note that you may want to use RSA-OAEP or RSA-KEM rather than PKCS#1 to avoid padding related attacks (RSA-OAEP should be directly available in Java / Android and is therefore recommended, but please do check with the KeyStore implementation and the targetted runtimes to be sure).


Certificate Path Verification of X509 Certificate

Now when i am validating the certificate do i need to trace back the whole chain to validate the certificate?

Not each time, no. You can do some caching, if you like (since root CAs tend to be valid for many years). But I don't think performance gains will be worth the added complexity of the caching idea.

Also: if you plan to honor the expiration dates in the root CA itself, then you have to check these using some other mechanism.

Also: you may have to account for the (unlikely) case of the intermediate CA being revoked.

So, unless you have a good reason not to check each time, then I recommend checking the complete chain from end-entity-certificate (inclusive) up to trust-anchor (inclusive). It's easier to understand.


How is the base64 encoded signature in Craig Wright's proof constructed?

Short version: the signature is correct, it is a real signature and therefore it is possible to verify it with one's favourite software. The scam is not based on a cryptographic attak but on what is signed. Craig Wright has recovered an old (and real) Satoshi's signature and tried to provide it as a new signature to validate his identity. It's, as someone suggested, like to cut out the last page from a contract, paste it to another contract and claim the new contract is ok.

More details:

Wright claimed that he provided a signature on a large file, a text from Sartre. As the text is big, the signature is the decryption of the hash of this text.
The clever move by Wright is to sign the SHA256 of this file, so the final signature is something like:
secp256k1(sha256(sha256(file)))
and one may remark the double use of the hash function SHA256 (while a standard signature would be something like secp256k1(sha256(message)).

The Bitcoin protocol describe how a transaction has to be signed:
secp256k1(sha256(sha256(transaction))).

The algorithm are the same, if the "transaction" and "file" are the same, or better, if their hashes are the same, one signature for the transaction is a valid signature for the file and viceversa.

Wright tried to sell to the world and old signature of a transaction as a signature of the hash of a text.
Why he did it? Because we are not provided of the original Sartre text and therefore is impossible to compute the valid SHA256 image (which text? how is formatted? which charset? newlines? every little change in the text would change the hash) and we cannot search for a given hex string into the blockchain.

A more complete guide to Wright process is available at http://blog.erratasec.com/2016/05/satoshi-how-craig-wrights-deception.html


Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?

I guess that it's also zero-knowledge, but I'll let you do the proof. However, an easier thing to note is that if $X=g^x$ and $X'=g^{x^2}$ then it follows that $(g,X,X,X')$ is a Diffie-Hellman tuple (i.e., it is of the form $(g,g^a,g^b,g^{ab})$. As such, you could use the standard Diffie-Hellman tuple Sigma protocol as a "black box".

(Note that Sigma protocols are defined as honest-verifier zero-knowledge, so that is the level we are aiming for here.)


Your assumptions are partially correct.  The wiring of the rotors is technically part of the algorithm, but because of the era in which Enigma was invented the rotors were kept secret, so discovering the rotor wiring became an initial step in the cryptanalysis of the machine.  The plugboard/steckerboard, however, was changed by the operator every day and its setting was definitely part of the key.

The full key to an Enigma message is made up of everything the operator needed to set in order to encipher and decipher a message.  There are four parts to the key.

Rotor order.  Each rotor had a Roman numeral engraved on it to identify it, and the operator had to install them in the assigned position.  This was set daily.
Ring position. Each rotor had an alphabet ring that could rotate about the rotor, and it had to be positioned correctly before installing the rotor in the machine.  This was set daily.
Letter starting position. Each rotor had to be rotated to display the correct starting letter.  This was set at the beginning of each message.
Plugboard wiring.  This was set daily.

The settings were changed every day.  The operator looked up the settings by date printed on a sheet of paper and would set up the machine for that day, establishing the key.  The starting position of the wheels had to be set prior to each message being sent or received.  If there was a problem or typo during the message, the operator had to start over by resetting the wheels, and retyping the entire message.

I believe the setting sheets were distributed monthly, and the naval versions were printed on water soluble paper so they could be destroyed in the event of imminent capture or sinking; but I don't have a reference for that.

Operating instructions for the machine can be viewed here:  http://www.ellsbury.com/enigma3.htm

An English translation of a manual for the machine can be found here:
http://www.ilord.com/enigma-manual1937-english.html


Is there a group where CDH is easy but DLog is hard?

Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.

This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G \times G \to G$ (same source & target groups).

  Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.

Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.

Unfortunately, having a self-bilinear map $e : G \times G \to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^{2xy}$ which is bilinear, but they are in (a subgroup of) an RSA group $\mathbb{Z}_{pq}$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!


You shouldn't be concerned if you use PKCS#1 v2 encryption padding - the OAEP.
OAEP, the Optimal Asymmetric Encryption Padding guarantees that even the slightest difference in raw plaintext (in your case, your symmetric keys) will result in huge difference in padded plaintext.


Can homomorphic encryption be used to exchange keys?

In short

It can be secure, but it will be very inefficient.

In detail

Those bit strings 0001, 0010, 0100, 1000, etc are just powers of two if you look them as integers (i.e., $2^0, 2^1, 2^2, 2^3$, etc) and applying logical bitwise or to some of them is equivalent to adding up some of the powers of two.

Therefore, what you have proposed is a scenario where Alice publishes several encryptions of powers of two, $c_i := Enc(2^i)$ and Bob combines them in some random way, that is, Bob chooses $b_i \in \{0,1\}$  and compute
$$c_B := \sum_{i=0}^{n-1} b_i\cdot c_i = Enc\left(\sum_{i=0}^{n-1} b_i\cdot 2^i\right).$$

It is easy to see that if each $b_i$ is chosen uniformly, then the distribution of the value encrypted by $c_B$ is uniform on $\{0, 1, ..., 2^n-1\}$, which is a perfect scenario (the exchanged key is uniform, then, hard to guess).

However, the problem with this approach is that an attacker could look at $c_B$ and all the $c_i$'s and try to figure out the values of $b_i$'s. Notice that if we manage to discover at least one $b_i$, then we know what is the $i$-th bit of the exchanged key. So, we must rule out that possibility.

A standard way of doing it is to use the Leftover Hash Lemma to guarantee that the distribution of $c_B$ is statistically close to the uniform on the set of ciphertexts $\mathcal C$, but it would require $n$ much bigger than the security parameters $\lambda$. It means that Alice would need to publish much more than $\lambda$ ciphertexts, each one having more than $\lambda$ bits, which means publishing much more than $\lambda^2$ bits (likely to be more than $\lambda^3$). And we still have to take into account the time required to encrypt and combine all those values...

Moreover, I don't think that there is another known way of making this key-exchange secure, since the problem of hiding these $b_i$'s is basically the same problem that the homomorphic encryption schemes face when they are turned into public-key schemes, and the solution I always see on the papers is the one I said (using Leftover Hash Lemma).


Is the "Hash Tree" described in this paper the same as a Merkle Hash Tree?

It turns out that the Hash Tree mentioned in the paper is pretty much the same as a Merkle Hash Tree. For further clarification see pages 344 & 345: https://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf.


If we assume that your ciphers have the IND-CPA property (indistinguishability under chosen-plaintext attack) then both methods will be equally good.

However exact reproducability of the values can only be achieved by the first method.


I will assume the way my class does it is the same way other classes such as CryptoJS do it.

Quite simply, there is a buffer in the class that absorbs the input until it reaches the hash block length or a multiple thereof, then processes that section of the buffer through the compression function. Whatever is left becomes the start point of the buffer.

How to implement that buffer is up to the programmer.


You should encrypt the data using a well-vetted standard, like TLS (for data in motion) or GPG (for data at rest).  Designing your own is more likely to lead to sadness.  The format of the data that you protect in this way is up to you and can be broken down into structs and chunks and headers etc. to your heart's delight.


How to forge Schnorr signatures if you can guess the challenge

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece.

Notation

In step 1, Alice sends $g^r$. Call this value $a=g^r$.
In step 3, Alice sends $r+se$. Call this value $b=r+se$.
In step 1-3, one value is sent in each step: {$a,e,b$}. We'll call these three values a transcript for public key $v$.
In step 4, with the new notation, Bob checks: $a=g^bv^{-e}$.

Basic question

With this notation, it may be easier to see how knowing $e$ can help. Generate a random $b$ and then compute $a$ so that the equation holds and {$a,e,b$} will accept.

Another thing to note

Other answers noted that since you choose $a$ directly, you do not really know an $r$ such that $a=g^r$ (by the discrete log problem). This is one thing that distinguishes a true proof from a simulated one.

A second thing to note, which is very important, is that to simulate a proof, you start by computing (choosing) $b$ and then you compute $a$ using $b$ and $e$. In a real execution, you compute everything in order.

The only way to forge?

The other answers have shown a way to simulate the proof. Is it the only way?

For example, is it possible to choose an $a$ value knowing $e$ and then compute the right $b$ to make {$a,e,b$} accept (short of knowing $s$)? The answer is no.

Pretend you have a black box that could do this: it takes {$a,e$} as input and returns the proper $b$ without knowing $s$. If such as box existed, you could query {$a,e_1$) and get $b_1$, and then query {$a,e_2$} with the same $a$ and different $e$, and get $b_2$. However one can verify that this is sufficient to compute $s$: in fact, $s=\frac{b_1-b_2}{e_1-e_2}$.  So there is a contradiction: the box doesn't know $s$ by definition and yet it does "know" $s$ (in the sense that it can compute it). Therefore, by contradiction, such a box cannot exist, and neither can a forgery {$a,e,b$} where $a$ and $e$ are chosen.

Enforcing only true transcripts

If we put all of the above together, it basically says that if {$a,e,b$} accepts, it must have either been computed by someone who truly knows $s$, or it was computed backward by choosing/knowing $b$ and $e$ before computing $a$.

Can we eliminate the second case? One way is to be Bob. Another might be to be there in person to see that $a$ is sent before $e$: however do you really know that Alice doesn't know $e$? Can you really be sure?

The answer is yes.

If you can ensure $a$ is computed before $e$, then we are done. A simple technique (called Fiat-Shamir) is to set $e=\mathcal{H}(a)$, where $\mathcal{H}$ is a hash function (technically a random oracle). If you choose/know $e$ first, you cannot find an $a$ that will hash to it (by preimage-resistance).


Why do the game-hops in Kyber and related papers contain 2 steps at a time?

I'm answering my own question here, because i finally found the answer and want to preserve it for future reference.

The Bos et al. paper states it more clearly.
The define the R-LWE problem as a problem on $m$ independent samples, either from the uniform distribution over the ring, or from the R-LWE Distribution where the secret $s$ is common to all the samples.
With this assumption, we can clearly do the game hop with two simultaneously exchanged parameters (here $m=2$).
I am assuming the definition for M-LWE is similar.

Regarding validity of splitting the game hop into two:
That may be possible, but is not obvious, i.e. I was not able to write down the reduction.


How is R-LWE related to lattice cryptography and homomorphic encryption?

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a way to discuss homomorphic encryption as well without essentially writing some (informal) lecture notes, so won't in this answer.
The LWE Problem:
The central hard problem for building constructions in lattice-based cryptography is the Learning With Errors problem.
There is a search and decisional form. The decisional form is to distinguish:
$$(A, As + e)\stackrel{?}{\approx}_c(A, u)$$
Here:

$A \gets\mathbb{Z}_q^{m\times n}$ is a uniformly random matrix
$s\gets \mathbb{Z}_q^n$ is a uniformly random vector
$e\gets \chi^m$ is a random "concentrated" value (meaning $\lVert e\rVert_\infty$ is "small").

The search problem is to recover $s$, given $(A, As + e)$.
This problem has a natural coding-theoretic [1] interpretation --- we can view $A$ as being the "generator matrix" of a random code, and $As + e$ being an encoding of $s$ under the aforementioned code that is sent through some "noisy" channel.
In this setting, the problem of recovering $s$ is equivalent to the problem of decoding a random linear code, which is thought to be hard. Note that this is a problem we would want to do in practice --- random linear codes tend to achieve optimal parameters (up to constant factors), so coding theorists would be very happy if we could decode them.
Average-case Hardness:
Before discussing lattices more, I'll quickly discuss average-case hardness (as this is quite relevant to lattice-based cryptography). There are roughly two settings where one can discuss the complexity of some problem:

In a "worst-case" setting. I.e., given any input instance, how long does it take you to solve the problem?
In an "average-case" settting. I.e., given an input instance drawn at random from a particular distribution, how long does it take you to solve the problem?

Concepts such as NP-hardness discuss the former, but they are not particularly useful for cryptography.
This is because one can have problems that are worst-case hard, but "most" instances of the problem are easy.
If one chose an "easy" instance of the problem during key generation in some cryptographic construction, it could lead to the scheme breaking, despite the problem being worst-case hard.
This means that cryptographic constructions have to pin down some distribution such that the underlying problem is thought to be average-case hard.
This can be more involved than you may think. If you think the underlying problem for RSA being "Factoring" vaguely, then one quickly runs into the unfortunate fact that random numbers are not too difficult to factor (for example, they are divisible by 2 with probability $1/2$ --- depending on how you define the factoring problem this may already suffice to "break" it). One can think about the problem of factoring semi-primes as being the general factoring problem where one specifies a plausible average-case hard distribution (that of semi-primes). This distribution is only plausibly hard though, and there are a number of non-trivial attacks depending on how a particular RSA instance is generated (for example, Pollard's $p-1$ algorithm). This is all to say that you can find some distribution over RSA instances which is likely average-case hard, but it is a more involved process than "just picking things randomly", and that the existence of non-trivial attacks even against the factoring of semi-primes means that we are really left with heuristic hardness of factoring in the end (although this has been fairly resilient over the years).
Lattice-based cryptography differs from this in a significant way due to the existence of worst-case to average-case reductions [2]. This essentially means that there exists some worst-case problem called SIVP (a slight generalization of the shortest vector problem you allude to) such that one can roughly [3] prove something of the form:

If SIVP is worst-case hard, then LWE is average-case hard

This is to say that lattice-based cryptography has a formal proof that the LWE distribution has a certain amount of average-case hardness, provided that a certain natural problem is worst-case hard.
The Ring Setting:
In the above I have only talked about LWE. The "Ring" setting (so working with RLWE rather than LWE) can be viewed as not choosing $A$ to be uniformly random, but instead uniformly random over some "structured subset of all matrices". This is not the most natural way to discuss things from a mathematical perspective, but may be useful initially.
This structured subset admits a compact representation, and more efficient operations generically.
This is to say that RLWE is mostly a way to improve efficiency, which while quite important in practice is not necessary to get the broad picture of lattice-based cryptography.

[1] There are some nuances here, the linear code should not be viewed as being a code in the binary symmetric channel (i.e. a "code with respect to the Hamming norm"), but instead in the additive white gaussian noise channel (say if you take $\chi$ to be discrete Gaussian, which is common).
[2] Note that there are other cryptographic problems with randomized "self-reductions" (for example it is know that if the discrete-log problem is worst-case hard, then it is average-case hard as well). The reductions in lattice cryptography are notable for being to an independently-studied (at least in the non-ring setting) worst-case problem.
[3] There are many caveats one must state here, but the largest one is that one does not work with SIVP in lattice-based cryptography, but instead an approximate version of it. It is known that this approximation problem is in $\text{NP}\cap\text{coNP}$, i.e. is not NP hard unless the polynomial hierarchy completely collapses, which is thought to be unlikely. Other caveats are mostly that there are many ancillary parameters that must satisfy certain inequalities. This is important in practice, but can ignored when just trying to get intuition.


Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.

This is called a Known-Plaintext Attack (KPA). In some real-world examples, this attack makes sense. Also, we want our cipher to resist to KPA, we don't rely on attackers not being able to find known-plaintexts.
Why would Alice send the plaintext together with ciphertext? If so, what is the aim of encryption?

Is there a situation this happens?

This is taken from Mark Burnett's answer

Example: We saw this with the old pkzip encryption method. In this case if you had any of the unencrypted files in the archive, you could use that to obtain the key to break the rest.

Also, in some militaries, the message must be started with
FROM: Name_of_the_Sender
TO: Name_of_the_Receiver

If you are intercepting the encrypted messages, this means that you know at least the first line plus 3 more characters from the plaintext.

How exactly could Oscar predict the word and location of cyphertext?

If you know the context, you can guess about the plaintext. Then you need to solve the equations for position $i$ to get the key. Once a candidate key is found, decrypt the rest of the ciphertext to see that is is not a false positive key. If false-positive, try next guess, if not wonderful.
Cryptanalysis is not an easy job but once successful gives lots of pleasure.


Why have Nonce and why encrypt everything in step 2 for Needham-Schroeder?

As Marcin already said, nonces are for replay protection. Imagine an attacker records message 2 and later on manages to comprimise the old key. He could then impersonate $ S $ and make $ A$ and $ B $ reuse the old key by sending the recorded message to $ A $.
To prevent this, the nonce is included. $ A $ remembers previously received nonces and does not accept messages if an already known nonce is included. If the attacker now tries to resend the old message again, he would fail.

Regarding the second point, I guess you want to ask if double encryption is necessary? If so, you forgot to include the IDs and the nonce :) Kerberos v4 used the same aporoach and was often critized for double encrypting the ticket to $ B $. In v5 they changed that and did your approach, so yes it is possible.
Without the IDs it is not possible though, $ A $ wouldn' t know to whom the ticket has to be delivered.

Regarding the last point, of course the key has to be encrypted. If we assume $ S$ has a shared key with  $ B $ too, this wouldn't be a problem however.
The main reason why $ S $ forwards the ticket to Alice and not to Bob is scalability I guess. $ S $ is a central component and thus reducing the number of message exchanges it has to initiate is probably a good thing.


How do i approach file encryption using encrypt-then-mac?

Derive a 256-bit master key from your password using a password-based key derivation function like scrypt or argon2.

(Don't use PBKDF2 if you can use newer better alternatives that take advantage of memory, not just time, to drive up the adversary's costs.)
Derive subkeys for each purpose using HKDF-SHA256 with a distinct info parameter.

You can feed this master key to HKDF-Expand as the initial keying material (IKM) with some additional salt, but that step isn't necessary if the master key is already derived by a salted PBKDF; you can also use this master key directly with HKDF-Extract as the pseudorandom key (PRK).
Generate known-answer test vectors for the scheme you think you're implementing, using another tool (e.g., write it in C with OpenSSL), so that you can do a self-test when you run your C# program to confirm that it's doing the same computation.
Consider copying the behavior of the scrypt file encryption tool, which has a simple file format and makes it easy to generate test vectors and confirm you're interoperating with another implementation of a good, secure protocol.


Diffie-Hellman: Calculating the private key from the public key with Java

There are several obvious ways to optimize the search.

The easiest approach would be to take advantage of the identity $g^e \cdot g = g^{e+1}$.  That is, if we have already computed $g^e$, and verified that it is not the value we're looking for, then to step to $g^{e+1}$, we don't compute $g^{e+1}$ from scratch; instead, we take the $g^e$ value we have, and multiply it by $g$ (modulo $p$), and that's the next value to check.

And, because you have $g=2$, this can be done as easily as adding $g^e$ to itself, and then subtracting $p$ if needed.

A more difficult (but ultimately more rewarding) optimization is to implement the 'bigstep/littlestep' algorithm.  This takes the equation $g^x = g^{ak+b}$ (for $k = 2^{16}$ and $-2^{-15} \le a < 2^{15}$, $0 \le b < 2^{16}$), and rewrites it as $g^x g^{-ak} = g^b$; we then create a list of the $2^{16}$ possible $g^x g^{-ak}$ values, and the $2^{16}$ possible $g^b$ values, and search for a match (which can be done in $O(n \log n)$ time using a fast sorting algorithm); this match gives us the $a, b$ values, which immediately gives us $x$.  This is obviously a lot more work; however doing this will allow you to find a match by doing around $2^{17}$ modular multiplications; this is a large gain over the previous optimization.


Yes, it is safe.  AAD (Additional Authenticated Data) is optional.  It's available for you to use when you have data you want authenticated (integrity checked) but do no wish to encrypt.  In general, in fact, it's far more common to use AEAD algorithms with only encrypted data and no AAD.


Given a linear block-cipher,how can an attacker decrypt any plaintext value encrypted,using 128 chosen ciphertexts

You already got the answer by yourself.

As a linear cipher with 128 bit, it can be described by a 128x128 matrix over GF(2). To break the cipher is to find that matrix. But that's easy: column k is the decryption of the k'th standard basis, i.e. the vector (0,0,0,...1,...,0,0,0) , with the 1 on the k'th place.

Example:
Decrypt(0001) = 1101
Decrypt(0010) = 0001
Decrypt(0100) = 1010
Decrypt(1000) = 1111

This gives the matrix M:
1011
1001
0011
1101

Now lets say the cipher text is $c= (1111)^T$

The decryption of c is $M*c = (1001)^T$


The security of data traffic over both SSTP & SSL

Assuming that the keys used for the SSL and SSTP layers are independent (which they should be, since both layers have their own separate key setup processes), compromising the outer layer (SSTP) cannot make the inner layer (SSL) any less secure than it would be if used alone.

To see why this is, imagine that there was an attack that did allow breaking SSL + SSTP significantly more easily than plain SSL alone.  Then an attacker could break plain SSL just as easily as SSL + SSTP, simply by taking a plain SSL datastream, tunneling it over his own SSTP connection (a trivial operation) and then breaking the combination.  But this contradicts the original assumption that breaking SSL alone would be harder than breaking SSL + SSTP.

For a more detailed analysis, see Maurer and Massey, "Cascade Ciphers: The Importance of Being First", Journal of Cryptology 6(1), pp. 55–61, 1993.


Authenticating somebody means verifying who they are. This always involves out-of-band information because otherwise you don't even know them.

If you like security games try to distinguish between two people without knowing anything about them. ;)

Even a PKI is a separate channel.

You can consider different authentication factors which are usually split into

Something the person knows (Password-based key agreement)
Something the person has (PKI, their private key)
Something the person is (like a fingerprint)

but in any case you need to somehow be able to verify the information you get using some out-of-band information.

Maybe the 3rd factor "inheritence" deserves a litte more attention. It also includes things that the person does. So you could require that your communication partner behaves in a specific way. However if that behavior is not used to identify somebody you are actually doing fraud detection or intrusion detection and not really authentication.

I suppose you could consider the case where you only know somebody from in-band interactions and you just want to make sure that it's always the same person. In this case you should just do a key exchange on the first interaction.


When confusion is applied during encryption?

Neither of those really represent how confusion might get introduced into an encryption function. Confusion typically gets introduced during the computation of the ciphertext, not before or after.

As an example, we can look at AES. AES is a substitution-permutation network. This means the encryption is done by doing several rounds of substitutions and then permutations. In the case of AES, there are 10-14 rounds of substitutions and permutations.

The way confusion gets introduced into AES is through propagation of bits through the rounds. Imagine if you flip one bit in K. In the first round, this might only effect the one bit of input. Once it passes through the substitution step in the AES S-box, all of the output bits of that S-box will be different. These "changed" bits then get distributed to several other S-boxes in the next round through the permutation step. This continues for all the rounds.

So a single bit change in the key started by only changing one bit in the intermediate computation, but then "spread out" through the encryption process to effect many ciphertext bits.


McEliece information set decoding attack vulnerability

An old thread, but I thought it deserved an answer.

Information-set decoding

In short, the idea behind information-set decoding is to pick a sufficiently large set of error-free coordinates in a sent codeword such that the corresponding columns in the generator matrix form an invertible submatrix. Then, the information sequence can easily be obtained by linear algebra.

A plain information-set decoding algorithm is the simplest form of information-set decoding. It randomly selects an information set and then computes the information by solving linear equations. Consider the following. Let $\mathbf u \in \mathbb F_{2}^{n}$ be an unknown information sequence and

\begin{equation}
\mathbf r = \begin{pmatrix}r_1 & r_2 & \cdots & r_n\end{pmatrix} = \mathbf u \mathbf G + \mathbf e \in \mathbb F_{2}^{n}
\end{equation}
a received codeword encoded by an $[n,k]$ linear code with generator matrix
\begin{equation}
\mathbf G = \begin{pmatrix} \mathbf g_1^T& \mathbf g_2^T& \cdots & \mathbf g_n^T\end{pmatrix}.
\end{equation}

Suppose we pick an information set $\mathcal I \subset {1,2,\ldots,n}$ of size $k$. Recall that $\mathcal I$ is an information set if and only if the vectors $(\mathbf g_i)_{i \in \mathcal I}$ are all linearly independent.
Now, define a masking function $\phi$ such that
$
    \phi(\mathbf G) = (\mathbf g_i^T)_{i \in \mathcal I}
$
and, thus,
\begin{equation}
    \phi(\mathbf r) = (r_i)_{i \in \mathcal I} = (\mathbf u \mathbf G + \mathbf e)_{i \in \mathcal I} =  (\mathbf u \mathbf G)_{i \in \mathcal I} + (\mathbf e)_{i \in \mathcal I}.
\end{equation}
There is non-zero probability that symbols in the information set being perturbed by error, and therefore the procedure usually needs to be iterated with different information sets until it finds one that is entirely error free.
Whenever the selected information set $\mathcal I$ is non-corrupted, i.e., $ (\mathbf e)_{i \in \mathcal I} = \mathbf 0 \iff \mathcal I \cap supp(\mathbf e) = \emptyset$, then the information symbols can be obtained by computing
\begin{equation}
    \phi(\mathbf r)\phi(\mathbf G)^{-1} = \phi(\mathbf u \mathbf G)\phi(\mathbf G)^{-1} = \mathbf u.
\end{equation}
If, on the other hand, the information set contains a non-zero number of errors, then consequently $\phi(\mathbf r)\phi(\mathbf G)^{-1} \neq \mathbf u$, and therefore another different $\mathcal I$ must be chosen, until a solution satisfying the weight constraint is found.

There are several improvements to this technique, involving birthday techniques. One classic and commonly referenced algorithm is Stern's algorithm.

Decoding attack

Message recovery:  Recovery of the message from a ciphertext is best done (if no structure can be exploited) by information-set decoding algorithms, by finding a minimum-weight codeword in the coset $\mathbf r+ \mathcal C$. This can be accomplished by constructing an extended code with the generator matrix
$$
\mathbf G' = \begin{pmatrix}\mathbf G\\ \mathbf r\end{pmatrix}.
$$
Then, an information-set decoding algorithm may be applied to find the minimum-weight codeword $\mathbf{e}$.

Key recovery: The purpose of a key recovery (structural attack) is to recover the private key from the public key. Many codes used in information transmission have a structure which allows for an efficient decoding procedure. In the context of information transmission, it does not pose a problem to have a structured code. In contrast, for code-based cryptography such as McEliece, security of the cryptosystem relies on that the public-key generator matrix is indistinguishable from a random one. Therefore, when structured codes are used, security will degrade because of the inherent structure of the public key.
It is sometimes possible to recover the private key by looking for low-weight codewords in the code generated by the public key. By exploiting the structure of the code, this procedure can sometimes be accelerated.

Information-set decoding is a big hammer

Information-set decoding applies to basically all code-based cryptography. Therefore, it serves as an upper bound on the security and naturally, parameters are designed according to this bound. The linear decoding problem is NP-hard and therefore breaking McEliece remains exponential in the worst case. If or when a new, more efficient information-set decoding algorithm is invented, the old parameters must re-scaled.


Key space size when either of two public keys are valid for authentication?

Yes, having two valid keys in effect halves the size of the keyspace — from 2256 to 2255 possible keys per each valid one.

Not to 2128 keys, which is what a 128-bit keylength would get you.

Remember that the number of possible keys grows exponentially with the number of bits per key.  (Adding one bit doubles the size of the keyspace, since the added bit has two possible values: 0 or 1.)
A 256-bit keyspace has 2256 possible keys, which is a huge number.  Even if you had literally billions of valid keys instead of just one, it wouldn't make finding one of them by brute force any less impossible.


Understanding MACs and why cleartext is sent over

A MAC is used to ensure two properties, really: the message has not been altered and the message has been indeed be sent by Alice and not Eve. If the MAC is secure, then Eve cannot change the message and compute a valid MAC for the modified message. Eve can read the message, but in this scenario we only protect the messages against modification and we want to know it comes from Alice (as Bob believes only Alice has the key for the MAC, so is the only one, besides himself, to be able to generate and check the MAC). Such MAC-only networks could occur, if speed (avoid encryption overhead) and authenticity are your main concerns, e.g. in alarm systems, where you don't want the alarm messages to be modified by an attacker, but you don't care about it being private.

It is possible to combine it with another cryptographic primitive if privacy is desired. It's most common to encrypt the data and then compute a MAC over the ciphertext and send both (EncryptThenMAC), also possible, but possibly less secure: encrypt the plaintext and its MAC and send the resulting ciphertext (MacThenEncrypt), or compute a ciphertext over the plaintext, and send the ciphertext together with the MAC of the plaintext. (EncryptAndMac) This leaks some info, possibly. But all three have been done. Or use an authenticated-encryption mode of a block cipher like GCM or OCB mode. These modes mostly follow the EncryptThanMac paradigm, as that has the better security proofs.


I have a problem with OFB mode, because I have heard that it is stronger than CFB.

On the contrary I would say that CFB is stronger.

OFB means encrypting the IV again and again to produce the keystream. If you end up in a cycle, the keystream will start repeating itself. (This should not be a practical weakness, but why chance it?)

CFB is more like CBC, in that it uses the ciphertext as input to the cipher for the next block. This means it will not enter cycles unless e.g. encrypting a constant plaintext. CFB can also recover from IV reuse if the plaintext it different (which is an advantage even over CTR).

  What are the advantages of using OFB (Output Feedback Mode)?

One advantage OFB does have over CFB is that you can pregenerate the keystream, since it does not depend on the plaintext. However, as the other answer states, encryption with either algorithm is serial and cannot be parallelized. That makes CTR the best choice for performance, since it also allows keystream pregeneration.

Of course, in the real world you should just use an authenticated encryption mode (like GCM) unless you are certain you know what you are doing.


By this paper, indistinguishability obfuscation is enough for that.


Why is SHA-512 limited to an input of $2^{128}$ bits?

The standard FIPS.180-4 defines a padding scheme that limits the upper input size.

  Then append the 128-bit block that is equal to the number $l$ expressed
  using a binary representation.

Where the $l$ is the message length. Therefore, according to the standard, you can hash at most $2^{128}$-bit-sized input messages.

This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA-512. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.


NTRU less secure than previously thought?

No, this result (as it stands) is of no practical use against NTRU as typically used.  To quote the paper:

  Note that there is a large value hidden in the o(1) term, so that our algorithm does not yield practical attacks for recommended NTRU parameters.

In addition, while it is subexponential, it's just barely so; they estimate the time as $2^{ (\ln 2/2+o(1))n/ \log \log n}$; even if we ignore the $o(1)$ term, this grows just slightly slower than an exponential function.

On the other hand, it may be that this attack might be useful against the use of NTRU as a somewhat homeomorphic cipher (which requires the error terms to be much smaller).  In addition, perhaps this result can be sharpened to be strong enough to be useful against NTRU.  So, while this isn't fatal to NTRU, the book isn't closed either.