On Tue, 15 Aug 2000, David Honig wrote:
[original poster asks :]
> >Essentially what i'm asking is: How would cryptography evolve once a
> >quantum computer is available?
> >
>
> Simple. Use bigger keys. Bigger by the work-factor that quantum
> computation gives you (see Grover's algorithm). E.g., a 512-bit symmetric
> block cipher should be good for a few more years, quantum computers
> or not. 3-AES anyone?
yup. but don't forget public key crypto...
what happens if quantum computers become practical :
symmetric crypto : barring specialised attacks for a cipher,
brute force search goes from 2^n to 2^(n/2) steps.
So 128 bit keys take 2^64 steps or so to break, 256 bit keys
take 2^128, 512 bit keys take 2^256 steps. So at 256 bits
or higher, you should be fine.
public-key crypto : factoring and discrete log become "easy."
Thus RSA and Diffie-Hellman and all their cousins become broken.
Search begins in earnest for alternative one-way functions and public-key
cryptosystems. As far as I know, NTRU doesn't have a quantum algorithm
for breaking it; there may be others.
Actually, this brings up a point - what weird public-key cryptosystems
not based on factoring or discrete log are there? I can think of
Arithmetica's system and NTRU off the top of my head, but not much more.
Thanks,
-David
