Soft question: What are examples of beautiful proofs in cryptography? [closed]

Question

These may include any proofs, reductions, constructions, etc. For example, simple solutions to problems which at first sight seem difficult. Elegant construction that hide deep mathematical concepts, but once presented are easy to use.

Anything which you deem elegant and clever.

Proofs with nice graphics are especially welcome.

(preferably ones that can fit reasonably into a StackExchange answer).

Answer 1

Theorem. The ECB mode of a block cipher is distinguishable under chosen-plaintext attack with laughably high advantage.

Proof.

Answer 2

Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes. (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.) Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$? Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots. What's the success probability?

Step 1 always succeeds. Step 2 always succeeds. Step 3 succeeds with probability $\varepsilon$. Step 4 is the interesting step.

• Every quadratic residue, like $y$, has up to four distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$. If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv \xi^2 \pmod n$ with the nontrivial integer equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$. And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$. Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$ Consequently, since integers have unique factorization, $n = pq$ must share some but not all factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know which of the four square roots $x$ of $y$ we began with even if it wanted to thwart us. So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$. If we retry until success, the expected number of trials to factor $n$ is about 2.

---

This proof was published by Michael Rabin in 1979 in a technical report on a proposal for a public-key signature scheme to justify its security in relation to factoring. Unlike the trivially breakable RSA proposal (paywall-free) that preceded it, Rabin's signature scheme was the first signature scheme in history that still stands under modern scrutiny, provided suitable parameter sizes are chosen, through the use of hashing not merely as a method to compress large messages but as an integral part of security to destroy the structure of messages. Today, textbooks and Wikipedia consistently misrepresent Rabin's cryptosystem as a broken encryption scheme or as a broken hashless signature scheme, as if almost nobody has ever bothered to read the paper.

Whether Rabin was the first to publish a proof that square roots enable factoring, I don't know—Fermat wrote a letter to Mersenne in about 1643 observing that finding a way to write $n$ as a difference of squares leads to factorization, so it seems likely that a number theorist before Rabin would have come upon the same incremental refinement that a modular square root algorithm leads to a factoring algorithm. But, then again, until the development of public-key cryptography in the 1970s, perhaps there would have been little interest in that observation without a square root algorithm in the first place, which obviously we didn't have then and still don't have now!

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root: by Bézout's identity, there exists some $d$ and $k$ such that $d e - k \phi(n) = \gcd(e, \phi(n)) = 1$, or $e d = 1 + k \phi(n)$, and so if $y \equiv x^e \pmod n$, then $$y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n,$$ by Euler's theorem; consequently $x \mapsto x^e \bmod n$ is a bijection.

Answer 3

My favorite crypto proof, is how to prove a graph coloring exists with zero knowledge. I like it because it doesn't require any cryptography.

Let's say we have a graph which I know of a coloring for with k colors and Bob wants to prove to Alice such a coloring exists and he knows it without revealing anything about it.

They draw the graph out on the floor and ask Alice to leave the room. Bob randomly snuffles the colors. So which color is random. Bob places a colored marker on each vertix matching his coloring and covers them with a Hat. Then Alice enters the room and picks two adjacent vertices and reveals their color. Alice verifies they are both from the agreed set of colors and are different.

The process is then repeated until desired confidence is reached. Each time Bob reshuffles the colors (e.g replace blue with green, red with blue,...) covers again and Alice chooses a new edge to reveal by random.

It is trivial if Bob indeed has a valid coloring it succeeds. It is also trivially zero knowledge, as the only thing you learn in a reveal is that in the current hidden coloring these two vertices have a different color which is guaranteed possible if really there is a valid coloring.

If Bob does not know a valid coloring then each reveal phase has a non-zero chance of failing. Bob can not set up the colors so that any reveal will work. So there is at least a $1/|E|$ chance of failing, controlled by Alice's random choice. So if repeated sufficiently many times, Alice can get arbitrary confidence.

I like this one, because it's a simple zero knowledge proof where we prove a fact (not like the circular cave example where we demonstrate ability in the physical world). Yet we use physical commitment (covering with hats) and it's very easy to follow the proof.

I also like multi party computation using physical oblivious transfer (with two envelopes) and commitment with envelopes and without cryptographic primitives.

Answer 4

Security fail of Non-SIV-mode ciphers based on AES-CTR by leaking plaintext xors when re-using nonce.

proof

Answer 5

How can you use polynomials evaluation to detect forgery on the internet?

