Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Maaartin on 18 Sep 2009 15:28 On Sep 17, 11:29 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > In the literature there are papers aiming to get highly nonlinear > functions satisfying SAC. I guess that, if one doesn't demand > anything concerning nonlinearity, one may in return get some > saving in computational cost. I am curious to know whether this > is the case. So the paper you mentioned would indeed interest me. > It would be nice, if you (or anyone in the group) happen to have > the exact reference at hand and kindly provide it to me. 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).
From: Maaartin on 20 Sep 2009 12:50 On Sep 18, 9:28 pm, Maaartin <grajc...(a)seznam.cz> 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). There's a dissertation by one the authors dealing with sboxes available online Kwangjo Kim: "A Study on the Construction and Analysis of Substitution Boxes for Symmetric Cryptosystems". There's a method for creating maximum order SAC functions there. I can't find it again, only some links where you get only free preview. I personally would be happy about a seach engine completelly ignoring all of *.springerlink.com, portal.acm.org, etc. The work is very old (1990), could somebody provide some newer result? There's a lot of papers on the internet dealing with sboxes, but I've found nothing new describing their construction.
From: Mok-Kong Shen on 21 Sep 2009 05:07 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. Thanks. M. K. Shen
From: biject on 21 Sep 2009 10:53 On Sep 18, 1:28 pm, Maaartin <grajc...(a)seznam.cz> 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). 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. 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? David A. Scott -- My Crypto code http://bijective.dogma.net/crypto/scott19u.zip http://www.jim.com/jamesd/Kong/scott19u.zip old version My Compression code http://bijective.dogma.net/ **TO EMAIL ME drop the roman "five" ** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged. As a famous person once said "any cryptograhic system is only as strong as its weakest link"
From: Maaartin on 21 Sep 2009 15:29
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). |