After a small search; it is a vote buying scheme.

  Chain voting, a vote buying scheme in which a crook gives the voter a pre-voted ballot, the voter votes that ballot, and then after leaving the polling place, sells his blank ballot to the crook, who votes it and then gives it to the next willing participant.

This is from Douglas W. Jones web page and reference 12 of the Rivest's article points his definition.

This attack is applied in many countries (I'll not give any source). One countermeasure can be paper-based PUF. Also, some ideas from University Voting Systems Competition might be interesting to look at.


How to calculate plaintext from modpower cipher

It is conjectured to be hard to recover $a$ given only $b$, $e$, and $n$. This is called the RSA assumption. If an efficient factorization algorithm exists, this assumption is false.

However, it is possible that the RSA assumption is false and there exists no efficient factorization algorithm. In other words, the hardness of factoring might not imply the RSA assumption is true.

In your question you merely call $n$ a large non-prime modulus. You have to be a little careful about the primes that make up $n$; there are lots of ways to screw up and accidentally make it easy to factor $n$.


How does Gilbert, MacWilliams, and Sloane's solution to “perfect integrity” work?

Let $r, s$ be uniform random nonnegative integers below $2^{130} - 5$, shared by Alice and Bob but kept secret from the adversary Mallory.  If Alice wants to send a single message $m \in \{0,1\}$ to Bob (this is a yes-or-no message—only two possible messages, with no secrecy of the message, the simplest scenario imaginable), she can compute the authenticator or authentication tag or MAC $$t = (r \cdot m + s) \bmod (2^{130} - 5)$$ along with $m$.  Suppose Mallory intercepts $(m, t)$, and wants to find $(m', t')$ for $m' \ne m$—that is, Mallory wants to find another message/authenticator pair whose message is any message other than $m$, in order to fool Bob.  Bob will accept the forgery $(m', t'$) only if $$t' = (r \cdot m' + s) \bmod (2^{130} - 5).$$  No matter what the real message $m$ and the real authenticator $t$ are, and no matter what forgery $m'$ and $t'$ Mallory attempts, and no matter how much computation Mallory can do, the probability that Mallory's forgery attempt succeeds—i.e., the probability that Bob accepts Mallory's forgery—is at most $1/(2^{130} - 5)$.  Why?

Consider Mallory's perspective: they don't know the real key; they only know a real message $m$ and its real authenticator $t$.  For any particular message $m$ and authenticator $t$, there are $2^{130} - 5$ different pairs of values $(r, s)$ satisfying $t = (r \cdot m + s) \bmod (2^{130} - 5)$: for each possible $r$ there is exactly one $s$ satisfying the equation, namely $s = (t - r \cdot m) \bmod (2^{130} - 5)$.  But only one of those $(r, s)$ pairs also satisfies $t' = (r \cdot m' + s) \bmod (2^{130} - 5)$ for any $m' \ne m$ and $t'$ (see below for more formal proof).

So—no matter what computation Mallory does!—given only $m$, $t$, and the knowledge that $t = (r \cdot m + s) \bmod (2^{130} - 5)$, Mallory can't narrow the candidate keys $(r, s)$ down to fewer than $2^{130} - 5$ possibilities, all with the same probability $1/(2^{130} - 5)$.  And since Mallory doesn't know which of the $2^{130} - 5$ values of $(r, s)$ Alice and Bob are actually using, Mallory has no hope of finding any $m'$ and $t'$ that will fool Bob, by satisfying $t' = r \cdot m' + s$, with probability higher than $1/(2^{130} - 5)$.

And this bound on forgery probability is the best you can hope for when there are $2^{130} - 5$ distinct authenticators on any given message: for any attempted forgery, the adversary could guess what the right authenticator is uniformly at random with probability $1/(2^{130} - 5)$.  In general, as long as there are only $n$ times as many possible authenticated messages as there are messages, whether the authenticator is tacked onto the end or the message is otherwise transformed to authenticate it, the best bound on forgery probability you can hope for is $1/n$.

I don't recommend the term ‘perfect integrity’, which is value-laden and ripe for confusion, but attaining this bound is the most reasonable interpretation of the term, and the theorem that the GMS authenticator attains this bound is unconditional in a specific technical sense.

We can write this a little more formally in the language of fields.  Since $p = 2^{130} - 5$ is a prime number, the integers modulo $p$ form a field, sometimes called $\mathbb Z/p\mathbb Z$ or $\mathbb F_p$.  If we understand the arithmetic to be done modulo $p$, we can write these equations in the event of a forgery a little more simply as

\begin{align*}
  t &= r m + s, \tag{$*$} \\
  t' &= r m' + s. \tag{$**$}
\end{align*}

Mallory knows $m$ and $t$, and assumes the equation $(*)$ is true—i.e., that Alice is computing the authenticator correctly.  Mallory succeeds at forgery in the event that the equation $(**)$ is also true, given that $(*)$ is true—that is, Mallory's forgery probability is the conditional probability

\begin{equation*}
  \Pr[\text{forgery} \mid \text{message/authenticator}]
  = \Pr[t' = r m' + s \mid t = r m + s].
\end{equation*}

We can rearrange this a little bit to eliminate the independent random variable $s$ by observing that $s = t - r m$, so we're interested in the probability that $t' = r m' + t - r m$, or equivalently $r = \frac{t' - t}{m' - m}$, since $m' \ne m$ and we're working in a field in which we can divide by any nonzero element.  In other words,

\begin{equation*}
  \Pr[t' = r m' + s \mid t = r m + s]
  = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}].
\end{equation*}

Since $r$ was a random variable with uniform distribution among $2^{130} - 5$ possibilities, and $m$, $m'$, $t$, and $t'$ were arbitrary (i.e., there's a for all quantifier here—the reasoning works for all values of $m$, $m'$, $t$, and $t'$, except when $m = m'$), we can conclude, irrespective of Mallory's computational powers,

\begin{equation*}
  \Pr[\text{forgery} \mid \text{message/authenticator}]
  = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}]
  = 1/(2^{130} - 5).
\end{equation*}

This bound on forgery probability applies even if Mallory gets to choose the original message $m$ in an attempt to make the task of forging the authenticator for a different $m'$ even easier.

This one-time authenticator is the basis for one of the most popular message authentication codes on the planet, Poly1305, widely used in the authenticated cipher ChaCha/Poly1305 by TLS and in the related authenticated cipher crypto_secretbox_xsalsa20poly1305.  I left out many practical details:

extending it to longer messages by interpreting the 128-bit chunks of a message $m$ as a polynomial $m_1 x^\ell + m_2 x^{\ell - 1} + \dotsb + m_\ell x$ over $\mathbb F_{2^{130} - 5}$ and evaluating it at the point $r$;
restricting the space of the evaluation points $r \in \mathbb F_{2^{130} - 5}$ for efficient software implementation; and
extending it to many messages by deriving $r$ and $s$ pseudorandomly with ChaCha or XSalsa20 for each message.

With these practical details sorted out, the forgery probability is still no more than $8\ell/2^{106}$ where $\ell$ is the number of 128-bit blocks in a message, plus whatever advantage the adversary can get by attacking the pseudorandom key derivation.

This might look very different from the Gilbert–MacWilliams–Sloane paper (paywall-free).  But actually, it is precisely (an instance of) the scheme described by Gilbert, MacWilliams, and Sloane, just without the language of projective space from algebraic geometry.

The geometric picture of the GMS scheme is that:

a $\text{message}$ is a line (drawn in solid black) through the origin that hits the equator (drawn in grey at $z = 0$),
a $\color{blue}{\text{key}}$ is a line (dashed blue) through the origin that doesn't hit the equator, and
an $\color{red}{\text{authenticated message}}$ is a line (dotted red) through the origin perpendicular to both message and key.

For any fixed message, every corresponding authenticated message under any key passes through the great circle perpendicular to that message (solid black)—but to know which line through that great circle requires knowledge of the key.  For any fixed key, every authenticated message under that key passes through the great circle perpendicular to that key (dashed blue)—but knowing one line through that great circle doesn't help to find any other line through that great circle for a forgery because there are many great circles that the authenticated message passes through and any one of them could correspond to the true key.

How do we compute this, though?  We won't actually work in real projective space; we'll work in the projective plane of a finite field, which is a little trickier to draw but easier to compute with, from algebraic geometry.

Fix a prime power $q$ and consider the finite field $k = \operatorname{GF}(q)$ of $q$ elements.  The projective plane $\mathbb P^2(k)$ over $k$ is (by one of several equivalent constructions) the set of lines in $k^3$ through the origin, with each line typically represented by any nonzero point on that line—the projective coordinates $(x : y : z)$ represent the same line as $(\lambda x : \lambda y : \lambda z)$ for any nonzero $\lambda \in k$, as long as $x, y, z \in k$ are not all zero.  (This rules out ‘$(0 : 0 : 0)$’ as a point on the projective plane.)  There are $q^2 + q + 1$ points on the projective plane, which can be counted in various different ways—for example, $q^2$ points of the form $(x : y : 1)$, $q$ points of the form $(x : 1 : 0)$, and the remaining point $(1 : 0 : 0)$.

In the GMS one-time authenticator, a message is a point $(1 : s : 0)$ on the ‘equator’ for some $s \in k$, and a key is a point $(i : j : 1)$ off the ‘equator’ for some $i, j \in k$ chosen uniformly at random.  An authenticated message is a line in the projective plane through the message and the key—equivalently, the set of all lines in $k^3$ through the origin that intersect the great circle on the unit sphere between the points where the message and key intersect the unit sphere (the dotted red circle in the diagram above).

Now, as the set of all lines in $k^3$ through a particular great circle on the unit sphere, a ‘line’ in projective space $\mathbb P^2(k)$ corresponds to a plane in the enclosing space $k^3$, so we can characterize it by a normal vector $L \in k^3$ to that plane: that is, the plane representing a projective line is the space of all vectors $v \in k^3$ perpendicular to $L$ so that $L \cdot v = 0$.  Any such normal vector $L = (x, y, z)$ is perpendicular to both $(1, s, 0)$ and $(i, j, 1)$, so it must solve the linear system

\begin{align*}
  0 &= L \cdot (1, s, 0) = x + y s, \tag{$\dagger$} \\
  0 &= L \cdot (i, j, 1) = x i + y j + z. \tag{$\ddagger$}
\end{align*}

Note, of course, that if $(x, y, z)$ is a solution then so is $(\lambda x, \lambda y, \lambda z)$ for any nonzero $\lambda \in k$.  Hence we can also view an authenticated message as a projective point which is ‘perpendicular’ to both $(1 : s : 0)$ and $(i : j : 1)$; such a point is given by $(-s : 1 : c)$ where $$s i - j = c,$$ which is Eq. $(17)$ of the paper.  (Eq. $(\dagger)$ implies $x = -y s$, and Eq. $(\ddagger)$ implies $z = y s i - y j$; dividing the coordinates by $y$ gives the form $$(x : y : z) = (x/y : y/y : z/y) = (-s : 1 : c)$$ for $c = z/y = s i - j$.)

