One of the most famous application of number theory is the RSA cryptosystem, which essentially initiated asymmetric cryptography.


I wonder if there are applications of number theory also in **symmetric** cryptography.


Thank you in advance for any comment / reference.


**NOTE:** Since RSA is based on [Euler's theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem), I'm looking for applications of number theory to symmetric cryptography that involve number-theoretic theorems at least as "complex" as Euler's theorem. For example, I do not consider [Caesar cipher](https://en.wikipedia.org/wiki/Caesar_cipher) as an application of number theory to symmetric cryptography, because it uses only the most basic definition of modular arithmetic.



Number theory in symmetric cryptography
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](https://en.wikipedia.org/wiki/Blum_Blum_Shub) 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)](https://en.wikipedia.org/wiki/KN-Cipher) 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](https://eprint.iacr.org/2016/492.pdf), 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](https://eprint.iacr.org/2006/021). 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.
4. **Edit** (I forgot one of my favourites): Wegman-Carter authenticators, which give high-performance MACs (message authentication codes) with information-theoretic security. Here, take a $\ge k$-bit finite field $\mathbb{F}\_q$ and fix an inclusion $\iota: \{0,1\}^k \to \mathbb{F}\_q$ (everything will operate on $k$-bit chunks of data) and a mapping $\pi: \mathbb{F}\_{q} \to \{0,1\}^t$ (this will produce a $t$-bit MAC). For each $n > 0$, we can define a map $(\{0,1\}^k)^n \to \mathbb{F}\_q[X]$ by $$M = (M\_1,\ldots,M\_n) \mapsto f\_M(X) := \iota(M\_n)X^n + \cdots + \iota(M\_1).$$ Now to produce (and verify) an authenticator for a message $M$ given a shared secret $(R \in \{0,1\}^k, S \in \{0,1\}^t)$, we compute $T = f\_M(R)\oplus S$ (where $\oplus$ denotes XOR in $\{0,1\}^t$). A crucial part of the security argument depends on the distribution of evaluations of polynomials over finite fields (see e.g. [Bernstein 2005](https://www.iacr.org/archive/eurocrypt2005/34940166/34940166.pdf) for an up-to-date description and analysis of this).


In all four examples, number-theoretic arguments are used to give strong justifications for the security of the primitive. But the last example is important because it is also used in practice: the Wegman-Carter construction can be seen in GHASH, which is used in [AES-GCM](https://en.wikipedia.org/wiki/Galois/Counter_Mode) (in this case, $q$ is a power of $2$), and it is also the basis of [Poly1305](https://en.wikipedia.org/wiki/Poly1305), a high-speed software authenticator. AES-GCM and ChaCha20-Poly1305 are two state-of-the-art algorithms for Authenticated Encryption that are widely used on the internet today.


