Measuring block cipher round function security using spectral radii

In this post, we shall show how spectral radii and more specifically L_{2,d}-spectral radii measure the security of block cipher round functions with small round key size and message size. This post will be mathematical, and it will incorporate subjects such as probability, linear algebra, and some quantum information theory. This post will be based on this previous post. We will leave the topics of algorithms for computing the L_{2,d}-spectral radius, the results of such computations, and our estimates for the security level of block ciphers for future posts.

Suppose that K,X are finite sets and F:K\times X\rightarrow X is a function. For each k\in K, define a mapping F_k:X\rightarrow X by letting F_k(x)=F(k,x). We say that F is a block cipher round function if F_k is a bijection for each k\in K. For our purposes, we shall assume all block ciphers are iterated block ciphers where a ciphertext is obtained from a plaintext simply by composing a sequence of round permutations and applying this sequence of round permutations to the plaintext.

In this post, we shall obtain from spectral radii calculations measures of security M for block cipher round functions such that if F:K\times X\rightarrow X,G:K\times Y\rightarrow Y are block cipher round functions, then M(F)=M(G) whenever the structures (K,X,F,(k)_{k\in K}),(K,Y,G,(k)_{k\in K}) are isomorphic (here, we add a constant for each element in K). We shall also obtain measures of security M where M(F)=M(G) whenever (J,X,F) and (K,Y,G) are isomorphic.

These measures of security are most useful for block cipher round functions F:K\times X\rightarrow X when |K|,|X| are small since we will need to be able to compute the value of these measures of security. Since spectral radii are used to make conclusions about the behavior of block ciphers as the number of rounds approaches infinity, spectral radii are a more useful measure of security for block ciphers with a large number of rounds. Spectral radii calculations are best for evaluating the security of Hashspin-like round functions since for Hashspin, |K|,|X| is small while many rounds of encryption are used. Unfortunately, if |X| is too small, the block cipher round function F is not usable to encrypt data, but the block cipher round function F may still be used to construct a cryptocurrency proof of work problem.

Suppose that F:K\times X\rightarrow X is a block cipher round function. Let \phi:S_X\rightarrow GL(V) be a linear representation of the symmetric group S_X. Then we shall write \rho_{2,d}(\phi,F) for \rho_{2,d}((\phi(F_k))_{k\in K}). If U is a non-trivial invariant subspace of V, and d\geq\dim(U), then \rho_{2,d}(\phi,F)=|K|, so in this case, \rho_{2,d}(\phi,F) does not tell us anything about the block cipher round function F. However, if d<\dim(U) for each non-trivial invariant subspace U of V, then a lower value of \rho_{2,d}(\phi,F) indicates that the block cipher \rho_{2,d}(\phi,F) is more secure. For this post, we shall therefore implicitly assume that d<\dim(U) for each non-trivial invariant subspace U of V, and in practice d will be much smaller than \dim(U) for each non-trivial invariant subspace U of V (this is mainly because \rho_{2,d}(\phi,F) is harder to compute when d is larger).

If (Z_k)_{k\in K}\in M_d(\mathbb{C})^K, and \Gamma((\phi(F_k))_{k\in K},(Z_k)_{k\in K})=\rho_{2,d}((\phi(F_k))_{k\in K}), then (Z_k)_{k\in K} inherits many properties of (\phi(F_k))_{k\in K}, and one should consider (Z_k)_{k\in K} to be one of the elements in M_d(\mathbb{C})^K that is closest to (\phi(F_k))_{k\in K}. Furthermore, \rho_{2,d}(\phi,F) is a measure of how
‘close’ (\phi(F_k))_{k\in K} is to the set M_d(\mathbb{C})^K in the sense that a larger value of \rho_{2,d}(\phi,F) means that the dynamics of (\phi(F_k))_{k\in K} resembles the dynamics of some element of M_d(\mathbb{C})^K more closely. For cryptographic security, we do not want the dynamics of \rho_{2,d}(\phi,F) to resemble the dynamics of M_d(\mathbb{C})^K, so we want the value of \rho_{2,d}(\phi,F) to be small.

