Ring learning with errors signature: Difference between revisions

Revision as of 03:18, 28 June 2015

Revision as of 12:38, 4 July 2015

Line 14:

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.  This new area of cryptography is called [[Post-quantum cryptography|Post Quantum]] or [[Quantum Safe Cryptography|Quantum Safe]] cryptography.  This article is about one class of these algorithms:  digital signatures based on the Ring [[Learning with errors|Learning with Errors]] problem.  The use of this problem in cryptography was introduced by Oded Regev in 2005 and has been the source of a rich literature of analysis and cryptographic designs.<ref>{{Cite web|title = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|url = http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|website = www.cims.nyu.edu|accessdate = 2015-05-24}}</ref>

An important feature of certain algorithms based on Ring-Learning with Errors is their provable reduction to known hard problems. The signature described below has a provable reduction to the [[Shortest vector problem|Shortest Vector Problem]] in an [[integerIdeal lattice cryptography|ideal lattice]]. 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 was developed by Lyubashevsky in his paper "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 some features of a RLWE-SIG which closely 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" />  A later section of this article provides references to other signatures based on Lyubashevsky's original work.