Ring learning with errors: Difference between revisions

Revision as of 21:28, 5 March 2015

Revision as of 21:47, 5 March 2015

Line 2:

<!-- EDIT BELOW THIS LINE -->

[[Digital Signature Algorithm|Digital Signatures]] are a crucial element of security on the Internet. They are used to verify the identities of online entities and to verify the integrity of software and information exchanged over the internet. However, the current digital signature algorithms used on the internet ([[RSA]] or [[Elliptic Curve Cryptography]]) will become insecure if sufficiently large [[quantum computers]] are ever built. One approach to creating a digital signature algorithm that remains secure even when attackers have a quantum computer is based on [[lattice|lattices]]. This article is about a [[Provable security|provably secure]] digital signature based on a particular form of lattice problems known as "Ring [[Learning with errors|Learning with Errors]]" or Ring-LWE. The basic algorithm drawn from Lyubashevsky's 2011 paper, "Lattice Signatures Without Trapdoors." It is duefurther torefined Lyubashevskyby Guneysu, Lybashevsky, and Poppleman in 20112012 and Singh in 2015.<ref name=":0">{{Cite web|url = https://eprint.iacr.org/2011/537|title = Lattice Signature without Trapdoors|date = 1 October 2011|accessdate = 1 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Lyubashevsky|first = Vadim}}</ref> and further refined by Guneysu, Lybashevsky, and Poppleman also in 2012.<ref name=":1">{{Cite web|url = http://www.iacr.org/cryptodb/data/paper.php?pubkey=24396|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|date = 2012|accessdate = 1 March 2015|website = International Association for Cryptologic Research|publisher = IACR|last = Gunesyu|first = Tim|last2 = Lyubashevsky|authorlink = Poppleman}}</ref><ref name=":2">{{Cite web|url = https://eprint.iacr.org/2015/138|title = A Practical Key Exchange for the Internet using Lattice Cryptography|date = 19 February 2015|accessdate = 5 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Singh|first = Vikram}}</ref>.

== Introduction ==

There are a number of digital signature algorithms based on the Learning with Errors problem over Rings. The mathematical foundations of the [[Learning with errors|Learning with Errors]] problem was introduced by Regev in 2005.<ref>{{Cite web|url = http://dl.acm.org/citation.cfm?id=1060590.1060603|title = On lattices, learning with errors, random linear codes, and cryptography|date = 2005|accessdate = 1 March 2015|website = ACM Digital Library|publisher = ACM|last = Regev|first = Oded}}</ref> The theory of signatures based on the Learning with Errors problem was developed further by Regev, Peikert and Lyubashevsky. In 2012 Lyubashevsky published "Lattice Signatures without Trapdoors." InIt is this paperalgorithm, hethe discussedTrapdoor theFree possibilityLattice ofSignature, making thewhich signaturesis smallerdescribed andbelow. more efficientThe bysignature workingalgorithm overpresented below has a ringprovable ofreduction to the Short Integer Solution problem for [[Ideal lattice cryptography|Ideal Lattices]]<ref name=":0" polynomials/>. ItThis isprovable thisreduction algorithmmakes whichthe issignature describedan belowattractive candidate for future standardization.

Researchers have created other lattice based signatures after Lyubashevsky's work.<ref>{{Cite web|url = https://eprint.iacr.org/2013/383|title = Lattice Signatures and Bimodal Gaussians|date = 10 December 2013|accessdate = 5 March 2015|website = Cryptology ePrint Archive|publisher = IACR|last = Ducas|first = Leo}}</ref> While they are somewhat more efficient than Lyubashevsky's Trapdoor Free Signature, they lack a security reduction to the worst case instances of a known hard problem. Some of these are closely related to the [[NTRU|NTRU public key system]] and its unprovable security assumptions.

The signature algorithm presented below has a provable reduction to the Short Integer Solution problem for [[Ideal lattice cryptography|Ideal Lattices]]<ref name=":0" />. This provable reduction makes the signature an attractive candidate for future standardization.

== ProvablyTrapdoor SecureFree Ring-LWELattice Signature (PSRSTFLS) ==

Lyubashevsky and others have done further research on lattice and Ring-LWE signatures but while providing more efficiency they (to date) lack a proof that their security is reducible to a well known hard mathematical problem. Some of those schemes are outlined in the sections call Non-Provable schemes below.

T

In this signature algorithm, we will be working in a ring (R) of polynomials of degree n with coefficients in the finite field Fq. We will follow the work of Gunesyu, Lyubashevsy, and Poppleman<ref closelyname=":1" and/> letas well as that of Singh<ref name=":2" /> closely. Let q be prime and n will be a power of 2.

== Provably Secure Ring-LWE Signature (PSRS) ==

Provably Secure Ring-LWE Signature (PSRS)

In this signature algorithm, we will be working in a ring (R) of polynomials of degree n with coefficients in the finite field Fq. We will follow the work of Gunesyu, Lyubashevsy, and Poppleman closely and let q be prime and n will be a power of 2.

=== Definitions: ===

Let

* R_n,q be the ring of degree less than n-1 polynomials with coefficients in F_q where q is a prime power.

* a be a fixed publicly known polynomial in R_n,q

* s₁ be a randomly chosen secret polynomial in R_n,q