If F:K\times X\rightarrow X is a function such that each F_k is selected uniformly at random from S_X and independently, \phi:S_X\rightarrow\text{GL}(V) is an irreducible representation with |V|>1, and d<<\dim(V), then experimental computations suggest that \rho_{2,d}(\phi,F) will tend to be very close to 1. Therefore, if F:K\times X\rightarrow X is a block cipher round function, then F should resemble a system of random permutations, so \rho_{2,d}(\phi,F)\approx 1 suggests that the block cipher round function F is secure, but if \rho_{2,d}(\phi,F)>>1, then one should consider the block cipher round function F to be insecure.

While \rho_{2,d}(\phi,F) is a measure of security for the block cipher F for all representations \phi, since we have limited computational resources, we would like to compute or estimate \rho_{2,d}(\phi,F) for the simplest representations. In particular, we would only like to compute or estimate \rho_{2,d}(\phi,F) for \phi:S_X\rightarrow GL(V) when the dimension of V is minimized.

Let K be a field. Let R_{n,K} denote the ring of all matrices A\in M_n(K) where there is some r where the sum of each row and the sum of each column is r. Define two subspaces K_{h}^{n},K_{l}^{n} of K^{n} by letting K_{h}^{n} consist of all vectors [x_{1},\dots,x_{n}]^{T} where x_{1}+\dots+x_{n}=0 and K_{l}^{n}=\{\lambda[1,\dots,1]^{T}\mid\lambda\in K\} where the vector [1,\dots,1]^{T} has n ones. The subscripts h,l stand for “hyperplane” and “line” respectively. Observe that K^{n}=K_{h}^{n}\oplus K_{l}^{n} except when K has prime characteristic p and p is a factor of n. If K is either the set of real or complex numbers, then K_{h}^{n},K_{l}^{n} are orthogonal. Suppose now that A\in R_{n,K}. The matrix A restricts to a linear operator A_{h}:K_{h}^{n}\rightarrow K_{h}^{n}.

If f:X\rightarrow X is a permutation, then let \phi_{K,p}(f):K^{X}\rightarrow K^{X} denote the permutation matrix that corresponds to f. More specifically, let (e_x)_{x\in X} be the standard basis for K^X; then \phi_{K,p}(f)(e_x)=e_{f(x)} for x\in X. Let \phi_{K,ph}(f):K_{h}^{X}\rightarrow K_{h}^{X} denote the mapping where \phi_{K,ph}(f)=(\phi_{K,p}(f))_h (i.e. \phi_{K,ph}(f) is \phi_{K,p}(f) restricted to the domain K^X_h). Write \phi_{ph} for \phi_{\mathbb{C},ph}. The representation \phi_{ph}:S_X\rightarrow\text{GL}(\mathbb{C}_h^X) shall be called the standard representation of S_X. We shall write \rho_{2,d}(F) for \rho_{2,d}(\phi_{ph},F).

If K has characteristic 0 or if the characteristic of K is not a factor of |X|, then let \pi_h:K^n\rightarrow K_h^n,\pi_l:K^n\rightarrow K_l^n be the projection mappings defined by \pi_h(e_{x_0})=e_{x_0}-\frac{1}{|X|}\sum_{x\in X}e_x and \pi_l(e_{x_0})=\frac{1}{|X|}\sum_{x\in X}e_x whenever x_0\in X. Observe that \pi_h+\pi_l=1_{K^n}. If K\in\{\mathbb{R},\mathbb{C}\}, then the projections \pi_h,\pi_l are orthogonal projections.

Linear approximation of conditional probability.

Suppose that A,B are finite sets, and \mathcal{A},\mathcal{B} are random variables supported on A,B respectively. Let p_{\mathcal{A},\mathcal{B}}:A\times B\rightarrow\mathbb{R} be the joint probability mass function for (\mathcal{A},\mathcal{B}). Then for a\in A,b\in B define the conditional non-uniformity of b given a as \text{cnu}_{\mathcal{B}|\mathcal{A}}(a,b)=\text{cnu}_{\mathcal{B}|\mathcal{A}}(b|a)=p_{\mathcal{A},\mathcal{B}}(a,b)-\frac{1}{|B|}p(a). In other words, \text{cnu}_{\mathcal{B}|\mathcal{A}}(b|a) is the difference between the probability p_{\mathcal{A},\mathcal{B}}(a,b) and what we would expect p_{\mathcal{A},\mathcal{B}}(a,b) to be if the conditional distribution of \mathcal{B} given \mathcal{A}=a were uniform on B. We observe that (1_{\mathbb{R}^A}\otimes\pi_{h})(p_{\mathcal{A},\mathcal{B}}) =\text{cnu}_{\mathcal{B}|\mathcal{A}}. In the case where \mathcal{A},\mathcal{B} are understood, we shall write \text{cnu} for \text{cnu}_{\mathcal{B}\mid\mathcal{A}} and p for p_{\mathcal{A},\mathcal{B}}.

