2274:
401:- The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose polynomial coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the infinity norm of the polynomial will be ≤ (b).
467:
where q is an odd prime congruent to 1 mod 4. For n=1024, GLYPH sets q = 59393, b=16383 and k the number of non-zero coefficients in the output of
Polyhash equal to 16. The number of non-zero coefficients k produced by the hash function is equal to 32 for both cases. The security of the signature
759:
Another approach to signatures based on lattices over Rings is a variant of the patented NTRU family of lattice based cryptography. The primary example of this approach is a signature known as the
Bimodal Lattice Signature Scheme (BLISS). It was developed by Ducas, Durmas, Lepoint and Lyubashevsky
425:
arbitrary bit strings into small polynomials according to some distribution. The example below uses a hash function, POLYHASH(ω), which accepts a bit string, ω, as input and outputs a polynomial with n coefficients such that exactly k of these coefficients have absolute value greater than zero and
136:
The first RLWE based signature was developed by
Lyubashevsky in his paper "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures" and refined in "Lattice Signatures Without Trapdoors" in 2011. A number of refinements and variants have followed. This article highlights the
446:
that polynomial will be discarded and the signing process will begin again. This process will be repeated until the infinity norm of the signature polynomial is less than or equal to the bound. Rejection sampling ensures that the output signature is not exploitably correlated with the signer's
360:
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
108:
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
124:
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. The signature described below has a provable reduction to the
404:
Using
Discrete Gaussian Sampling - For an odd integer q, the coefficients are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. The references provide more details on this
471:
As noted above, the polynomial Φ(x) which defines the ring of polynomials used will be x + 1. Finally, a(x) will be a randomly chosen and fixed polynomial with coefficients from the set { -(q-1)/2 to (q-1)/2 }. The polynomial a(x) should be chosen in a
352:
43:
is a class of cryptographic algorithms designed to be resistant to attack by a quantum cryptography. Several post quantum digital signature algorithms based on hard problems in lattices are being created replace the commonly used
87:
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
462:
Following GLYPH and as noted above, the maximum degree of the polynomials will be n-1 and therefore have n coefficients. Typical values for n are 512, and 1024. The coefficients of these polynomials will be from the field
480:
the output of a true noise random number generator (TRNG) or using the digital expansion of well known mathematical constans such as pi or e. All signers and verifiers of signatures will know n, q, b, k, Φ(x), a(x) and
507:
The polynomials s(x) and e(x) serve as the private key and t(x) is the corresponding public key. The security of this signature scheme is based on the following problem. Given a polynomial t(x) find small polynomials
104:
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.
739:
The GLYPH signature scheme described in this document closely follows the work of
Lyubashevsky, Gunesyu and Popplemen from 2011 and 2012. There are a number of other variations to their work. These include:
160:/Φ(x) ). 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:
1152:
Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical
Lattice-Based Cryptography: A Signature Scheme for Embedded Systems". In Prouff, Emmanuel; Schaumont, Patrick (eds.).
64:
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. A relatively small
381:. The signature algorithm will create random polynomials which are small with respect to a particular infinity norm bound. This is easily done by randomly generating all of the
393:) in a manner which is guaranteed or very likely to be less than or equal to this bound. In the literature on Ring Learning with Errors, there are two common ways to do this:
165:
813:
454:
will be (b - k), where b is the range of the uniform sampling described above and k will be the number of non-zero coefficients allowed in an "accepted" polynomial
117:
cryptography. This article is about one class of these algorithms: digital signatures based on the Ring
Learning with Errors problem. The use of the general
2254:
2084:
377:
for a polynomial is simply the largest absolute value of the coefficients of the polynomial when those coefficients are viewed as integers in Z rather than Z
1714:
1307:
133:. 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.
632:
Following GLYPH, to verify a message m expressed as a bit string, the verifying entity must possess the signer's public key (t(x)), the signature (c(x), z
137:
fundamental mathematical structure of RLWE signatures and follows the original
Lyubashevsky work and the work of Guneysu, Lyubashevsky and Popplemann (
27:
provides a rich set of different cryptographic algorithms the create digital signatures. However, the primary public key signatures currently in use (
1424:
83:. Its security is based on the classical difficulty of factoring the product of two large and unknown primes into the constituent primes. The
1842:
1207:
Lyubashevsky, Vadim (2009-01-01). "Fiat-Shamir with Aborts: Applications to
Lattice and Factoring-Based Signatures". In Matsui, Mitsuru (ed.).
468:
scheme is closely tied to the relative sizes of n, q, b, and k. Details on setting these parameters can be found in references 5 and 6 below.
1937:
52:. Ring learning with errors based digital signatures are among the post quantum signatures with the smallest public key and signature sizes
1837:
1063:
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". In Gilbert, Henri (ed.).
751:
Work by Akleylek, Bindel, Buchmann, Kramer and Marson on security proofs for the signature with fewer security assumptions and documented
1566:
32:
138:
1745:
1739:
871:
Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring".
839:
731:
This brief derivation demonstrates that the verification process will have c'(x) = c(x) if the signature was not tampered with.
1106:
1863:
1417:
1224:
1169:
1090:
564:
Compute c(x) = POLYHASH(ω | m) (This is a polynomial with k non-zero coefficients. The "|" denotes concatenation of strings)
96:
will easily accomplish the task. Shor's algorithm can also quickly break digital signatures based on what is known as the
817:
2307:
2302:
1481:
121:
problem in cryptography was introduced by Oded Regev in 2005 and has been the source of several cryptographic designs.
1930:
1549:
1506:
497:
Generate two small polynomials s(x) and e(x) with coefficients chosen uniformly from the set {-b,...-1, 0, 1, ..., b}
1471:
1461:
1410:
788:
1278:
1625:
1539:
1486:
410:
398:
2133:
1650:
1534:
84:
409:
In the RLWE signature GLYPH used as an example below, coefficients for the "small" polynomials will use the
1923:
1791:
1724:
2249:
2204:
2017:
1888:
1781:
1630:
1544:
1466:
473:
422:
101:
68:
capable of processing only ten thousand of bits of information would easily break all of the widely used
2128:
1640:
1529:
1511:
940:
Smolin, John A.; Smith, Graeme; Vargo, Alexander (July 11, 2013). "Oversimplifying quantum factoring".
535:
Following GLYPH, to sign a message m expressed as a bit string, the signing entity does the following:
130:
48:
and elliptic curve signatures. A subset of these lattice based scheme are based on a problem known as
2244:
1893:
1873:
369:
A RLWE signature uses polynomials which are considered "small" with respect to a measure called the "
114:
110:
49:
40:
1776:
1073:
2234:
2224:
2079:
1832:
1603:
1211:. Lecture Notes in Computer Science. Vol. 5912. Springer Berlin Heidelberg. pp. 598–616.
1156:. Lecture Notes in Computer Science. Vol. 7428. Springer Berlin Heidelberg. pp. 530–547.
1186:
2229:
2219:
2022:
1982:
1975:
1965:
1960:
1786:
1433:
347:{\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}
126:
69:
24:
72:
cryptography algorithms used to protect privacy and digitally sign information on the internet.
1970:
1868:
1719:
1658:
1593:
1068:
761:
527:
If this problem is difficult to solve, then the signature scheme will be difficult to forge.
2277:
2123:
2069:
1734:
1491:
1448:
2239:
2163:
1645:
1456:
959:
890:
118:
8:
2002:
1751:
493:
An entity wishing to sign messages generates its public key through the following steps:
145:
93:
963:
894:
35:
will become completely insecure if scientists are ever able to build a moderately sized
2108:
2092:
2039:
1598:
1521:
1501:
1496:
1476:
991:
949:
922:
880:
435:
97:
80:
76:
45:
28:
1036:
2168:
2158:
2029:
1858:
1801:
1729:
1615:
1301:
1220:
1165:
1086:
983:
975:
914:
906:
847:
61:
23:
from intentional modification and to authenticate the source of digital information.
16:
1114:
2103:
1704:
1212:
1157:
1078:
995:
967:
926:
898:
477:
65:
36:
1216:
1187:"The shortest vector in a lattice is hard to approximate to within some constant"
1161:
1082:
2178:
2098:
2059:
2007:
1992:
141:). This presentation is based on a 2017 update to the GLP scheme called GLYPH.
760:
and documented in their paper "Lattice Signatures and Bimodal Gaussians." See
676:
If c'(x) ≠ c(x) reject the signature, otherwise accept the signature as valid.
434:
A key feature of RLWE signature algorithms is the use of a technique known as
2296:
2259:
2214:
2173:
2153:
2049:
2012:
1987:
979:
910:
902:
851:
439:
374:
370:
2209:
2054:
2044:
2034:
1997:
1946:
1898:
1878:
987:
149:
20:
918:
2188:
1796:
1673:
885:
382:
971:
2148:
2118:
2113:
2074:
1822:
1554:
601:
B - k) go to step 1. (This is the rejection sampling step noted above)
2138:
1576:
1067:. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23.
2183:
2143:
1883:
1817:
1688:
1683:
1678:
1581:
1559:
1369:
1345:
1321:
1107:"What does GCHQ's "cautionary tale" mean for lattice cryptography?"
752:
745:
1286:
International Association of Cryptographic Research eprint Archive
1250:
954:
1709:
1668:
1279:"GLYPH: A New Instantiation of the GLP Digital Signature Scheme"
870:
75:
One of the most widely used public key algorithm used to create
2064:
1827:
413:
method and the value b will be much smaller than the value q.
1663:
1620:
1588:
1571:
1151:
840:"Researchers Report Milestone in Developing Quantum Computer"
89:
416:
364:
640:(x)), and the message m. The verifier does the following:
421:
Most RLWE signature algorithms also require the ability to
148:
modulo a degree n polynomial Φ(x) with coefficients in the
1191:
In Proc. 39th Symposium on Foundations of Computer Science
1756:
1610:
744:
Work by Bai and Galbraith on short signatures documented
1062:
547:(x) with coefficients from the set {-b, ..., 0, ...., b}
1154:
Cryptographic Hardware and Embedded Systems – CHES 2012
1012:
2085:
Cryptographically secure pseudorandom number generator
168:
1394:
92:memory and capable of executing a program known as
604:The signature is the triple of polynomials c(x), z
346:
109:disposal. This new area of cryptography is called
442:of a signature polynomial exceeds a fixed bound,
2294:
1306:: CS1 maint: bot: original URL status unknown (
939:
814:"Quantum computing breakthrough claim from IBM"
1288:. Archived from the original on 28 August 2017
1931:
1418:
1370:"Cryptology ePrint Archive: Report 2013/383"
1346:"Cryptology ePrint Archive: Report 2015/755"
1322:"Cryptology ePrint Archive: Report 2013/838"
1248:
1206:
786:
1432:
1938:
1924:
1425:
1411:
1184:
503:Distribute t(x) as the entity's public key
426:less than an integer bound b (see above).
1072:
953:
884:
627:
450:In the example which follows, the bound,
488:
1209:Advances in Cryptology – ASIACRYPT 2009
1065:Advances in Cryptology – EUROCRYPT 2010
837:
734:
615:Transmit the message along with c(x), z
530:
2295:
1276:
1251:"Lattice Signatures Without Trapdoors"
1919:
1406:
1272:
1270:
1268:
1266:
1264:
1244:
1242:
1240:
1238:
1236:
1202:
1200:
1147:
1145:
1143:
1141:
1139:
1137:
1135:
1133:
1131:
429:
1746:Naccache–Stern knapsack cryptosystem
1007:
1005:
782:
780:
778:
776:
156:for an odd prime q ( i.e. the ring Z
644:Verify that the infinity norms of z
457:
13:
1261:
1233:
1197:
1128:
1037:"The Learning with Errors Problem"
789:"ETSI - Quantum-Safe Cryptography"
14:
2319:
1390:
1002:
773:
144:A RLWE-SIG works in the quotient
102:elliptic curve discrete logarithm
2273:
2272:
1945:
811:
673:Compute c'(x) = POLYHASH(ω' | m)
539:Generate two small polynomials y
1777:Discrete logarithm cryptography
1362:
1338:
1314:
1178:
728:(x) = w(x) (as defined above)
500:Compute t(x) = a(x)·s(x) + e(x)
417:Hashing to a "small" polynomial
365:Generating "small" polynomials.
2134:Information-theoretic security
1099:
1056:
1029:
933:
864:
831:
805:
670:Map w'(x) into a bit string ω'
656:, if not reject the signature.
383:coefficients of the polynomial
178:
172:
100:problem and the more esoteric
1:
766:
589:Until the infinity norms of z
85:integer factorization problem
55:
1792:Non-commutative cryptography
1249:Lyubashevsky, Vadim (2011).
1217:10.1007/978-3-642-10366-7_35
1185:Micciancio, Daniele (1998).
1162:10.1007/978-3-642-33027-8_31
838:Markoff, John (2015-03-04).
561:Map w(x) into a bit string ω
438:. In this technique, if the
7:
2250:Message authentication code
2205:Cryptographic hash function
2018:Cryptographic hash function
1889:Identity-based cryptography
1782:Elliptic-curve cryptography
1083:10.1007/978-3-642-13190-5_1
691:(x) - t(x)c(x) = a(x)· + z
10:
2324:
2308:Lattice-based cryptography
2129:Harvest now, decrypt later
787:Dahmen-Lhuissier, Sabine.
33:Elliptic Curve Signatures)
2303:Post-quantum cryptography
2268:
2245:Post-quantum cryptography
2197:
1953:
1915:
1894:Post-quantum cryptography
1851:
1843:Post-Quantum Cryptography
1810:
1769:
1697:
1639:
1520:
1447:
1440:
1402:
1398:
1255:Cryptology ePrint Archive
50:Ring learning with errors
41:Post quantum cryptography
2235:Quantum key distribution
2225:Authenticated encryption
2080:Random number generation
903:10.1103/PhysRevA.54.1034
2230:Public-key cryptography
2220:Symmetric-key algorithm
2023:Key derivation function
1983:Cryptographic primitive
1976:Authentication protocol
1966:Outline of cryptography
1961:History of cryptography
1787:Hash-based cryptography
1434:Public-key cryptography
127:Shortest Vector Problem
25:Public key cryptography
19:are a means to protect
1971:Cryptographic protocol
1277:Chopra, Arjun (2017).
762:BLISS signature scheme
659:Compute w'(x) = a(x)·z
628:Signature Verification
516:(x) such that: a(x)·f
423:cryptographically hash
348:
2124:End-to-end encryption
2070:Cryptojacking malware
1449:Integer factorization
550:Compute w(x) = a(x)·y
489:Public key generation
349:
2240:Quantum cryptography
2164:Trusted timestamping
735:Further developments
623:(x) to the verifier.
531:Signature generation
474:Nothing Up My Sleeve
166:
119:Learning with Errors
2003:Cryptographic nonce
1752:Three-pass protocol
972:10.1038/nature12290
964:2013Natur.499..163S
895:1996PhRvA..54.1034B
713:(x) + e(x)·c(x) + y
582:(x) = e(x)·c(x) + y
571:(x) = s(x)·c(x) + y
447:secret key values.
146:ring of polynomials
21:digital information
2109:Subliminal channel
2093:Pseudorandom noise
2040:Key (cryptography)
1522:Discrete logarithm
844:The New York Times
436:rejection sampling
430:Rejection sampling
344:
98:discrete logarithm
77:digital signatures
17:Digital signatures
2290:
2289:
2286:
2285:
2169:Key-based routing
2159:Trapdoor function
2030:Digital signature
1911:
1910:
1907:
1906:
1859:Digital signature
1802:Trapdoor function
1765:
1764:
1482:Goldwasser–Micali
1226:978-3-642-10365-0
1171:978-3-642-33026-1
1111:www.cc.gatech.edu
1092:978-3-642-13189-9
948:(7457): 163–165.
873:Physical Review A
476:" manner such as
62:quantum computing
2315:
2276:
2275:
2104:Insecure channel
1940:
1933:
1926:
1917:
1916:
1748:
1649:
1644:
1604:signature scheme
1507:Okamoto–Uchiyama
1445:
1444:
1427:
1420:
1413:
1404:
1403:
1400:
1399:
1396:
1395:
1384:
1383:
1381:
1380:
1366:
1360:
1359:
1357:
1356:
1342:
1336:
1335:
1333:
1332:
1318:
1312:
1311:
1305:
1297:
1295:
1293:
1283:
1274:
1259:
1258:
1246:
1231:
1230:
1204:
1195:
1194:
1182:
1176:
1175:
1149:
1126:
1125:
1123:
1122:
1113:. Archived from
1103:
1097:
1096:
1076:
1060:
1054:
1053:
1051:
1050:
1044:www.cims.nyu.edu
1041:
1033:
1027:
1026:
1024:
1023:
1009:
1000:
999:
957:
937:
931:
930:
888:
886:quant-ph/9602016
879:(2): 1034–1063.
868:
862:
861:
859:
858:
835:
829:
828:
826:
825:
816:. Archived from
809:
803:
802:
800:
799:
784:
717:(x) - e(x)·c(x)
706:(x) - e(x)·c(x)
458:Other parameters
411:uniform sampling
399:Uniform Sampling
353:
351:
350:
345:
343:
342:
327:
326:
308:
307:
292:
291:
273:
272:
257:
256:
232:
231:
222:
221:
206:
205:
193:
192:
94:Shor's algorithm
66:quantum computer
60:Developments in
37:quantum computer
2323:
2322:
2318:
2317:
2316:
2314:
2313:
2312:
2293:
2292:
2291:
2282:
2264:
2193:
1949:
1944:
1903:
1847:
1811:Standardization
1806:
1761:
1744:
1693:
1641:Lattice/SVP/CVP
1635:
1516:
1462:Blum–Goldwasser
1436:
1431:
1393:
1388:
1387:
1378:
1376:
1374:eprint.iacr.org
1368:
1367:
1363:
1354:
1352:
1350:eprint.iacr.org
1344:
1343:
1339:
1330:
1328:
1326:eprint.iacr.org
1320:
1319:
1315:
1299:
1298:
1291:
1289:
1281:
1275:
1262:
1247:
1234:
1227:
1205:
1198:
1183:
1179:
1172:
1150:
1129:
1120:
1118:
1105:
1104:
1100:
1093:
1074:10.1.1.297.6108
1061:
1057:
1048:
1046:
1039:
1035:
1034:
1030:
1021:
1019:
1011:
1010:
1003:
938:
934:
869:
865:
856:
854:
836:
832:
823:
821:
810:
806:
797:
795:
785:
774:
769:
737:
727:
723:
716:
712:
705:
701:
694:
690:
686:
666:
662:
651:
647:
639:
635:
630:
622:
618:
611:
607:
596:
592:
585:
581:
574:
570:
557:
553:
546:
542:
533:
523:
519:
515:
511:
491:
478:one-way hashing
466:
460:
432:
419:
392:
388:
380:
367:
359:
332:
328:
316:
312:
297:
293:
281:
277:
262:
258:
246:
242:
227:
223:
217:
213:
201:
197:
188:
184:
167:
164:
163:
159:
155:
58:
12:
11:
5:
2321:
2311:
2310:
2305:
2288:
2287:
2284:
2283:
2281:
2280:
2269:
2266:
2265:
2263:
2262:
2257:
2255:Random numbers
2252:
2247:
2242:
2237:
2232:
2227:
2222:
2217:
2212:
2207:
2201:
2199:
2195:
2194:
2192:
2191:
2186:
2181:
2179:Garlic routing
2176:
2171:
2166:
2161:
2156:
2151:
2146:
2141:
2136:
2131:
2126:
2121:
2116:
2111:
2106:
2101:
2099:Secure channel
2096:
2090:
2089:
2088:
2077:
2072:
2067:
2062:
2060:Key stretching
2057:
2052:
2047:
2042:
2037:
2032:
2027:
2026:
2025:
2020:
2010:
2008:Cryptovirology
2005:
2000:
1995:
1993:Cryptocurrency
1990:
1985:
1980:
1979:
1978:
1968:
1963:
1957:
1955:
1951:
1950:
1943:
1942:
1935:
1928:
1920:
1913:
1912:
1909:
1908:
1905:
1904:
1902:
1901:
1896:
1891:
1886:
1881:
1876:
1871:
1866:
1861:
1855:
1853:
1849:
1848:
1846:
1845:
1840:
1835:
1830:
1825:
1820:
1814:
1812:
1808:
1807:
1805:
1804:
1799:
1794:
1789:
1784:
1779:
1773:
1771:
1767:
1766:
1763:
1762:
1760:
1759:
1754:
1749:
1742:
1740:Merkle–Hellman
1737:
1732:
1727:
1722:
1717:
1712:
1707:
1701:
1699:
1695:
1694:
1692:
1691:
1686:
1681:
1676:
1671:
1666:
1661:
1655:
1653:
1637:
1636:
1634:
1633:
1628:
1623:
1618:
1613:
1608:
1607:
1606:
1596:
1591:
1586:
1585:
1584:
1579:
1569:
1564:
1563:
1562:
1557:
1547:
1542:
1537:
1532:
1526:
1524:
1518:
1517:
1515:
1514:
1509:
1504:
1499:
1494:
1489:
1487:Naccache–Stern
1484:
1479:
1474:
1469:
1464:
1459:
1453:
1451:
1442:
1438:
1437:
1430:
1429:
1422:
1415:
1407:
1392:
1391:External links
1389:
1386:
1385:
1361:
1337:
1313:
1260:
1232:
1225:
1196:
1177:
1170:
1127:
1098:
1091:
1055:
1028:
1013:"Introduction"
1001:
932:
863:
830:
804:
771:
770:
768:
765:
757:
756:
749:
736:
733:
725:
721:
714:
710:
703:
699:
692:
688:
684:
678:
677:
674:
671:
668:
667:(x) - t(x)c(x)
664:
660:
657:
649:
645:
637:
633:
629:
626:
625:
624:
620:
616:
613:
609:
605:
602:
594:
590:
587:
583:
579:
576:
572:
568:
565:
562:
559:
555:
551:
548:
544:
540:
532:
529:
521:
517:
513:
509:
505:
504:
501:
498:
490:
487:
464:
459:
456:
431:
428:
418:
415:
407:
406:
402:
390:
386:
378:
366:
363:
357:
341:
338:
335:
331:
325:
322:
319:
315:
311:
306:
303:
300:
296:
290:
287:
284:
280:
276:
271:
268:
265:
261:
255:
252:
249:
245:
241:
238:
235:
230:
226:
220:
216:
212:
209:
204:
200:
196:
191:
187:
183:
180:
177:
174:
171:
157:
153:
57:
54:
9:
6:
4:
3:
2:
2320:
2309:
2306:
2304:
2301:
2300:
2298:
2279:
2271:
2270:
2267:
2261:
2260:Steganography
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2236:
2233:
2231:
2228:
2226:
2223:
2221:
2218:
2216:
2215:Stream cipher
2213:
2211:
2208:
2206:
2203:
2202:
2200:
2196:
2190:
2187:
2185:
2182:
2180:
2177:
2175:
2174:Onion routing
2172:
2170:
2167:
2165:
2162:
2160:
2157:
2155:
2154:Shared secret
2152:
2150:
2147:
2145:
2142:
2140:
2137:
2135:
2132:
2130:
2127:
2125:
2122:
2120:
2117:
2115:
2112:
2110:
2107:
2105:
2102:
2100:
2097:
2094:
2091:
2086:
2083:
2082:
2081:
2078:
2076:
2073:
2071:
2068:
2066:
2063:
2061:
2058:
2056:
2053:
2051:
2050:Key generator
2048:
2046:
2043:
2041:
2038:
2036:
2033:
2031:
2028:
2024:
2021:
2019:
2016:
2015:
2014:
2013:Hash function
2011:
2009:
2006:
2004:
2001:
1999:
1996:
1994:
1991:
1989:
1988:Cryptanalysis
1986:
1984:
1981:
1977:
1974:
1973:
1972:
1969:
1967:
1964:
1962:
1959:
1958:
1956:
1952:
1948:
1941:
1936:
1934:
1929:
1927:
1922:
1921:
1918:
1914:
1900:
1897:
1895:
1892:
1890:
1887:
1885:
1882:
1880:
1877:
1875:
1872:
1870:
1867:
1865:
1862:
1860:
1857:
1856:
1854:
1850:
1844:
1841:
1839:
1836:
1834:
1831:
1829:
1826:
1824:
1821:
1819:
1816:
1815:
1813:
1809:
1803:
1800:
1798:
1795:
1793:
1790:
1788:
1785:
1783:
1780:
1778:
1775:
1774:
1772:
1768:
1758:
1755:
1753:
1750:
1747:
1743:
1741:
1738:
1736:
1733:
1731:
1728:
1726:
1723:
1721:
1718:
1716:
1713:
1711:
1708:
1706:
1703:
1702:
1700:
1696:
1690:
1687:
1685:
1682:
1680:
1677:
1675:
1672:
1670:
1667:
1665:
1662:
1660:
1657:
1656:
1654:
1652:
1647:
1642:
1638:
1632:
1629:
1627:
1624:
1622:
1619:
1617:
1614:
1612:
1609:
1605:
1602:
1601:
1600:
1597:
1595:
1592:
1590:
1587:
1583:
1580:
1578:
1575:
1574:
1573:
1570:
1568:
1565:
1561:
1558:
1556:
1553:
1552:
1551:
1548:
1546:
1543:
1541:
1538:
1536:
1533:
1531:
1528:
1527:
1525:
1523:
1519:
1513:
1512:Schmidt–Samoa
1510:
1508:
1505:
1503:
1500:
1498:
1495:
1493:
1490:
1488:
1485:
1483:
1480:
1478:
1475:
1473:
1472:Damgård–Jurik
1470:
1468:
1467:Cayley–Purser
1465:
1463:
1460:
1458:
1455:
1454:
1452:
1450:
1446:
1443:
1439:
1435:
1428:
1423:
1421:
1416:
1414:
1409:
1408:
1405:
1401:
1397:
1375:
1371:
1365:
1351:
1347:
1341:
1327:
1323:
1317:
1309:
1303:
1287:
1280:
1273:
1271:
1269:
1267:
1265:
1256:
1252:
1245:
1243:
1241:
1239:
1237:
1228:
1222:
1218:
1214:
1210:
1203:
1201:
1192:
1188:
1181:
1173:
1167:
1163:
1159:
1155:
1148:
1146:
1144:
1142:
1140:
1138:
1136:
1134:
1132:
1117:on 2015-07-06
1116:
1112:
1108:
1102:
1094:
1088:
1084:
1080:
1075:
1070:
1066:
1059:
1045:
1038:
1032:
1018:
1014:
1008:
1006:
997:
993:
989:
985:
981:
977:
973:
969:
965:
961:
956:
951:
947:
943:
936:
928:
924:
920:
916:
912:
908:
904:
900:
896:
892:
887:
882:
878:
874:
867:
853:
849:
845:
841:
834:
820:on 2015-09-23
819:
815:
808:
794:
790:
783:
781:
779:
777:
772:
764:
763:
754:
750:
747:
743:
742:
741:
732:
729:
718:
707:
696:
681:
680:Notice that:
675:
672:
669:
658:
655:
643:
642:
641:
614:
603:
600:
588:
577:
566:
563:
560:
549:
538:
537:
536:
528:
525:
502:
499:
496:
495:
494:
486:
484:
479:
475:
469:
455:
453:
448:
445:
441:
440:infinity norm
437:
427:
424:
414:
412:
403:
400:
396:
395:
394:
384:
376:
375:infinity norm
372:
371:infinity norm
362:
354:
339:
336:
333:
329:
323:
320:
317:
313:
309:
304:
301:
298:
294:
288:
285:
282:
278:
274:
269:
266:
263:
259:
253:
250:
247:
243:
239:
236:
233:
228:
224:
218:
214:
210:
207:
202:
198:
194:
189:
185:
181:
175:
169:
161:
151:
147:
142:
140:
134:
132:
131:ideal lattice
128:
122:
120:
116:
112:
106:
103:
99:
95:
91:
86:
82:
78:
73:
71:
67:
63:
53:
51:
47:
42:
38:
34:
30:
26:
22:
18:
2210:Block cipher
2055:Key schedule
2045:Key exchange
2035:Kleptography
1998:Cryptosystem
1947:Cryptography
1899:OpenPGP card
1879:Web of trust
1535:Cramer–Shoup
1377:. Retrieved
1373:
1364:
1353:. Retrieved
1349:
1340:
1329:. Retrieved
1325:
1316:
1290:. Retrieved
1285:
1254:
1208:
1190:
1180:
1153:
1119:. Retrieved
1115:the original
1110:
1101:
1064:
1058:
1047:. Retrieved
1043:
1031:
1020:. Retrieved
1017:pqcrypto.org
1016:
945:
941:
935:
876:
872:
866:
855:. Retrieved
843:
833:
822:. Retrieved
818:the original
812:Shah, Agam.
807:
796:. Retrieved
792:
758:
738:
730:
719:
708:
697:
682:
679:
653:
631:
598:
534:
526:
506:
492:
482:
470:
461:
451:
449:
443:
433:
420:
408:
368:
355:
162:
150:finite field
143:
135:
123:
115:Quantum Safe
111:Post Quantum
107:
79:is known as
74:
59:
15:
2198:Mathematics
2189:Mix network
1869:Fingerprint
1833:NSA Suite B
1797:RSA problem
1674:NTRUEncrypt
695:(x) - c(x)
524:(x) = t(x)
356:The field Z
2297:Categories
2149:Ciphertext
2119:Decryption
2114:Encryption
2075:Ransomware
1823:IEEE P1363
1441:Algorithms
1379:2016-01-17
1355:2016-01-17
1331:2016-01-17
1121:2015-07-05
1049:2015-05-24
1022:2015-07-05
857:2015-07-05
824:2015-06-01
798:2015-07-05
767:References
70:public key
56:Background
2139:Plaintext
1292:26 August
1069:CiteSeerX
980:0028-0836
955:1301.7007
911:1050-2947
852:0362-4331
698:= a(x)·y
648:(x) and z
619:(x) and z
608:(x) and z
593:(x) and z
578:Compute z
567:Compute z
543:(x) and y
512:(x) and f
361:studied.
337:−
321:−
302:−
286:−
267:−
251:−
237:…
2278:Category
2184:Kademlia
2144:Codetext
2087:(CSPRNG)
1884:Key size
1818:CRYPTREC
1735:McEliece
1689:RLWE-SIG
1684:RLWE-KEX
1679:NTRUSign
1492:Paillier
1302:cite web
1193:: 92–98.
988:23846653
720:= a(x)y
709:= a(x)y
389:, ..., a
373:". The
1954:General
1730:Lamport
1710:CEILIDH
1669:NewHope
1616:Schnorr
1599:ElGamal
1577:Ed25519
1457:Benaloh
996:4422110
960:Bibcode
927:2231795
919:9913575
891:Bibcode
724:(x) + y
702:(x) + z
687:(x) + z
663:(x) + z
554:(x) + y
520:(x) + f
485:= b-k.
405:method.
2065:Keygen
1852:Topics
1828:NESSIE
1770:Theory
1698:Others
1555:X25519
1223:
1168:
1089:
1071:
994:
986:
978:
942:Nature
925:
917:
909:
850:
683:a(x)·z
652:(x) ≤
636:(x), z
597:(x) ≤
397:Using
129:in an
2095:(PRN)
1664:Kyber
1659:BLISS
1621:SPEKE
1589:ECMQV
1582:Ed448
1572:EdDSA
1567:ECDSA
1497:Rabin
1282:(PDF)
1040:(PDF)
992:S2CID
950:arXiv
923:S2CID
881:arXiv
599:β = (
90:qubit
1864:OAEP
1838:CNSA
1715:EPOC
1560:X448
1550:ECDH
1308:link
1294:2017
1221:ISBN
1166:ISBN
1087:ISBN
984:PMID
976:ISSN
915:PMID
907:ISSN
848:ISSN
793:ETSI
753:here
746:here
31:and
1874:PKI
1757:XTR
1725:IES
1720:HFE
1651:SIS
1646:LWE
1631:STS
1626:SRP
1611:MQV
1594:EKE
1545:DSA
1530:BLS
1502:RSA
1477:GMR
1213:doi
1158:doi
1079:doi
968:doi
946:499
899:doi
612:(x)
586:(x)
575:(x)
558:(x)
391:n-1
139:GLP
113:or
81:RSA
46:RSA
29:RSA
2299::
1705:AE
1540:DH
1372:.
1348:.
1324:.
1304:}}
1300:{{
1284:.
1263:^
1253:.
1235:^
1219:.
1199:^
1189:.
1164:.
1130:^
1109:.
1085:.
1077:.
1042:.
1015:.
1004:^
990:.
982:.
974:.
966:.
958:.
944:.
921:.
913:.
905:.
897:.
889:.
877:54
875:.
846:.
842:.
791:.
775:^
452:β,
444:β,
385:(a
39:.
1939:e
1932:t
1925:v
1648:/
1643:/
1426:e
1419:t
1412:v
1382:.
1358:.
1334:.
1310:)
1296:.
1257:.
1229:.
1215::
1174:.
1160::
1124:.
1095:.
1081::
1052:.
1025:.
998:.
970::
962::
952::
929:.
901::
893::
883::
860:.
827:.
801:.
755:.
748:.
726:2
722:1
715:2
711:1
704:2
700:1
693:2
689:2
685:1
665:2
661:1
654:β
650:2
646:1
638:2
634:1
621:2
617:1
610:2
606:1
595:2
591:1
584:2
580:2
573:1
569:1
556:2
552:1
545:2
541:1
522:2
518:1
514:2
510:1
508:f
483:β
472:"
465:q
463:F
387:0
379:q
358:q
340:1
334:n
330:x
324:1
318:n
314:a
310:+
305:2
299:n
295:x
289:2
283:n
279:a
275:+
270:3
264:n
260:x
254:3
248:n
244:a
240:+
234:+
229:2
225:x
219:2
215:a
211:+
208:x
203:1
199:a
195:+
190:0
186:a
182:=
179:)
176:x
173:(
170:a
158:q
154:q
152:Z
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.