Skip to main content
1 of 2
Ben Smith
  • 879
  • 8
  • 13

Here are a few interesting examples of symmetric primitives whose claimed security is/was based on number-theoretic problems:

  1. From the 1980s: the famous Blum-Blum-Shub deterministic random bit generator is a classic example. Let $N = pq$ be the product of two large safe primes, and consider the sequence defined by $x_{i+1} = x_i^2 \pmod{N}$, where $x_0$ is the random seed (which can be any value in $(\mathbb{Z}/N\mathbb{Z})^\times\setminus\{1\}$). After each squaring, you extract some of the bits of $x_i$ to form the pseudorandom stream. The security of the bit generator - that is, the indistinguishability from a uniform random stream - can be reduced to number-theoretic problems. The idea is that if you only take the least significant bit of $x_i$ (or up to $O(\log\log N)$) at each iteration, then breaking this generator reduces to solving the Quadratic Rediduosity Problem $\bmod N$.

  2. A second classic example (this time from the 1990s): the KN cipher (Knudsen-Nyberg) was a number-theoretic block cipher designed specifically to resist differential cryptanalysis. The cipher was applied to 64-bit blocks, and the round function was defined as follows: choose a basis of $\mathbb{F}_{2^{37}}$ where the operation $x \mapsto x^3$ is particularly efficient. Let $E: \mathbb{F}_{2}^{32}: \to \mathbb{F}_{2^{37}}$ be some affine map, and let $F: \mathbb{F}_{2^{37}} \to \mathbb{F}_{2}^{32}$ be the map defined by cubing in $\mathbb{F}_{2^{37}}$, followed by throwing away five coefficients of the polynomial representation (w.r.t. the "nice cubing" basis). Now, dividing the 64-bit cipher state into two 32-bit values $L$ and $R$ in $\mathbb{F}_2^{32}$, the round function is $(L,R) \mapsto (R,L+F(E(R)+K))$, where $K \in \mathbb{F}_{2^{37}}$ is the secret key. The nonlinearity of the cubing permutation is important. The KN-cipher was subsequently broken using higher-order differential cryptanalysis, but its ideas have proven influential: the more recent MiMC cipher, for example, revisits the KN-cipher targeting applications in multi-party computation and zero-knowledge proofs.

  3. An example from the 2000s using "deeper" results in number theory: the Charles-Goren-Lauter hash function. Here we consider the $2$-isogeny graph of supersingular $j$-invariants over a suitably large $\mathbb{F}_{p^2}$: this is an important example of a Ramanujan graph, and this is key to the construction. The bits of the message $(m_0,m_1,\ldots,m_n)$ drive a non-backtracking walk of length $n$ in the isogeny graph (which is $(2+1)$-regular, so at each step you have $2$ choices: "low" or "high" w.r.t. some ordering on $\mathbb{F}_{p^2}$, and you go "low" if $m_i = 0$ and "high" if $m_i = 1$). The final hash value is a projection of the ending point $j_n$ of your walk into $\mathbb{F}_p$. The security of the hash function reduces to problems connected with finding cycles in the isogeny graph, which are provably large.

Ben Smith
  • 879
  • 8
  • 13