Measures of uniformity for probability vectors

Suppose that F:K\times X\rightarrow X is a block cipher round function. Let A be a complex Banach algebra. Let \phi: S_{X}\rightarrow A be a representation. Suppose that a_{k}\in A for each k\in K, and a_{k}\phi(f)=\phi(f)a_{k} whenever f\in S_{X},k\in K. Set \mathbf{a}=(a_{k})_{k\in K}. Then define M_{\phi,\mathbf{a}}(F)=\rho(\sum_{k\in K}a_{k}\cdot \phi(F_{k})). If \mathbf{a}=(A_k)_{k\in K}\in M_d(\mathbb{C})^K, then define M_{\phi,\mathbf{a}}(F)=\rho(\sum_{k\in K}A_k\otimes \phi(F_k))=\rho(\sum_{k\in K}(A_k\otimes I)(I \otimes \phi(F_k))). We shall write M_{\mathbf{a}}(F) for M_{\phi_{ph},\mathbf{a}}(F) whenever \mathbf{a}=(A_k)_{k\in K}\in M_d(\mathbb{C})^K.

We observe that \phi(g)[\sum_{k\in K}a_{k}\cdot \phi(F_{k})]\phi(g)^{-1}=\sum_{k\in K}a_{k}\cdot \phi(gF_{k}g^{-1}) for each function g. Therefore, whenever (K,X,F,(k)_{k\in K}),(K,Y,G,(k)_{k\in K}) are isomorphic block ciphers, we have M_{\phi,\mathbf{a}}(F)=M_{\phi,\mathbf{a}}(G). The quantity M_{\phi,\mathbf{a}}(F) is actually a measure of security of the block cipher F in the sense that a lower value of M_{\phi,\mathbf{a}}(F) signifies that the block cipher F has a higher level of cryptographic security.

Some attacks

Suppose that F:K\times X\rightarrow X is a block cipher round function. We shall now outline attacks where the quantities of the form M_{\phi,\mathbf{a}}(F) measure the susceptibility of the block cipher round function F to such an attack. We do not expect for these specific attacks to be practical against any reasonable block cipher round function. Nevertheless, it is not too difficult to compute or estimate numerical values for the susceptibility of a block cipher round function F when |K|,|X| are small, and these numerical values can be used as an indicator of the overall security of the block cipher round function F.

Attack 1: (Input-output correlation): Suppose that F:K\times X\rightarrow X is a block cipher round function for a block cipher that uses N rounds of encryption.

Let (\mathcal{K}_n)_{n=0}^{\infty} be a sequence of independent random variables where each \mathcal{K}_n is has the uniform distribution on the set K. Suppose that (\mathcal{X}_n)_{n=0}^{\infty} is a Markov chain where \mathcal{X}_{n+1}=F(\mathcal{K}_n,\mathcal{X}_n) for all n\geq 0 and where \mathcal{X}_0 is an element of X selected uniformly at random. An attacker could potentially exploit some non-uniformity in the distribution of (\mathcal{X}_{0},\mathcal{X}_{N}).

Attack 1-A: Suppose that our N round block cipher is used to encrypt data. If an attacker has a single ciphertext y, and the distribution (\mathcal{X}_{0},\mathcal{X}_{N}) is not uniform, then an attacker may be able to calculate the conditional probability P(\mathcal{X}_0=x|\mathcal{X}_N=y) for each x\in X, and then the attacker will know which plaintext is most likely to correspond to the ciphertext y. If the distribution of (\mathcal{X}_{0},\mathcal{X}_{N}) is uniform (or close enough to uniform), then given a ciphertext y each plaintext is equally likely, so an attacker will not be able to gather any information about the plaintext from a single ciphertext.

Attack 1-B: If a cryptocurrency mining algorithm (like Hashspin) requires one to compute encrypt elements using a block cipher E consisting of applying N rounds of the round function F, then any non-uniformity in (\mathcal{X}_0,\mathcal{X}_N) presents a potential security weakness in the mining algorithm. If the distribution of (\mathcal{X}_{0},\mathcal{X}_N) is not uniform, then given an x\in X, an adversary may be able to produce the most likely values of E_k(x) without needing to compute E_k(x) and without even knowing the key k. A user may therefore use this information to determine which values x\in X are most likely to result in a block reward.