Of course, rather than drawing out doodles of lines and planes on a napkin, we can represent a message by the element $s \in \operatorname{GF}(q)$ alone, a key by a pair of elements $i, j \in \operatorname{GF}(q)$, and an authenticator by an element $c \in \operatorname{GF}(q)$, and then encode those in bit strings to transmit on a conventional medium like ethernet.  And if you pick $q = 2^{130} - 5$, you wind up with exactly the scheme this post started with.  The correspondence with the GMS notation is:

\begin{equation*}
\begin{array}{r|c|c}
\text{role} & \text{this post} & \text{GMS} \\
\hline
\text{prime power modulus} & 2^{130} - 5 & q \\
\text{message} & m & s \\
\text{key} & (r, s) & (i, -j) \\
\text{authentication tag} & t & c \\
\text{authentication equation} & t = rm + s & si - j = c
\end{array}
\end{equation*}

Appendix: Asymptote code for the diagram

import three;

size(10cm, 0);

triple msg = (1, 4, 0);         // (1 : s : 0)
triple key = (1/2, 1/5, 1);     // (i : j : 1)
real tag = ypart(msg)*xpart(key) - ypart(key);
triple authmsg =                // (-s : 1 : si - j)
  (-ypart(msg), 1, tag);

void
drawaxis(triple A, string text, align align)
{
  Label L = Label(text, position=EndPoint, align=align);
  draw(O--1.5A, arrow=Arrow3(TeXHead2), L=L);
}

drawaxis(X, "$x$", align=W);
drawaxis(Y, "$y$", align=E);
drawaxis(Z, "$z$", align=N);

draw(circle(c=O, r=1, normal=Z), p=gray(0.5));

draw(1.5 unit(msg) -- 1.5 unit(-msg), arrow=Arrows3, p=black,
  L=Label("\noindent msg:\\$(1 : s : 0)$", position=BeginPoint, align=SE));
dot(unit(msg), p=black);
dot(unit(-msg), p=black);

draw(1.5 unit(key) -- 1.5 unit(-key), arrow=Arrows3, p=blue + dashed,
  L=Label("\noindent key:\\$(i : j : 1)$", position=BeginPoint, align=NW));
dot(unit(key), p=blue);
dot(unit(-key), p=blue);

draw(1.5 unit(authmsg) -- 1.5 unit(-authmsg), arrow=Arrows3, p=red + dotted,
  L=Label("\noindent auth msg:\\$(-s : 1 : c)$", position=EndPoint, align=S));
dot(unit(authmsg), p=red);
dot(unit(-authmsg), p=red);

draw(circle(c=O, r=1, normal=msg), p=black);
draw(circle(c=O, r=1, normal=key), p=blue + dashed);
draw(circle(c=O, r=1, normal=authmsg), p=red + dotted);
draw(
  0.2 unit(key) -- 0.2 (unit(key) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));
draw(
  0.2 unit(msg) -- 0.2 (unit(msg) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));

draw(unitsphere,
     surfacepen=material(white + opacity(0.5), ambientpen=white));


Well, we know that the ciphertext $c$ is a Quadratic Residue, then both $c \bmod p$ is a QR (modulo $p$) and $c \bmod q$ is a QR (modulo $q$).  And, we know that (for valid ciphertexts) $c$ has a Jacobi of 1, and so if it is not a QR, then both $c \bmod p$ is a non-QR (modulo $p$) and $c \bmod q$ is a nonQR (modulo $q$).

And, we have the private key, and so we can have the value of $p$.  So, one simple way to decrypt $c$ is to first evaluate $c \bmod p$, and then check if it is a QR; for example, check the value of $(c \bmod p)^{(p-1)/2} \mod p$; if it evaluates to 1, then $c$ is a QR (and so the plaintext is 0); if it evaluates to $p-1$, then $c$ is not a QR (and so the plaintext is 1).


AES-128 CBC encryption : ciphertext size seems too large

ECB and CBC require padding or a scheme called ciphertext stealing if the size of the messages is not a multiple of the block size. Commonly a scheme such as PKCS#7 padding is applied, quite often by default (i.e. without you explicitly specifying it, e.g. OpenSSL defaults to PKCS#7 compatible padding).
Such padding schemes are created to apply for messages with any binary value. That means that if the size of the plaintext is identical to a multiple then the padding is applied nevertheless. The reason for this is that it is otherwise impossible to distinguish between the plaintext and possible padding. In your case that means that the input to CBC mode is a block of plaintext and another block of just padding.
If your message is always a multiple of 16 then you can use CBC without padding, usually by specifying this explicitly. If you use a scheme that only e.g. contains text strings that cannot end with a zero byte then you could use "zero padding". This is also useful for languages that use NUL-byte termination for the strings such as C. Beware, some implementations will always pad when using "zero padding" as well.
Ciphertext stealing is not used much, it could be used for messages longer than one block.
Finally, you could do without CBC altogether and use counter mode (CTR mode or SIC mode) or one of the authenticated ciphers based on it (GCM for instance).


How does the wider cryptographic community view non-abelian group based cryptography?

Almost all cryptographic algorithms which use groups actually work in subgroups generated by a conventional element; even if the group as a whole is non-abelian, the subgroup is cyclic, thus abelian. The Anshel-Anshel-Goldfeld protocol tries to use non-commutativity itself, and relies on "how much non-abelian" the group is.

All asymmetric cryptographic algorithms rely at some point on a presumably hard problem. We do not know whether hard problems really exist, neither asymptotically (that's the whole P=NP problem) nor in practice (when given a specific computational budget, e.g. $2^{80}$ elementary operations). Our only tool is accumulation of work: we take many cryptographers and mathematicians, we let them loose on the problem for a few decades, and we see if they find some way to solve the problem.

To be honest, I had never heard of the Anshel-Anshel-Goldfeld protocol before this morning. It is described in an article which was published in Mathematical Research Letters, which is not usually associated with cryptologic research. There is a bit of research on doing cryptography with braid groups (the AAG protocol is just an instance of that); see this page for a lot of relevant pointers. It is still a recent and widely unexplored area, so, regardless of its inherent merits, the AAG protocol cannot be deemed secure yet. Also, it is only a framework, explained generically over an unspecified non-abelian group; it cannot be declared secure in abstracto.

Infinite non-abelian groups, or anything infinite for that matter, have a slight practical issue: they do not fit well in actual computers which have only a finite amount of RAM. Even for infinite sets where each element can be encoded in a finite (but unbounded) amount of RAM, such as plain integers, variable size easily leads to side-channel leakage, and that's a bad thing.


Should Diffie-Hellman on Curve25519 be validated?

From DJB's page:

Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys.
There are some unusual non-Diffie-Hellman elliptic-curve protocols that need to ensure "contributory" behavior.

So for (EC)DH using Curve25519 you don't need to validate public keys.
If you are using Curve25519 for some other elliptic curve protocol you may need to perform validation by making sure the public key isn't in some small subset of possible public keys.


Signal/TextSecure multiparty Chat. Does the protocol transmits a symmetric key?

Yes, the channel is assumed to be secure. "When sending a message to a group, we simply deliver a pairwise encrypted message to each member of the group."
It's ephemeral. The double ratchet system ensures that ephemeral keys get changed out, so the compromise will be recovered from.


How does this formula work $(aG + bG) = (a + b) G$ in ECDSA?

..how does this formula $(aG+bG) = (a+b)G$ work in ECDSA?

Perfectly well. It follows from the definition of $kG$ as $\overbrace{G+\cdots+G}^{k\text{ times}}$, associativity and commutativity of point addition. Notice that operator $+$ in $(aG+bG)$ and $G+\cdots+G$ is elliptic curve point addition, while operator $+$ in $(a+b)$ is addition in $\Bbb Z$ (signed integers) or $\Bbb Z_n$ (integers modulo $n$, where $n$ is the order of $G$).

Be confident that $3G+4G=7G$ holds, and if $Q=3G$, $W=4G$, $P=7G$ then $Q+W=P$.
The issue is on what arguments the point addition of the final $+$ is computed.

In the question, what's shown after Q = is the X coordinate $Q_x$ of point $Q$. The Y coordinate is missing. Therefore what follows Q = does not settle between two points: $Q$ of coordinates $(Q_x,Q_y)$ and $-Q$ of coordinates $(Q_x,Q'_y)$ with $(Q_y)^2=(Q_x)^3+7\bmod p$ (per the equation of secp256k1) and $Q'_y=p-Q_y$. Same issue for $W$ and $P$.

  Why is the answer of this sum not this value (..)

This value ended up being the X coordinate for $Q-W$ (or equivalently $-Q+W$) instead of $Q+W$ as thought, due to the above. This also is the X coordinate for the base point $G$, because $Q-W=3G-4G=(3-4)G=(-1)G=-G$.


How much can we compress RSA public keys?

Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification".
The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm.
So if it were possible to decompress arbitrary 104 to 128-bit strings into secure 2048-bit RSA public keys faster than factoring as David Schwartz suggests then that would be quite remarkable. Every time you ran the algorithm you'd effectively be finding the approximately equal sized factors of some 2048bit number of which you'd specified a lot of the bits.
Although there's no theoretical reason I can think of why this should be impossible, nor would it render RSA necessarily insecure, it does strike me as rather unlikely.

As you hint, a further (impractical) way to reduce the storage of the unspecified low bits of the modulus would be to store their residues modulo various small primes and reconstruct using the CRT. In theory this should save between 3 to 4 bits for a 2048-bit modulus. You save the space because you can rely on the residues not being zero.


Questions about Symmetric Encryption part of TLS

I learnt that you could use the key as a AES Key & encrypt the session with AES. Or you could use something like Elgamal encryption.

Elgamal encryption could be used directly with a static private key. The key type would be identical to the one used for (static or ephemeral) Diffie-Hellman. However, it would not be efficient both when it comes to space nor CPU.

So in practice, what is used more commonly? Is it something like AES or is it something like Elgamal?

AES is used much more. Elgamal is not used much because it has drawbacks even compared to e.g. RSA encryption using PKCS#1 or ECIES. One main issue is mapping the message to the cyclic group G, another is the required ciphertext expansion.

AES seems to be quite complicated as compared to Elgamal - Elgamal is just multiplication with the key modulo.

