Effect of Quantum Computing Attacks On Key Strength
The two best known quantum computing attacks are based on Shor's algorithm and Grover's algorithm. Of the two, Shor's offers the greater risk to current security systems.
Derivatives of Shor's algorithm are widely conjectured to be effective against all mainstream public-key algorithms including RSA, Diffie-Hellman and elliptic curve cryptography. According to Professor Gilles Brassard, an expert in quantum computing: "The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption. In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer." The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available. The implication of this attack is that all data encrypted using current standards based security systems such as the ubiquitous SSL used to protect e-commerce and Internet banking and SSH used to protect access to sensitive computing systems is at risk. Encrypted data protected using public-key algorithms can be archived and may be broken at a later time.
Mainstream symmetric ciphers (such as AES or Twofish) and collision resistant hash functions (such as SHA) are widely conjectured to offer greater security against known quantum computing attacks. They are widely conjectured to be most vulnerable to Grover's algorithm. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case. Thus in the presence of large quantum computers an n-bit key can provide at least n/2 bits of security. Quantum brute force is easily defeated by doubling the key length, which has little extra computational cost in ordinary use. This implies that at least a 160-bit symmetric key is required to achieve 80-bit security rating against a quantum computer.
Read more about this topic: Key Size
Famous quotes containing the words effect of, effect, quantum, attacks, key and/or strength:
“To get time for civic work, for exercise, for neighborhood projects, reading or meditation, or just plain time to themselves, mothers need to hold out against the fairly recent but surprisingly entrenched myth that “good mothers” are constantly with their children. They will have to speak out at last about the demoralizing effect of spending day after day with small children, no matter how much they love them.”
—Wendy Coppedge Sanford. Ourselves and Our Children, by Boston Women’s Health Book Collective, introduction (1978)
“Because just as arms have no force outside if there is no counsel within a house, study is vain and counsel useless that is not put to virtuous effect when the time calls.”
—François Rabelais (1494–1553)
“The receipt to make a speaker, and an applauded one too, is short and easy.—Take of common sense quantum sufficit, add a little application to the rules and orders of the House, throw obvious thoughts in a new light, and make up the whole with a large quantity of purity, correctness, and elegancy of style.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“I find that with me low spirits and feeble health come and go together. The last two or three months I have had frequent attacks of the blues. They generally are upon me or within me when I am somewhat out of order in bowels, throat, or head.”
—Rutherford Birchard Hayes (1822–1893)
“Woe unto you, lawyers! for ye have taken away the key of knowledge: ye entered not in yourselves, and them that were entering in ye hindered.”
—Bible: New Testament Jesus, in Luke 11:52.
“The days of our years are threescore years and ten; and if by reason of strength they be fourscore years, yet is their strength labour and sorrow; for it is soon cut off, and we fly away.”
—Bible: Hebrew Psalms 90:10.
The Book of Common Prayer (1662)