We say that the block cipher round function F:K\times X\rightarrow X is a near root of a Latin square if (\mathcal{X}_{0},\mathcal{X}_{r}) is uniformly distributed for some r. Let \mathbf{a}=(1)_{k\in K}. Then the spectral radius M_{\mathbf{a}}(F) is a measure of how quickly the distribution of (\mathcal{X}_{0},\mathcal{X}_{r}) becomes uniform as r\rightarrow\infty (a lower value of M_{\mathbf{a}}(F) means (\mathcal{X}_{0},\mathcal{X}_{r}) becomes uniform more quickly). In particular, M_{\mathbf{a}}(F)=0 if and only if F is a near root of Latin square.

Attack 2 (Correlation with alternate probabilistic computation):

Suppose that F:K\times X\rightarrow X is a block cipher round function. Furthermore, suppose that (\mathcal{K}_{n})_{n} is a sequence of independent random variables that are uniformly distributed on the set K. Let A be a finite set. Let A_k:\mathbb{C}^A\rightarrow\mathbb{C}^A be a linear transformation for each k\in K. Suppose that \mathcal{Y}_{n} is a sequence of random variables supported on A where P(\mathcal{Y}_{n+1}=b\mid \mathcal{Y}_{n}=a,\mathcal{K}_{n}=k)=\langle A_ke_a,e_b\rangle for each a,b\in A,k\in K. Let \mathcal{X}_0=x_0 and let \mathcal{Y}_0=a_0. Let \mathcal{X}_{n+1}=F(\mathcal{K}_{n},\mathcal{X}_{n}) whenever n\geq 0. Let N be a fixed natural number, and suppose that N rounds of the block cipher are used. Let \mathbf{a}=(\frac{1}{|K|}A_k)_{k\in K}.

Attack 2-B: Suppose that a cryptocurrency mining algorithm requires one to compute N rounds of the block cipher round function F. Then a miner may be able to predict the value of F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0) without needing to compute F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0). A miner would instead probabilistically compute \mathcal{Y}_N subject to the condition that \mathcal{K}_j=k_j for 0\leq j<N. Based only on the value that \mathcal{Y}_N assumes, a user can decide whether the input x_0 and round keys (k_0,\dots,k_{N-1}) are likely to result in a block reward, and if a block reward is unlikely, then the miner would choose not to compute F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0). To thwart this attack, the block cipher round function F should be chosen so that for each a\in A, the conditional distribution of \mathcal{X}_N given \mathcal{Y}_N=a is close to uniform. In particular, the block cipher F should be chosen to minimize \text{cnu}_{\mathcal{X}_N\mid\mathcal{Y}_N}.

Let p(b,y)=p_{\mathcal{Y}_N,\mathcal{X}_N}(b,y) whenever b\in A,y\in X. Then for b\in A,y\in X, we know that

p(b,y)=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes e_{x_0}),e_b\otimes e_y\rangle

and

p(b)=\langle(\frac{1}{|K|}\sum_{k\in K}A_k)^N e_{a_0},e_b\rangle

=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes\sum_{x\in X}e_x),e_b\otimes e_y\rangle.

Therefore,

\text{cnu}(y|b)=p(b,y)-\frac{1}{|X|}p(b)

=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes e_{x_0}-\frac{1}{|X|}\sum_{x\in X}e_x),e_b\otimes e_y\rangle

=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_{ph}(F_k))^N(e_{a_0}\otimes \pi_h(e_{x_0})),e_b\otimes e_y\rangle.

Therefore, since \rho(\sum_{k\in K}\frac{1}{|K|}A_k\otimes\phi_{ph}(F_k))=M_{\mathbf{a}}(F), a lower value of M_{\mathbf{a}}(F) indicates that the block cipher F is more secure.

Attack 3 (Correlation with alternate quantum computation):

