Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Maaartin on 21 Sep 2009 15:33 On Sep 21, 4:53 pm, biject <biject.b...(a)gmail.com> wrote: > I found the paper very interesting. But why do > you think it makes no "strong boxes" doesn't the > paper imply if you have "strong boxes" of n by n then > using methods in the paper you get a strong box of > n+1 by n+1. Yes, I get larger "strong boxes" according to the paper. But they satisfy only the 0-th order SAC (according to his dissertation), which is not very much. Just look at the hint in my previous posting. > The question is if you have every box meeting the > criteria for n by n does the technique generate all > the s boxes of n+1 by n+1 meeting the same criteria? With criteria given as 0-th order SAC, yes. With stricter criteria, no.
From: Mok-Kong Shen on 21 Sep 2009 17:44 Maaartin wrote: > On Sep 21, 11:07 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> Maaartin wrote: >>> The design method is rather trivial recursion. To my own surprise I >>> found it again: >>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.4537 >>> Just look at the pictures at the end and you'll see that 1. it works. >>> 2. it makes no "strong" boxes (whatever it means). >> Thank you very much (even though my poor knowledge doesn't allow >> me to capture too much of the paper). >> >> BTW, I am afraid that, being a layman, I may have entirely >> misunderstood SAC. I understood till now that, if any input bit >> of an arbitraily given input is flipped, then exactly half of >> the bits of the corresponding output will be flipped. Is that >> correct or not? Excuse me for this very dumb question. > > According to the paper, for the AVALANCHE EFFECT the following must > hold: ON THE AVERAGE exactly half of the output bits changes when a > single input gets flipped. Here it doesn't matter what bits changes > how often (so changing the first bit every time would be fine if the > other bits changed sometimes, so the average taken over all input > combinations and all output bits would be 50%). > > SAC is more specific, it requires that "each of the output bits > changes with a probability of one half." So still "on the average" > taken over all input combinations x, but now each output bit must > behave according to the rule. This is just a different formulation > (taken from wiki) of what's stated in the formula in the paper. > > The paper is IMHO easy - just find there the example of a 3 bit SAC > function and extend it to 4 bits according to the simpler picture > (fig. 2) at the end of the paper. Verify that the condition still > holds. Maybe extending it once again gives you more confidence in your > understanding. After you see it works, think about a problem with it > (hint: extend it 100 times using the same k and j). Thank you very much for the explanation. The condition I stated in the previous post indeed isn't SAC. Nevertheless, I would like now to ask some questions about that: (1) Does there exist n bit (n even, n>2) bijective functions such that, for all possible inputs, if any bit of the input is flipped, then 'exactly' half of the bits of the corresponding output will be flipped? (2) If the answer to (1) is yes, is there a effective method of finding such functions? (3) If the answer to (1) is yes, how do such functions compare with functions satisfying SAC (from the viewpoint of crypto)? BTW, I found the paper by Kwangjo Kim, which you said in the other post you failed to find again: http://citeseer.ist.psu.edu/336097.html Thanks, M. K. Shen
From: Greg Rose on 21 Sep 2009 20:57 In article <h98s46$u64$00$1(a)news.t-online.com>, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: >Maaartin wrote: >> On Sep 21, 11:07 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >>> Maaartin wrote: >>>> The design method is rather trivial recursion. To my own surprise I >>>> found it again: >>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.4537 >>>> Just look at the pictures at the end and you'll see that 1. it works. >>>> 2. it makes no "strong" boxes (whatever it means). >>> Thank you very much (even though my poor knowledge doesn't allow >>> me to capture too much of the paper). >>> >>> BTW, I am afraid that, being a layman, I may have entirely >>> misunderstood SAC. I understood till now that, if any input bit >>> of an arbitraily given input is flipped, then exactly half of >>> the bits of the corresponding output will be flipped. Is that >>> correct or not? Excuse me for this very dumb question. >> >> According to the paper, for the AVALANCHE EFFECT the following must >> hold: ON THE AVERAGE exactly half of the output bits changes when a >> single input gets flipped. Here it doesn't matter what bits changes >> how often (so changing the first bit every time would be fine if the >> other bits changed sometimes, so the average taken over all input >> combinations and all output bits would be 50%). >> >> SAC is more specific, it requires that "each of the output bits >> changes with a probability of one half." So still "on the average" >> taken over all input combinations x, but now each output bit must >> behave according to the rule. This is just a different formulation >> (taken from wiki) of what's stated in the formula in the paper. >> >> The paper is IMHO easy - just find there the example of a 3 bit SAC >> function and extend it to 4 bits according to the simpler picture >> (fig. 2) at the end of the paper. Verify that the condition still >> holds. Maybe extending it once again gives you more confidence in your >> understanding. After you see it works, think about a problem with it >> (hint: extend it 100 times using the same k and j). > >Thank you very much for the explanation. The condition I stated >in the previous post indeed isn't SAC. Nevertheless, I would like >now to ask some questions about that: > >(1) Does there exist n bit (n even, n>2) bijective functions such >that, for all possible inputs, if any bit of the input is flipped, >then 'exactly' half of the bits of the corresponding output will >be flipped? Sure. Take a linear function of the input bits, so that c = Ap, where c and p are n-bit vectors and A is a binary square matrix. Assign exactly n/2 ones to every column of A, randomly. Now flipping any bit of p will flip exactly n/2 bits of c. >(2) If the answer to (1) is yes, is there a effective method of >finding such functions? Random assignment is fine, since you will have no security anyway. >(3) If the answer to (1) is yes, how do such functions compare >with functions satisfying SAC (from the viewpoint of crypto)? SAC is an interesting criterion, since it is provably not sufficient and not provably necessary. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: Mok-Kong Shen on 22 Sep 2009 10:28 Greg Rose wrote: > > Mok-Kong Shen wrote: >> (1) Does there exist n bit (n even, n>2) bijective functions such >> that, for all possible inputs, if any bit of the input is flipped, >> then 'exactly' half of the bits of the corresponding output will >> be flipped? > > Sure. Take a linear function of the input bits, so > that c = Ap, where c and p are n-bit vectors and A > is a binary square matrix. Assign exactly n/2 ones > to every column of A, randomly. Now flipping any > bit of p will flip exactly n/2 bits of c. I understand that in evaluating Ap 'mul' and 'add' are replaced by 'and' and 'xor'. But with the random assigment described above, would A be always invertible, i.e. would the function be guaranteed bijective? Sorry for this layman's question. Thanks, M. K. Shen
From: Maaartin on 22 Sep 2009 12:47
On Sep 22, 4:28 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Greg Rose wrote: > I understand that in evaluating Ap 'mul' and 'add' are replaced > by 'and' and 'xor'. Yes. But you can still call it mul and add, they are multiplication and addition (just in a different field). > But with the random assigment described > above, would A be always invertible, i.e. would the function be > guaranteed bijective? Sorry for this layman's question. Surely not. Can you compute the determinant? Or better, can you transform a matrix to a triangular form? To your next question ( :D ): You can make it bijective, too. |