Ring learning with errors signature: Difference between revisions

Revision as of 10:02, 30 December 2023

Latest revision as of 18:15, 3 July 2025

(6 intermediate revisions by 4 users not shown)

Line 8:

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|access-date = 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 the 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|access-date = 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|journal = In Proc. Of EUROCRYPT, Volume 6110 ofbook LNCS|date = 2010|pages = 1–23|first1 = Vadim|last1 = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev| title=Advances in Cryptology – EUROCRYPT 2010 | chapter=On Ideal Lattices and Learning with Errors over Rings | series=Lecture Notes in Computer Science | volume=6110 |citeseerx = 10.1.1.297.6108|doi=10.1007/978-3-642-13190-5_1| isbn=978-3-642-13189-9 |editor-last=Gilbert|editor-first=Henri }}</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|access-date = 2015-07-05|url-status = dead|archive-url = https://web.archive.org/web/20150706150530/http://www.cc.gatech.edu/~cpeikert/soliloquy.html|archive-date = 2015-07-06}}</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">{{Cite book|title=Cryptographic Hardware and Embedded Systems – CHES 2012|last1=Güneysu|first1=Tim|last2=Lyubashevsky|first2=Vadim|last3=Pöppelmann|first3=Thomas|date=2012|publisher=Springer Berlin Heidelberg|isbn=978-3-642-33026-1|editor-last=Prouff|editor-first=Emmanuel|series=Lecture Notes in Computer Science|volume=7428|pages=530–547|chapter=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|doi=10.1007/978-3-642-33027-8_31|editor-last2=Schaumont|editor-first2=Patrick}}</ref> 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 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|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|doi = 10.1007/978-3-642-10366-7_35|title = Advances in Cryptology – ASIACRYPT 2009|volume = 5912|chapter = Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures}}</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| journal=Cryptology ePrint Archive }}</ref> A number of refinements and variants have followed. This article highlights the fundamental [[mathematical structure]] of RLWE signatures and follows the original Lyubashevsky work and the work of Guneysu, Lyubashevsky and Popplemann ([https://web.archive.org/web/20140518004537/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 name=":3">{{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=International Association of Cryptographic Research eprint Archive|archive-url=https://web.archive.org/web/20170828012937/https://eprint.iacr.org/2017/766.pdf|archive-date=28 August 2017|access-date=26 August 2017|url-status=bot: unknown}}</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:

Line 16:

<math>a(x) = a_0 + a_1x + a_{2}x^2 + \ldots + a_{n-3}x^{n-3} + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

The field Z_q has its representative elements in the set { -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 }. When n is a power of 2, the polynomial Φ(x) will be the [[cyclotomic polynomial]] xⁿ + 1. Other choices of n are possible but the corresponding cyclotomic polynomials are more complicated or their security not as well studied.

=== Generating "small" polynomials. ===