Let V be a finite dimensional complex Hilbert space. Suppose that \mathcal{E}_{k}\in C(V) is a quantum channel for each k\in K. For this attack to be effective, (\mathcal{E}_k)_{k\in K} must be simpler than (F_k)_{k\in K} in some sense. We shall now try to predict information about F_{k_n}\dots F_{k_1}(x_0) without needing to fully compute F_{k_n}\dots F_{k_1}(x_0). Suppose that P\in L(V) is a fixed density operator, and x_0\in X is a fixed element. Now, let \mu:J\rightarrow L(V) be a mapping where
\mu(j) is positive semidefinite for j\in J, and \sum_{j\in J}\mu(j)=1_V (i.e. \mu is a measurement).

If i\in J,y\in X, then let p(i,y) be the probability of obtaining the measurement outcome i when applying the measurement \mu to the state \mathcal{E}_{k_n}\dots\mathcal{E}_{k_1}(P) and where
F_{k_n}\dots F_{k_1}(x_0)=y where k_1,\dots,k_n\in K are selected uniformly at random and independently. We would like for \text{cnu}(y|i) to be as close to zero as possible. We shall use spectral radii to determine the limiting behavior of \text{cnu}(y|i). We know that p(i,y)=\langle\sum_{k\in K}(\frac{1}{|K|}(\mathcal{E}_k\otimes\phi_p(F_k)))^n(P\otimes e_{x_0}),\mu(i)\otimes e_{y}\rangle. Furthermore, p(i)=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k)^n(P),\mu(i)\rangle=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\sum_{x\in X}e_x),\mu(i)\otimes e_y\rangle.

Therefore,

\text{cnu}(y|i)=p(i,y)-\frac{1}{|X|}p(i)

=\langle (\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes   e_{x_0}),\mu(i)\otimes e_y\rangle-\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\frac{1}{|X|}\cdot\sum_{x\in X}e_x),\mu(i)\otimes e_y\rangle

=\langle\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\pi_h(e_{x_0})),\mu(i)\otimes e_y\rangle

