Ring learning with errors signature: Difference between revisions

Revision as of 07:17, 13 April 2017

Revision as of 18:13, 27 August 2017

Line 4:

}}

[[Digital signature]]s are a means to protect [[Digital data|digital information]] from intentional modification and to authenticate the source of digital information. [[Public key cryptography]] provides a rich set of different cryptographic algorithms the create digital signatures. However, all of the primary public key signatures currently in use ([[RSA (cryptosystem)|RSA]] and [[Elliptic Curve Digital Signature Algorithm|Elliptic Curve Signatures)]] will become completely insecure if scientists are ever able to build a moderately sized [[quantum computer]].<ref name=":2">{{Cite web|title = ETSI - Quantum-Safe Cryptography|url = http://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography|website = ETSI|accessdate = 2015-07-05|first = Sabine|last = Dahmen-Lhuissier}}</ref> New digital signature algorithms such as the Ring [[learningPost-quantum withcryptography|Post errorsquantum cryptography]] signature ('''RLWE-SIG''',is a.k.a. '''GLP''',class namedof aftercryptographic thealgorithms initialsdesigned ofto thebe authors)resistant describedto inattack thisby articlea arequantum examplescryptography. of aSeveral newpost classquantum ofdigital [[Quantumsignature Safealgorithms Cryptography|Quantumbased Safe]]on cryptographichard algorithmsproblems designedin tolattices resistare cryptanalyticbeing attackscreated runreplace onthe acommonly used [[QuantumRSA computing(cryptosystem)|quantum computerRSA]].<ref>{{Cite journal|titleand =elliptic Post-quantumcurve signatures. key A exchangesubset of forthese lattice thebased scheme TLSare based protocolon a fromproblem known the ringas [[Ring learning with errors]]. problem|urlRing =learning http://eprint.iacr.org/2014/599|datewith =errors 2014|firstbased =digital Joppesignatures W.|lastare =among Bos|first2the =post Craig|last2quantum =signatures Costello|first3with =the Michael|last3smallest =public Naehrig|first4key =and Douglas|last4signature = Stebila}}</ref><ref name=":1" />sizes

== Background ==

Line 11:

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.

Even though we do not know when a quantum computer to break RSA and other digital signature algorithms will exist, there has been active research over the past decade to create cryptographic algorithms which remain secure even when an attacker has the resources of a quantum computer at their disposal.<ref name=":2" /><ref name=":4">{{Cite web|title = Introduction|url = http://pqcrypto.org/|website = pqcrypto.org|accessdate = 2015-07-05}}</ref> This new area of cryptography is called [[Post-quantum cryptography|Post Quantum]] or [[Quantum Safe Cryptography|Quantum Safe]] cryptography.<ref name=":2" /><ref name=":4" /> This article is about one class of these algorithms: digital signatures based on the Ring Learning with Errors problem. The use of thisthe general [[Learning with errors|Learning with Errors]] problem in cryptography was introduced by Oded Regev in 2005 and has been the source of several cryptographic designs.<ref>{{Cite web|title = The Learning with Errors Problem|url = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|website = www.cims.nyu.edu|accessdate = 2015-05-24}}</ref>

The creators of the [[Ring based Learning with Errors| (RLWE]]) basis for cryptography believe that an important feature of these algorithms based on Ring-Learning with Errors is their provable reduction to known hard problems.<ref>{{Cite journal|title = On ideal lattices and learning with errors over rings|url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.297.6108|publisher = Springer|journal = In Proc. of EUROCRYPT, volume 6110 of LNCS|date = 2010|pages = 1–23|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref><ref>{{Cite web|title = What does GCHQ's "cautionary tale" mean for lattice cryptography?|url = http://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdate = 2015-07-05}}</ref> The signature described below has a provable reduction to the [[Shortest vector problem|Shortest Vector Problem]] in an [[Ideal lattice cryptography|ideal lattice]].<ref name=":0" /> This means that if an attack can be found on the Ring-LWE cryptosystem then a whole class of presumed hard computational problems will have a solution.<ref>{{Cite journal|title = The shortest vector in a lattice is hard to approximate to within some constant|url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.7305|journal = in Proc. 39th Symposium on Foundations of Computer Science|date = 1998|pages = 92–98|first = Daniele|last = Micciancio}}</ref>

The first RLWE-SIG based signature was developed by Lyubashevsky in his paper "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures"<ref name=":5">{{Cite book|title = Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures|url = http://link.springer.com/chapter/10.1007/978-3-642-10366-7_35|publisher = Springer Berlin Heidelberg|date = 2009-01-01|isbn = 978-3-642-10365-0|pages = 598–616|series = Lecture Notes in Computer Science|first = Vadim|last = Lyubashevsky|editor-first = Mitsuru|editor-last = Matsui}}</ref> and refined in "Lattice Signatures Without Trapdoors" in 2011.<ref name=":1">{{Cite journal|title = Lattice Signatures Without Trapdoors|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky}}</ref> A number of refinements and variants have followed. This article highlights somethe featuresfundamental mathematical structure of a RLWE-SIG whichsignatures closelyand follows the original Lyubashevsky work and is due to the work of Guneysu, Lyubashevsky and Popplemann ([http://www.di.ens.fr/~lyubash/papers/signaturechess.pdf GLP]).<ref name=":0" /> This presentation is based on a 2017 update to the GLP scheme called GLYPH.<ref>{{Cite web|url=https://eprint.iacr.org/2017/766.pdf|title=GLYPH: A New Instantiation of the GLP Digital Signature Scheme|last=Chopra|first=Arjun|date=2017|website=https://eprint.iacr.org|archive-url=|archive-date=|dead-url=|access-date=26 August 2017}}</ref>

A RLWE-SIG works in the quotient [[ring of polynomials]] modulo a degree n polynomial Φ(x) with coefficients in the [[finite field]] Z_q for an odd prime q ( i.e. the ring Z_q[x]/Φ(x) ).<ref name=":1" /> Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod Φ(x). For this presentation a typical polynomial is expressed as: