lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Sat, 15 Aug 2015 18:54:19 +0200 From: Dmitry Khovratovich <khovratovich@...il.com> To: "discussions@...swordhashing.net" <discussions@...swordhashing.net> Subject: Re: [PHC] Dumb idea of the day: Public key crypto based on random permutations So how do you encrypt exactly with this operation? Sent from my iPhone > On 15 Aug 2015, at 15:12, Bill Cox <waywardgeek@...il.com> wrote: > > This is what my code from last night does... I think! This is too simple and obvious to be new, yet too useful to work. Can one of you guys debunk this quickly for me before I get too excited? I coded it in 56 lines of attached Python, and it seems to work. Attack away! > > In short, I think I figured out how to create simple and fast public key protocols based on the security of random permutations and no other assumptions. If true, I think this would be a big deal. I seems like it will be faster than elliptic curves, requiring no more bits, and also appears to be postquantum secure when the random permutation is. The algorithm is supersimple, easily in the realm of what we can prove secure. > > The following construction allows us to turn just about any random permutation from n bits to n bits into an addition operator, suitable for abelian group addition. Let F(x) be a random permutation of nbits, such as AES. Define the @ operator as follows: > > a @ b = Finv(F(a) + F(b)) > > This seems to be real addition. From Wikipedia, here are the 5 properties I have to prove to show that this creates an abelian group: > >  Closure > Since F is a random permutation, there is a value o = Finv(1). Consider the sequence: > > a, a @ o, A @ o @ o, A @ o @ o @ o, .... > > This sequence goes through all combinations of F(a) + k, for any k, before applying Finv. Since it's a random permutation, Finv also goes through all values. > >  Associativity > Obvious from definition of a @ b > >  Identity element > The identity element is i = Finv(0). a @ i = Finv(F(a) + F(i)) = Finv(F(a) + F(Finv(0))) = Finv(F(a) + 0) = a > >  Inverse element > The inverse of element 'a' is Finv(F(a)): > > a @ a = Finv(F(a) + F(a)) = Finv(F(a) + F(Finv(F(a)))) = Finv(F(a)  F(a)) = Finv(0) = o > >  Commutativity > We have to show (a @ b) @ c = a @ (b @ c): > > (a @ b) @ c = Finv(F(Finv(F(a) + F(b))) + F(c)) > = Finv(F(a) + F(b) + F(c)) > = Finv(F(a) + Finv(F(F(b) + F(c)))) > = a @ (b @ c) > > That should prove it works. However, just because it's an abelian group based on random permutations doesn't prove it's secure. Where are the holes? > > Bill > <twocats_construction.py>
Powered by blists  more mailing lists