=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_{ph}(F_k))^n(P\otimes\pi_h(e_{x_0}),\mu(i)\otimes e_y\rangle.

Let \mathbf{a}=(\frac{1}{K}\mathcal{E}_k)_{k\in K}. Then since \rho(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_{ph}(F_k))=M_\mathbf{a}(F), a lower value of M_\mathbf{a}(F) gives evidence that the block cipher round function F has a higher level of cryptographic security.

We do not expect for a quantum attack similar to this one to be effective against block cipher round functions, but this attack still illustrates how spectral radii calculations can be used to predict a block cipher’s level of cryptographic security.

We will leave it to the reader to find other kinds of representations \phi:S_X\rightarrow V and attacks such that a lower value of M_{\phi,\mathbf{a}}(F) indicates that F is more resistant to such attacks.

Universality

Let V be a real or complex finite dimensional vector space. I claim that at least when F is a near root Latin square, then for all \mathbf{a}\in L(V)^K, there is a version of Attack 2 so that the value of M_{\mathbf{a}}(F) precisely measures how resistant the block cipher F is to this version of Attack 2.

By considering every complex vector space of dimension g as a real vector space of dimension 2g, for simplicity, we shall assume that the vector space V is a real vector space and that F is a near root Latin square. We can also assume that V=\mathbb{R}^d_h for some d. Let t>0. Let \mathbf{a}=(A_k)_{k\in K}. Suppose that B_k=t\cdot A_k\oplus I_l where I_l is the identity function on \mathbb{R}^d_l. Then by choosing a small enough t>0, we can guarantee that B_k has only non-negative entries and is therefore doubly stochastic for each k\in K. Let \mathbf{b}=(B_k)_{k\in K}. In this case,

M_{\mathbf{b}}(F)=\rho(\sum_{k\in K}B_k\otimes\phi_{ph}(F_k))=\rho(\sum_{k\in K}(A_k\cdot t\oplus I_l)\otimes\phi_{ph}(F_k))

=\max(\rho(\sum_{k\in K}A_k\cdot t\otimes\phi_{ph}(F_k)),\rho(\sum_{k\in K}\phi_{ph}(F_k))) =\rho(\sum_{k\in K}A_k\cdot t\otimes\phi_{ph}(F_k))=t\cdot M_\mathbf{a}(F).

Here, M_\mathbf{b}(F) is a measure of how susceptible F is to a version of Attack 2, so M_\mathbf{a}(F) is also a measure of how susceptible F is to a version of Attack 2 even though \mathbf{a} is an arbitrary collection of matrices.

Maximization on a compact set

Let V be a finite dimensional real or complex vector space. Let \mathcal{C}\subseteq L(V)^r be a compact set. Then define \rho_{\mathcal{C}}(A_1,\dots,A_r) to be the maximum value of \rho(X_1\otimes A_1+\dots+X_r\otimes A_r) such that (X_1,\dots,X_r)\in\mathcal{C}, and set M_{\phi,\mathcal{C}}(F)=\rho_{\mathcal{C}}((\phi(F_k))_{j\in K}) whenever \phi:S_X\rightarrow \text{Gl}_n(\mathbb{C}) is a linear representation and F:K\times X\rightarrow X is a block cipher round function. Let M_{\mathcal{C}}(F)=M_{\phi_{ph},\mathcal{C}}(F). The measures of security of the form M_{\phi,\mathcal{C}}(F) are typically more useful than the measures of security of the form M_{\phi,\mathbf{a}}(F) since it is more important to know how well F fares against an optimized attack than it is to know how well F fares against unoptimized versions of Attacks 1-3. Given a specific integer d\geq 1, the following sets (\mathcal{C}_{r,d,i})_{i=1}^{15} are sets where M_{\mathcal{C}_{r,d,i}}(F) is a useful measure of security of the block cipher round function F. We set \mathcal{C}_{r,d,i}\subseteq M_d(\mathbb{C})^r for 1\leq i\leq 10 and we set \mathcal{C}_{r,d,i}\subseteq L(M_d(\mathbb{C}))^r for 11\leq i\leq 15.

Suppose that (X_1,\dots,X_r)\in M_d(\mathbb{C})^r.

  1. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,1} iff each X_j is row stochastic.
  2. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,2} iff each X_j is column stochastic.
  3. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,3} iff each X_j is doubly stochastic.
  4. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,4} iff each X_j is a permutation matrix.
  5. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,5} iff each X_j is a row stochastic 0-1 matrix.
  6. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,6} iff each X_j is a column stochastic 0-1 matrix.
  7. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,7} iff \Phi(X_1,\dots,X_r) is a quantum channel.
  8. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,8} iff \Phi(X_1,\dots,X_r) is unital.
  9. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,9} iff \Phi(X_1,\dots,X_r) is a quantum channel and each X_j is real.
  10. (X_1,\dots,X_r)\in\mathcal{C}_{r,d,10} iff \Phi(X_1,\dots,X_r) is unital and each X_j is real.
  11. (Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,11} iff each Z_j is a quantum channel.
  12. (Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,12} iff each Z_j is a completely positive and unital.
  13. (Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,13} iff each Z_j is a unital channel.
  14. (Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,14} iff each Z_j is a mixed unitary channel.
  15. (Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,15} iff each Z_j is a unitary channel.

Normalization

While M_{\phi,\mathbf{a}}(F) is a measure of security for block cipher round functions F, this measure of security is not normalized since M_{\phi,k\mathbf{a}}(F)=k\cdot M_{\phi,\mathbf{a}}(F) for each scalar k. We shall show that if F is an ideal block cipher round function, and \phi:S_X\rightarrow\text{Gl}(V) is a linear representation and V has no invariant subspace of dimension 1, then M_{\phi,\mathbf{a}}(F)=\rho_{2}(\mathbf{a}). Now, define N_{\phi,\mathbf{a}}(F)=\frac{M_{\phi,k\mathbf{a}}(F)}{\rho_2(\mathbf{a})}. Then N_{\phi,\mathbf{a}}(F) measures the factor by which M_{\phi,\mathbf{a}}(F) deviates from the ideal value \rho_2(\mathbf{a}). In practice, the value of M_{\phi,\mathbf{a}}(F) will typically be close to \rho_2(\mathbf{a}). Therefore, the values of N_{\phi,\mathbf{a}}(F) will typically be close to 1 which is much easier to work with than a value close to \rho_2(\mathbf{a}).

The maximum value of N_{\phi,\mathbf{a}}(F) for \mathbf{a}\in M_d(\mathbb{C})^K is simply \rho_{2,d}(\phi,F). Therefore, \rho_{2,d}(\phi,F) is a measure of security of the block cipher F. We observe that 1\leq\rho_{2,d}(\phi,F)\leq\sqrt{|K|}, and that a value of \rho_{2,d}(\phi,F) that is closer to 1 indicates a greater level of cryptographic security.

