Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Maaartin on 1 Oct 2009 08:10 On Oct 1, 12:05 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I hope that this has finally cleared the issue. I think so. Do not forget, nobody gets paid for answering here, people do it just as help to others or out of interest, so you should not expect anybody to read very carefully. You were right, but everybody else thought about something different. > If I understand correctly, the current state of affairs is as follows: > > (1) For n = 0 (mod 4) there is no linear bijective function satisfying > the condition. Right, although I do not understood yet the reason Greg gave. > (2) For n = 0 (mod 2) n != 0 (mod 4) the existence of such linear > bijective functions has been verified up to n = 30 and it seems very > plausible that this is indeed a general result. In the meantime, verified for up to n=54, strangely I've found no solution for n=58 and n=60 yet, it's still running. It looks like the algorithm needed an improvement (that's no surprise, writing even such a simple program after midnight rarely works well). > (3) For n = 4, no bijective function at all satisfying the condition > exists (assuming that my previous program run is correct). > > So the following question remains: > > For n = 0 (mod 4), n > 4, do there exist bijective functions > (by necessity nonlinear, see (1) above) which satisfy the condition > that flipping any one input bit always causes exactly 2 output bits > to flip? No idea. > Since n=8 seems to be a quite interesting case, I attempted to use > my program that had previously processed the n=4 case to investigate. > However, it turns out that my program is much too inefficient for > that use and would require far too much run time on my PC than I > could afford. In my program I employ essentially brute force. I know > that I can reduce the search space by 50% through implementing a > check. I have however not yet considered even to try out that > short-cut, because even with a 50% reduction in run time I'll > still have no "practical" chance of successfully running the program > for the case n=8 to an end on my poor PC. I should be grateful, if There're 256! = 8e506 possibilities, so reducing it to 4e506 doesn't help much, does it? > anyone could provide good ideas of really essentially cutting down > the processing time in the present case as compared to my naive > bruteforcing. Currently, I've got no idea. But do not forget: Greg wrote the following > SAC is an interesting criterion, since it is > provably not sufficient and not provably > necessary. which I translate as "SAC is quite useless". What about concentrating on DPmax and LPmax? The evaluation is not more complicated than SAC.
From: Scott Fluhrer on 1 Oct 2009 11:27 "Maaartin" <grajcar1(a)seznam.cz> wrote in message news:7b0412db-fa7f-4f3a-b6bc-9e8c0867934c(a)o41g2000yqb.googlegroups.com... On Oct 1, 12:05 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > > > For n = 0 (mod 4), n > 4, do there exist bijective functions > > (by necessity nonlinear, see (1) above) which satisfy the condition > > that flipping any one input bit always causes exactly 2 output bits > > to flip? > > No idea. The answer is no (and that answer is still 'no' even without the conditions on n). If we flip any input bit, then two output bits will flip; this implies that the parity of the output (whether there's an even number of '1' bits) will remain the same. We can move to any input setting by successively flipping input bits, this means that the output parity will still be fixed, and so half the possible outputs will be impossible (and hence the function cannot be bijective). -- poncho
From: Mok-Kong Shen on 1 Oct 2009 11:39 Scott Fluhrer wrote: > "Maaartin" <grajcar1(a)seznam.cz> wrote: > Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >>> For n = 0 (mod 4), n > 4, do there exist bijective functions >>> (by necessity nonlinear, see (1) above) which satisfy the condition >>> that flipping any one input bit always causes exactly 2 output bits >>> to flip? >> No idea. > > The answer is no (and that answer is still 'no' even without the conditions > on n). If we flip any input bit, then two output bits will flip; this > implies that the parity of the output (whether there's an even number of '1' > bits) will remain the same. We can move to any input setting by > successively flipping input bits, this means that the output parity will > still be fixed, and so half the possible outputs will be impossible (and > hence the function cannot be bijective). Pardon! There was a typo in my previous post. I am sorry. That question should read: For n = 0 (mod 4), n > 4, do there exist bijective functions (by necessity nonlinear, see (1) above) which satisfy the condition that flipping any one input bit always causes exactly n/2 output bits to flip? Thanks, M. K. Shen
From: Scott Fluhrer on 1 Oct 2009 12:07 "Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message news:ha2ift$hjb$02$1(a)news.t-online.com... > Scott Fluhrer wrote: >> "Maaartin" <grajcar1(a)seznam.cz> wrote: >> Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >>>> For n = 0 (mod 4), n > 4, do there exist bijective functions >>>> (by necessity nonlinear, see (1) above) which satisfy the condition >>>> that flipping any one input bit always causes exactly 2 output bits >>>> to flip? >>> No idea. >> >> The answer is no (and that answer is still 'no' even without the >> conditions on n). If we flip any input bit, then two output bits will >> flip; this implies that the parity of the output (whether there's an even >> number of '1' bits) will remain the same. We can move to any input >> setting by successively flipping input bits, this means that the output >> parity will still be fixed, and so half the possible outputs will be >> impossible (and hence the function cannot be bijective). > > Pardon! There was a typo in my previous post. I am sorry. That question > should read: > > For n = 0 (mod 4), n > 4, do there exist bijective functions > (by necessity nonlinear, see (1) above) which satisfy the condition > that flipping any one input bit always causes exactly n/2 output bits > to flip? The answer to that question is also "no", by the same reasoning: if n=0 mod 4, then n/2 is even, and as the above argument shows, no bijective function exists where a flip to a single input bit always causes an even number of output bits to flip -- poncho
From: Mok-Kong Shen on 1 Oct 2009 12:28
Scott Fluhrer wrote: > "Mok-Kong Shen" wrote: >> For n = 0 (mod 4), n > 4, do there exist bijective functions >> (by necessity nonlinear, see (1) above) which satisfy the condition >> that flipping any one input bit always causes exactly n/2 output bits >> to flip? > > The answer to that question is also "no", by the same reasoning: if n=0 mod > 4, then n/2 is even, and as the above argument shows, no bijective function > exists where a flip to a single input bit always causes an even number of > output bits to flip Hearty thanks for your clear and ingenious demonstration of the non-existence of such functions. M. K. Shen |