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:
“Considered physiologically, everything ugly weakens and saddens man. It reminds him of decay, danger, impotence; it actually reduces his strength. The effect of ugliness can be measured with a dynamometer. Whenever anyone feels depressed, he senses the proximity of something “ugly.” His feeling of power, his will to power, his courage, his pride—they decline with ugliness, they rise with beauty.”
—Friedrich Nietzsche (1844–1900)
“The second [of Zeno’s arguments about motion] is the one called “Achilles.” This is to the effect that the slowest as it runs will never be caught by the quickest. For the pursuer must first reach the point from which the pursued departed, so that the slower must always be some distance in front.”
—Zeno Of Elea (c. 490–430 B.C.)
“But how is one to make a scientist understand that there is something unalterably deranged about differential calculus, quantum theory, or the obscene and so inanely liturgical ordeals of the precession of the equinoxes.”
—Antonin Artaud (1896–1948)
“The rebel, unlike the revolutionary, does not attempt to undermine the social order as a whole. The rebel attacks the tyrant; the revolutionary attacks tyranny. I grant that there are rebels who regard all governments as tyrannical; nonetheless, it is abuses that they condemn, not power itself. Revolutionaries, on the other hand, are convinced that the evil does not lie in the excesses of the constituted order but in order itself. The difference, it seems to me, is considerable.”
—Octavio Paz (b. 1914)
“This is the Key of the Kingdom:
In that Kingdom is a city;”
—Unknown. This Is the Key (l. 1–2)
“Fearlessness is a more than ordinary strength of mind, which raises the soul above the troubles, disorders, and emotions which the prospect of great dangers are used to produce. And by this inward strength it is that heroes preserve themselves in a calm and quiet state, and enjoy a presence of mind and the free use of their reason in the midst of those terrible accidents that amaze and confound other people.”
—François, Duc De La Rochefoucauld (1613–1680)