If X,Y are real or complex random variables, then define the covariance between X and Y by \text{Cov}(X,Y)=E[(X-E(X))\overline{(Y-E(Y))}] whenever this quantity exists.

If X is a random variable with values in a finite dimensional inner product space V and \text{Var}(\langle v,X\rangle) exists for each v\in V, then there is a unique (necessarily positive semidefinite P) with \langle Pu,v\rangle=\text{Cov}(\langle u,X\rangle,\langle v,X\rangle). We shall write \text{Cov}(X) for this positive semidefinite matrix P so that \langle \text{Cov}(X)u,v\rangle=\text{Cov}(\langle u,X\rangle,\langle v,X\rangle).

Theorem:

  1. \text{Cov}(X+Y)=\text{Cov}(X)+\text{Cov}(Y) whenever X,Y are independent.
  2. \text{Cov}(AX)=A\text{Cov}(X)A^*.

Proof:

  1. \langle\text{Cov}(X+Y)u,v\rangle=\text{Cov}(\langle u,X+Y\rangle,\langle v,X+Y\rangle)

=\text{Cov}(\langle u,X\rangle+\langle u,Y\rangle,\langle v,X\rangle+\langle v,Y\rangle)

=\text{Cov}(\langle u,X\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,X\rangle ,\langle v,Y\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,Y\rangle )

=\text{Cov}(\langle u,X\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,Y\rangle ) =\langle\text{Cov}(X)u,v\rangle+\langle\text{Cov}(Y)u,v\rangle=\langle(\text{Cov}(X)+\text{Cov}(Y))u,v\rangle.

Therefore, \text{Cov}(X+Y)=\text{Cov}(X)+\text{Cov}(Y).

  1. \langle\text{Cov}(AX)u,v\rangle=\text{Cov}(\langle u,AX\rangle,\langle v,AX\rangle)

=\text{Cov}(\langle A^*u,X\rangle,\langle A^*v,X\rangle)=\langle\text{Cov}(X)A^*u,A^*v\rangle=\langle A\text{Cov}(X)A^*u,v\rangle.

Therefore, \text{Cov}(AX)=A\text{Cov}(X)A^*. Q.E.D.

Suppose that V is a finite dimensional inner product space, and A_{0},\dots,A_{r-1}:V\rightarrow V are linear operators. Suppose now that (X_{n})_{n=0}^{\infty} is a sequence of independent random variables. Suppose that there is an operator Q_{0} with \text{Cov}(X_{n})=Q_{0} for all n.

Let \iota:\{0,\dots,r-1\}\times\omega\rightarrow\omega be an injective function. Define a collection of random variables (Z_{n,m})_{n,m\geq 0} by letting Z_{n,m+1}=A_{0}Z_{\iota(0,n),m}+\dots+A_{r-1}Z_{\iota(r-1,n),m} for all m,n\geq 0.

Observe that for each m\geq 0, the sequence (Z_{n,m})_{n\geq 0} is a sequence of independent random variables. Observe that there is a sequence of operators (Q_m)_{m} where \text{Cov}(Z_{n,m})=Q_m for all m,n\geq 0. In this case, we have Q_{m+1}=\Phi(A_0,\dots,A_{r-1})(Q_m) for all m\geq 0, so Q_m=\Phi(A_0,\dots,A_{r-1})^m(Q_0) for all m\geq 0.

Lemma: Suppose that x is a normally distributed random variable with values
in V and whose covariance operator is the identity operator. If V is a complex inner product space, then suppose that when we consider V as a real inner product space, then the covariance operator is \frac{1}{2}I where I is the identity operator on V. If u,v,a\in V, then

  1. \text{Tr}(A)=E(\langle Ax,x\rangle),
  2. \langle u,v\rangle=E(\langle x,v\rangle\cdot\langle u,x\rangle), and
  3. E(\|\langle x,a\rangle\|^2)=E(\|\langle a,x\rangle\|^2)=\|a\|^2

