Opened 11 years ago

Last modified 4 years ago

#11450 new enhancement

Metaticket: Updates to BooleanFunction class

Reported by: jpflori Owned by: asante
Priority: major Milestone: sage-6.4
Component: cryptography Keywords: boolean function, cryptography, walsh hadamard transform, days94
Cc: jpflori, ruhm, asante Merged in:
Authors: Jean-Pierre Flori Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #25739 #25740 #25742 Stopgaps:

Status badges

Description (last modified by asante)

I've commited several changes to the BooleanFunction? class:

  1. The walsh hadamard transform compute the transform of the opposite, I corrected it
    • already fixed
  1. A lot of computation were made using ints, I change most of them to longs, also adding a warning when computations will overflow. I changed the code to compute the hamming weight to deal with 64 bits integers.
  1. I typed some variables and now store the result of walsh hdamard transform and autocorrelation in c arrays for faster computations, because of that I deleted the _compute_walsh_hadamard_cached method. Of course everything still gets resetted when one modifies the boolean function.
  1. I added sig_on/sig_off around some c loops.

Attachments (1)

trac_11450-bf_long.patch (21.7 KB) - added by jpflori 11 years ago.
Fixes and optimizations.

Download all attachments as: .zip

Change History (16)

Changed 11 years ago by jpflori

Fixes and optimizations.

comment:1 Changed 11 years ago by jpflori

I must acknowledge that this patch could be considered temporary, but IMHO gives better results on modern computers currently.

A more complete solution should involve (transparently) different implementations according to the lenth of integers involved as is done e.g.for integer_mod, i.e. use fixed length integer or gmp/mpir according to the the length of integers involved.

comment:2 Changed 9 years ago by jpflori

This surely needs more work, especially on 32 bits.

comment:3 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 9 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 5 years ago by jpflori

  • Cc ruhm asante added

Some parts of this old patch could be integrated. Especially fixing the sign of the walsh-hadamard transform. The rest is more discussable.

comment:8 Changed 5 years ago by asante

Maybe this should also be split up in several commits -- at the moment it looks a bit like a patchbomb.

I looked at the attached patch and at least in the comments it says the Walsh(-Hadamard)-Transform of f is f(\alpha) = \sum_{x \in \GF(2)^n} f(x) \cdot {-1}^{\langle \alpha, x \rangle} (line 61 vs 70) - in the literature this seems to not be used consistently. In Claude Carlets chapters on boolean functions from "Boolean Models and Methods in Mathematics, Computer Science, and Engineering" this definition is for the Fourier-Transform where the Walsh-Transform is the Fourier-Transform of the sign function of f (what equals the old line). I think the code also computes the Walsh-Transform, but I'll check this again.

comment:9 Changed 5 years ago by jpflori

Sure the patch cannot be used as is.

comment:10 Changed 5 years ago by jpflori

As far as the WH is concerned, I'd say it's the fourier transform of the "sign" function. As stated in the doc it is

sum_{i\in\{0,1\}^n} (-1)^{f(i)\oplus i \cdot j}

(apart from a bizarre wrong change in the patch.)

But the code uses for the sign function:

(bitset_in(self._truth_table,i)<<1)-1

that is

2*f(i)-1 = -(-1)^f(i)

For crypto applications it changes nothing and it also could be valid mathematically, but still this additional minus is not so natural.

comment:11 Changed 5 years ago by ruhm

A ticket of 6-years ago :-o

+1 for fixing the sign in Walsh-Hadamard transform. And as far as I know, in the context of Boolean function for cryptography, the Walsh-Hadamard transform is a Fourier transform of the sign function.

The fix for the sign must also be applied in the implementation of linear approximation matrix of SBox (see https://github.com/sagemath/sage/blob/master/src/sage/crypto/mq/sbox.py#L483). Its just a matter of removing the "negative" sign when calling A.transpose() in line 535.

I suggest this ticket can be changed into a meta-ticket. Then create separate sub-tickets for each issue addressed in the description.

comment:12 follow-up: Changed 5 years ago by jpflori

We can also just close this ticket as wontfix.

I just wanted to draw your attention on the changes I proposed here a long time ago as you seem to be interested in this topic.

comment:13 in reply to: ↑ 12 Changed 5 years ago by ruhm

Replying to jpflori:

We can also just close this ticket as wontfix.

Yes, thats also possible.

I just wanted to draw your attention on the changes I proposed here a long time ago as you seem to be interested in this topic.

Yes, I am :-) and I do think these changes are important. I never notice this ticket before. Now I know why.

Regards, Rusydi

comment:14 Changed 4 years ago by asante

  • Dependencies set to #25739 #25740 #25742
  • Description modified (diff)
  • Keywords days94 added
  • Owner changed from mvngu to asante

OK, so in order to make this a meta ticket, I guess we should split it in some new tickets and put them as dependencies for this ticket?

We have the following things in this ticket:

  1. The walsh hadamard transform compute the transform of the opposite, I corrected it

this is already fixed

  1. A lot of computation were made using ints, I change most of them to longs, also adding a warning when computations will overflow. I changed the code to compute the hamming weight to deal with 64 bits integers.

change to 64-bit integers - ticket: #25742

  1. I typed some variables and now store the result of walsh hdamard transform and autocorrelation in c arrays for faster computations, because of that I deleted the _compute_walsh_hadamard_cached method. Of course everything still gets resetted when one modifies the boolean function.

type variables in cython code - ticket: #25740

  1. I added sig_on/sig_off around some c loops.

sig_check in c loops - ticket: #25739

comment:15 Changed 4 years ago by asante

  • Summary changed from Updates to BooleanFunction class to Metaticket: Updates to BooleanFunction class
Note: See TracTickets for help on using tickets.