In this post, we shall show how spectral radii and more specifically 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 spectral radius, the results of such computations, and our estimates for the security level of block ciphers for future posts.
Suppose that are finite sets and is a function. For each , define a mapping by letting . We say that is a block cipher round function if is a bijection for each . 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 for block cipher round functions such that if are block cipher round functions, then whenever the structures are isomorphic (here, we add a constant for each element in ). We shall also obtain measures of security where whenever and are isomorphic.
These measures of security are most useful for block cipher round functions when 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 Hashspinlike round functions since for Hashspin, is small while many rounds of encryption are used. Unfortunately, if is too small, the block cipher round function is not usable to encrypt data, but the block cipher round function may still be used to construct a cryptocurrency proof of work problem.
Suppose that is a block cipher round function. Let be a linear representation of the symmetric group . Then we shall write for . If is a nontrivial invariant subspace of , and , then , so in this case, does not tell us anything about the block cipher round function . However, if for each nontrivial invariant subspace of , then a lower value of indicates that the block cipher is more secure. For this post, we shall therefore implicitly assume that for each nontrivial invariant subspace of , and in practice will be much smaller than for each nontrivial invariant subspace of (this is mainly because is harder to compute when is larger).
If , and , then inherits many properties of , and one should consider to be one of the elements in that is closest to . Furthermore, is a measure of how
‘close’ is to the set in the sense that a larger value of means that the dynamics of resembles the dynamics of some element of more closely. For cryptographic security, we do not want the dynamics of to resemble the dynamics of , so we want the value of to be small.
If is a function such that each is selected uniformly at random from and independently, is an irreducible representation with , and , then experimental computations suggest that will tend to be very close to . Therefore, if is a block cipher round function, then should resemble a system of random permutations, so suggests that the block cipher round function is secure, but if , then one should consider the block cipher round function to be insecure.
While is a measure of security for the block cipher for all representations , since we have limited computational resources, we would like to compute or estimate for the simplest representations. In particular, we would only like to compute or estimate for when the dimension of is minimized.
Let be a field. Let denote the ring of all matrices where there is some where the sum of each row and the sum of each column is . Define two subspaces of by letting consist of all vectors where and where the vector has ones. The subscripts stand for “hyperplane” and “line” respectively. Observe that except when has prime characteristic and is a factor of . If is either the set of real or complex numbers, then are orthogonal. Suppose now that . The matrix restricts to a linear operator .
If is a permutation, then let denote the permutation matrix that corresponds to . More specifically, let be the standard basis for ; then for . Let denote the mapping where (i.e. is restricted to the domain ). Write for . The representation shall be called the standard representation of . We shall write for .
If has characteristic or if the characteristic of is not a factor of , then let be the projection mappings defined by and whenever Observe that . If , then the projections are orthogonal projections.
Linear approximation of conditional probability.
Suppose that are finite sets, and are random variables supported on respectively. Let be the joint probability mass function for . Then for define the conditional nonuniformity of given as . In other words, is the difference between the probability and what we would expect to be if the conditional distribution of given were uniform on We observe that In the case where \mathcal{A},\mathcal{B} are understood, we shall write for and for .
Measures of uniformity for probability vectors
Suppose that is a block cipher round function. Let be a complex Banach algebra. Let be a representation. Suppose that for each , and whenever . Set . Then define . If , then define . We shall write for whenever .
We observe that for each function . Therefore, whenever are isomorphic block ciphers, we have . The quantity is actually a measure of security of the block cipher in the sense that a lower value of signifies that the block cipher has a higher level of cryptographic security.
Some attacks
Suppose that is a block cipher round function. We shall now outline attacks where the quantities of the form measure the susceptibility of the block cipher round function 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 when are small, and these numerical values can be used as an indicator of the overall security of the block cipher round function .
Attack 1: (Inputoutput correlation): Suppose that is a block cipher round function for a block cipher that uses rounds of encryption.
Let be a sequence of independent random variables where each is has the uniform distribution on the set Suppose that is a Markov chain where for all and where is an element of selected uniformly at random. An attacker could potentially exploit some nonuniformity in the distribution of .
Attack 1A: Suppose that our round block cipher is used to encrypt data. If an attacker has a single ciphertext , and the distribution is not uniform, then an attacker may be able to calculate the conditional probability for each , and then the attacker will know which plaintext is most likely to correspond to the ciphertext . If the distribution of is uniform (or close enough to uniform), then given a ciphertext each plaintext is equally likely, so an attacker will not be able to gather any information about the plaintext from a single ciphertext.
Attack 1B: If a cryptocurrency mining algorithm (like Hashspin) requires one to compute encrypt elements using a block cipher consisting of applying rounds of the round function , then any nonuniformity in presents a potential security weakness in the mining algorithm. If the distribution of is not uniform, then given an , an adversary may be able to produce the most likely values of without needing to compute and without even knowing the key . A user may therefore use this information to determine which values are most likely to result in a block reward.
We say that the block cipher round function is a near root of a Latin square if is uniformly distributed for some . Let . Then the spectral radius is a measure of how quickly the distribution of becomes uniform as (a lower value of means becomes uniform more quickly). In particular, if and only if is a near root of Latin square.
Attack 2 (Correlation with alternate probabilistic computation):
Suppose that is a block cipher round function. Furthermore, suppose that is a sequence of independent random variables that are uniformly distributed on the set . Let be a finite set. Let be a linear transformation for each . Suppose that is a sequence of random variables supported on where for each . Let and let . Let whenever Let be a fixed natural number, and suppose that rounds of the block cipher are used. Let .
Attack 2B: Suppose that a cryptocurrency mining algorithm requires one to compute rounds of the block cipher round function . Then a miner may be able to predict the value of without needing to compute . A miner would instead probabilistically compute subject to the condition that for . Based only on the value that assumes, a user can decide whether the input and round keys are likely to result in a block reward, and if a block reward is unlikely, then the miner would choose not to compute . To thwart this attack, the block cipher round function should be chosen so that for each , the conditional distribution of given is close to uniform. In particular, the block cipher should be chosen to minimize .
Let whenever . Then for , we know that
and
.
Therefore,
Therefore, since , a lower value of indicates that the block cipher is more secure.
Attack 3 (Correlation with alternate quantum computation):
Let be a finite dimensional complex Hilbert space. Suppose that is a quantum channel for each For this attack to be effective, must be simpler than in some sense. We shall now try to predict information about without needing to fully compute . Suppose that is a fixed density operator, and is a fixed element. Now, let be a mapping where
is positive semidefinite for , and (i.e. is a measurement).
If , then let be the probability of obtaining the measurement outcome when applying the measurement to the state and where
where are selected uniformly at random and independently. We would like for to be as close to zero as possible. We shall use spectral radii to determine the limiting behavior of . We know that . Furthermore,
Therefore,
Let . Then since , a lower value of gives evidence that the block cipher round function 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 and attacks such that a lower value of indicates that is more resistant to such attacks.
Universality
Let be a real or complex finite dimensional vector space. I claim that at least when is a near root Latin square, then for all , there is a version of Attack 2 so that the value of precisely measures how resistant the block cipher is to this version of Attack 2.
By considering every complex vector space of dimension as a real vector space of dimension , for simplicity, we shall assume that the vector space is a real vector space and that is a near root Latin square. We can also assume that for some . Let . Let . Suppose that where is the identity function on . Then by choosing a small enough , we can guarantee that has only nonnegative entries and is therefore doubly stochastic for each . Let . In this case,
.
Here, is a measure of how susceptible is to a version of Attack 2, so is also a measure of how susceptible is to a version of Attack 2 even though is an arbitrary collection of matrices.
Maximization on a compact set
Let be a finite dimensional real or complex vector space. Let be a compact set. Then define to be the maximum value of such that , and set whenever is a linear representation and is a block cipher round function. Let . The measures of security of the form are typically more useful than the measures of security of the form since it is more important to know how well fares against an optimized attack than it is to know how well fares against unoptimized versions of Attacks 13. Given a specific integer , the following sets are sets where is a useful measure of security of the block cipher round function . We set for and we set for .
Suppose that .
 iff each is row stochastic.
 iff each is column stochastic.
 iff each is doubly stochastic.
 iff each is a permutation matrix.
 iff each is a row stochastic 01 matrix.
 iff each is a column stochastic 01 matrix.
 iff is a quantum channel.
 iff is unital.
 iff is a quantum channel and each is real.
 iff is unital and each is real.
 iff each is a quantum channel.
 iff each is a completely positive and unital.
 iff each is a unital channel.
 iff each is a mixed unitary channel.
 iff each is a unitary channel.