Proof:

  1. Suppose that e_1,\dots,e_n is a basis for V and
    x=x_1e_1+\dots+x_ne_n where x_1,\dots,x_n are real or complex-valued random variables. Then E(\langle Ax,x\rangle=\sum_{i,j}E(\langle x_iAe_i,x_je_j\rangle)
    =\sum_{i,j}E(x_i\cdot\overline{x_j})\langle Ae_i,e_j\rangle =\sum_{i}\langle Ae_i,e_i\rangle=\text{Tr}(A).
  1. \langle u,v\rangle=v^*u=\text{Tr}(v^*u)=\text{Tr}(uv^*) =E(\langle uv^*x,x\rangle) =E(v^*x\langle u,x\rangle)
    =E(\langle x,v\rangle\cdot\langle u,x\rangle).
  2. This is a special case of 2. Q.E.D.

Proposition: E(\|X-E(X)\|^2)=\text{Tr}(\text{Cov}(X)).

Proof: Let y be a randomly selected element of V where y is given a normal distribution. As before, if V is real, then suppose that the covariance matrix of y is the identity matrix, and if V is complex, then when we consider V as a real vector space, suppose that the covariance matrix of V is 1/2 of the identity matrix. To make the proof simpler, we shall assume that E(X)=0. Then

\text{Tr}(\text{Cov}(X))=E_{y}(\langle\text{Cov}(X)y,y\rangle)=E_y(\text{Cov}(\langle y,X\rangle,\langle y,X\rangle))=E_y(\text{Var}_X(\langle y,X\rangle))

=E_y(E_X(|\langle y,X\rangle|^2))=E_X(E_y|\langle y,X\rangle|^2)=E_X(\|X\|^2). Q.E.D.

Therefore, E(\|Z_{n,m}-E(Z_{n,m})\|^2)=\text{Tr}(\Phi(A_0,\dots,A_{r-1})^{m}(Q_0)). We conclude that, \rho_2(A_0,\dots,A_{r-1}) is a measure of the growth rate of \|Z_{n,m}-E(Z_{n,m})\|.

The function \iota should be considered as an ideal block cipher round function. Suppose now that E(Z_{n,m})=0 for all m,n. The collection of random variables (Z_{n,m})_{n=0}^{\infty} should be considered to be an ideal model of (A_0\otimes\phi_{ph}(F_0)+\dots+A_{r-1}\otimes\phi_{ph}(F_{r-1}))^m(\pi_h(\mathbf{x})) where each entry in \mathbf{x} has the same distribution as Z_{n,0} and is independent. Therefore, if F is a good block cipher round function, then we should expect to have M_{\mathbf{a}}(F)\approx\phi_2(\mathbf{a}).

When V is a real vector space and A_0,\dots,A_{r-1} is in general position, then the central limit theorem applies to the random variables Z_{n,m}. As m\rightarrow\infty, the random variables Z_{n,m} will approach a multivariate normal distribution (and the standard proof of the multivariate central limit theorem that uses characteristic functions applies to the random variables Z_{n,m}).

Suppose that F:K\times X\rightarrow X is a block cipher round function. Then whenever (v_x)_{x\in X} is a dominant eigenvector for \sum_{k\in K}A_k\otimes\phi_{ph}(F_k), we should expect for (v_x)_{x\in X} to be approximately normally distributed in V and statistically significant deviations from normality may indicate that the block cipher round function F has a security weakness.

Conclusion

The measure of security \rho_{2,d}(F) of a block cipher round function F is interesting for purely mathematical reasons but also measures how effective low memory attacks are against F compared to that of an ideal block cipher round function. The measure of security \rho_{2,d}(F) seems more meaningful than measures of security M_{\phi,\mathcal{C}}(F) since \rho_{2,d}(F) takes into account all values \rho(\sum_{k\in K}A_k\otimes\phi(F_k)) where (A_k)_{k\in K}\in M_d(\mathbb{C})^K instead of restricting one’s attention to when (A_k)_{k\in K}\in\mathcal{C} for some compact set \mathcal{C}. Estimating M_{\phi,\mathcal{C}}(F) may be awkward since \rho(\sum_{k\in K}A_k\otimes\phi(F_k)) in practice would have many local but not global maxima (A_k)_{k\in K}\in\mathcal{C} while in practice, one encounters very few local but not global maxima when estimating \rho_{2,d}(F).

While we believe that \rho_{2,d}(F) is a good measure of security to the block cipher F, it has a few disadvantages. It is a new measure of security that has not yet stood the test of time, and \rho_{2,d}(F) may be difficult to estimate when the block cipher round function F is too complex or large. \rho_{2,d}(F) also only measures the security against attacks that require an extremely limited amount of memory. We therefore recommend using \rho_{2,d} to measure the security of block ciphers when used in conjunction with other measures of security.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: