Re: Symmetric Encryption attacked by quantum computers?

From: Ben Rudiak-Gould (br276deleteme_at_cam.ac.uk)
Date: 11/10/05 

Date: Thu, 10 Nov 2005 22:16:56 +0000

Don wrote:
> I have read that if you are using a symmetric cipher with a 256 bit
> key, it would take a quantum computer about 2^128 steps to break. How
> is this possible if the computer would still have to brute force the
> algorithm?

Grover's algorithm:

     http://en.wikipedia.org/wiki/Grover's_algorithm

Though usually described as "database search" (because Grover called it
that), it's really a way of finding a satisfying assignment of a classical
or quantum circuit in roughly 2^(N/2) times the circuit evaluation time,
where N is the number of inputs.

(The people who said "by superposition" are sort of right, but it's like
saying a classical computer cracks ciphers by loading and storing. One
doesn't automatically get fast computation from superposition -- one needs
an algorithm, and they're hard to find.)

-- Ben

Relevant Pages

  • Re: Symmetric Encryption attacked by quantum computers?
    ... >I have read that if you are using a symmetric cipher with a 256 bit ... A quantum computer would be able to search ... also use a superposition of states on one processor. ...
    (sci.crypt)
  • Symmetric Encryption attacked by quantum computers?
    ... I have read that if you are using a symmetric cipher with a 256 bit ... it would take a quantum computer about 2^128 steps to break. ... is this possible if the computer would still have to brute force the ...
    (sci.crypt)
  • Re: How long would it take a computer to completely "solve" chess?
    ... The kind of tree search you need to do to determine the ... a quantum computer will turn it into an easy one. ... the types of problem for which there's an algorithm to solve it using ... because each other type of problem in PSPACE can be reduced to it. ...
    (sci.math)
  • Serially Factoring large prime numbers --- Shors algorithm modification
    ... I believe Shor's algorithm uses a quantum computer to factor large prime numbers product. ... When the X qubits settle down, you have obtained the first X bits of the solution. ... Feed the problem into the "X" qubit quantum computer along with the first X bits of the solution. ...
    (sci.math)
  • Re: Quantum Computing and protein folding
    ... >> Would a quantum computer be able to efficiently, and accurately, solve ... a protein polypeptide itself is a quantum mechanical system that seems ... > problem any fatser using brute force as an algorithm. ... Maybe someone will someday figure out how to make such an algorithm ...
    (comp.theory)
Loading