Re: Quantum Cryptography and resistance
At 01:42 PM 8/16/00 -0400, [EMAIL PROTECTED] wrote: >Hence it will be necessary to scale up the QC from 5 bits to 1024 bits >or more. This will take years of work and no one knows if it will be >possible. Current Quantum Computer Engineering in 5 lines or less: The current approach requires that you 1. isolate the quantumshit from interactions with the rest of us while it evolves 2. arrange the quantumshit to introduce your initial constraints 3. cause the quantumshit to evolve according to the rules of your system.
Re: Quantum Cryptography and resistance
Quantum cryptography will be of little practical value for the average person. That's because you need to get photons unchanged from one person to the other. This requires either a line of sight or a fiber optic cable, neither of which is likely to be available. Quantum computers allow fast search for symmetric ciphers like DES or AES. The effect is essentially to halve the key size. A 128 bit key attacked by a QC becomes as strong as a 64 bit key would be attacked by conventional computers. The new AES standard provides for 256 bit keys. These will still provide 128 bits of strength against quantum computers, making them practically invulnerable. So QCs will provide no significant problems against symmetric ciphers once AES is in widespread use. Quantum computers also allow fast factoring and finding discrete logs, essentially destroying the principles behind the most widely used public key systems. This uses Shor's algorithm, which works by finding the period of a sequence. The recent IBM announcement was apparently an implementation of just this algorithm for a 5 bit QC. Hence it will be necessary to scale up the QC from 5 bits to 1024 bits or more. This will take years of work and no one knows if it will be possible. If it happens, people will have to switch to keys larger than the largest quantum computers, which will probably be a losing battle; or they will have to use the more obscure, less efficient and possibly less secure public key alternatives. No doubt if large QCs appear on the horizon we will see considerably more cryptographic effort put into developing and establishing the security of alternative methods for PKC.
Re: Quantum Cryptography and resistance
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
Re: Quantum Cryptography and resistance
At 01:37 PM 8/15/00 -0400, Timothy Brown wrote: >Hey, folks - > >Can anyone provide pointers for the layman to documents describing >theoretical cryptosystems resistant to quantum cryptanalysis? The >assumption is made that those systems would be implemented on quantum >computing devices. > >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?
