Hi, I am working on analyzing the input distribution and statistical distances outlined in Table3.py and Theorem5.py, and I have encountered a few issues. I would greatly appreciate your insights on the following three points:

Is it necessary to send one full layout as an the input? FC[id,:]@ matrix @ CF?
I attempted to generate 10 transition matrices, each of size (2^16−1)×(2^16−1) one for each round, by performing the operation: distribution = FC @ matrix @ CF

However, even generating a single matrix appears to be computationally unfeasible (impossible). Is this an expected limitation, or is there an alternative approach I should consider to handle the matrix computations? I tried parallel processing, using GPUs but nothing seems to work.

As an alternative approach, I redirected the standard output distribution back to the input by computing the CF_inverse matrix. I then performed the operation: stationary_distr@CF_inv

This gave me the equivalent of FC @ matrix at the output, and as expected, I obtained a statistical distance of zero for all rounds, confirming the correctness of the approach. However, when I perturb some values of the input distribution (a copy of the stationary_distr), I observed that the statistical distance does not follow a consistent trend; with increasing rounds, the values do not increase as anticipated (sometimes they even decreased). Could this behavior be due to the perturbation technique or a limitation in the statistical distance metric being used?

`def get_distance(matrix, CF, FC, rounds, CF_inv):

scale of matrix

matrix_scale = (CC_SCALE)**rounds
### compute stationary distribution ###
# initialize distribution vector
stationary_distr = np.ones(F, dtype=object)

# probability of each layout is related to the number of plaintexts
# and is equal to 255^{# of non-identical entries}
for full_index in range(F):
    layout_weight = bin(full_index+1).count('1')
    stationary_distr[full_index] = 255**layout_weight
# scale of stationary_distribution
stationary_distr_scale = 2**128 - 1

old_distribution = FC[0, :]@matrix@CF
actual_intermediate = FC[0, :]@matrix
intermediate = old_distribution@CF_inv  # This will be of shape (624,)

# This is the place where we are remapping the output to the input
reConvert = stationary_distr@CF_inv
# perform encryp. using transition matrix
distribution = reConvert@matrix@CF

# I don't know the exact # of values,
matrix_scale = (sum(distribution)*stationary_distr_scale)/sum(stationary_distr)

# verify that both distributions sum to 1
if (sum(distribution)*stationary_distr_scale
    != sum(stationary_distr)*matrix_scale):
    print("VIOLATION")
    return 1

# compute TV distance
total_difference = 0
for i in range(F):
    total_difference += abs(distribution[i]*stationary_distr_scale
                        - stationary_distr[i]*matrix_scale)
    #total_difference += abs(distribution[i]/matrix_scale - stationary_distr[i]/stationary_distr_scale)                    

if(total_difference == 0):
   return 0
else:       
   # return log_2 of the distance
   return (math.log2(total_difference)
        -math.log2(matrix_scale*stationary_distr_scale)
        -math.log2(2))

I would greatly appreciate any guidance or recommendations you may have regarding these observations.

Hello, Thank you for looking into our code, and my apologies for the late reply. Please find comments on your questions below.

Question 1: It is not necessary to send one full layout as the input. In our case, since the number of layouts (2^16-1) is much smaller than the total number of possible inputs (2^128-1), and since one round of random S-boxes randomizes you over the layouts, only working over the layouts is a simplification that we can implement without loss of generality. One could modify our code to see the output distribution when starting from any specific input. Note here that you should get the same results as our layout-based implementation (with one round more).

Question 2: If we want to study the statistical distance from uniform, it suffices to compute the (2^16-1)x(2^16-1) matrix FC@matrix@CF. The ith row of this matrix gives the output distribution over layouts if our input lies in the ith layout. This matrix is very large and computationally expensive to generate. Our approach to avoiding this issue (which is implemented in this repo) is to batch the rows of this matrix and compute a few of them at a time (using parallel computation). We only wanted to verify that a few rounds are sufficiently close to the stationary distribution, which is something that does not require access to the entire matrix at once. Even with the batching and parallelism, our code took several hours to run on a relatively fast personal computer.

Depending on what you want to do with the FC@matrix@CF matrix, you may want to use a similar approach as our code: compute FC@matrix@CF a few rows at a time. An additional heuristic is that layouts with low weight (e.g. when the two inputs agree on everything except one block) should take the longest to reach the stationary distribution. Generating the entire matrix at once may also be slower because it will be too large to store in RAM.

Question 3: I am not sure I followed your setup completely. It is generally the case that starting from any distribution, the statistical distance from the stationary distribution should never increase with the number of rounds. This is known from e.g. the Data Processing Inequality. If you are observing a non-monotone behavior, it could be the case that by inverting the last matrix you are not keeping the starting point the same.

AnPelec / t-wise-ind-SPN

Some queries #2

scale of matrix