phc-discussions - Re: [PHC] Dumb idea of the day: Public key crypto based on random permutations

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 15 Aug 2015 18:54:19 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.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 post-quantum secure when the random permutation is.  The algorithm is super-simple, 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 n-bits, 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>