Fix a field $k$. Encode a message $m$ as a polynomial $m_1 x^\ell + m_2 x^{\ell - 1} + \cdots + m_\ell x$ of degree $\ell$ in $k$ with zero constant term. Suppose the sender and receiver share secret uniform random elements $r, s \in k$. The authenticator $$a := m(r) + s = m_1 r^\ell + m_2 r^{\ell - 1} + \cdots + m_\ell r + s$$ if sent alongside $m$ can detect forgery: the receiver, on receipt of a possibly modified message/authenticator $(m', a')$, can compute $m'(r) + s$ and verify whether $a'$ matches—but a forger, who knows $m$ and $a$ but not $r$ or $s$, has probability at most $\ell/\#k$ of finding any authenticator $a'$ for a distinct message $m' \ne m$. (There is a good chance that your web browser is using this with crypto.stackexchange.com right now!)

How does this work?

1. Polynomial evaluation at uniform random points has bounded difference probability: if $H_r(m) = m(r)$ for any nonzero polynomial $m$ with zero constant term, and if $r$ is uniform random, then for any $m \ne m'$ of degree at most $\ell$, and for any $\delta$, $$\Pr[H_r(m) - H_r(m') = \delta] \leq \ell/\#k.$$

   Proof. In the event $H_r(m) - H_r(m') = \delta$, $r$ is a root of the nonconstant polynomial $m(x) - m'(x) - \delta$ of degree at most $\ell$. There are at most $\ell$ such roots, each with probability $1/\#k$ if $r$ is uniform random; thus the event occurs with probability at most $\ell/\#k$.

2. If $m \mapsto H_r(m)$ has difference probability bounded by $\varepsilon$, then $m \mapsto H_r(m) + s$ for independent uniform random $s \in k$ has one-time forgery probability bounded by $\varepsilon$: for any $m' \ne m$, $a$, and $a'$, $$\Pr[H_r(m') + s = a' \mid H_r(m) + s = a] \leq \varepsilon.$$ That is, even if an adversary is given a message $m$ and its authenticator $a$, any forgery attempt $(m', a')$ has probability at most $\varepsilon$ of succeeding.

   Proof. \begin{align} \Pr&[H_r(m') + s = a' \mid H_r(m) + s = a] \\ &= \Pr[H_r(m') + a - H_r(m) = a'] \\ &= \Pr[H_r(m') - H_r(m) = a' - a] \\ &\leq \varepsilon. \end{align}

How do you authenticate many messages? Derive $(r_i, s_i)$ for the $i^{\mathit{th}}$ message by a pseudorandom function of the message sequence number $i$, under a secret key. If doing so raised the forgery probability appreciably, mounting a forgery attack would serve as a distinguisher for the pseudorandom function family, breaking its security! This is how NaCl crypto_secretbox_xsalsa20poly1305 and TLS ChaCha/Poly1305 work. It is also very close to how AES-GCM works, except AES-GCM reuses $r$ between messages in Carter–Wegman structure.

---

The idea was essentially first published by Gilbert, MacWilliams, and Sloane in 1974[1] (paywall-free), but the language of Carter and Wegman's universal hashing research program published in 1979[2] (paywall-free) made for a neater exposition[3] (paywall-free) by viewing polynomial evaluation as a universal hash family, which was then applied with pseudorandom permutation families by Shoup[4] to make for practical cryptography. Any other universal hash family with bounded difference probability works too—e.g., the polynomial division hash $m \mapsto (m \cdot x^t) \bmod f$ on $m \in \operatorname{GF}(2)[x]$ for a uniform random irreducible $f \in \operatorname{GF}(2)[x]$ of degree $t$, somewhat like a CRC—but polynomial evaluation hashes are generally the cheapest to generate keys for and to compute.

Answer 6

The indifferentiability framework by Maurer et al. is an important and widely used framework when discussing security of hash functions. The essence of the framework is that if a hash function $\mathcal{H(\cdot)}$ is indifferentiable form a Random oracle $\mathcal{RO}$ then "any" cryptosystem $\mathcal{C(\cdot)}$ using $\mathcal{RO}$ remains secure when the latter is replaced with $\mathcal{H(\cdot)}$.

Before going any further, let's look at concrete examples. In the first example $\mathcal{C(\cdot)}$ is a signing algorithm for short, fixed length output. We could use a hash $\mathcal{H(\cdot)}$ to obtain a signing algorithm for long messages. This is also known as hash-and-sign algorithm. In the second example, $\mathcal{C(\cdot)}$ is itself a hash construction(M-D, Sponge), here $\mathcal{H(\cdot)}$ will be the underlying compression or permutation.

Remark: I wrote "any" because it was shown that plain indifferentiability doesn't give any guarantee against a multi-stage adversary. The framework can be extended to take that into account(look at resource restricted indifferentiability or context-restricted indifferentiability)

The proof is beautiful imo because it's "merely" drawing boxes. :) Moreover, the impossibility proof that $\mathcal{RO}$ cannot be in general instantiated by any $\mathcal{H(\cdot)}$ is given as a "simple" entropy calculation.

Before presenting the proof some background should be presented.

Random oracles and impossibility results

The random oracle methodology allows to design efficient and secure cryptosystems, assuming access to a random oracle. Canetti et al. showed that $\mathcal{RO}$ can in general not be instantiated any $\mathcal{H(\cdot)}$. However in practice protocols seems to remain secure. Formalizing the conditions under which the RO methodology is justify was in part the aim of the indifferentiability framework.

Indifferentiability

The framework uses systems as building blocks(Signing algorithms, Hash functions and others are represented as such). A system provides a number of interfaces that can be queried and give back answers. We are iterested in systems that provide 2 types interfaces, public and private.

Definiton: a system $\mathcal{S}$ is said to be indifferentiable form $\mathcal{T}$ if for any distinguisher system $\mathcal{D}$(with output 0 or 1) there exists the system $\mathcal{P}$ such that the advantage $$|P[\mathcal{D}(\mathcal{S^{priv}}, \mathcal{S^{pub}}) = 1] - P[\mathcal{D}(\mathcal{T^{priv}}, \mathcal{P(T^{pub})}) = 1]|$$ is negligible. The setup is beautifuly summarized in the following picture.

From this notion the following theorem follows:

Theorem: $\mathcal{S}$ indifferentiable from $\mathcal{T} \iff\forall \mathcal{C(\cdot)}, \mathcal{C(S)}$ is as secure as $\mathcal{C(T)}$. In this theorem $\mathcal{C(\cdot)}$ is a crytosystem that makes use of another resources, $\mathcal{T}$ is the ideal resource and $\mathcal{S}$ is the available resource that will be used to construct the ideal resources.

Proof:

I will present only the "$\Rightarrow$" part of the proof, the other part can be found in the paper.

The proof is bascially given by the following picture

Here $\mathcal{E}$ is a so-called environment that runs the cryptosystem and output 0 or 1. The two systems are equally secure if the output of the do not give any information which setting we are in.

As we can see, the essence of the proof is that by connecting systems we get a new Systems. In this case, this is showed using doted lines around $\mathcal{A, C, E}$, we get a new system $\mathcal{D}$. By the indifferentiability property the two cryptostystems are equally secure.

Answer 7

Another extremely beautiful yet simple construction with an elegant proof is the one-time pad.

The one-time pad is an information-theoretical secure encryption scheme. It is usually described as a xor between a binary plaintext $m$ and a uniform random key $k$ sampled for every new message, both of the same size(i.e $c = m \oplus k$).

This definition can be beautifully generalized as follows:

Definition: Given a group $(G, *)$ the one-time pad over $G$ is defined as $$Input: m \in G$$ $$k \xleftarrow{$} G$$ $$c = m*k $$

Proof:

We need to show that given a uniform random variable $K$ Independent of another random variable $M$ with some distribution, then the random variable $C = M * K$ is Independent of $M$. In other word the the ciphertext does not give any information about the plaintext

Part 1: $P*K$ is uniform

We have that $P^C[c] = P^{MK}[m * k = c] = P^K[k = c * m^ {-1}] = \frac{1}{|G|}$.

Part 2: $C$ is Independent of $M$

$P^{C, M}[c, m] = P^{C, M}[m|c]\cdot P^{C}[c] = P^{C,M}* \frac{1}{|G|}$.(using part 1)

Finally, $P^{C, M}[m|c] = p^{C, K}[m|c*m^{-1}] = P^M[m]$(by independence of $M$ and $K$).

In conclusion $C$ and $M$ are independent.

Answer 8

If the question is also applicable to which formulas should be in your cryptographic "toolbox" (and that are beautifully simple) I would add Boltzman's entropy equation (for calculating Entropy which is s = k(logW), but swapped with Claude Shannon's interpretation as it also structurally relates to information theory (and not the decay of gas) and is something that every cryptographer must know how to do, important for combinatorics and security assumption values (passwords, private keys, ciphertext, etc..).

It's also beautifully simple, with a few ways to write it:

${log_2(L^N)}$ = Entropy in bits (where L is the size of the library and N is the length of the string.)

Formul (source) :

The entropy of a discrete random variabe X is defined as: ${\\H(X) = E {\lfloor \log \frac{1}{P_i} \rceil} = \sum_{i} P_i \ log \frac{1}{P_i} }$

and where the sum is over the range of X, and ${P_i}$ = ${Pr[x=i]}$

For example, if X is a uniform random variable on a string of r bits, each ${P_i = \frac{1}{2^r}}$ so that ${log\frac{1}{P^i} = }$r thus the expected entropy of x is ${H(X)=}$r.

(i.e. if x is a binary number where i=2, (base two) and is 256 bits long, where r=256 denoting the length of x, the maximum entropy of x is 256, where h=256).

Put differently, the entropy "H" of a discrete random variable "X" is defined as:

${\\H(X) = - \sum_{i=1}^{n} P(x_i) \ log_b P(x_i) }$

If we equate beauty with its usefulness: then again, I think every cryptographer should be able to - at a minimum - calculate entropy when dealing with any random length of any text character (number or string) in numerous situations related to cryptographic operations in order to calculate the potential message space and determine the potential maximum theoretical Entropy as bits of security (i.e. 128-bit security, 128 bits of entropy).

Note: the formula doesn't tell us whether the number is random or not or if bits are distributed uniformly, but simply helps calculate the minimum range of numbers an attacker would need to brute force search to guess/find the random number, and since the random number cannot carry more than 1-bit of entropy for every bit in the number, its maximum entropy is equal to that minimum range. So even if a 256-bit number was sourced from a large range of 512-bit numbers, it still only carries a maximum of 256-bits of entropy as it would be sufficient to search all 256-bit numbers (the minimum range) to find it.

(example potentially random 256-bit binary number: 1000110110001000110011010011011101111111010111100111100010111011000010110010010000000110000100111111010111101101011100010101100111010100100100100100001000110000000111001010011111000011001001110110011001101111010001010111000100100001010110011001111111111101 And the zero-indexed maximum range of 256-bit binary numbers: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111)

Answer 9

How can you expand a short-input pseudorandom function family $F_k\colon \{0,1\}^t \to \{0,1\}^n$ to long inputs?

Let $H_r\colon \{0,1\}^* \to \{0,1\}^t$ be a universal hash family with bounded collision probability. Define $F'_{k,r} \colon \{0,1\}^* \to \{0,1\}^n$ by $$F'_{k,r}(m) := F_k(H_r(m)).$$ In other words, compress a long input $m$ with hash that merely has low collision probability—which can be extremely cheap to evaluate!—and then scramble the result with the short-input PRF.

Theorem. If $F_k$ is a secure pseudorandom function family and if $H_r$ has bounded collision probability, then $F'_{k,r}$ is a nearly as secure pseudorandom function family, with insecurity that grows quadratically in the number of uses.

Specifically: Suppose $F_k$ has $q$-query PRF distinguishing advantage bounded by $\varepsilon_0$. Suppose $H_r$ has collision probability bounded by $\varepsilon_1$, so that $\Pr[H_r(m) = H_r(m')] \leq \varepsilon_1$ for any $m \ne m'$. Then the PRF distinguishing advantage of $F'_{k,r}$ is bounded by $\varepsilon_0 + \binom{q}{2} \varepsilon_1 = \varepsilon_0 + O(q^2) \varepsilon_1$.

Proof. The idea is to show two parts:

• Consider an idealized variant $f(H_r(m))$ where $f\colon \{0,1\}^t \to \{0,1\}^n$ is a uniform random function—what the pseudorandom function family $F_k$ aspires to resemble. The random function $F'_{k,r}(m) = F_k(H_r(m))$ can't be much different from $f(H_r(m))$ because $F_k$ can't be much different from $f$.
• If $f' \colon \{0,1\}^* \to \{0,1\}^n$ is a uniform random long-input function, which is what $F'_{k,r}$ aspires to be, the random function $f(H_r(m))$ is potentially distinguishable from $f'(m)$ only in the event that you find collisions in $H_r$—which happens with very low probability. So $f(H_r(m))$ can't be distinguished from $f'(m)$ unless collisions occur in $H_r$, which happens only with low probability.

Thus, $F'_{k,r}(m) = F_k(H_r(m))$ can't be much different from $f(H_r(m))$ which in turn can't be distinguished from $f'(m)$ except with low probability, which is exactly what we hope to prove.

---

Let $A'$ be a putative PRF distinguisher against $F'_{k,r}$—a random decision algorithm that takes an oracle $\mathcal O$ and returns a decision $A'(\mathcal O)$, either 0 or 1, depending on whether it thinks the oracle is for a uniform random function $f'$ or it thinks the oracle is for $F'_{k,r}$ under some key $(k, r)$. If it's a good distinguisher, it returns answers with substantially different probability for $F'_{k,r}$ and for $f'$: $|\Pr[A'(F'_{k,r})] - \Pr[A'(f')]|$ is large, far away from zero. We will show that if $A'$ is a good distinguisher, then there is a nearly-as-good distinguisher $A$ for $F_k$, so the best distinguisher for $F'_{k,r}$ can't be much better than the best distinguisher for $F_k$.

1. Define $A(\mathcal O) := A'(\mathcal O \mathbin\circ H_r)$—in other words, we will try to distinguish $F_k$ by simply using it as $F'_{k,r}$ with a random $r$ and applying $A'$. Note that $$A(F_k) = A'(F_k \mathbin\circ H_r) = A'(F'_{k,r}).$$

2. For the $q$ queries $x_1, x_2, \dots, x_q$ submitted by the distinguisher $A'$ (suppose, without loss of generality, that they are all distinct), the distribution on $$\bigl(f'(x_1), f'(x_2), \dots, f'(x_q)\bigr)$$ and the distribution on $$\bigl(f(H_r(x_1)), f(H_r(x_2)), \dots, f(H_r(x_q))\bigr)$$ are almost the same: As long as the $x_i$ are distinct, the $f'(x_i)$ are all independent uniform random $n$-bit strings, and as long as the $y_i = H_r(x_i)$ are distinct, the $f(y_i)$ are independent uniform random $n$-bit strings too.

   So in the event that there are no collisions in $H_r$ among the $\{x_i\}$, that is no $i \ne j$ such that $H_r(x_i) = H_r(x_j)$, the two functions $f'$ and $f \mathbin\circ H_r$ have exactly the same distribution. And since $H_r$ has low collision probability, the event of collisions in $H_r$ among the $\{x_i\}$ is small—call this event $C$, so that $$\Pr[A(f \mathbin\circ H_r) \mid \lnot C] = \Pr[A'(f')].$$

3. First, we can set a bound on the probability of $C$, any collision at all:

   \begin{multline} \Pr[C] = \Pr[\exists i < j. H_r(x_i) = H_r(x_j)] \\ \leq \sum_{i<j} \Pr[H_r(x_i) = H_r(x_j)] \leq \sum_{i<j} \varepsilon_1 = \binom{q}{2} \varepsilon_1. \end{multline}

   Next, we can split $\Pr[A'(f \mathbin\circ H_r)]$ into two cases—the case of any collisions, and the case of no collisions, by the chain rule: $$\Pr[A'(f \mathbin\circ H_r)] = \Pr[A'(f \mathbin\circ H_r) \mid C]\,\Pr[C] + \Pr[A'(f \mathbin\circ H_r) \mid \lnot C]\,\Pr[\lnot C] \\ \leq \Pr[C] + \Pr[A'(f \mathbin\circ H_r) \mid \lnot C] = \binom{q}{2} \varepsilon_1 + \Pr[A'(f')];$$ hence $\Pr[A'(f \mathbin\circ H_r)] - \Pr[A'(f')] \leq \binom{q}{2} \varepsilon_1$. Conversely, because we can always replace $A'$ by $\lnot A'$, we can reverse the signs, so $$|\Pr[A'(f \mathbin\circ H_r)] - \Pr[A'(f')]| \leq \binom{q}{2} \varepsilon_1.$$

   Finally, notice that the distinguishing advantage of $A'$ is a kind of metric on probability distributions, in this case on $F'_{k,r}$ and $f'$, which inspires us to apply the triangle inequality $|a - c| \leq |a - b| + |b - c|$. Thus,

   \begin{align} |\Pr[A'(F'_{k,r})] &- \Pr[A'(f')]| = |\Pr[A(F_k)] - \Pr[A'(f')] \\ &\leq |\Pr[A(F_k)] - \Pr[A(f)]| + |\Pr[A(f)] - \Pr[A'(f')]| \\ &= |\Pr[A(F_k)] - \Pr[A(f)]| + |\Pr[A'(f \mathbin\circ H_r)] - \Pr[A'(f')]| \\ &\leq \varepsilon_0 + \binom{q}{2} \varepsilon_1. \end{align}

---

Why do I like this? It is a little involved, but it breaks down into two basic concepts reflecting the structure of the construction, and it demonstrates a few standard techniques in cryptographic proofs:

• showing that an attack on a composite cryptosystem leads to an attack on a component with slightly but quantifiably lower advantage
• reasoning about idealized components and setting bounds on the distance between two cryptosystems (‘distinguishing advantage’) by setting bounds on their respective distances from an intermediate cryptosystem with idealized components
• setting bounds on collision probabilities, which a lot of things in cryptography turn out to boil down to!