424:, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme. The corresponding private key would be roughly 14,000 bits. An RLWE version of the classic MQV variant of a DiffieâHellman key exchange was later published by Zhang et al. in 2014. The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice. This article will closely follow the RLWE work of Ding in "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem". For this presentation a typical polynomial is expressed as:
3290:
sleeve" or NUMS technique. An example of parameters generated in this way are the prime numbers for the
Internet Key Exchange (RFC 2409) which embed the digits of the mathematical constant pi in the digital representation of the prime number. Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves. The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.
862:. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. Other cases for q and n are thoroughly discussed in "A Toolkit for Ring-LWE Cryptography" and in Singh's "Even More Practical Key Exchange for the Internet using Lattice Cryptography." and another paper by Singh. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.
4733:
1085:. The description which follows does not contain any explanation of why the key exchange results in the same key at both ends of a link. Rather, it succinctly specifies the steps to be taken. For a thorough understanding of why the key exchange results in the initiator and responder having the same key, the reader should look at the referenced work by Ding et al.
33:
3289:
Also in their
November 2015 paper, Alkim, Ducas, Pöppelmann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a "nothing up my
169:
of sufficient size were built, all of the public key algorithms based on these three classically hard problems would be insecure. This public key cryptography is used today to secure
Internet websites, protect computer login information, and prevent our computers from accepting malicious software.
3334:
A variant of the approach described above is an authenticated version in the work of Zhang, Zhang, Ding, Snook and
Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices." The concept of creating what has been called a DiffieâHellman-like Key Exchange using lattices
3036:
Depending on the specifics of the parameters chosen, there is an extremely small probability that this key exchange will fail to produce the same key. Parameters for the key exchange can be chosen to make the probability of failure in the key exchange very small; much less than the probability of
410:
The idea of using LWE and Ring LWE for key exchange was first proposed and filed at the
University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper appeared in 2012 after a provisional
3338:
In
November 2015, Alkim, Ducas, Pöppelmann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters. Software based on the work of Alkim, Ducas, Pöppelmann, and Schwabe is found on GitHub at
3310:. The best method to gauge the practical security of a given set of lattice parameters is the BKZ 2.0 lattice reduction algorithm. According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.
2726:
2866:
2417:
854:. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. An overview of Gaussian sampling is found in a presentation by Peikert.
2924:
are only approximately equal. In order to extract a shared key using this approximate equal values, a reconciliation function, also known as a signal function is used. This function indicates the region in which each coefficient of a polynomial
617:
254:
key exchanges that are used to secure the establishment of secret keys over untrusted communications channels. Like DiffieâHellman and
Elliptic Curve DiffieâHellman, the Ring-LWE key exchange provides a cryptographic property called
779: â 1)/2} ). The algorithm's security depends on an ability to generate random polynomials which are small with respect to the infinity norm. This is done simply by randomly generating the coefficients for a polynomial (s
2197:
3197:
Because the key exchange uses random sampling and fixed bounds there is a small probability that the key exchange will fail to produce the same key for the initiator and responder. If we assume that the
Gaussian parameter
3322:
for OpenSSL 1.0.1f. based on his work and others published in "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem." Software implementing the work of Singh is found on GitHub at
3078:. The presentation assumed that n was a power of 2 and that q was a prime which was congruent to 1 (mod 2n). Following the guidance given in Peikert's paper, Singh suggested two sets of parameters for the RLWE-KEX.
2497:
3029:
The methods of reconciliation and key string generation depends on the specific RLWE-KEX scheme in question. Some method is based on modular arithmetic, while others may be based on high-dimension geometry.
3335:
with a reconciliation function appears to have first been presented by French researchers
Aguilar, Gaborit, Lacharme, Schrek, and Zemor at PQCrypto 2010 in their talk, "Noisy DiffieâHellman Protocols."
2625:
1650:
2268:
1843:
161:
group. These problems are very difficult to solve on a classical computer (the type of computer the world has known since the 1940s through today) but are rather easily solved by a relatively small
414:
In 2014, Peikert presented a key-transport scheme following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used.
2630:
1720:
1552:
2754:
3232:
4713:
4543:
376:
2572:
2339:
1675:
1241:
1083:
3193:
2759:
1423:
149:
algorithms. The security of these algorithms is based on a similarly small number of computationally hard problems in classical computing. These problems are the difficulty of
3135:
4173:
2523:
929:
The key exchange will take place between two devices. There will be an initiator for the key exchange designated as (I) and a respondent designated as (R). Both I and R know
736:
2549:
2057:
1483:
1361:
1176:
1017:
970:
2347:
51:
2030:
1456:
3883:
227:
is a type of public key algorithm which establishes a shared secret key between two communicants on a communications link. The classic example of a key exchange is the
3276:
3076:
680:
430:
405:
310:
990:
3024:
2997:
2970:
2922:
2895:
2315:
1977:
1920:
1890:
1773:
1334:
1307:
1270:
1149:
1122:
647:
165:
using only 5 to 10 thousand of bits of memory. There is optimism in the computer industry that larger scale quantum computers will be available around 2030. If a
4301:
1746:
769:
4396:
2943:
2288:
1997:
1940:
1863:
4296:
744:." The infinity norm for a polynomial is simply the value of the largest coefficient of the polynomial when the coefficients are considered as integers in
4025:
3279:
4204:
4198:
2062:
4322:
3876:
3757:
3421:
417:
The "New Hope" implementation selected for Google's post-quantum experiment, uses
Peikert's scheme with variation in the error distribution.
819:} the polynomial will be small with respect to the bound (b). Singh suggest using b = 5. Thus coefficients would be chosen from the set {
4771:
3366:
217:
3940:
2422:
4766:
4008:
3965:
3930:
251:
236:
4761:
4389:
858:
For the rest of this article, the random small polynomials will be sampled according to a distribution which is simply specified as
69:
3920:
3869:
3998:
3945:
2583:
232:
228:
4084:
3278:= x + 1. This represents a 70% reduction in public key size over the n = 1024 parameters of Singh, and was submitted to NIST's
3249:
In their November 2015 paper, Alkim, Ducas, Pöppelmann, and Schwabe recommend the following parameters n = 1024, q =12289, and
792:
411:
patent application was filed in 2012. The security of the protocol is proven based on the hardness of solving the LWE problem.
186:
105:) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a
3740:
Chen, Yuanmi; Nguyen, Phong Q. (2011). "BKZ 2.0: Better Lattice Security Estimates". In Lee, Dong Hoon; Wang, Xiaoyun (eds.).
2205:
1780:
4592:
4109:
3993:
846:
Sampling â For an odd value for q, the coefficients are randomly chosen by sampling from the set { â(q â 1)/2 to (
231:. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link.
1557:
2721:{\displaystyle \operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}}
378:). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod
94:
which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The
4382:
4250:
4183:
3925:
263:
programs and ensure that there are no long term secret keys that can be compromised that would enable bulk decryption.
4708:
4663:
4476:
4347:
4240:
4089:
4003:
3988:
4587:
4099:
3970:
3361:
3356:
3307:
1680:
202:
122:
4703:
4352:
4332:
3371:
3351:
3299:
276:
243:
198:
178:
174:
126:
118:
114:
96:
3817:
4693:
4683:
4538:
4291:
4062:
3510:
2732:
1488:
850: â 1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter
157:
in a carefully chosen finite field, and the difficulty of computing discrete logarithms in a carefully chosen
4688:
4678:
4481:
4441:
4434:
4424:
4419:
4245:
3892:
3303:
3205:
2861:{\displaystyle \operatorname {Mod} _{2}(v,w)={\biggl (}v+w.{\frac {q-1}{2}}{\Biggr )}{\bmod {q}}{\bmod {2}}}
209:
91:
315:
4429:
4327:
4178:
4117:
4052:
3399:
3033:
If the key exchange worked properly, the initiator's string and the respondent's string will be the same.
2557:
2324:
1660:
1184:
1022:
224:
213:
3150:
1369:
4736:
4582:
4528:
4193:
3950:
3907:
3792:
3092:
889:) to be the "private key" in a public key exchange. The corresponding public key will be the polynomial
843:
795:â The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let
683:
150:
3717:"Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?"
2502:
2412:{\displaystyle \mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}}
693:
2528:
4698:
4622:
4104:
3915:
2035:
1461:
1339:
1154:
995:
948:
182:
110:
3404:
2657:
4461:
4210:
280:
154:
247:
4567:
4551:
4498:
4235:
4057:
3980:
3960:
3955:
3935:
3427:
740:
The RLWE-KEX uses polynomials which are considered "small" with respect to a measure called the "
612:{\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}
3744:. Lecture Notes in Computer Science. Vol. 7073. Springer Berlin Heidelberg. pp. 1â20.
3588:
3394:
Regev, Oded (2005). "On lattices, learning with errors, random linear codes, and cryptography".
121:
algorithms which are based on the difficulty of solving certain mathematical problems involving
208:
There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are
4627:
4617:
4488:
4317:
4260:
4188:
4074:
3753:
3417:
3252:
3052:
656:
381:
286:
260:
162:
142:
975:
4562:
4163:
3745:
3409:
2005:
1431:
421:
166:
113:
in use today will be easily broken by a quantum computer if such computers are implemented.
106:
3775:"Post-quantum key exchange for the TLS protocol from the ring learning with errors problem"
3002:
2975:
2948:
2900:
2873:
2293:
1955:
1898:
1868:
1751:
1312:
1285:
1248:
1127:
1100:
625:
220:
algorithms in addition to the public key, key exchange algorithm presented in this article
256:
190:
1725:
787:) which are guaranteed or very likely to be small. There are two common ways to do this:
181:. One class of quantum resistant cryptographic algorithms is based on a concept called "
751:
4637:
4557:
4518:
4466:
4451:
3319:
2928:
2273:
1982:
1925:
1848:
173:
Cryptography that is not susceptible to attack by a quantum computer is referred to as
158:
3455:
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem
4755:
4718:
4673:
4632:
4612:
4508:
4471:
4446:
741:
3431:
945:), and have the ability to generate small polynomials according to the distribution
4668:
4513:
4503:
4493:
4456:
4405:
4357:
4337:
272:
194:
138:
87:
83:
3045:
The RLWE-KEX exchange presented above worked in the Ring of Polynomials of degree
3773:
Bos, Joppe W.; Costello, Craig; Naehrig, Michael; Stebila, Douglas (2014-01-01).
4647:
4255:
4132:
3749:
4607:
4577:
4572:
4533:
4281:
4013:
146:
3396:
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
3302:
problem that has been proven to be as hard as the worst case solution to the
4597:
3413:
3716:
3491:
Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01).
3340:
4642:
4602:
4342:
4276:
4147:
4142:
4137:
4018:
3298:
The security of this key exchange is based on the underlying hardness of
189:
in 2005. A specialized form of Learning with errors operates within the
2756:
is the mod 2 operation to eliminate the error terms defined as follows:
2551:
denotes the floor and the rounding to the nearest integer respectively.
2192:{\displaystyle k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}}
17:
4168:
4127:
3453:
3283:
3692:
3547:"A Practical Key Exchange for the Internet using Lattice Cryptography"
3324:
4523:
4286:
3828:
3238:) = 5 (see Singh), then the probability of key agreement failure is
3667:
3564:
3492:
1088:
The key exchange begins with the initiator (I) doing the following:
3634:
3473:
4122:
4079:
4047:
4040:
4035:
4030:
3774:
3616:
3546:
2492:{\displaystyle Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}}
807:, âb + 1, âb + 2. ... â2, â1, 0, 1, 2, ... ,
312:
with coefficients in the field of integers mod q (i.e. the ring
145:
over the Internet has been primarily based on a small number of
129:-KEX is provably reducible to a known hard problem in lattices.
4378:
3865:
4215:
4069:
26:
2849:
2839:
125:. Unlike older lattice based cryptographic algorithms, the
2714:
151:
factoring the product of two carefully chosen prime numbers
2620:{\displaystyle \operatorname {Sig} :Zq\rightarrow \{0,1\}}
1336:
with small coefficients by sampling from the distribution
1151:
with small coefficients by sampling from the distribution
1019:
is usually the discrete Gaussian distribution on the ring
3615:
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013).
3589:"An Efficient and Parallel Gaussian Sampler for Lattices"
2263:{\displaystyle sk_{I}=\operatorname {Mod} _{2}(k_{I},w)}
1838:{\displaystyle sk_{R}=\operatorname {Mod} _{2}(k_{R},w)}
1845:
is calculated, based on the reconciliation information
803:. If we randomly choose coefficients from the set: { â
47:
4544:
Cryptographically secure pseudorandom number generator
3208:
873:) as stated, we can randomly choose small polynomials
259:"; the aim of which is to reduce the effectiveness of
3255:
3153:
3095:
3055:
3005:
2978:
2951:
2931:
2903:
2876:
2762:
2735:
2633:
2586:
2560:
2531:
2505:
2425:
2350:
2327:
2296:
2276:
2208:
2065:
2038:
2008:
1985:
1958:
1928:
1901:
1871:
1851:
1783:
1754:
1728:
1683:
1663:
1645:{\displaystyle k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}}
1560:
1491:
1464:
1434:
1372:
1342:
1315:
1288:
1251:
1187:
1157:
1130:
1103:
1025:
998:
978:
951:
754:
696:
659:
628:
433:
384:
318:
289:
3853:
3398:. STOC '05. New York, NY, USA: ACM. pp. 84â93.
2972:
lies and helps to make sure that the error terms in
2574:
is the characteristic function of the complement of
4656:
4412:
4310:
4269:
4228:
4156:
4098:
3979:
3906:
3899:
3793:"Workshop on Cybersecurity in a Post-Quantum World"
42:
may be too technical for most readers to understand
3270:
3226:
3187:
3129:
3070:
3018:
2991:
2964:
2937:
2916:
2889:
2860:
2748:
2720:
2619:
2566:
2543:
2517:
2491:
2411:
2333:
2309:
2282:
2262:
2191:
2051:
2024:
1991:
1971:
1934:
1914:
1884:
1857:
1837:
1767:
1740:
1714:
1669:
1644:
1546:
1477:
1450:
1417:
1355:
1328:
1301:
1264:
1235:
1170:
1143:
1116:
1077:
1011:
984:
964:
763:
730:
674:
641:
611:
399:
370:
304:
239:are the two most popular key exchange algorithms.
2833:
2796:
3452:Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012).
3511:"Experimenting with Post-Quantum Cryptography"
649:of this polynomial are integers mod
137:Since the 1980s the security of cryptographic
4390:
3877:
3668:"Cryptology ePrint Archive: Report 2015/1092"
3635:"Cryptology ePrint Archive: Report 2015/1120"
3565:"Cryptology ePrint Archive: Report 2015/1120"
3026:do not result in different mod q operations.
1715:{\displaystyle w=\operatorname {Sig} (k_{R})}
8:
2614:
2602:
2538:
2532:
2512:
2506:
2486:
2435:
2406:
2403:
2390:
2378:
2365:
2359:
2202:Initiator side's key stream is produced as
242:The RLWE Key Exchange is designed to be a "
4397:
4383:
4375:
3903:
3884:
3870:
3862:
3858:
3854:
3691:D., Carrel; D., Harkins (November 1998).
3403:
3280:Post-Quantum Cryptography Standardization
3254:
3209:
3207:
3173:
3152:
3115:
3094:
3054:
3037:undetectable garbles or device failures.
3010:
3004:
2983:
2977:
2956:
2950:
2930:
2908:
2902:
2881:
2875:
2852:
2848:
2842:
2838:
2832:
2831:
2813:
2795:
2794:
2767:
2761:
2740:
2734:
2694:
2668:
2652:
2632:
2585:
2559:
2530:
2504:
2468:
2441:
2424:
2393:
2368:
2351:
2349:
2341:is the signal function defined as below:
2326:
2301:
2295:
2275:
2245:
2229:
2216:
2207:
2180:
2164:
2154:
2138:
2128:
2109:
2093:
2083:
2070:
2064:
2043:
2037:
2013:
2007:
1984:
1963:
1957:
1927:
1906:
1900:
1876:
1870:
1850:
1820:
1804:
1791:
1782:
1759:
1753:
1727:
1703:
1682:
1662:
1633:
1617:
1607:
1591:
1581:
1565:
1559:
1535:
1519:
1509:
1496:
1490:
1469:
1463:
1439:
1433:
1409:
1393:
1377:
1371:
1347:
1341:
1320:
1314:
1293:
1287:
1256:
1250:
1224:
1208:
1192:
1186:
1162:
1156:
1135:
1129:
1108:
1102:
1058:
1043:
1030:
1024:
1003:
997:
977:
956:
950:
753:
716:
695:
658:
633:
627:
597:
581:
562:
546:
527:
511:
492:
482:
466:
453:
432:
383:
351:
336:
323:
317:
288:
70:Learn how and when to remove this message
54:, without removing the technical details.
3493:"Post-quantum key exchange - a new hope"
3242:2 for the 128-bit secure parameters and
3049: â 1 or less mod a polynomial
2749:{\displaystyle \operatorname {Mod} _{2}}
1547:{\displaystyle k_{R}=p_{I}s_{R}+2e'_{R}}
3742:Advances in Cryptology â ASIACRYPT 2011
3474:"Lattice Cryptography for the Internet"
3383:
3341:https://github.com/tpoeppelmann/newhope
3227:{\textstyle {\frac {8}{\sqrt {2\pi }}}}
3662:
3660:
3658:
3656:
3654:
3617:"A Toolkit for Ring-LWE Cryptography"
3246:2 for the 256-bit secure parameters.
799:be an integer that is much less than
371:{\displaystyle R_{q}:=Z_{q}/\Phi (x)}
52:make it understandable to non-experts
7:
4205:NaccacheâStern knapsack cryptosystem
3540:
3538:
3536:
3534:
3532:
3530:
3447:
3445:
3443:
3441:
3389:
3387:
3325:https://github.com/vscrypto/ringlwe.
2567:{\displaystyle \operatorname {Sig} }
2334:{\displaystyle \operatorname {Sig} }
2270:from the reconciliation information
1670:{\displaystyle \operatorname {Sig} }
1236:{\displaystyle p_{I}=as_{I}+2e_{I}.}
1078:{\displaystyle R_{q}=Z_{q}/\Phi (x)}
3367:Ring learning with errors signature
3188:{\displaystyle \Phi (x)=x^{1024}+1}
1418:{\displaystyle p_{R}=as_{R}+2e_{R}}
1245:The initiator sends the polynomial
839: â 1, 0, 1, 2, 3, 4, 5 }.
197:. This specialized form is called
3256:
3154:
3130:{\displaystyle \Phi (x)=x^{512}+1}
3096:
3056:
1063:
697:
660:
385:
356:
290:
246:" replacement for the widely used
109:. This is important because some
25:
3693:"The Internet Key Exchange (IKE)"
2518:{\displaystyle \lfloor .\rfloor }
731:{\displaystyle \Phi (x)=x^{n}+1.}
4732:
4731:
3818:"Noisy DiffieâHellman protocols"
3234:and the uniform sampling bound (
2544:{\displaystyle \lfloor .\rceil }
2352:
1748:function on each coefficient of
31:
4236:Discrete logarithm cryptography
2052:{\displaystyle \chi _{\alpha }}
1722:. This is computed by applying
1478:{\displaystyle \chi _{\alpha }}
1356:{\displaystyle \chi _{\alpha }}
1171:{\displaystyle \chi _{\alpha }}
1012:{\displaystyle \chi _{\alpha }}
965:{\displaystyle \chi _{\alpha }}
775: â 1)/2,..., 0, ... (
4593:Information-theoretic security
3265:
3259:
3163:
3157:
3105:
3099:
3065:
3059:
2788:
2776:
2646:
2640:
2599:
2257:
2238:
1832:
1813:
1709:
1696:
1072:
1066:
1055:
1049:
706:
700:
669:
663:
443:
437:
420:For somewhat greater than 128
394:
388:
365:
359:
348:
342:
299:
293:
1:
3472:Peikert, Chris (2014-01-01).
3318:In 2014 Douglas Stebila made
1777:Respondent side's key stream
252:elliptic curve DiffieâHellman
237:Elliptic Curve DiffieâHellman
4251:Non-commutative cryptography
153:, the difficulty to compute
4709:Message authentication code
4664:Cryptographic hash function
4477:Cryptographic hash function
4348:Identity-based cryptography
4241:Elliptic-curve cryptography
3750:10.1007/978-3-642-25385-0_1
3515:Google Online Security Blog
2321:In the above key exchange,
229:DiffieâHellman key exchange
4788:
4772:Lattice-based cryptography
4588:Harvest now, decrypt later
3362:Ideal lattice cryptography
3357:Lattice-based cryptography
3139:For 256 bits of security,
3081:For 128 bits of security,
279:key exchange works in the
119:post-quantum cryptographic
4767:Post-quantum cryptography
4727:
4704:Post-quantum cryptography
4374:
4353:Post-quantum cryptography
4302:Post-Quantum Cryptography
3861:
3857:
3779:Cryptology ePrint Archive
3621:Cryptology ePrint Archive
3551:Cryptology ePrint Archive
3497:Cryptology ePrint Archive
3478:Cryptology ePrint Archive
3372:Ring learning with errors
3352:Post-quantum cryptography
3300:ring learning with errors
1282:Generate two polynomials
1097:Generate two polynomials
199:ring learning with errors
179:post-quantum cryptography
97:ring learning with errors
4762:Cryptographic algorithms
4694:Quantum key distribution
4684:Authenticated encryption
4539:Random number generation
3721:crypto.stackexchange.com
3271:{\displaystyle \Phi (x)}
3071:{\displaystyle \Phi (x)}
2870:Note that the values of
1657:Use the signal function
675:{\displaystyle \Phi (x)}
400:{\displaystyle \Phi (x)}
305:{\displaystyle \Phi (x)}
117:-KEX is one of a set of
4689:Public-key cryptography
4679:Symmetric-key algorithm
4482:Key derivation function
4442:Cryptographic primitive
4435:Authentication protocol
4425:Outline of cryptography
4420:History of cryptography
4246:Hash-based cryptography
3893:Public-key cryptography
3414:10.1145/1060590.1060603
3304:shortest vector problem
3282:project under the name
985:{\displaystyle \alpha }
92:cryptographic algorithm
4430:Cryptographic protocol
3545:Singh, Vikram (2015).
3272:
3228:
3189:
3131:
3072:
3020:
2993:
2966:
2939:
2918:
2891:
2862:
2750:
2722:
2621:
2568:
2545:
2519:
2493:
2413:
2335:
2311:
2284:
2264:
2193:
2053:
2026:
2025:{\displaystyle e'_{I}}
1993:
1973:
1936:
1916:
1886:
1859:
1839:
1769:
1742:
1716:
1671:
1646:
1548:
1479:
1452:
1451:{\displaystyle e'_{R}}
1419:
1357:
1330:
1303:
1266:
1237:
1172:
1145:
1118:
1079:
1013:
986:
966:
765:
732:
676:
643:
613:
401:
372:
306:
225:key exchange algorithm
218:RLWE digital signature
214:homomorphic encryption
4583:End-to-end encryption
4529:Cryptojacking malware
3908:Integer factorization
3294:Key exchange security
3273:
3229:
3190:
3132:
3073:
3021:
3019:{\displaystyle k_{I}}
2994:
2992:{\displaystyle k_{R}}
2967:
2965:{\displaystyle R_{q}}
2940:
2919:
2917:{\displaystyle k_{R}}
2892:
2890:{\displaystyle k_{I}}
2863:
2751:
2723:
2622:
2569:
2546:
2520:
2494:
2414:
2336:
2312:
2310:{\displaystyle k_{I}}
2285:
2265:
2194:
2054:
2027:
1994:
1974:
1972:{\displaystyle p_{R}}
1937:
1917:
1915:{\displaystyle p_{R}}
1895:The Respondent sends
1887:
1885:{\displaystyle k_{R}}
1860:
1840:
1770:
1768:{\displaystyle k_{R}}
1743:
1717:
1672:
1647:
1549:
1480:
1453:
1420:
1358:
1331:
1329:{\displaystyle e_{R}}
1304:
1302:{\displaystyle s_{R}}
1267:
1265:{\displaystyle p_{I}}
1238:
1173:
1146:
1144:{\displaystyle e_{I}}
1119:
1117:{\displaystyle s_{I}}
1080:
1014:
987:
967:
771:(i.e.from the set {â(
766:
733:
690:is a power of 2 then
684:cyclotomic polynomial
677:
644:
642:{\displaystyle a_{i}}
614:
402:
373:
307:
210:public-key encryption
111:public key algorithms
4699:Quantum cryptography
4623:Trusted timestamping
3253:
3206:
3151:
3093:
3053:
3003:
2976:
2949:
2929:
2901:
2874:
2760:
2733:
2631:
2584:
2558:
2529:
2503:
2423:
2348:
2325:
2294:
2274:
2206:
2063:
2036:
2006:
1983:
1956:
1926:
1899:
1869:
1849:
1781:
1752:
1726:
1681:
1661:
1558:
1489:
1462:
1432:
1370:
1340:
1313:
1286:
1249:
1185:
1155:
1128:
1101:
1023:
996:
992:. The distribution
976:
949:
752:
694:
657:
626:
431:
382:
316:
287:
283:modulo a polynomial
183:learning with errors
4462:Cryptographic nonce
4211:Three-pass protocol
2188:
2117:
2021:
1999:from the Responder.
1865:and the polynomial
1741:{\displaystyle Sig}
1641:
1543:
1447:
281:ring of polynomials
191:ring of polynomials
155:discrete logarithms
88:public key exchange
4568:Subliminal channel
4552:Pseudorandom noise
4499:Key (cryptography)
3981:Discrete logarithm
3268:
3224:
3185:
3127:
3068:
3016:
2989:
2962:
2935:
2914:
2887:
2858:
2746:
2718:
2713:
2617:
2564:
2541:
2515:
2489:
2409:
2331:
2307:
2280:
2260:
2189:
2176:
2105:
2049:
2022:
2009:
1989:
1969:
1932:
1912:
1882:
1855:
1835:
1765:
1738:
1712:
1667:
1642:
1629:
1544:
1531:
1475:
1448:
1435:
1415:
1353:
1326:
1299:
1262:
1233:
1168:
1141:
1114:
1075:
1009:
982:
962:
764:{\displaystyle Zq}
761:
728:
672:
653:. The polynomial
639:
609:
397:
368:
302:
143:digital signatures
4749:
4748:
4745:
4744:
4628:Key-based routing
4618:Trapdoor function
4489:Digital signature
4370:
4369:
4366:
4365:
4318:Digital signature
4261:Trapdoor function
4224:
4223:
3941:GoldwasserâMicali
3759:978-3-642-25384-3
3596:www.cc.gatech.edu
3423:978-1-58113-960-0
3222:
3221:
3041:Parameter choices
2938:{\displaystyle v}
2829:
2697:
2671:
2484:
2457:
2401:
2376:
2283:{\displaystyle w}
1992:{\displaystyle w}
1942:to the Initiator.
1935:{\displaystyle w}
1858:{\displaystyle w}
1428:Generate a small
1272:to the Responder.
844:Discrete Gaussian
622:The coefficients
261:mass surveillance
80:
79:
72:
16:(Redirected from
4779:
4735:
4734:
4563:Insecure channel
4399:
4392:
4385:
4376:
4207:
4108:
4103:
4063:signature scheme
3966:OkamotoâUchiyama
3904:
3886:
3879:
3872:
3863:
3859:
3855:
3843:
3842:
3840:
3839:
3833:
3827:. Archived from
3825:pqc2010.cased.de
3822:
3814:
3808:
3807:
3805:
3804:
3789:
3783:
3782:
3770:
3764:
3763:
3737:
3731:
3730:
3728:
3727:
3713:
3707:
3706:
3704:
3703:
3688:
3682:
3681:
3679:
3678:
3664:
3649:
3648:
3646:
3645:
3631:
3625:
3624:
3612:
3606:
3605:
3603:
3602:
3593:
3585:
3579:
3578:
3576:
3575:
3561:
3555:
3554:
3542:
3525:
3524:
3522:
3521:
3507:
3501:
3500:
3488:
3482:
3481:
3469:
3463:
3462:
3460:
3449:
3436:
3435:
3407:
3391:
3330:Other approaches
3277:
3275:
3274:
3269:
3233:
3231:
3230:
3225:
3223:
3214:
3210:
3194:
3192:
3191:
3186:
3178:
3177:
3136:
3134:
3133:
3128:
3120:
3119:
3077:
3075:
3074:
3069:
3025:
3023:
3022:
3017:
3015:
3014:
2998:
2996:
2995:
2990:
2988:
2987:
2971:
2969:
2968:
2963:
2961:
2960:
2944:
2942:
2941:
2936:
2923:
2921:
2920:
2915:
2913:
2912:
2896:
2894:
2893:
2888:
2886:
2885:
2867:
2865:
2864:
2859:
2857:
2856:
2847:
2846:
2837:
2836:
2830:
2825:
2814:
2800:
2799:
2772:
2771:
2755:
2753:
2752:
2747:
2745:
2744:
2727:
2725:
2724:
2719:
2717:
2716:
2698:
2695:
2672:
2669:
2626:
2624:
2623:
2618:
2573:
2571:
2570:
2565:
2550:
2548:
2547:
2542:
2524:
2522:
2521:
2516:
2498:
2496:
2495:
2490:
2485:
2480:
2469:
2458:
2453:
2442:
2418:
2416:
2415:
2410:
2402:
2394:
2377:
2369:
2355:
2340:
2338:
2337:
2332:
2316:
2314:
2313:
2308:
2306:
2305:
2289:
2287:
2286:
2281:
2269:
2267:
2266:
2261:
2250:
2249:
2234:
2233:
2221:
2220:
2198:
2196:
2195:
2190:
2184:
2169:
2168:
2159:
2158:
2143:
2142:
2133:
2132:
2113:
2098:
2097:
2088:
2087:
2075:
2074:
2058:
2056:
2055:
2050:
2048:
2047:
2031:
2029:
2028:
2023:
2017:
1998:
1996:
1995:
1990:
1978:
1976:
1975:
1970:
1968:
1967:
1941:
1939:
1938:
1933:
1921:
1919:
1918:
1913:
1911:
1910:
1891:
1889:
1888:
1883:
1881:
1880:
1864:
1862:
1861:
1856:
1844:
1842:
1841:
1836:
1825:
1824:
1809:
1808:
1796:
1795:
1774:
1772:
1771:
1766:
1764:
1763:
1747:
1745:
1744:
1739:
1721:
1719:
1718:
1713:
1708:
1707:
1676:
1674:
1673:
1668:
1651:
1649:
1648:
1643:
1637:
1622:
1621:
1612:
1611:
1596:
1595:
1586:
1585:
1570:
1569:
1553:
1551:
1550:
1545:
1539:
1524:
1523:
1514:
1513:
1501:
1500:
1484:
1482:
1481:
1476:
1474:
1473:
1457:
1455:
1454:
1449:
1443:
1424:
1422:
1421:
1416:
1414:
1413:
1398:
1397:
1382:
1381:
1362:
1360:
1359:
1354:
1352:
1351:
1335:
1333:
1332:
1327:
1325:
1324:
1308:
1306:
1305:
1300:
1298:
1297:
1271:
1269:
1268:
1263:
1261:
1260:
1242:
1240:
1239:
1234:
1229:
1228:
1213:
1212:
1197:
1196:
1177:
1175:
1174:
1169:
1167:
1166:
1150:
1148:
1147:
1142:
1140:
1139:
1123:
1121:
1120:
1115:
1113:
1112:
1084:
1082:
1081:
1076:
1062:
1048:
1047:
1035:
1034:
1018:
1016:
1015:
1010:
1008:
1007:
991:
989:
988:
983:
971:
969:
968:
963:
961:
960:
925:The key exchange
835: â 2,
831: â 3,
827: â 4,
823: â 5,
815: â 1,
811: â 2,
793:Uniform Sampling
770:
768:
767:
762:
737:
735:
734:
729:
721:
720:
681:
679:
678:
673:
648:
646:
645:
640:
638:
637:
618:
616:
615:
610:
608:
607:
592:
591:
573:
572:
557:
556:
538:
537:
522:
521:
497:
496:
487:
486:
471:
470:
458:
457:
422:bits of security
406:
404:
403:
398:
377:
375:
374:
369:
355:
341:
340:
328:
327:
311:
309:
308:
303:
271:Starting with a
216:algorithms, and
185:" introduced by
167:quantum computer
163:quantum computer
107:quantum computer
75:
68:
64:
61:
55:
35:
34:
27:
21:
4787:
4786:
4782:
4781:
4780:
4778:
4777:
4776:
4752:
4751:
4750:
4741:
4723:
4652:
4408:
4403:
4362:
4306:
4270:Standardization
4265:
4220:
4203:
4152:
4100:Lattice/SVP/CVP
4094:
3975:
3921:BlumâGoldwasser
3895:
3890:
3852:
3847:
3846:
3837:
3835:
3831:
3820:
3816:
3815:
3811:
3802:
3800:
3791:
3790:
3786:
3772:
3771:
3767:
3760:
3739:
3738:
3734:
3725:
3723:
3715:
3714:
3710:
3701:
3699:
3690:
3689:
3685:
3676:
3674:
3672:eprint.iacr.org
3666:
3665:
3652:
3643:
3641:
3639:eprint.iacr.org
3633:
3632:
3628:
3614:
3613:
3609:
3600:
3598:
3591:
3587:
3586:
3582:
3573:
3571:
3569:eprint.iacr.org
3563:
3562:
3558:
3544:
3543:
3528:
3519:
3517:
3509:
3508:
3504:
3490:
3489:
3485:
3471:
3470:
3466:
3458:
3451:
3450:
3439:
3424:
3405:10.1.1.110.4776
3393:
3392:
3385:
3380:
3348:
3332:
3316:
3314:Implementations
3296:
3251:
3250:
3204:
3203:
3169:
3149:
3148:
3111:
3091:
3090:
3051:
3050:
3043:
3006:
3001:
3000:
2979:
2974:
2973:
2952:
2947:
2946:
2927:
2926:
2904:
2899:
2898:
2877:
2872:
2871:
2815:
2763:
2758:
2757:
2736:
2731:
2730:
2712:
2711:
2692:
2683:
2682:
2666:
2653:
2629:
2628:
2582:
2581:
2556:
2555:
2527:
2526:
2501:
2500:
2470:
2443:
2421:
2420:
2346:
2345:
2323:
2322:
2297:
2292:
2291:
2290:and polynomial
2272:
2271:
2241:
2225:
2212:
2204:
2203:
2160:
2150:
2134:
2124:
2089:
2079:
2066:
2061:
2060:
2039:
2034:
2033:
2004:
2003:
1981:
1980:
1959:
1954:
1953:
1924:
1923:
1902:
1897:
1896:
1872:
1867:
1866:
1847:
1846:
1816:
1800:
1787:
1779:
1778:
1755:
1750:
1749:
1724:
1723:
1699:
1679:
1678:
1659:
1658:
1613:
1603:
1587:
1577:
1561:
1556:
1555:
1515:
1505:
1492:
1487:
1486:
1465:
1460:
1459:
1430:
1429:
1405:
1389:
1373:
1368:
1367:
1343:
1338:
1337:
1316:
1311:
1310:
1289:
1284:
1283:
1252:
1247:
1246:
1220:
1204:
1188:
1183:
1182:
1158:
1153:
1152:
1131:
1126:
1125:
1104:
1099:
1098:
1039:
1026:
1021:
1020:
999:
994:
993:
974:
973:
972:with parameter
952:
947:
946:
927:
786:
782:
750:
749:
712:
692:
691:
655:
654:
629:
624:
623:
593:
577:
558:
542:
523:
507:
488:
478:
462:
449:
429:
428:
380:
379:
332:
319:
314:
313:
285:
284:
275:integer q, the
269:
257:forward secrecy
135:
90:algorithm is a
76:
65:
59:
56:
48:help improve it
45:
36:
32:
23:
22:
15:
12:
11:
5:
4785:
4783:
4775:
4774:
4769:
4764:
4754:
4753:
4747:
4746:
4743:
4742:
4740:
4739:
4728:
4725:
4724:
4722:
4721:
4716:
4714:Random numbers
4711:
4706:
4701:
4696:
4691:
4686:
4681:
4676:
4671:
4666:
4660:
4658:
4654:
4653:
4651:
4650:
4645:
4640:
4638:Garlic routing
4635:
4630:
4625:
4620:
4615:
4610:
4605:
4600:
4595:
4590:
4585:
4580:
4575:
4570:
4565:
4560:
4558:Secure channel
4555:
4549:
4548:
4547:
4536:
4531:
4526:
4521:
4519:Key stretching
4516:
4511:
4506:
4501:
4496:
4491:
4486:
4485:
4484:
4479:
4469:
4467:Cryptovirology
4464:
4459:
4454:
4452:Cryptocurrency
4449:
4444:
4439:
4438:
4437:
4427:
4422:
4416:
4414:
4410:
4409:
4404:
4402:
4401:
4394:
4387:
4379:
4372:
4371:
4368:
4367:
4364:
4363:
4361:
4360:
4355:
4350:
4345:
4340:
4335:
4330:
4325:
4320:
4314:
4312:
4308:
4307:
4305:
4304:
4299:
4294:
4289:
4284:
4279:
4273:
4271:
4267:
4266:
4264:
4263:
4258:
4253:
4248:
4243:
4238:
4232:
4230:
4226:
4225:
4222:
4221:
4219:
4218:
4213:
4208:
4201:
4199:MerkleâHellman
4196:
4191:
4186:
4181:
4176:
4171:
4166:
4160:
4158:
4154:
4153:
4151:
4150:
4145:
4140:
4135:
4130:
4125:
4120:
4114:
4112:
4096:
4095:
4093:
4092:
4087:
4082:
4077:
4072:
4067:
4066:
4065:
4055:
4050:
4045:
4044:
4043:
4038:
4028:
4023:
4022:
4021:
4016:
4006:
4001:
3996:
3991:
3985:
3983:
3977:
3976:
3974:
3973:
3968:
3963:
3958:
3953:
3948:
3946:NaccacheâStern
3943:
3938:
3933:
3928:
3923:
3918:
3912:
3910:
3901:
3897:
3896:
3891:
3889:
3888:
3881:
3874:
3866:
3851:
3850:External links
3848:
3845:
3844:
3809:
3784:
3765:
3758:
3732:
3708:
3697:tools.ietf.org
3683:
3650:
3626:
3607:
3580:
3556:
3526:
3502:
3483:
3464:
3437:
3422:
3382:
3381:
3379:
3376:
3375:
3374:
3369:
3364:
3359:
3354:
3347:
3344:
3331:
3328:
3315:
3312:
3295:
3292:
3267:
3264:
3261:
3258:
3220:
3217:
3213:
3184:
3181:
3176:
3172:
3168:
3165:
3162:
3159:
3156:
3126:
3123:
3118:
3114:
3110:
3107:
3104:
3101:
3098:
3067:
3064:
3061:
3058:
3042:
3039:
3013:
3009:
2986:
2982:
2959:
2955:
2934:
2911:
2907:
2884:
2880:
2855:
2851:
2845:
2841:
2835:
2828:
2824:
2821:
2818:
2812:
2809:
2806:
2803:
2798:
2793:
2790:
2787:
2784:
2781:
2778:
2775:
2770:
2766:
2743:
2739:
2715:
2710:
2707:
2704:
2701:
2693:
2691:
2688:
2685:
2684:
2681:
2678:
2675:
2667:
2665:
2662:
2659:
2658:
2656:
2651:
2648:
2645:
2642:
2639:
2636:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2563:
2540:
2537:
2534:
2514:
2511:
2508:
2488:
2483:
2479:
2476:
2473:
2467:
2464:
2461:
2456:
2452:
2449:
2446:
2440:
2437:
2434:
2431:
2428:
2408:
2405:
2400:
2397:
2392:
2389:
2386:
2383:
2380:
2375:
2372:
2367:
2364:
2361:
2358:
2354:
2344:Define subset
2330:
2319:
2318:
2304:
2300:
2279:
2259:
2256:
2253:
2248:
2244:
2240:
2237:
2232:
2228:
2224:
2219:
2215:
2211:
2200:
2187:
2183:
2179:
2175:
2172:
2167:
2163:
2157:
2153:
2149:
2146:
2141:
2137:
2131:
2127:
2123:
2120:
2116:
2112:
2108:
2104:
2101:
2096:
2092:
2086:
2082:
2078:
2073:
2069:
2046:
2042:
2020:
2016:
2012:
2000:
1988:
1966:
1962:
1944:
1943:
1931:
1909:
1905:
1893:
1879:
1875:
1854:
1834:
1831:
1828:
1823:
1819:
1815:
1812:
1807:
1803:
1799:
1794:
1790:
1786:
1775:
1762:
1758:
1737:
1734:
1731:
1711:
1706:
1702:
1698:
1695:
1692:
1689:
1686:
1666:
1655:
1640:
1636:
1632:
1628:
1625:
1620:
1616:
1610:
1606:
1602:
1599:
1594:
1590:
1584:
1580:
1576:
1573:
1568:
1564:
1542:
1538:
1534:
1530:
1527:
1522:
1518:
1512:
1508:
1504:
1499:
1495:
1472:
1468:
1446:
1442:
1438:
1426:
1412:
1408:
1404:
1401:
1396:
1392:
1388:
1385:
1380:
1376:
1364:
1350:
1346:
1323:
1319:
1296:
1292:
1274:
1273:
1259:
1255:
1243:
1232:
1227:
1223:
1219:
1216:
1211:
1207:
1203:
1200:
1195:
1191:
1179:
1165:
1161:
1138:
1134:
1111:
1107:
1074:
1071:
1068:
1065:
1061:
1057:
1054:
1051:
1046:
1042:
1038:
1033:
1029:
1006:
1002:
981:
959:
955:
926:
923:
856:
855:
840:
784:
780:
760:
757:
727:
724:
719:
715:
711:
708:
705:
702:
699:
671:
668:
665:
662:
636:
632:
620:
619:
606:
603:
600:
596:
590:
587:
584:
580:
576:
571:
568:
565:
561:
555:
552:
549:
545:
541:
536:
533:
530:
526:
520:
517:
514:
510:
506:
503:
500:
495:
491:
485:
481:
477:
474:
469:
465:
461:
456:
452:
448:
445:
442:
439:
436:
396:
393:
390:
387:
367:
364:
361:
358:
354:
350:
347:
344:
339:
335:
331:
326:
322:
301:
298:
295:
292:
268:
265:
248:DiffieâHellman
233:DiffieâHellman
159:elliptic curve
134:
131:
78:
77:
39:
37:
30:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4784:
4773:
4770:
4768:
4765:
4763:
4760:
4759:
4757:
4738:
4730:
4729:
4726:
4720:
4719:Steganography
4717:
4715:
4712:
4710:
4707:
4705:
4702:
4700:
4697:
4695:
4692:
4690:
4687:
4685:
4682:
4680:
4677:
4675:
4674:Stream cipher
4672:
4670:
4667:
4665:
4662:
4661:
4659:
4655:
4649:
4646:
4644:
4641:
4639:
4636:
4634:
4633:Onion routing
4631:
4629:
4626:
4624:
4621:
4619:
4616:
4614:
4613:Shared secret
4611:
4609:
4606:
4604:
4601:
4599:
4596:
4594:
4591:
4589:
4586:
4584:
4581:
4579:
4576:
4574:
4571:
4569:
4566:
4564:
4561:
4559:
4556:
4553:
4550:
4545:
4542:
4541:
4540:
4537:
4535:
4532:
4530:
4527:
4525:
4522:
4520:
4517:
4515:
4512:
4510:
4509:Key generator
4507:
4505:
4502:
4500:
4497:
4495:
4492:
4490:
4487:
4483:
4480:
4478:
4475:
4474:
4473:
4472:Hash function
4470:
4468:
4465:
4463:
4460:
4458:
4455:
4453:
4450:
4448:
4447:Cryptanalysis
4445:
4443:
4440:
4436:
4433:
4432:
4431:
4428:
4426:
4423:
4421:
4418:
4417:
4415:
4411:
4407:
4400:
4395:
4393:
4388:
4386:
4381:
4380:
4377:
4373:
4359:
4356:
4354:
4351:
4349:
4346:
4344:
4341:
4339:
4336:
4334:
4331:
4329:
4326:
4324:
4321:
4319:
4316:
4315:
4313:
4309:
4303:
4300:
4298:
4295:
4293:
4290:
4288:
4285:
4283:
4280:
4278:
4275:
4274:
4272:
4268:
4262:
4259:
4257:
4254:
4252:
4249:
4247:
4244:
4242:
4239:
4237:
4234:
4233:
4231:
4227:
4217:
4214:
4212:
4209:
4206:
4202:
4200:
4197:
4195:
4192:
4190:
4187:
4185:
4182:
4180:
4177:
4175:
4172:
4170:
4167:
4165:
4162:
4161:
4159:
4155:
4149:
4146:
4144:
4141:
4139:
4136:
4134:
4131:
4129:
4126:
4124:
4121:
4119:
4116:
4115:
4113:
4111:
4106:
4101:
4097:
4091:
4088:
4086:
4083:
4081:
4078:
4076:
4073:
4071:
4068:
4064:
4061:
4060:
4059:
4056:
4054:
4051:
4049:
4046:
4042:
4039:
4037:
4034:
4033:
4032:
4029:
4027:
4024:
4020:
4017:
4015:
4012:
4011:
4010:
4007:
4005:
4002:
4000:
3997:
3995:
3992:
3990:
3987:
3986:
3984:
3982:
3978:
3972:
3971:SchmidtâSamoa
3969:
3967:
3964:
3962:
3959:
3957:
3954:
3952:
3949:
3947:
3944:
3942:
3939:
3937:
3934:
3932:
3931:DamgĂ„rdâJurik
3929:
3927:
3926:CayleyâPurser
3924:
3922:
3919:
3917:
3914:
3913:
3911:
3909:
3905:
3902:
3898:
3894:
3887:
3882:
3880:
3875:
3873:
3868:
3867:
3864:
3860:
3856:
3849:
3834:on 2015-06-14
3830:
3826:
3819:
3813:
3810:
3798:
3794:
3788:
3785:
3780:
3776:
3769:
3766:
3761:
3755:
3751:
3747:
3743:
3736:
3733:
3722:
3718:
3712:
3709:
3698:
3694:
3687:
3684:
3673:
3669:
3663:
3661:
3659:
3657:
3655:
3651:
3640:
3636:
3630:
3627:
3622:
3618:
3611:
3608:
3597:
3590:
3584:
3581:
3570:
3566:
3560:
3557:
3552:
3548:
3541:
3539:
3537:
3535:
3533:
3531:
3527:
3516:
3512:
3506:
3503:
3498:
3494:
3487:
3484:
3479:
3475:
3468:
3465:
3457:
3456:
3448:
3446:
3444:
3442:
3438:
3433:
3429:
3425:
3419:
3415:
3411:
3406:
3401:
3397:
3390:
3388:
3384:
3377:
3373:
3370:
3368:
3365:
3363:
3360:
3358:
3355:
3353:
3350:
3349:
3345:
3343:
3342:
3336:
3329:
3327:
3326:
3321:
3313:
3311:
3309:
3308:ideal lattice
3305:
3301:
3293:
3291:
3287:
3285:
3281:
3262:
3247:
3245:
3241:
3237:
3218:
3215:
3211:
3201:
3195:
3182:
3179:
3174:
3170:
3166:
3160:
3147:= 40961, and
3146:
3142:
3137:
3124:
3121:
3116:
3112:
3108:
3102:
3089:= 25601, and
3088:
3084:
3079:
3062:
3048:
3040:
3038:
3034:
3031:
3027:
3011:
3007:
2984:
2980:
2957:
2953:
2932:
2909:
2905:
2882:
2878:
2868:
2853:
2843:
2826:
2822:
2819:
2816:
2810:
2807:
2804:
2801:
2791:
2785:
2782:
2779:
2773:
2768:
2764:
2741:
2737:
2728:
2708:
2705:
2702:
2699:
2689:
2686:
2679:
2676:
2673:
2663:
2660:
2654:
2649:
2643:
2637:
2634:
2611:
2608:
2605:
2596:
2593:
2590:
2587:
2579:
2577:
2561:
2552:
2535:
2509:
2481:
2477:
2474:
2471:
2465:
2462:
2459:
2454:
2450:
2447:
2444:
2438:
2432:
2429:
2426:
2398:
2395:
2387:
2384:
2381:
2373:
2370:
2362:
2356:
2342:
2328:
2302:
2298:
2277:
2254:
2251:
2246:
2242:
2235:
2230:
2226:
2222:
2217:
2213:
2209:
2201:
2185:
2181:
2177:
2173:
2170:
2165:
2161:
2155:
2151:
2147:
2144:
2139:
2135:
2129:
2125:
2121:
2118:
2114:
2110:
2106:
2102:
2099:
2094:
2090:
2084:
2080:
2076:
2071:
2067:
2044:
2040:
2018:
2014:
2010:
2001:
1986:
1964:
1960:
1951:
1950:
1949:
1948:
1929:
1907:
1903:
1894:
1877:
1873:
1852:
1829:
1826:
1821:
1817:
1810:
1805:
1801:
1797:
1792:
1788:
1784:
1776:
1760:
1756:
1735:
1732:
1729:
1704:
1700:
1693:
1690:
1687:
1684:
1664:
1656:
1654:
1638:
1634:
1630:
1626:
1623:
1618:
1614:
1608:
1604:
1600:
1597:
1592:
1588:
1582:
1578:
1574:
1571:
1566:
1562:
1540:
1536:
1532:
1528:
1525:
1520:
1516:
1510:
1506:
1502:
1497:
1493:
1470:
1466:
1444:
1440:
1436:
1427:
1410:
1406:
1402:
1399:
1394:
1390:
1386:
1383:
1378:
1374:
1365:
1348:
1344:
1321:
1317:
1294:
1290:
1281:
1280:
1279:
1278:
1257:
1253:
1244:
1230:
1225:
1221:
1217:
1214:
1209:
1205:
1201:
1198:
1193:
1189:
1180:
1163:
1159:
1136:
1132:
1109:
1105:
1096:
1095:
1094:
1093:
1089:
1086:
1069:
1059:
1052:
1044:
1040:
1036:
1031:
1027:
1004:
1000:
979:
957:
953:
944:
940:
936:
932:
924:
922:
920:
916:
912:
908:
904:
900:
896:
892:
888:
884:
880:
876:
872:
868:
863:
861:
853:
849:
845:
841:
838:
834:
830:
826:
822:
818:
814:
810:
806:
802:
798:
794:
790:
789:
788:
778:
774:
758:
755:
747:
743:
742:infinity norm
738:
725:
722:
717:
713:
709:
703:
689:
685:
666:
652:
634:
630:
604:
601:
598:
594:
588:
585:
582:
578:
574:
569:
566:
563:
559:
553:
550:
547:
543:
539:
534:
531:
528:
524:
518:
515:
512:
508:
504:
501:
498:
493:
489:
483:
479:
475:
472:
467:
463:
459:
454:
450:
446:
440:
434:
427:
426:
425:
423:
418:
415:
412:
408:
391:
362:
352:
345:
337:
333:
329:
324:
320:
296:
282:
278:
274:
266:
264:
262:
258:
253:
249:
245:
240:
238:
234:
230:
226:
221:
219:
215:
211:
206:
204:
200:
196:
192:
188:
184:
180:
176:
171:
168:
164:
160:
156:
152:
148:
144:
140:
139:key exchanges
132:
130:
128:
124:
120:
116:
112:
108:
104:
100:
98:
93:
89:
85:
74:
71:
63:
53:
49:
43:
40:This article
38:
29:
28:
19:
4669:Block cipher
4514:Key schedule
4504:Key exchange
4494:Kleptography
4457:Cryptosystem
4406:Cryptography
4358:OpenPGP card
4338:Web of trust
3994:CramerâShoup
3836:. Retrieved
3829:the original
3824:
3812:
3801:. Retrieved
3799:. 2015-04-02
3796:
3787:
3778:
3768:
3741:
3735:
3724:. Retrieved
3720:
3711:
3700:. Retrieved
3696:
3686:
3675:. Retrieved
3671:
3642:. Retrieved
3638:
3629:
3620:
3610:
3599:. Retrieved
3595:
3583:
3572:. Retrieved
3568:
3559:
3550:
3518:. Retrieved
3514:
3505:
3496:
3486:
3477:
3467:
3454:
3395:
3337:
3333:
3317:
3306:(SVP) in an
3297:
3288:
3248:
3243:
3239:
3235:
3199:
3196:
3144:
3140:
3138:
3086:
3082:
3080:
3046:
3044:
3035:
3032:
3028:
2869:
2729:
2580:
2575:
2553:
2343:
2320:
2059:and Compute
1946:
1945:
1652:
1276:
1275:
1091:
1090:
1087:
942:
938:
934:
930:
928:
918:
914:
910:
906:
902:
898:
894:
890:
886:
882:
878:
874:
870:
866:
864:
859:
857:
851:
847:
836:
832:
828:
824:
820:
816:
812:
808:
804:
800:
796:
776:
772:
748:rather than
745:
739:
687:
682:will be the
650:
621:
419:
416:
413:
409:
270:
267:Introduction
244:quantum safe
241:
222:
212:algorithms,
207:
195:finite field
175:quantum safe
172:
136:
102:
99:key exchange
95:
84:cryptography
81:
66:
57:
41:
4657:Mathematics
4648:Mix network
4328:Fingerprint
4292:NSA Suite B
4256:RSA problem
4133:NTRUEncrypt
1092:Initiation:
4756:Categories
4608:Ciphertext
4578:Decryption
4573:Encryption
4534:Ransomware
4282:IEEE P1363
3900:Algorithms
3838:2015-06-06
3803:2015-06-06
3726:2017-03-16
3702:2017-03-16
3677:2015-11-11
3644:2016-01-17
3601:2015-05-29
3574:2015-12-23
3520:2017-02-08
3378:References
1485:. Compute
187:Oded Regev
147:public key
133:Background
4598:Plaintext
3400:CiteSeerX
3257:Φ
3244:less than
3240:less than
3219:π
3155:Φ
3097:Φ
3057:Φ
2820:−
2774:
2703:∉
2677:∈
2638:
2600:→
2554:Function
2539:⌉
2533:⌊
2513:⌋
2507:⌊
2475:−
2463:…
2448:−
2439:−
2404:⌉
2391:⌊
2385:…
2379:⌋
2366:⌊
2363:−
2236:
2045:α
2041:χ
1811:
1694:
1677:to find
1471:α
1467:χ
1349:α
1345:χ
1277:Response:
1164:α
1160:χ
1064:Φ
1005:α
1001:χ
980:α
958:α
954:χ
698:Φ
661:Φ
602:−
586:−
567:−
551:−
532:−
516:−
502:⋯
386:Φ
357:Φ
291:Φ
60:June 2015
4737:Category
4643:Kademlia
4603:Codetext
4546:(CSPRNG)
4343:Key size
4277:CRYPTREC
4194:McEliece
4148:RLWE-SIG
4143:RLWE-KEX
4138:NTRUSign
3951:Paillier
3432:53223958
3346:See also
3143:= 1024,
2696:if
2670:if
2499:. Here,
2186:′
2115:′
2019:′
1952:Receive
1639:′
1541:′
1445:′
1366:Compute
1181:Compute
783:, ..., s
277:Ring-LWE
123:lattices
103:RLWE-KEX
18:RLWE-KEX
4413:General
4189:Lamport
4169:CEILIDH
4128:NewHope
4075:Schnorr
4058:ElGamal
4036:Ed25519
3916:Benaloh
3320:a patch
3284:NewHope
3085:= 512,
2002:Sample
1947:Finish:
1554:. Then
686:. When
193:over a
46:Please
4524:Keygen
4311:Topics
4287:NESSIE
4229:Theory
4157:Others
4014:X25519
3756:
3430:
3420:
3402:
881:) and
865:Given
842:Using
791:Using
4554:(PRN)
4123:Kyber
4118:BLISS
4080:SPEKE
4048:ECMQV
4041:Ed448
4031:EdDSA
4026:ECDSA
3956:Rabin
3832:(PDF)
3821:(PDF)
3592:(PDF)
3459:(PDF)
3428:S2CID
2999:and
2032:from
1458:from
913:) + 2
273:prime
177:, or
4323:OAEP
4297:CNSA
4174:EPOC
4019:X448
4009:ECDH
3797:NIST
3754:ISBN
3418:ISBN
3175:1024
2897:and
2525:and
1979:and
1922:and
1309:and
1124:and
897:) =
250:and
235:and
203:RLWE
141:and
127:RLWE
115:RLWE
86:, a
4333:PKI
4216:XTR
4184:IES
4179:HFE
4110:SIS
4105:LWE
4090:STS
4085:SRP
4070:MQV
4053:EKE
4004:DSA
3989:BLS
3961:RSA
3936:GMR
3746:doi
3410:doi
3202:is
3117:512
2945:in
2850:mod
2840:mod
2765:Mod
2738:Mod
2635:Sig
2588:Sig
2562:Sig
2419:of
2329:Sig
2227:Mod
1802:Mod
1691:Sig
1665:Sig
921:).
781:n-1
201:or
82:In
50:to
4758::
4164:AE
3999:DH
3823:.
3795:.
3777:.
3752:.
3719:.
3695:.
3670:.
3653:^
3637:.
3619:.
3594:.
3567:.
3549:.
3529:^
3513:.
3495:.
3476:.
3440:^
3426:.
3416:.
3408:.
3386:^
3286:.
2627::
2578:.
2357::=
937:,
933:,
726:1.
407:.
330::=
223:A
205:.
4398:e
4391:t
4384:v
4107:/
4102:/
3885:e
3878:t
3871:v
3841:.
3806:.
3781:.
3762:.
3748::
3729:.
3705:.
3680:.
3647:.
3623:.
3604:.
3577:.
3553:.
3523:.
3499:.
3480:.
3461:.
3434:.
3412::
3266:)
3263:x
3260:(
3236:b
3216:2
3212:8
3200:Ï
3183:1
3180:+
3171:x
3167:=
3164:)
3161:x
3158:(
3145:q
3141:n
3125:1
3122:+
3113:x
3109:=
3106:)
3103:x
3100:(
3087:q
3083:n
3066:)
3063:x
3060:(
3047:n
3012:I
3008:k
2985:R
2981:k
2958:q
2954:R
2933:v
2910:R
2906:k
2883:I
2879:k
2854:2
2844:q
2834:)
2827:2
2823:1
2817:q
2811:.
2808:w
2805:+
2802:v
2797:(
2792:=
2789:)
2786:w
2783:,
2780:v
2777:(
2769:2
2742:2
2709:.
2706:E
2700:v
2690:,
2687:1
2680:E
2674:v
2664:,
2661:0
2655:{
2650:=
2647:)
2644:v
2641:(
2615:}
2612:1
2609:,
2606:0
2603:{
2597:q
2594:Z
2591::
2576:E
2536:.
2510:.
2487:}
2482:2
2478:1
2472:q
2466:,
2460:,
2455:2
2451:1
2445:q
2436:{
2433:=
2430:q
2427:Z
2407:}
2399:4
2396:q
2388:,
2382:,
2374:4
2371:q
2360:{
2353:E
2317:.
2303:I
2299:k
2278:w
2258:)
2255:w
2252:,
2247:I
2243:k
2239:(
2231:2
2223:=
2218:I
2214:k
2210:s
2199:.
2182:I
2178:e
2174:2
2171:+
2166:I
2162:s
2156:R
2152:e
2148:2
2145:+
2140:R
2136:s
2130:I
2126:s
2122:a
2119:=
2111:I
2107:e
2103:2
2100:+
2095:I
2091:s
2085:R
2081:p
2077:=
2072:I
2068:k
2015:I
2011:e
1987:w
1965:R
1961:p
1930:w
1908:R
1904:p
1892:.
1878:R
1874:k
1853:w
1833:)
1830:w
1827:,
1822:R
1818:k
1814:(
1806:2
1798:=
1793:R
1789:k
1785:s
1761:R
1757:k
1736:g
1733:i
1730:S
1710:)
1705:R
1701:k
1697:(
1688:=
1685:w
1653:.
1635:R
1631:e
1627:2
1624:+
1619:R
1615:s
1609:I
1605:e
1601:2
1598:+
1593:R
1589:s
1583:I
1579:s
1575:a
1572:=
1567:R
1563:k
1537:R
1533:e
1529:2
1526:+
1521:R
1517:s
1511:I
1507:p
1503:=
1498:R
1494:k
1441:R
1437:e
1425:.
1411:R
1407:e
1403:2
1400:+
1395:R
1391:s
1387:a
1384:=
1379:R
1375:p
1363:.
1322:R
1318:e
1295:R
1291:s
1258:I
1254:p
1231:.
1226:I
1222:e
1218:2
1215:+
1210:I
1206:s
1202:a
1199:=
1194:I
1190:p
1178:.
1137:I
1133:e
1110:I
1106:s
1073:)
1070:x
1067:(
1060:/
1056:]
1053:x
1050:[
1045:q
1041:Z
1037:=
1032:q
1028:R
943:x
941:(
939:a
935:n
931:q
919:x
917:(
915:e
911:x
909:(
907:s
905:)
903:x
901:(
899:a
895:x
893:(
891:p
887:x
885:(
883:e
879:x
877:(
875:s
871:x
869:(
867:a
860:D
852:Ï
848:q
837:q
833:q
829:q
825:q
821:q
817:b
813:b
809:b
805:b
801:q
797:b
785:0
777:q
773:q
759:q
756:Z
746:Z
723:+
718:n
714:x
710:=
707:)
704:x
701:(
688:n
670:)
667:x
664:(
651:q
635:i
631:a
605:1
599:n
595:x
589:1
583:n
579:a
575:+
570:2
564:n
560:x
554:2
548:n
544:a
540:+
535:3
529:n
525:x
519:3
513:n
509:a
505:+
499:+
494:2
490:x
484:2
480:a
476:+
473:x
468:1
464:a
460:+
455:0
451:a
447:=
444:)
441:x
438:(
435:a
395:)
392:x
389:(
366:)
363:x
360:(
353:/
349:]
346:x
343:[
338:q
334:Z
325:q
321:R
300:)
297:x
294:(
255:"
101:(
73:)
67:(
62:)
58:(
44:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.