[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <CBCFBF54-B2B0-49B1-A0AC-505596D19DCE@gmail.com>
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>
Powered by blists - more mailing lists