Normalization
While is a measure of security for block cipher round functions , this measure of security is not normalized since for each scalar . We shall show that if is an ideal block cipher round function, and is a linear representation and has no invariant subspace of dimension , then . Now, define . Then measures the factor by which deviates from the ideal value . In practice, the value of will typically be close to . Therefore, the values of will typically be close to which is much easier to work with than a value close to .
The maximum value of for is simply . Therefore, is a measure of security of the block cipher . We observe that , and that a value of that is closer to indicates a greater level of cryptographic security.
If are real or complex random variables, then define the covariance between and by whenever this quantity exists.
If is a random variable with values in a finite dimensional inner product space and exists for each , then there is a unique (necessarily positive semidefinite ) with . We shall write for this positive semidefinite matrix so that .
Theorem:
 whenever are independent.
 .
Proof:
Therefore, .
Therefore, . Q.E.D.
Suppose that is a finite dimensional inner product space, and are linear operators. Suppose now that is a sequence of independent random variables. Suppose that there is an operator with for all .
Let be an injective function. Define a collection of random variables by letting for all
Observe that for each , the sequence is a sequence of independent random variables. Observe that there is a sequence of operators where for all . In this case, we have for all , so for all .
Lemma: Suppose that is a normally distributed random variable with values
in and whose covariance operator is the identity operator. If is a complex inner product space, then suppose that when we consider as a real inner product space, then the covariance operator is where is the identity operator on . If , then
 ,
 , and
