[Crypto] S-box Linear Approximation Matrix scaling

[Friedrich Wiemer]

I recently stumbled across the fact that the implementation of SBox().linear_approximation_matrix() returns scaled Fourier coefficients.
While the documentation says exactly this, i.e., "[the matrix] encodes the bias[es]", my personal intuition is that this matrix should contain the actual Fourier coefficients.
In fact, the matrix is computed using the Fourier-Walsh transform for each component function and then scales the resulting matrix accordingly. On the other side, this scaling is then for other methods reversed (e.g. in the `nonlinearity` and `linearity` method).

Of course, my argument is basically only personal taste, but my feeling is that containing the unscaled Fourier coefficients is, what one would assume when only looking at the API and not at the documentation.
So, I propose to change this, but would like to hear your opinions on this?

[Rusydi H. Makarim]

Hi Friedrich,

The way it is defined in the code is consistent with the paper mentioned in the documentation (H. Heys paper on tutorial of differential and linear cryptanalysis) which, I believe, is used by many cryptanalysis researchers or students to learn differential and linear cryptanalysis for the first time. Together with the paper, SageMath can be a companion educational tool for introducing the concept of linear and differential cryptanalysis. In that respect i think its more beneficial to change its description in the documentation rather than changing the function.

Regards,
Rusydi

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Samuel Lelievre]

How about adding an optional argument "scaled", defaulting to True:

Then if S is an S-box, for instance

    sage: from sage.crypto.sbox import SBox

    sage: S = SBox(7,6,0,4,2,5,1,3)

one could call

    sage: S.linear_approximation_matrix()

or

    sage: S.linear_approximation_matrix(scaled=True)

to get the scaled matrix, and

    sage: S.linear_approximation_matrix(scaled=False)

to get the unscaled matrix.

[Friedrich Wiemer]

Ah, thats a very good idea!
Then I would suggest to extend this scaled argument to the following:

"bias" - return actual biases that is in [-0.5, 0.5]
"correlation" - return correlations, so in [-1, 1]
"absolute bias" - return biases*2^n (default)
"fourier coefficient" - return fourier coefficients, in [-2^n, 2^n]

With this, I guess, the doc-string can also be improved to make the default behavior clearer.

[Friedrich Wiemer]

I opened a ticket for this: #24819