No, that's an oversimplification, please check the Wikipedia page on Elgamal encryption. Beware that these calculations are using huge numbers. Exponentiation and multiplication over such inmense values are not very fast. And, unfortunately, unlike DH, it's not easy to use Elgamal with Elliptic Curves - ECIES is more useful for encryption with Elliptic Curves.

So how come it provides security comparable to AES with all it's s-boxes, p-boxes etc? Is it because for every message a new session key is used with Elgamal?

No, Elgamal is not used with session keys at all. Session keys are symmetric keys derived from a shared secret. Elgamal is for asymmetric encryption. As mentioned, AES is now commonly used within authenticated encryption, which provides semantic security, something that is really important in a transport protocol.


Why is public key cryptography (RSA) used in sites like Google or Facebook?

[I assume you're talking about Google's web search service, and not Gmail.]

Google doesn't encrypt the web page data in storage, because it's not secret data.  Encryption is optionally used by users to securely communicate with Google, and that's different.

Using certificate based keys and encryption assures the users that they are communicating with the Real Google and not a Fake Google that could give them false results.  It also protects the users' privacy from eavesdroppers; so if someone was searching for 'cancer' their employer or family wouldn't know.


Linear congruential generator with non constant increment

The state can be trivially recovered from two consecutive output (and hence all further outputs can be predicted).

For the first output, the system updates the seed to $\text{seed}_1$, and then outputs the lower 32 bits of $\text{seed_1}$, which we'll call $\text{output}_1$

For the second output, the system first computes:

  $\text{seed}_2$ = 1683268614LL * $\text{output}_1$ + ($\text{seed}_1$ >> 32)

Then, the system outputs $\text{output}_2$, the lower 32 bits of $\text{seed}_2$.

Hence, if the attacker computes:

  $\text{output}_2$ - 1683268614LL * $\text{output}_1$ $\bmod{2^{32}}$

That gives him the upper 32 bits of $\text{seed}_1$.  With the entire value of $\text{seed}_1$, the rest of the sequence can be predicted.

With a standard LCG, you can also reconstruct internal states, but not this easily...


How secure is a pronounceable password in terms of entropy?

Yes, the entropy depends on the generation process. The study you link to has the answer for the (fixed) process used there:

  To overcome this [flaw in the original program], we generated the full list of eight-character pronounceable passwords without duplicates (≈ 1.2 billion) and assigned each password on this list with equal probability, resulting in 30.2 bits of entropy.

That is equivalent to five base 64 characters. I.e. you lose about 2.25 bits of entropy per character by making the password pronounceable, compared to using random base 64 passwords.

However, like the implementation they used, it is possible the algorithm is flawed and does not generate all possible pronounceable passwords with equal probability. In that case you lose even more entropy. So I would check the program carefully before relying on it.


Why aren't hash values for "nothing" (empty) defined as all zeros?

Why would that be a convenient property? It would be pretty annoying if I would test an empty string input, hash that and then XOR it with a value. I would get the same value back. You want the output of a hash function to seem random; getting a value of zero is not what you want at all. You don't want any exceptions to the output of the hash function.

Imagine a crypto currency that requires the first $x$ number of bits to be set to zero for a crypto coin to be mined. You could just input the empty string to be rich beyond belief.

The only thing worse from having an empty string result in $n$ zero valued bytes is to have $n$ zero valued bytes return $n$ zero values bytes. Because in that case $H(0^n)$ would equal $0^n$ but $H(H(0^n))$ would as well, to infinity and beyond.

This would be called a cycle of 1 length; hash functions should never enter a cycle (in practice) when hashing the output of previous hashes. Of course, the hash function would not be considered secure anymore: $H(x) = x$ is called a pre-image and secure hash functions should be secure against pre-image attacks.


Is AES-GCM with static key and dynamic salt safe to reuse IV/nonce

In your description, AES/GCM is always used with a new, fresh key, different from all previous keys. Thus, you are not reusing IV with the same key. In that sense, this should be fine from a security point of view.

However, this seems overly complex and begs the question of: why? The simple way would be to use the static key "as is" and to use a random IV for each message.

GCM is actually defined for all IV sizes up to $2^{64}-1$ bits. When using as IV a controlled monotonic counter such as a message sequence number, a 12-byte IV is recommended, as it guarantees non-reuse. However, when using a random IV, the probability of IV reuse is actually lowest if you use a bit larger IV os 16 bytes or more. When the IV is not exactly 12 bytes in length, the GCM specification mandates a first pass of hashing with its internal, keyed, soft-of-hash function (called GHASH). As an added bonus, internal IV reuse, which would be made quite improbable thanks to the whole 128-bit space, would furthermore be "hidden" from onlookers because GHASH is keyed. Not all implementations of GCM support IV sizes of more than 12 bytes, but then, why would you use poor implementations?

To sum up, while what you suggest does not seem obviously flawed, a simpler and more standard solution exist: just use your key as is, and a random IV. Preferably, boost the IV size to 16 bytes.


Suitable Symmetric Algorithm for Encryption

Is there any particular reason to use a key length of just 40 bits? Because it is vulnerable to brute-force attacks. To have a reasonable strength, the minimum reasonable key length nowadays is 128 bit (source).

If you don't care about this stuff, you may use one of the following: DES-40, RC2, RC5, Blowfish. These ciphers support a key length of 40 bits, as you require. Anyway, any of these ciphers always has block size different from 5 bytes, which you are probably interested into. I'm not aware of any cipher with a block size of 5-byte/40-bit.
The alternative would be to use a stream cipher that supports a key length of 40 bits, such as RC4 (you can find many more here).


Non-Interactive Zero-Knowledge-Proof for discret Logarithm?

It seems, what you are looking for is a Non-Interactive Zero Knowledge Proof of Knowledge (NIZKPok) of a discrete logarithm.

The Schnorr identification scheme is an (interactive) ZKPoK and can be transformed in to a non interactive one (in the random oracle model) using the Fiat-Shamir transformation.

It works in any group, is perfectly sound and computationally zero knowledge under the discrete logarithm assumption for that group in the random oracle model.

http://publikationen.stub.uni-frankfurt.de/files/4280/schnorr.pdf

http://en.wikipedia.org/wiki/Schnorr_signature


What key is used to encrypt the certificate and certificate verify message in TLS1.3?

Due to the design of TLS 1.3 and different to earlier TLS versions the normal (EC)DHE key exchange is already finished once the server sends the certificate. They key server_handshake_traffic_secret used to encrypt the certificate and other handshake messages is based on the same key material as the keys which are used for the application data later. For the exact details on which separate keys exist and how they are derived from the common key material see RFC 8446 section 7.1 Key Schedule.


Zero-knowledge proof system which is not proof of knowledge?

There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of.


Number of keys for a monoalphabetic cipher

Your teacher is right, and here's why:

What happens if you encrypt A with G and B with G? You can't decipher it, because you have no idea if the G in the ciphertext was an A or a B.

So…

For the plaintext letter A you can use the ciphertext letter A, B, C, … , X, Y, or Z. ($26$ possible letters.)
For B you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A. ($25$ possible letters.)
For C you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A or B. ($24$ possible letters.)
...
For Z you can only use the remaining letter. ($1$ possible letter.)

The whole number of possible keys is $26\times25\times24\times [...] \times2\times1 = 26!$ (The exclamation mark denotes the factorial of a number.)


Is AES-CTR-NoPadding resistant to variable-length chosen-plaintext attack?

Your fundamental misunderstanding is that encryption does NOT provide security for plaintexts of different lengths. This is explicit in the definition, where indistinguishability only holds as long as the challenge plaintexts (of which one is encrypted) are of the same length.

In practice, in cases where length reveals information, one needs to pad.


Making a one-way function harder to reverse

(2) and (3) are expected to cost slightly more to invert than (1), no matter what the distribution on $x$ might be, because the only known preimage search algorithms treat them as black boxes to be evaluated forward and search more or less by guessing and checking (optimized with rainbow tables or quantum computers).

The expected cost of any such algorithm is the cost of evaluating the function, times the expected number of times you must evaluate it.  The cost of evaluating (2) and (3) is the same, but they both cost about twice what (1) costs.  You can make things much costlier by using a modern password hash such as scrypt or argon2.

However, if the only possible values of $x$ are the strings red and blue with equal probability, then the difference in cost is negligible.  The adversary has a 50-50 chance of getting it right in one try.

So a much more important question is: How are you using this in your application?  How does it fit into the protocol?  What security properties do you hope to achieve by it?  What costs do you hope to impose on an adversary trying to break the system?

If the distribution on $x$ has >=128 bits of entropy, or if there are actually two inputs of which one is a secret with >=128-bit entropy and the other maybe has low entropy, there's no reason to try to raise the costs of evaluating the function by iterating SHA-256 or using scrypt or argon2.  On the other hand, if you're storing password hashes, then you should absolutely use something designed for password hashes that raises the area*time cost and thwarts attackers with high levels of parallelism.


Protecting my message without encryption

I think this is a question that comes down to understanding the basic Alice, Bob and Eve diagram from cryptography textbooks, like this one from Wikimedia that I've chosen because of its license and no other reason:

Alice and Bob are communicating over a channel, depicted as the green line, and Eve is eavesdropping on that channel, metaphorically depicted as if there was a blue cable that plugs into the channel and carries its signal to Eve.  The reason Alice and Bob use encryption is because they're worried that the diagrammed situation might occur, and the goal of encryption is to make it so that, in that situation, Eve cannot learn much about their communication.

So it's hard to answer your question how to protect your messages without encryption other than by saying this: prevent any situation like the one described by that diagram from ever arising.  But that's not a concrete or actionable recommendation—it depends on the physical details of whatever scenario you're considering.  But to give one concrete example, the United States government uses something called a Sensitive Compartmented Information Facility (SCIF) to physically protect officials using sensitive information from being eavesdropped on.  Example passage from the article:

  Because SCIFs are supposed to distance sensitive information from the
  rest of the world, the Directive begins with architectural
  details—like adding a vestibule and extra interstitial reception
  spaces as "padding" between the SCIF and the outside. If the SCIF is a
  building (rather than a tent), it has to be reinforced concrete or
  lined with solid steel. Everything from the depth of the drywall to
  the thickness of the insulation is mandated by the document, too.

  The first—and most traditional—surveillance threat is sound, so SCIFs
  are lined with thick acoustic piling. In most cases, noise-masking
  devices like transducers are installed to garble what's going on
  inside, too. According to the BBC, another type of wave-emitting
  device creates a ring of electronic signals around the space, blocking
  other types of electronic surveillance, while a lining of special,
  foil-like material also blocks more traditional audio surveillance
  (similar to an average Faraday Cage).

That's an extreme example, of course, but (a) without details it's basically impossible to make concrete recommendations and (b) specific recommendations would likely be off-topic here.


How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box?