Proof:
 Suppose that is a basis for and
where are real or complexvalued random variables. Then
.

.  This is a special case of 2. Q.E.D.
Proposition:
Proof: Let be a randomly selected element of where is given a normal distribution. As before, if is real, then suppose that the covariance matrix of is the identity matrix, and if is complex, then when we consider as a real vector space, suppose that the covariance matrix of is of the identity matrix. To make the proof simpler, we shall assume that . Then
Q.E.D.
Therefore, We conclude that, is a measure of the growth rate of
The function should be considered as an ideal block cipher round function. Suppose now that for all . The collection of random variables should be considered to be an ideal model of where each entry in has the same distribution as and is independent. Therefore, if is a good block cipher round function, then we should expect to have .
When is a real vector space and is in general position, then the central limit theorem applies to the random variables . As , the random variables 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 ).
Suppose that is a block cipher round function. Then whenever is a dominant eigenvector for , we should expect for to be approximately normally distributed in and statistically significant deviations from normality may indicate that the block cipher round function has a security weakness.
Conclusion
The measure of security of a block cipher round function is interesting for purely mathematical reasons but also measures how effective low memory attacks are against compared to that of an ideal block cipher round function. The measure of security seems more meaningful than measures of security since takes into account all values where instead of restricting one’s attention to when for some compact set . Estimating may be awkward since in practice would have many local but not global maxima while in practice, one encounters very few local but not global maxima when estimating .
While we believe that is a good measure of security to the block cipher , it has a few disadvantages. It is a new measure of security that has not yet stood the test of time, and may be difficult to estimate when the block cipher round function is too complex or large. also only measures the security against attacks that require an extremely limited amount of memory. We therefore recommend using to measure the security of block ciphers when used in conjunction with other measures of security.