Score:1

Are there any estimates for the spectral radius and distribution of eigenvalues for the AES, DES, etc round functions?

ne flag

Suppose that $F:K\times X\rightarrow X$ is a function such that for each $k\in K$, the mapping $F_{k}:X\rightarrow X$ defined by letting $F_{k}(x)=F(k,x)$ is a bijection. Suppose that $F$ is the round function for some cryptographic function such as a block cipher or cryptographic hash function. Let $V_{X}$ be the complex vector space consisting of all tuples $(\alpha_{x})_{x\in X}$ such that $\sum_{x\in X}\alpha_{x}=0$. Define an irreducible linear representation of $\phi$ the permutation group $S_{X}$ on $V_{X}$ by letting $\phi(f)(\alpha_{x})_{x\in X})=(\alpha_{f(x)})_{x\in X}$.

Define a linear transformation $L_{F}=\sum_{k\in K}\phi(F_{k})$.

If the permutations $F_{k}$ are random and independently selected, then the circular law seems to hold for the linear transformation $L_{F}$, so the eigenvalues of $L_{F}$ should be approximately uniformly distributed on the disk $\{z\in\mathbb{C}:|z|^{2}\leq |K|\}$, and the spectral radius of $L_{F}$ should be around $\sqrt{|K|}$. Of course, in practice the round functions $F_{k}$ are non-random for block cipher round functions $F$. It seems like it would be good to try to make the spectral radius of $L_{F}$ quite low in order to make the random variables $Z_{n}$ as uniform on $X^{2}$ as possible where the value of $Z_{n}$ is a random pair $(x,y)$ where $x$ is selected from $X$ uniformly at random and $y=F_{k_{1}}\dots F_{k_{n}}(x)$ for randomly and independently selected $k_{1},\dots,k_{n}\in K$.

Now, there are some instances where $L_{F}$ is nilpotent for rather trivial reasons. For example, if $F(k,x)=k\oplus g(x)$ for some permutation $g$ (as is the case with AES), then $L_{F}$ is nilpotent. One could also ensure that $L_{F}$ is nilpotent for some Feistel cipher block functions $F$.

Is there any computation or estimate of the spectral radius or distribution of eigenvalues of $L_{F}$ for the round functions for SHA-256 or any other modern block cipher or cryptographic hash function $F$ where $L_{F}$ is not nilpotent?

Mathematics terminology

$S_{X}$ is the group of all permutations from $X$ to $X$.

If $V,W$ are vector spaces, then let $\text{Hom}(V,W)$ be the set of all linear transformations $L:V\rightarrow W$. If $G$ is a group, and $V$ is a vector space, then a linear representation of $G$ on the vector space $V$ is a function $\phi:G\rightarrow\text{Hom}(V,V)$ such that $\phi(g)\circ\phi(h)=\phi(gh)$ whenever $g,h\in G$. We say that $\phi$ is irreducible there does not exist a proper non-trivial subspace $W$ of $V$ such that $\phi(g)(w)\in W$ whenever $w\in W$.

If $A$ is a square matrix, then an eigenvalue of $A$ is a scalar $\lambda$ such that $A\mathbf{x}=\lambda\mathbf{x}$ for some non-zero vector $\mathbf{x}$.

If $A$ is a square matrix with real or complex entries, then define the spectral radius $\sigma(A)$ of $A$ to be $$\max\{|\lambda|:\text{$\lambda$ is an eigenvalue of $A$}\}.$$

Suppose that $K$ is the field of real or complex numbers and $V$ is a vector space over the field $K$. A norm on a vector space $V$ is a function $\|\cdot\|:V\rightarrow[0,\infty)$ such that if $\alpha\in K,\mathbf{x},\mathbf{y}\in V$, then

  1. $\|\alpha\cdot\mathbf{x}\|=|\alpha|\cdot\|\mathbf{x}\|,$

  2. $\mathbf{x}\neq 0$ if and only if $\|\mathbf{x}\|>0$, and

  3. $\|\mathbf{x}+\mathbf{y}\|\leq\|\mathbf{x}\|+\|\mathbf{y}\|$.

It turns out that the spectral radius is always $$\sigma(A)=\lim_{n\rightarrow\infty}\sqrt[n]{\|A^{n}\|}$$ regardless of the norm chosen.

We say that an $n\times n$ matrix $A$ is nilpotent if it satisfies one of the following properties:

  1. $A^{n}=0$.

  2. $A^{k}=0$ for some $k$.

  3. All the eigenvalues of $A$ are $0$.

  4. The spectral radius of $A$ is $0$.

Joseph Van Name avatar
ne flag
I had to edit the question to exclude the case where $L_{F}$ is nilpotent.
Paul Uszak avatar
cn flag
Whilst not a mathy person, I don't recognise many of the terms/concepts you're using. Might this be more suitable for Maths Overflow ( with only a small relevance to cryptography?) Our focus on round functions is principally to do with metrics of confusion and diffusion.
Joseph Van Name avatar
ne flag
I have added some mathematical terminology. The spectral radius $\sigma(L_{F})$ of $L_{F}$ is a measure of something like confusion since it measures how uniform the random variables $Z_{n}$ become as $n\rightarrow\infty$, but $\sigma(L_{F})$ may be hard to calculate or estimate.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.