Before we start with vectorial Boolean functions, let's recall the definition of the nonlinearity of a Boolean function:

$$\mathcal{NL}(f) = \min_{a \in \mathbb{F}_2^n} d_H(f, \ell_a \oplus b),$$

where $\ell_a \oplus b$ represents the affine Boolean function defined by the bitvector $a$: $\ell_a(x) = a \cdot x$ ($\cdot$ is the dot product).
The above equation pretty much defines the nonlinearity of a Boolean function as the minimum Hamming distance $d_H$ to some affine function.

This distance $d_H$ can be expressed using the Walsh-Spectrum of $f$.
That is, $d_H(f, \ell_a) = 2^{n - 1} - \frac{1}{2}\mathcal{W}_f(a)$.
To see why this is true, the definition of the Walsh transform should help:
$$\mathcal{W}_f(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) \oplus \ell_a(x)}.$$
(and note that $(-1)^{g(x)} = 1 - 2g(x)$, $\sum_x g(x) = w_H(x))$)

Minimizing the distance hence corresponds to maximizing the Walsh-Spectrum:
$$\mathcal{NL}(f) = 2^{n - 1} - \frac{1}{2} \max_{a \in \mathbb{F}_2^n} \left|\mathcal{W_f(a)}\right|.$$

Why the absolute value? Remember that we're measuring the distance to affine functions and note that $d_H(f, \ell_a \oplus 1) = 2^{n - 1} + \frac{1}{2}\mathcal{W}_f(a)$.

Why is this useful? Well, it turns out there is a rather efficient algorithm to compute the Walsh-Spectrum of some Boolean function. See for example here.

Now that we can compute the nonlinearity of a Boolean function, it's easy to define that of a vectorial Boolean function $F$:

$$\mathcal{NL}(F) = \min_{a \in \mathbb{F}_2^n} \mathcal{NL}(F \cdot a).$$

In other words, the nonlinearity is the minimum of the nonlinearities of the Boolean functions which are linear combinations of the coordinates (outputs) of $F$.

Given what we know about the nonlinearity of Boolean functions, we can compute this as

$$\mathcal{NL}(F) =  2^{n - 1} - \frac{1}{2} \max_{a \in \mathbb{F}_2^n, b \in \mathbb{F}_2^m} \left|\mathcal{W}_{F\cdot b}(a)\right|.$$

Sometimes the expression in the absolute value is called the Walsh transform of $F$:
$$\mathcal{W}_F(a, b) = \mathcal{W}_{F\cdot b}(a)$$

To compute this, you can use the fast Walsh-Hadamard transform (FWHT) algorithm again.
Note also this corresponds directly to the LAT (depending on conventions, the term $2^{n - 1}$ is added or not).


Can cryptography be used to hide routing information from the router?

The solution is called onion routing; the gist of it is that there are a number of anonymising servers; when Alice wants to send a message to Bob, she picks a random route through a number of the servers; she then repeatedly encrypts the message for each hop, and sends the encrypted message (which states only the first hop in the clear) to the first server.

The first server then decrypts the message, which reveals the second hop.  It then sends the message to the second hop (batching it with a number of other messages, so someone cannot correlate incoming and outgoing messages).

The second server, again, decrypts the message, which reveals the third hop; and then batch-forwards it to the third hop.

This continues until we get to the last server, which decrypts the message, which reveals the actual destination (Bob) it then batch-forwards it to B0b.

Bob then decrypts the message, this reveals the message that Alice originally sent.

There are a number of subtle points; these points are well studied in the literature.

Now, because of all the above 'batch-forwarding', this doesn't work for real-time communication; for messages that don't mind some unpredictable delay, it's workable.


This is the pre-image attack on hash functions, i.e.

pre-image attack : given a hash value $y$ find a pre-image $x$ such that $y=h(x)$.

Good designed cryptographic hash functions have $\mathcal{O}(2^{n})$ classical pre-image resistance for $n$-bit output. The classical attack tries all possible input space to find a $x$ that hashes the target hash value. Due to the birthday paradox, we don't expect that all values exist in $2^n$ bit space. Some will occur more than one. This will not change the complexity.

Assuming that you are using base64 encoding to store the values, then each position in the string hash 64 possible character (= is used for padding).

