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: |
Description (last modified by )
I've commited several changes to the BooleanFunction? class:
- The walsh hadamard transform compute the transform of the opposite, I corrected it
- already fixed
- 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.
- ticket: #25742
- 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.
- ticket: #25740
- I added sig_on/sig_off around some c loops.
- ticket: #25739
Attachments (1)
Change History (16)
Changed 11 years ago by
comment:1 Changed 11 years ago by
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
This surely needs more work, especially on 32 bits.
comment:3 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:4 Changed 9 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:5 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 5 years ago by
- 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
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
Sure the patch cannot be used as is.
comment:10 Changed 5 years ago by
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
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: ↓ 13 Changed 5 years ago by
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
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
- 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:
- The walsh hadamard transform compute the transform of the opposite, I corrected it
this is already fixed
- 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
- 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
- I added sig_on/sig_off around some c loops.
sig_check in c loops - ticket: #25739
comment:15 Changed 4 years ago by
- Summary changed from Updates to BooleanFunction class to Metaticket: Updates to BooleanFunction class
Fixes and optimizations.