Ring learning with errors signature: Difference between revisions

Revision as of 14:15, 16 May 2018

Revision as of 15:32, 27 May 2018

Line 2:

== Background ==

Developments in [[quantum computing]] over the past decade and the optimistic prospects for real quantum computers within 20 years have begun to threaten the basic cryptography that secures the internet.<ref>{{Cite web|title = Quantum computing breakthrough claim from IBM|url = http://www.cio.co.uk/news/r-and-d/quantum-computing-breakthrough-claim-from-ibm-3609914/|accessdate = 2015-06-01|first = Agam|last = Shah}}</ref><ref>{{Cite news|title = Researchers Report Milestone in Developing Quantum Computer|url = https://www.nytimes.com/2015/03/05/science/quantum-computing-nature-google-uc-santa-barbara.html|newspaper = The New York Times|date = 2015-03-04|access-date = 2015-07-05|issn = 0362-4331|first = John|last = Markoff}}</ref> A relatively small [[quantum computer]] capable of processing only ten thousand of bits of information would easily break all of the widely used [[Public-key cryptography|public key]] cryptography algorithms used to protect privacy and digitally sign information on the internet.<ref name=":2" /><ref>{{Cite journal|title = Efficient Networks for Quantum Factoring|url = https://arxiv.org/abs/quant-ph/9602016|journal = Physical Review A|date = 1996|issn = 1050-2947|pages = 1034–1063|volume = 54|issue = 2|doi = 10.1103/PhysRevA.54.1034|first = David|last = Beckman|first2 = Amalavoyal N.|last2 = Chari|first3 = Srikrishna|last3 = Devabhaktuni|first4 = John|last4 = Preskill|arxiv = quant-ph/9602016}}</ref>

One of the most widely used public key algorithm used to create [[digital signatures]] is known as [[RSA (cryptosystem)|RSA]]. Its security is based on the classical difficulty of factoring the product of two large and unknown primes into the constituent primes. The [[integer factorization problem]] is believed to be intractable on any conventional computer if the primes are chosen at random and are sufficiently large. However, to factor the product of two n-bit primes, a quantum computer with roughly 6n bits of logical [[qubit]] memory and capable of executing a program known as [[Shor's algorithm|Shor’s algorithm]] will easily accomplish the task.<ref>{{Cite journal|title = Oversimplifying quantum factoring|url = http://www.nature.com/nature/journal/v499/n7457/full/nature12290.html|journal = Nature|date = July 11, 2013|issn = 0028-0836|pages = 163–165|volume = 499|issue = 7457|doi = 10.1038/nature12290|first = John A.|last = Smolin|first2 = Graeme|last2 = Smith|first3 = Alexander|last3 = Vargo|pmid=23846653}}</ref> Shor's algorithm can also quickly break digital signatures based on what is known as the [[discrete logarithm]] problem and the more esoteric [[Elliptic curve cryptography|elliptic curve discrete logarithm]] problem. In effect, a relatively small quantum computer running Shor's algorithm could quickly break all of the digital signatures used to ensure the privacy and integrity of information on the internet today.