Concentrate on a target user_id, an attacker will search 50 character keyspace to match. $$ \text{hash} \stackrel{?}{=}\operatorname{SHA512}(\text{user_id}, \operatorname{SHA512}(key_i)$$ This will make $64^{50} = 2^{6\cdot 50} = 2^{300}$ This is a huge number to deal with any available computing power. If you are using another encoding, you can adjust the values.

Hash functions are designed to run fast. This will also make an attack time fast if there is any. You can make it slow by making iterations or you can use already existing solutions like HKDF, PBKDF2, etc. They have iterations to increase the attack time.

Your scheme seems fine up besides there are some considerations;

There is already HMAC (Hash Based Message Authentication Code or keyed-hash message authentication code). It's security proven by Bellare, Mihir (June 2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance under the assumption that the compression function is PRF.

You can use HMAC with SHA512, too. If the size does not really an issue, you the full output of the HMAC-SHA512, (or your scheme)


Which encryption technique should be adopted to keep the search functionalities?

There are two possibilities related to your "search" (partial or exact) and you do not specify which you're using.
Let us imagine the plaintext is ATTACK AT DAWN. Let us suppose that the encryption translates this to QWWQTHXQWXBQNO: each letter is encoded as a different letter regardless of its position (so, A is always encrypted as Q and so on). However obtained, this is a Caesar cipher and is weak. But it allows you to simply search for DAWN because it will always be BQNO.
A different cipher scheme (for example the Vernam cipher) would encode each letter as a different letter depending on its position. So to be sure to find DAWN inside a 1000-character string, you would need to look for 997 different strings - DAWN encoded starting at 0, 1, 2,... 996. This is more secure, and even completely secure if you encode one string. If you encode lots of different records, then this devolves into a Vigenère cipher, which can be attacked. The more the records, the easier the attack.
AES would encode each letter into a different letter depending on its position and what the other letters are. This makes it impossible to look for DAWN because you would need to look for a jillion possible sequences (the encrypted version of DAWN in ATTACK AT DAWN would be be different from the DAWN of RETIRE AT DAWN, even if the word starts at the tenth position in each case).
So, use of a strong cipher means you cannot do partial matches but only full matches.
You can very slightly ameliorate this situation by encoding different, shorter chunks and only looking for matches wider than twice a single chunk. With chunks of 2 characters [only an example, AES won't (efficiently) do that], AW will always be encoded as, say, QR. If you look for DAWN, the plaintext string, once divided in 2-char chunks, will either contain ?D AW N? or DA WN. So you look for DA, AW and WN; if you find the encrypted form of AW, either you retrieve the record, decrypt, and do a plaintext search for confirmation, or you need to also look for additional 625 combinations (from AD AW NA to ZD AW NZ). With bytes, that's actually 65025 combinations. And that's with 2-byte chunks; with N byte chunks you'll need (N-1)^2 combinations, which quickly becomes prohibitive.
And, of course, using short chunks over many records weakens the encryption. In general, the ability of using (arbitrarily small) matches leaks information.
different approach #1
You can perhaps filter the records, without breaking the encryption, and restrict the returned records to a reasonable number. Then, have them transmitted in the encrypted form, and decrypted on the client, and searched again for the string. This allows you zero-trusting the server; the plaintext never exists in the server in any form. You could use a stronger encryption on the records, since you're not going to seach the encrypted returned records and you have to decrypt them all anyway.
different approach #2
With some databases (e.g. MySQL), you can have memory storage transient tablespace, or RAM disks, where the information can be stored in plaintext form.
You can decrypt all the information upon user login and store it in a RAM disk or tablespace, thereby rendering it searchable.
When the system is powered off or brought to rest, that information is lost, unless specific physical attacks are carried out (so-called "cold boot" or "cryo" attacks, involving the rapid refrigeration of RAM chips to preserve their content).
This leaves you vulnerable to the host system being subverted, but if the client's code is sent by the host system (as it usually happens in Web applications), a host subversion will be enough to break the encryption by simply accessing the user's credentials on the client side.
You do have, therefore, to (limitedly) "trust" the server, albeit not at rest.
If the server is just data storage, and the client code is not hosted there, then you can't go this way without implicitly adding trust in the server security.


What security guarantees do blockchains provide for data storage?

What security guarantees does it give? Things like availability (to which entity, under what condition and delay, with selection according to what criteria/tag), proof of origin (for one who finds that data), non-repudiation.

In respect of data storage the blockchain itself (in a decentralised form) gives us very few guarantees.  When it is coupled with a cryptocurrency (eg. Ehtereum) then it isn't the blockchain that provides security primarily, but the cryptocurrency via the blockchain. In such cases it is the miners of the cryptocurrency that have a vested interest to keep your data.  And it costs money.
The blockchain is useful as a means to deliver something worthwhile.  Much like torrents if there is no one seeding, then it isn't a useful means of delivery.


Breaking a Mersenne-twister RNG with unsequential outputs

If you can identify which outputs are revealed and which are thrown off (ex. every other output is thrown off), you may be able to successfully analyze the twister so that you can predict future outputs.
However, the bigger problem here is that you are limiting outputs to the range [0,12]. With a 32 or 64 bit word length, a set of numbers in that range will not reveal nearly enough information about the state (even if none were discarded and all outputs were revealed to you).


As I have a new hash every 3 second, it's easy for everyone to collect a big numbers of hash.  And as the difference between every UUID is always 3000 ms, maybe this could make it easier for the hacker to crack the key.

You might be reassured to read up on the security requirements that MACs are designed for.  Chapter 9 of the Handbook of Applied Cryptography is a good, freely available source.  (Section 9.2.2 is the most relevant.)

But to make this short, good MACs are expected to resist adaptive chosen text attacks, where the attacker doesn't just see the tags, they get to:

Choose messages of their own liking;
Cause you to compute these messages' tags;
Pick messages based on what they learn from earlier ones.

A MAC is considered broken if an attacker in that scenario can learn enough to successfully forge tags for other messages than the ones they caused you to authenticate.  That's a scenario much, much more adverse than the one you describe, where they only passively see tags (and no messages).

So as long as you can keep the key secret, you probably have much bigger security concerns than this.


RSA: select $e$ given $n$ and $\varphi(n)$

There are four different solutions, of which three have been identified as the "trivial solutions" in the comments to this question.

$e=d=1$ which is obviously fullfilling the condition that $1\cdot 1\equiv 1 \pmod{\varphi(n)}$ should hold.
$e=d=\varphi(n)-1$ which is fullfilling the condition that $(\varphi(n)-1)^2\equiv 1 \pmod{\varphi(n)}$ as $(\varphi(n)-1)^2=((\varphi(n))^2-2\varphi(n)+1) \bmod{\varphi(n)}=1$
$e=d=\sqrt{\varphi(n)+1}$ (if integer) which is also obviosuly true as $\sqrt{\varphi(n)+1}^2=(\varphi(n)+1)\bmod{\varphi(n)}=1$, this is the solution you stumbled across.
Use a full modular square root finding algorithm as documented as algorithm 3.44 in the Handbook of Applied Cryptography on page 102. (PDF version) However this requires you to know the prime factorization of $\varphi(n)$ which may be infeasible to obtain for sufficiently large $n$.


usefulness of a collision attack that's not also a 2nd pre-image attack

What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$?

One example is when $m$ and $m'$ are or contain randomly selected material.  If they're using cryptography correctly, the honest parties generally choose keys, random IVs or similar material randomly, and thus have no control over what their values are either.  This affords many opportunities for attacks that require finding some collision but don't care about what the colliding values are.

One example is secure coin tossing.  If Alice is calling the toss and Bob is throwing it, they execute this protocol:

Alice secretly picks her call (Heads or Tails) for the toss, and a sufficiently large random salt;
Alice computes commitment = hash(salt || call);
Alice sends commitment to Bob.
Bob tosses a coin, gets outcome;
Bob sends outcome to Alice;
Alice sends call and salt to Bob;
Bob verifies that commitment = hash(salt || call).  If it checks out, Bob knows Alice didn't cheat.
If outcome = call then Alice won the coin toss, otherwise she lost.

If Alice can find any pair of salts such that hash(salt1 || Heads) = hash(salt2 || Tails), then she can break the protocol.  It doesn't matter what the values of salt1 and salt2 are as long as they lead to a collision in this context.
 So collision resistance implies Alice can't cheat this protocol.

To address Ross Snider's answer you linked from another SE site.  I'll boldface one really important bit:

    Bob can use a collision attack to his advantage in many ways. Here is one of the simpliest: Bob finds a collision between two binaries $b$ and $b′$ ($H(b)=H(b′)$) such that $b$ is a valid Microsoft Windows security patch and $b′$ is malware. (Bob works for Windows). Bob sends his security patch up the chain of command, where behind a vault they sign the code and ship the binary to Windows users around the world to fix a flaw. Bob can now contact and infect all Windows computers around the world with $b′$ and the signature that Microsoft computed for $b$.

  But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.

It is a collision attack indeed, not a second preimage attack, and it hinges on these points:

"Bob works for Windows."  This may be a parenthetical in the quote, but it is a critical assumption.  The scenario assumes (perhaps less than explicitly) that Bob is the author of both the legitimate patch and the malware, and gets to craft them together as a colliding pair.  That's the assumption that you're missing; if instead Bob was trying to construct a malware patch that matched a legitimate one that somebody else constructed, then you would be right and it would indeed be a second preimage attack.
Executable file formats allow for arbitrary data to be embedded into a file without affecting the program's runtime behavior.  This means that Bob gets a lot of latitude to embed random data into both the legitimate patch and the malware.

Those two factors taken together are what allows Bob the opportunity to try a much cheaper collision attack instead of a second preimage attack.


Wikipedia shows you how to create a rainbow table.

The information you are looking for is under "Precomputed hash chains"

The reduction function tries to create a new input, the non hashed part which is the password in rainbow tables, from a hash.  We want to choose a reduction function that will try to equally reduce the hash into new inputs such that it tries not to create the same input so many times.

Consider the following example.  We want to create a rainbow table for all 5 character number combinations for the md5 function.

Lets start out with 12345 as the input. The md5 hash is 827ccb0eea8a706c4c34a16891f84e7b.  The reduction function can be as simple as taking the first 5 numbers and using that as the next input.  This method will produce reasonably distributed new inputs.

So the hash

"827 ccb 0 eea 8 a706c4c4a16891f84e7b" would create "82708"

The next hash would be 71b8e22700e63c2a0c1bad6506549d3b then would be reduced to 71822 accordingly.

So our current chain will consist of:

12345 -> 827ccb0eea8a706c4c34a16891f84e7b ->

82708 -> 71b8e22700e63c2a0c1bad6506549d3b ->

71822

The chain can go as long as you want, until it his a previous input, after which it enters a cycle - i.e.  when it hits that point, it will just repeat itself and it will be useless.

Having a longer chain is going to reduce the space need to store these values but increase the time it needs to recalculate the entire chain.

All that would need to be stored would be the starting and ending point of the chain.

Given a hash, you use your same reduction function on it to get an input and repeats itself until that matches the end of a chain.

If it matches the end of a chain, you can just recalculate those values to determine which input it was.

NOTE: You want to make sure that you have every value from 00000 to 99999 in these chains, otherwise it will be incomplete.

If you need characters a to z instead of 0 - 9, you could just convert the hash to base 26.


How long does a good AES encryption take?

From this answer Different ways/algorithms for implementing AES you can see that AES is already pretty fast. By using the hardware instruction you can even get down to $\sim1.3$ cycles/byte[1].

$1 GB = 2^{30} B \approx 10^9 B$

Your CPU is working at $2.2$ GHz, in other word $2.2 \times 10^9$ cycles per second. To encrypt $1 GB$ you need $1.3 \times 2^{30}$ cycles. In other word, it would take $\frac{1.3 \times 2^{30}}{2.2 \times 10^9} = 0.634$ seconds. So clearly AES is super fast.

read more:

[1] Breakthrough AES Performance with Intel® AES New Instructions


There is a minimal number of rounds for theoretical security. 4 rounds are required to construct a strong pseudo random permutation (PRP) from a pseudo-random function (PRF).

In practice, cryptographers don't tend to design ciphers with a heavy PRF for the f-function but instead apply more rounds with a weaker f-function to get the requisite strength.

For this reason, there is no typical or default choice for the number of rounds in a Fiestel cipher. The optimal choice depends entirely on the internal security properties of the key schedule and F-function for the specific cipher in question.


Is linear secret sharing over the addittive group of integers modulo $p$ with $p$ non-prime secure?

What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer.

In short, a domain is the input space. As said the input space can be any domain. Note that the secret $s$ is from the domain, too.
The note simply says that whatever the domain $\mathscr{D}$ is we can simply impose an addition operation on it. Order them, and number them starting from 0. Now, if the number of elements in the domain is $n = |\mathscr{D}|$ then it is equal to $\mathbb{Z}_n$ which is a cyclic group under addition.

Is using as domain $\mathbb{Z}_p$ (additive group of integers modulo $p$) with $p$ non-prime secure?

Yes.

Does it make any difference if $p$ is prime or not?

It doesn't make any difference. This secret-sharing doesn't need the multiplicative inverses. Any finite group can be safe. All we need is the group operations.

As Kodlu mentioned in the comments

This secret scheme can also be defined on the multiplicative groups where the inverse exists naturally. Take each $s_i$ for $1\leq i\leq k-1$ random from the domain and calculate $$s_k = s \cdot s_1^{-1} \cdot s_2^{-1} \cdots s_{k-1}^{-1}$$


how hashing algorithm is shared in public key

First: This picture is wrong.  Signature is not encryption with the private key.  Encryption with the private key is a category error; it doesn't make sense.  This suggests to me that whatever source you are reading is likely to be full of confusing misinformation.

That said: The signer and verifier have to agree in advance what signature scheme to use, which entails a choice of hash function.

In brain-damaged protocols, the signature or metadata around it specifies which signature scheme to use (including the choice of hash function), and the verifier will happily use it.  This means that a forger can pick any weak signature scheme that the verifier supports—including completely nonsensical ones, like none, or the secret-key HMAC-SHA256 when the signer meant to use the public-key RSASSA-PSS—and persuade the verifier to use it, against the wishes of the signer.

In your system, in order to avoid leaving a trail of devastation and screaming cryptographers in your wake like JWT did, you should have the verifier store alongside the public key (not the potentially forged document!) whatever metadata you need to specify a particular signature scheme for that public key.  For example, in x.509 certificates, alongside the public key there is a field specifying what cryptosystem the public key is meant for.  Then there is no need for the signature to control which signature scheme the verifier uses: the verifier already knows for each public key which one to use.

As a simplification, you can just use a single signature scheme in your application, Ed25519, and never reuse keys in your application for any other purpose.  Then there's no need for any metadata.  If you ever need to replace the signature scheme, just replace the keys too.


Available programs that can verify the working of a simple substitution cipher

Regarding the test of unicity

You could just script the test in Python (or any other language, really). The language in which you already implemented your cipher might be a good choice otherwise.

Then, given the size you are talking about (256 possibilities of 16bits = 4Ko), you can basically just generate all the results in a 256-array, and check the unicity of each element in your array.

Regarding your cipher

I've got a pretty hard time figuring the security level of your application. With a basic substitution over basically each character (8bit), your ciphertext is extremely vulnerable even with not-so-long messages, and especially if your data/protocol/application has any kind of predictable headers and such. It's not clear which kind of threat you want to protect the data from.


When does a feedback shift register count as non-linear?

Yes, you're right.

XOR is considered a linear function in this case. So the feedback into the registers is linear.  A non linear feedback shift register is a more generalised example where the feedback function can be anything. You can also call them generalised linear feedback shift registers GLFSR).
S-boxes, AND operations, permutations, and so forth are all good.  So the re-entrant bit is more than just a simple XOR operation of register bits. This frees you from the rigidity of Galois, Fibonacci and other predefined taps.  But then you'd have to make sure that lockup doesn't occur and the registers do not settle into some sort of funky stable pattern.

A picture showing a not so complex non linear feedback function f, but it could be anything as you suggest:-

This immediately brings up the interesting possibility of a secure hash function being f.  Or would that just be too much..?


Initialize the eight working variables SHA256

The variables a, b, c, d, e, f, g, h are assigned on each round of the compression function main loop, but the interim hash values are considered only per message chunk (i.e. after all rounds have completed)

I found the Wikipedia pseudo-code easier to understand than the description in your question, and it is clear there how the variables relate to interim hash values. Note where your reference relates previous hash components $H_0^{(i)}=a+H_0^{(i-1)}$ the pseudocode just assigns h0 = a + h0, because there is no need to keep previous hash values, just a current one which is updated after processing each chunk.

Just before calculating the rounds for the each chunk, both the current H array and a, b, c, d, e, f, g, h hold the same data. This changes during calculation of the rounds, and you need to keep the value of H so it can be added back in at the end of the chunk.

When starting the first message chunk, before any processing rounds, H and a, b, c, d, e, f, g, h hold the "initial values of H" (based on square roots of first 8 primes). You do not use those initial values again.


Best method to achieve authenticated encryption with openssl

If as you say you

  have the ability to give the receiver a key by a trusted channel.

then there is no need to involve any public key cryptography here. Just generate a symmetric key and send that key to your friend over the trusted channel.

Later, once you are ready to send the file, simply encrypt the file using an authenticated encryption mode and send the encrypted file to your friend. They can then use they key to verify the ciphertext's authenticity and decrypt.

You're saying that you specifically want to know how to do that with the OpenSSL commandline tools. This is a bit off-topic here, but nevertheless here we go.

Disclaimer: Do not use anything I write below in any actual application, I make no claim whatsoever that the use of openssl described below is actually secure in practice.

Note, I'll be using bash syntax in the following, I have no idea if it works in other shells.

First thing we need to do is generate keys. We'll be using AES-128, so we will generate 16 random bytes and store them in a key file. (encoded as hex to make our life easier later on.)

openssl rand -hex 16 > enc.key

we will also generate a separate MAC key, I will explain why in a minute:

openssl rand -hex 16 > mac.key

These two files you will give to your friend.

The first idea -- since we want an authenticated encryption mode -- would be to use something like AES-GCM, sadly however, the commandline tool openssl enc will then tell us that

  AEAD ciphers not supported by the enc utility

Bummer! And the authors are unwilling to change that.
So we will have to do the authentication the hard way. For example with AES-CTR + HMAC. This is why we created a separate MAC key before.

And because the authors of OpenSSL really want you to shoot yourself in the foot: If you actually specify a key, then the openssl enc utility will not create an IV for us, so we will have to do that ourselves as well.
So let's get going. We generate an initialization vector

openssl rand -hex 16 > file.iv

and then encrypt our file file.txt using AES-CTR using the generated IV and the key we previously exchanged.

openssl enc -aes-128-ctr -in file.txt -out file.aes -K $(cat enc.key) -iv $(cat file.iv)

compute the HMAC over both the IV and the ciphertext

cat file.iv file.aes | openssl dgst -mac HMAC -macopt hexkey:$(cat mac.key) -out file.mac

and now you can send file.iv,file.aes,file.mac to your friend.

Then again, because the OpenSSL authors really, really want you to shoot yourself in the foot, the openssl dgst utility naturally does not support verification. Instead your friend will have to do verification by hand:

if [ "$(cat file.iv file.aes | openssl dgst -mac HMAC -macopt hexkey:$(cat mac.key))" == "$(cat file.mac)" ]; then
    echo "MAC verification succesful."
    openssl enc -d -aes-128-ctr -in file.aes -out file.txt -K $(cat enc.key) -iv $(cat file.iv);
else
    echo "MAC verification failed."
fi

And if everything went well they should now have the plaintext back.

By now I hope every reader has realized that there's way too much that could go wrong in all of this and has decided not to do encrypted file-transfer by hand.


Generate hash value using public key along with message

Actually, the notation of the authors is not complete. They simply do not define what it means to hash several values at once. However, what one would do in practice is appending everything. So $H_i$ would be
$$H_i = \mathcal{H}(m\|Y_1\|Y_2\|\ldots\|Y_i)$$

where $\|$ denotes string concatenation.


Taking advantage of one-time pad key reuse?

There is a great graphical representation (which I found on cryptosmith, but they keep changing their url structures, so I've added the graphics in here) of the possible problems that arise from reusing a one-time pad.

Let's say you have the image

and you encrypt it by using the binary one-time-pad (xor-ing on black and white)

.

You get the following extremely secure encryption

.

If you then encrypt a smiley face with the same one-time-pad,

you get another secure encryption

.

But if you have both and you xor them together

then you get the image

which, as you can qualitatively and intuitively see is very insecure.

Reusing the same key multiple times is called giving the encryption 'depth' - and it is intuitive that the more depth given, the more likely it is that information about the plaintext is contained within the encrypted text.

The process of 'peeling away' layered texts has been studied, as ir01 mentions, and those methods improve with more layers.


Why can’t the public key exponent in RSA be negative?

Why can the public key exponent not be negative?

Technically, it can be.  There's just no point to using such negative exponents in general, since for every valid negative RSA exponent, there is an equivalent positive one that is easier to calculate with.

Specifically, for any exponent $e$, message $m$ and modulus $n = pq$, changing $e$ by any integer multiple of $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$ does not affect the ciphertext $c = m^e \bmod n$.
This is because $\lambda(n)$ is the exponent of the multiplicative group of integers modulo $n$, and therefore $m^{\lambda(n)} \equiv 1 \pmod n$ for all $m$ coprime to $n$.  Thus, $$m^{e+\lambda(n)} = m^e \cdot m^{\lambda(n)} \equiv m^e \cdot 1 = m^e \pmod n.$$

(If $m$ happens to share a factor with $n$, then $m^{\lambda(n)} \not\equiv 1 \pmod n$.  However, since RSA moduli are squarefree, it is true that $m^{\lambda(n)+1} \equiv m \pmod n$ for all $m$, and so the conclusion $m^{e+\lambda(n)} \equiv m^e \pmod n$ still holds.  In any case, as noted below, having $m$ share a factor with $n$ is incredibly unlikely for RSA moduli of practical size.)

  Let's say we have a message $m = 10, e = -3, N = 55$ then encrypting the cipher text would be: $m^{-3} = \frac 1 {1000} \mod 55$. Can we only use integers when writing in terms of a modulus?

Yes, we only use integers in modular arithmetic.

But that turns out not to be much of a loss, since we can still calculate modular inverses, i.e. solutions $x$ to the equation $x \cdot m \equiv 1 \pmod n$.  For example, for $m = 8$ and $n = 55$, we have $7 \cdot 8 = 56 \equiv 1 \pmod{55}$, so $7$ is the inverse of $8$ modulo $55$.  Finding such modular inverses can be efficiently done using the extended Euclidean algorithm.

Alas, this doesn't quite work for all numbers.  For example, $10$ has no inverse modulo $55$, since $10$ and $55$ are not coprime; they both share the factor $5$.  But for real-world RSA moduli, which are products of two very large primes, it's extremely unlikely that you'll ever randomly stumble across another number that shares a factor with the modulus.  (And if you do, you've just factored the modulus by pure luck!)

Thus, if we really wanted to use RSA with negative exponents $e < 0$, we could just assume that any messages will almost surely be invertible modulo $n$, and calculate $$m^e = m^{-1 \cdot -e} \equiv (m^{-1})^{-e} \pmod n,$$ where $m^{-1}$ denotes the inverse of $m$ modulo $n$.  As long as $e$ is otherwise a valid RSA exponent (i.e. coprime to $\lambda(n)$, and not equivalent to $1$ modulo $\lambda(n)$), the math would work out just fine.

But there's still no point in using such negative exponents, since we can always convert any negative (or over-large) exponents into equivalent positive ones in the range $2 < e < \lambda(n)$ just by adding a suitable integer multiple of $\lambda(n)$ to them.  This does require knowing $\lambda(n)$, which implies knowledge of the factors of $n$, and thus of the private key.  But the code that generates the key will know that anyway, and can thus ensure that the exponents lie in the proper range.

In particular, while it would be mathematically possible to work with negative RSA exponents, I'm not aware of any practical RSA implementations that would include the extra complexity needed to support them.

  Also, why can't the public key exponent be greater than $\phi(N)$?

Technically, it can be, but again, there's no point in using exponents larger than $\lambda(n) < \phi(n)$, since using an over-large exponent would just waste CPU time for no good reason, compared to using an equivalent smaller exponent.

In particular, some RSA key generation standards require the exponents to be positive and less than $\lambda(n)$, and most RSA implementations will only accept positive exponents (and may require them to be less than $n$).  See this related question for more information.


How does the birthday attack work in AUTH and UF-CMA games?

There is no generic attack that works against all PRFs (for exactly the reasons you mentioned -- if the PRF is secure beyond the birthday bound, there's no attack).

There is an attack on many of the specific PRF schemes that are used in practice, precisely because those specific ones are not secure beyond the birthday bound.  These attacks involve taking advantage of specific details of the design of that particular PRF (e.g., finding internal collisions).


Can Bob prove that Alice have a key which encrypts C into A?

You do not really specify what your encryption scheme is. "AES" is a block-cipher, that requires a secure mode of operation to be turned into an actual secure encryption scheme.

But I will assume in the following that you are referring to some encryption scheme based on AES that is at least considered CPA secure. (e.g. AES-CBC or AES-CTR). In that case:

No, being able to do so would break CPA security of the encryption scheme.

To see why, consider the following. We have a symmetric encryption scheme $(\mathsf{Enc},\mathsf{Dec})$. Now assume towards contradiction that there exists some efficient algorithm $\mathcal{P}$ that Bob could use to convince himself that $(c,m)$ is a pair of ciphertext and plaintext such that $m = \mathsf{Dec}(k,c)$ with an unknown but fixed key $k$. I.e., let's say it holds that $$\Pr[\mathcal{P}(m,c) = 1\vert m = \mathsf{Dec}(k,c)] \ge 2/3$$
$$\Pr[\mathcal{P}(m',c) = 1\vert m' \neq \mathsf{Dec}(k,c)] \le 1/3$$

Then this algorithm trivially allows us to break CPA security. The attacker $\mathcal{A}(1^n)$ outputs two random messages $m_0,m_1$ and receives the challenge ciphertext $c^*$. $\mathcal{A}$ then simply outputs $\mathcal{P}(m_1,c^*)$. If $c^*$ is an encryption of $m_0$ then  $\mathcal{A}$ outputs $0$ with probability at least $2/3$. Likewise if $c^*$ is an encryption of $m_1$ then  $\mathcal{A}$ outputs $1$ with probability at least $2/3$.
Therefore overall $\mathcal{A}$ can distinguish ciphertexts of $m_0$ and $m_1$ with probability $2/3$ and thus significantly better than random chance.

What is however possible is for Alice to prove to Bob that she knows a key $k$ such that $m = \mathsf{Dec}(k,c)$ without revealing $k$.


What is the connection between "replay attack" to CCA security?

These are different - protection against a replay attack could for example be done by recording that a message was already handled or by including a timestamp in the message and not processing the message if it is too old.

Note that for a replay attack the attacker doesn't get the plaintext, but does get access to at least 1 previously sent message. In CCA the attacker doesn't not have access to previously sent messages, and can request back the plaintext for chosen ciphertexts.


Compromise between HMAC and Digital Signature, by encrypting and sending secret key?

No, this will not work, for two fundamental reasons:

You cannot "encrypt with the private key and decrypt with the public key" in any meaningful sense.*  And if you could, it would be totally useless, because the public key is, by definition, public — if you could decrypt with the public key, so could anyone else.

In particular, in your scheme, anybody with access to a "signed" message could decrypt the MAC key (which they need to verify the message, anyway), use that key to forge other messages, and attach the same encrypted MAC key to them.
Even if you scheme worked, it would provide no performance improvement over conventional signature schemes.  Specifically, the standard way to sign messages of arbitrary length is to hash them with a cryptographic hash function, and then sign the hash value.  Thus, for long messages, the performance of conventional signatures is dominated by the time needed to compute the hash value, which is approximately the same as (and, in fact, strictly less than) the time needed to apply HMAC to the same message using the same hash.**

*) Yes, I'm aware that, for the RSA cryptosystem, signature generation and verification are very similar to encryption and decryption, except with the public and private exponents swapped.  This duality is peculiar to RSA, and does not extend to most other public-key cryptosystems.  And even for RSA, the duality breaks once you introduce message padding, which is needed to turn "textbook RSA" into an actual secure cryptosystem.

**) HMAC does place somewhat lower security requirements on the hash function than signatures do (in particular, it does not require the hash to be collision resistant), so you could potentially use a faster and less secure hash for HMAC.  That is, assuming your scheme worked in the first place, which it does not.  And, given that there exist plenty of modern hash functions that are both fast and secure, you'd still be trading a lot of precious security margin for, at best, a very modest gain in speed.


There seem to be some errors or inconsistencies in the question.

If $P \oplus P' = [0000\delta 000]$, and we use the 2-round structure shown in the picture, then the corresponding ciphertext pairs should satisfy $C \oplus C' = [xyzt\delta000]$.  This is different from what you wrote (did you omit the final swap shown in the picture above?).

If we let $C=(C_L,C_R)$ and $P=(P_L,P_R)$, etc., then one correct equation is:

$$F(C_R) \oplus F(C'_R) = [xyzt].$$
This follows because, if you look at the picture, the input to the $F$-box in the second (last) round is the same as the right half of the ciphertext.

Note that this is different from what you wrote.  (I cannot explain what you wrote; perhaps your notation does not match the picture you included, or something else.)

Edit: Now that you added a link to the paper where you got this from, I can explain what's going on.

First, at a high level: this is not the right first paper to learn differential cryptanalysis from.  You first need to understand the fundamental concepts of differential cryptanalysis before you will be prepared to understand that article.  That paper is a research paper written for expert cryptographers, who can be assumed to know those concepts.  It is not intended to be understandable to someone who does not already know advanced concepts of differential cryptanalysis.  Trying to explain the article to someone who does not understand those differential concepts is going to be ... challenging.

So, my primary recommendation is to go learn about differential cryptanalysis first, before trying to read that article.  There are good sources on this (you can search this site).  One of my favorites is Biham & Shamir's little book, Differential Cryptanalysis of the DES; it gives an excellent introduction to the topic.  But there are other sources as well.  Whatever source you read, make sure you understand the following concepts: differential characteristic, iterative characteristic, 1-R attack, 2-R attack, distinguishing attack, key-recovery attack.

Once you know those concepts, I can explain concisely what it is going on the particular paper you are referring to.  They are using a 2-R attack on Blowfish.  As a special peculiarity of Blowfish, after doing the last 2 rounds of Blowfish, you xor the output with two key values ($P_{10}$ and $P_{11}$ in this case).  That's not shown in your picture.  So, once you take that into account, the input to the last-round $F$-box will be $C_L \oplus P_{10}$, or $L \oplus P_{10}$ in the paper's notation.  Also since the two ciphertexts satisfy $C_L \oplus C'_L = [\delta000]$ (or in the paper's notation, $L \oplus L' = [\delta000]$.  Therefore, the input to the last-round $F$-box in the first encryption is $L \oplus P_{10}$, and the input to the last-round $F$-box in the second encryption is $L' \oplus P_{10} = L \oplus P_{10} \oplus [\delta000]$.  The equation shown in the paper then follows.

If that didn't make sense to you, I apologize, but you'll probably need to spend more time becoming expert at differential cryptanalysis before you'll be able to follow this paper.


Let formalize it

Round function $R:\{0,1\}^b \to \{0,1\}^y$ (This is bad naming, $F$ was better here as in DES)

Input to each round is $b+y$ bit register/array $I$.

Output of each round $O = (R(\texttt{MSB}(b,I)) \oplus \texttt{LSB}(y,I)) \mathbin\| \texttt{MSB}(b,I)$

Therefore $O$ is again $b+y$ bits register/array as an input to next round.

$\texttt{MSB}(b,I)$ the Most Significant $b$ Bits of register $I$.
$\texttt{LSB}(y,I)$ the Least Significant $y$ Bits of register $I$.

Example
Let $I=\texttt{[0,1,1,1,0,1,0,0,1,0,0,1,1,0,0,1]}$ be 16-bit register then

$\texttt{MSB}(3,I) = \texttt{[0,1,1]}$, and
$\texttt{LSB}(12,I) = \texttt{[1,0,1,0,0,1,0,0,1,1,0,0,1]}$

Note that here we used binary representation for $I$, not the array repsentation.


Link encryption isn't really a cryptographic concept, it's more a kind of networking protocol.

Link encryption protects the message only "on the wire" between routers. Looking at the OSI model, that would be on layer 2. And yes, it therefore is applied on all things regarding routing.

However, if you look at the Wikipedia article about link encryption, they list two advantages:

  encryption is automatic so there is less opportunity for human error.
  if the communications link operates continuously and carries an unvarying level of traffic, link encryption defeats traffic analysis.

And that's just nonsense.

Link encryption is useful in some scenarios, for example if you have to worry about wiretapping and you trust the routers. This does make sense, for example in a military communication network, or some other organization where routing stations are part of it. Additionally, you need some way to know or agree on cryptographic keys, and having a key exchange for every "layer 2"-package would be a performance nightmare.

However, if you don't trust the routers, then link encryption just adds extra effort for encryption and decryption and no benefit at all. If you consider something like man-in-the-middle attacks, then those attackers actually are usually routers (or can act as one). And in fact, you need to give routers the routing information (including adresses of senders and receivers) so that they can do their job.

So if you're thinking about Internet traffic, this doesn't make any sense, and it doesn't increase security. However, you could consider the wireless networking protocols (e.g. WPA2, UMTS, ...) as link encryption on that insecure communication channel, which is easy to monitor.

Other than that, I don't think the concept offers much more, and it really depends on the level of trust and the situation. I don't see any benefit in having link encryption between all routers - if you don't control the routers yourself.


Usability of padding scheme in blinded RSA signature?

In the blind RSA signature scheme the blinding of a message
$m$ (to be blindly signed) is multiplicative with value $r^e$, where
you ensure that $r$ is invertible modulo $N$.

So if the sender receives the signed blinded message back from the
signer, he can unblind by multiplying with $r^{-1}$, yielding $s\equiv
m^d \pmod N$ which is a valid (textbook) RSA signature for $m$.

Padding by the sender

Note, that $m$ could also be the result of any padding method for RSA
signatures, which however
needs to be applied by the sender before blinding. By denoting this padding as $f$ we can simply
consider the blinded message to be $m'\equiv f(m)r^e \pmod N$ (which clearly can be unblinded after blind signing).

Padding by the signer

Denoting the blinded message which is sent to the signer as $m'\equiv
mr^e \pmod N$, then padding by the signer means that the signer
changes the blinded message $m'\equiv mr^e \pmod N$ to some $m''$ before
signing. Padding methods for RSA signatures hash the original
message (possibly with some parameters), padd the hash value to some
certain format and the result is then interpreted as an element in
$Z_N$, which is then exponentiated with the private signing exponent
$d$.

Observe that in doing so the signer padds an already blinded message and denote this padded blinded
message as $m''=f(m')=f(mr^e)$. If such a padding to the message $m'$ received by the signer is applied by the
signer, then the signature obtained by the sender for $m''$ will be $s' \equiv (f(mr^e))^d \pmod N$
and then unblinding, i.e., computing $s'\cdot r^{-1} \equiv (f(mr^e))^d\cdot r^{-1} \pmod N$,
will yield some element from $Z_N$ which is clearly not a valid signature $m^d\pmod N$ for the message $m$ the sender wants to be signed
(for padding functions $f$ we assume to be applied, i.e., involving hashing. Clearly, if $f$ is the identity function then it works, but that is no padding).


The only 2 "common" algorithms that I know off the top of my head with 18 rounds are Clefia and Camellia with 128-bit keys.

Anubis may also be an option, I believe that with a 320-bit key it uses 18 rounds, I have no idea why that would be used instead of AES.

I suppose it is also trivial to add rounds to AES or Twofish in hardware, both the key schedule and round function support additional rounds without modification to their core.


Integrity of format preserving Encryption

The non-malleability of FPE is not a property that can be universally or even most of the time relied on to provide strong integrity protection, as the answer you're quoting points at when it says that "FFX can provide integrity protection in very limited circumstances" (my boldface).  Such cases are the exception, not the rule.

For any cipher that produces ciphertexts no longer than the plaintexts, the best it can offer in terms of integrity is the very weak property that an attacker's forged ciphertexts will decrypt to pseudorandom plaintexts, which the attacker cannot in practice predict better than chance and thus exploit.  This really isn't much, because the defender is unable to detect the forgeries, but most encryption-only modes don't even offer that much.

The exception that the answer you link to talks about is cases where plaintexts are redundantly coded—where the alphabet and length of the strings in which the messages are coded allows for $M$ distinct combinations, but there's only $N < M$ distinct valid messages and you can unambiguously distinguish these $N$ coded messages from the other $M - N$ invalid ones.

In that circumstance, if we encrypt messages with a non-malleable cipher, an attacker who forges a ciphertext only manages to hit upon one that decrypts to a valid plaintext with $N/M$ probability.  In exceptional cases where $N/M$ is extremely small (say, $2^{-128}$) this could offer meaningful security, but if we're talking credit card numbers, which have a single checksum digit, it means an attacker's forgeries would be undetectable 10% of the time. Not good!

As for best practice, the thing I'd say that FPE should be avoided whenever you can, period.  It's not designed to offer optimal security, but rather it's a compromise for situations where legacy issues prevent you from using optimal solutions.


Security of stream cipher with a priori knowledge of message

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

If the output of the key stream generator is indistinguishable from a random stream and uncorrelated to the plaintext, then no, you cannot.

Consider the case where we know almost all of the paintext, that is, we have an encrypted message $e = m \oplus s$ (where $m$ is the plaintext, and $s$ is the keystream output), and we know apriori that either $m = m_1$ or $m = m_2$ (but we don't know which).

We can compute $e \oplus m_1$ and $e \oplus m_2$, one of which will be $s$ and the other will be $s \oplus m_1 \oplus m_2$

However, if we assume that $s$ is random and uncorrelated, then both $s$ and $s \oplus m_1 \oplus m_2$ will be random; we have no way of deciding which is which.  Any hypothesis testing on $s = e \oplus m_1$ will give the same expected result as on $s = e \oplus m_2$


How can I prove that a set of ciphers are the encryption of a set of plaintexts?

If you are allowing for probabilistic proofs, simply have the one doing the encryption encrypt the set multiple times. All of these encrypted sets are sent to you.

You then ask the one doing the encryption to reveal the keys for all but one of the sets. You do the decryption to verify that all of those sets decrypt to the proper plaintexts. This is a cut-and-choose protocol (see Cut-and-Choose Protocol by Crépeau).

If the adversary is going to cheat, they will only be able to encrypt one set incorrectly and you have to randomly not choose that set for verification. You can set the probability of this to be arbitrarily low (at the cost of communication and computation) by setting the number of copies of the set the one doing the encryption must encrypt to be high enough.


Is there a multiple asymmetric encryption algorithm, which requires all private keys to reveal the secret?

@Erez points to the simple and often good enough solution. In more general terms, you want to split the private key knowledge into several "shares" such that all of them are needed to actually obtain the private key. This calls for a few comments:

To make the splitting/sharing easier, you can do things indirectly: generate a random symmetric key K, encrypt the RSA private key with K, and so the splitting over K. Thus, whatever splitting mechanism you use, you need to do it only on K, which is small enough to make it easy and allow for short "shares"; it is also "structureless" (it is a bunch of uniformly random bits) which may avoid some problems.
The simplest form of splitting of a secret into n shares is a XOR: for a secret K, generate n-1 random values ri of the same size. Share si is then the value ri, except for the last share sn which is equal to the XOR of K and all the ri together. It is easily shown that the XOR of all shares yields K, and without all the shares you have absolutely no information on the secret K.

Shamir's secret sharing, that @Erez points to, is just a generalization of that XOR mechanism, to support for a threshold: making n shares such that any t of them (t is lower than n) allow reconstruction, but t-1 shares yield no information whatsoever. When t = n, Shamir's secret sharing becomes the XOR-based mechanism described above.
A very nice feature of such "private key split" is that it is entirely done on the key holders side. From the point of view of whoever encrypts, this is plain asymmetric encryption (say, RSA).
When you use a private key sharing, there is a potential conceptual problem: though all shares are needed to decrypt the data, the reconstruction must occur "somewhere", and all people who witness the reconstruction learns the complete secret. This gives them the power to decrypt alone other messages encrypted with the same key. Depending on your context, this may or may not be a problem.

Protocols that solve that issue are called "group decryption" or more generally "multi-party computation". Such a protocol would make share holders participate in a common decryption, such that at the end of the protocol all participants learn the decrypted value, but not the shares from other share holders. There are many variants depending on the threshold you want to achieve, the number of communication rounds, the sizes of individual messages, the number of passively or actively cheating share holders you want to tolerate, whether you want traitors to be revealed... This is a complex research area. Start with this question for some pointers.


Proving item association without revealing one of the associated items

What it sounds like you are looking for is a Commitment Scheme; that is, a way for Alice to compute a 'Commitment' based on a 'value', and publish the 'Commitment' to Bob (or a group of Bobs).  Just from the tag, Bob cannot deduce the value (even if he know it's one of a small set of values).  However, Alice at some point can 'open' the commitment, revealing the value; Bob can then verify that the revealed value did, in fact, correspond to the value that Alice originally committed to.

If so, well, this is quite well studied territory.  The simplest commitment method is based on a secure hash function (say, SHA-256).  We have all parties agree on a secure hash function, and the length of large random values (say, 128 or 256 bits) that will be used.  To commit to a value, Alice selects a random value for R, and then computes:

Commitment := SHA256( R | Identity )

(where | is string concatination).  She then publishes the Commitment as her tag, and saves the value of R she used.

Bob is unable to deduce anything about the identity from the tag; the best thing he can try is to iterate through the possible values of R, and if Alice chose a large enough R, he can't do that.

When it becomes time for Alice to open the commitment (that is, reveal the identity), she publishes both the identity and the value R; Bob can then verify that those two do, in fact, hash to the published tag.  He also knows that it is computationally infeasible to find two different values that hash to the same commitment (because that's a property of a cryptographically secure hash function), and so the value that Alice revealed must be the value she originally committed to.

One subtle point in this particular technique: the reason we had all parties agree on the length of R is to prevent Alice from changing her mind about it. If not, then Alice can try to cheat in this way: she might try (for example) to commit to the value 01 02, and use the R value 00 00 00 (note: this R value is too small to be secure, this is just a toy example); and so she would publish SHA256( 00 00 00 01 02 ).  However, when it comes time to reveal, she might change her mind, and claim the Identity 00 01 02, and that she used the R value 00 00; this also gives SHA256( 00 00 00 01 02 ), which is the exact same identity.  Preventing Alice from changing the length of R after the commitment stops this method of cheating.


Cryptography scheme to prove you really are the author for something

The solution is easy if you have a Trusted Authority(TA). Assuming that there is no TA.
A direct digital signature can be a solution. However, how we can trust that Satoshi is not faking person $x$ by stealing his keys or he killed the person $x$ to steal the keys.
A solution
by using biometrics to uniquely identify the original person.
Satoshi follows the steps;

produces a private-public keys $k_{priv_s}, k_{pub_s}$  for his digital signatures.

he appends his biometric data; his fingerprint $fp_s$, his unique DNA code $dna_s$, and his iris $iris_s$ data to the document $d$.
$$author = d \| fp_s \| dna_s \| iris_s $$

$Sign(k_{priv_s},author)$ by using digital signature standard.

Adds the signature and $k_{pub_s}$ to the document before print.

Secretly publishes the document.

So that, when a person showed up with the signature key to reveal himself, the others have to look at the biometric data to match.
The entropies;
Possible values: O’Gorman,L., Comparing Passwords, Tokens, and Biometrics
for User Authentication;

A biometric doesn’t have a fixed number of possible values. Theoretically, the keyspace of biometrics such as fingerprints is unlimited because if you could measure the continuous signal with infinite precision, no two would be the same. But, one could say the same for passwords, that if you allowed the password length to be unlimited, you’d also have an unlimited keyspace

Fingerprints; Young et. al, Entropy of Fingerprints;

The average number of minutiae present in each image was 28.02. Therefore, dividing the entropy of 55.02 bits by the average minutiae of 28.02, each minutia provides 1.963 bits of entropy.

Note: Fingerprint copying; I've found only this, it is easy to detect it when there are observers.
Note: I changed the key generation from biometrics. Some of them are not exactly reliable.

Claims to be the Satoshi

nChain chief scientist Craig S. Wright that he created Bitcoin. But it is debunked and the claims are called nonsense.


What is the run-time on finding collisions with MACs,...?

What is the run-time on finding collisions with MACs...

Well, the definition of a MAC is of the form "if you don't know the key, then it is infeasible to ...".  This definition does not assert anything if you do know the key (or are able to select it); hence it does not provide any nontrivial lower bound.

In particular, with common MACs (e.g. CMAC, Carter-Wegman MACs), it is trivial to generate second preimages.  For CMAC, we can actually generate preimages; we just select an arbitrary prefix (of a multiple of the block length), and compute what the last block needs to be to generate the target image.  For Carter-Wegman MACs, we can generate second preimages by looking into the almost universal hash function, and trivially generating a second message that produces the same hash for the given key (at least, for every au hash I've heard of).

On the other hand, we come to HMAC.  For HMAC, we can generate collisions between two different keys in two ways:

If HMAC is given a short key (no longer than the hash block size), it xor's it into the IPAD/OPAD patterns.  That implies if we append a zero byte to the key, say, $K_2 = K_1 || 00$, then the result of the xor's will be the same, and so $HMAC(K_1, M) = HMAC(K_2, M)$ for any $M$.
By taking advantage that, if the key is longer than the hash block size, HMAC first hashes the key, and then uses that hash as the key.  Hence, we can select two different keys, $K_1$ (which is long), and $K_2 = Hash(K_1)$, then we have $HMAC(K_1, M) = HMAC(K_2, M)$ for any message $M$.

If we disallow those approaches (and perhaps say that the keys must be the same length), then it is easy to see that finding a collision with HMAC is no easier than finding a collision in the underlying hash function (as a collision in the HMAC will imply a collision in either the upper or lower hashes of the HMAC, or in the hash that preprocesses long keys).

So, bottom line: the definition of MAC does not ensure making finding collisions (assuming the attacker knows the key) difficult; we can find MACs (such as HMAC with a fixed length key) where it is believed to be difficult; we can also find MACs where it is easy.


How do you prevent the risk of damage to the security of Fully Homomorphic Encryption?

Part (a) above makes me believe there is a risk with FHE security being damaged. Is it possible to use another encryption scheme where this risk is mitigated ?

I'm not sure what you mean by that. In what way is security damaged? All ciphers risk security being damaged by leakage. For example if the key leaks, security is damaged.

I think what they are saying is, they distribute shares of the secret key to all parties. This needs to be done in such a way that even if all corrupted parties get together and reveal their shares to each other. And additionally reveal any leaked information they have gleaned during the protocol execution, the original secret key $sk$ cannot be reconstructed.

As a more concrete example, say we are using additive secret sharing. Assume some number of parties is corrupt (say $n/2$). Thus we assume the adversary knows all of those $n/2$ shares. But there are $n/2$ shares held by uncorrupt parties that are not known to the adversary. Assume, however, that some information about those shares is leaked (not sure what that info is, perhaps they say in the paper). They are saying that even given that information, the security of the FHE should not be damaged.


Using MITM to attack three keys 3-DES encryption?

No, we are not able to break 3-keys 3-DES encryption using something similar to Meet-in-the-Midle with cost much lower than $2^{112}$ encryptions; much less triple encryption in general.

In the case of triple encryption with 3 k-bit keys in general, in order to apply MitM, we'd need to group 2 keys together on one side, thus would have cost $O(2^{2k})$ for this half. There's even a formal proof, see this. The space complexity of that MitM remains $O(2^k)$ blocks, since we can chose to pre-compute the values for the side with the shortest key, then perform the search with the other half.

In the case of DES, we know the structure and can open the block cipher, and in particular break the middle cipher into two halves of 8 rounds. However, each of these haves still receives all the keys bits of the midle DES, therefore we can't use that to reduce the complexity of plain MitM to $2^{56+28}$ encryptions on each half, as we could if 28 key bits went exclusively to the first 8 rounds, and the 28 other bits exclusively to the last 8 rounds.

Notice that clever attacks exist against 2-keys 3-DES, and are nearly practical; see this.