7064:
25:
7116:
The security of the protocol is proven based on the hardness of solving the LWE problem. 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. The "new hope"
7135:
was created and converted to a digital signature in 2011 by
Lyubashevsky. The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems." These papers
7112:
The idea of using LWE and Ring LWE for key exchange was 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 patent
7402:
Craig Gentry, Chris
Peikert, and Vinod Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 197-206,
6523:
3923:
3297:
2351:
2012:
6747:
1068:
3479:
2118:
90:. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the
6333:
1929:
Intuitively, if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision problem to the solver for the search problem. Denote the given samples by
2460:
4293:
7323:
Chris
Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342,
7388:
Chris
Peikert and Brent Waters, “Lossy trapdoor functions and their applications,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 187-196,
7298:
Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93,
5511:
4801:
384:
4979:
986:
6860:
4426:
1682:
1163:
4874:
4067:
3556:
5404:
3387:
1596:
5223:
2782:
7050:
3643:
3169:
1871:
796:
631:
6237:
6085:
1391:
842:
677:
460:
6387:
3340:
5722:
5272:
5027:
1806:
1242:
6164:
5957:
3683:
3519:
7136:
laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.
5570:
187:
6020:
5448:
5304:
5121:
2928:
1349:
6644:
4202:
5525:
problem serves as a versatile problem used in construction of several cryptosystems. In 2005, Regev showed that the decision version of LWE is hard assuming quantum hardness of the
3718:
3204:
2518:
1426:
754:
2267:
2232:
1198:
495:
4005:
3830:
3774:
1102:
876:
276:
5628:
1530:
907:
532:
6790:
5342:
5085:
4909:
3053:
2984:
2717:
2688:
2659:
2630:
2197:
1301:
418:
329:
219:
6412:
3020:
1709:
6907:
6112:
5671:
4722:
4118:
4091:
3971:
3947:
3835:
3587:
3209:
2829:
2272:
1933:
7529:
6566:
5977:
5807:
4607:
4027:
3796:
3740:
2168:
2034:
1731:
1455:
1264:
719:
7008:
4647:
1758:
1482:
2955:
5836:
5590:
4755:
4459:
5893:
4571:
4545:
6655:
6407:
5863:
5785:
4320:
3113:
2138:
991:
927:
697:
5765:
6975:
6955:
6927:
6880:
6810:
6586:
6263:
6184:
6132:
5181:
5161:
5141:
5047:
4687:
4667:
4519:
4499:
4479:
4340:
4222:
4163:
3093:
2872:
2852:
2802:
2598:
2578:
2558:
2538:
2483:
2054:
1919:
1899:
1126:
552:
296:
242:
132:
112:
6612:
2540:
is prime, it takes it to the uniform distribution. So, given a polynomial-time solver for the decision problem that errs with very small probability, since
6933:
The proof of correctness follows from choice of parameters and some probability analysis. The proof of security is by reduction to the decision version of
3392:
2059:
6268:
2356:
7522:
7436:
4227:
43:
7132:
5725:. The disadvantage of Peikert's result is that it bases itself on a non-standard version of an easier (when compared to SIVP) problem GapSVP.
7613:
7577:
7515:
5453:
4760:
334:
4917:
935:
5741:
problem. The cryptosystem as well as the proof of security and correctness are completely classical. The system is characterized by
7608:
6815:
4345:
1601:
1131:
534:. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function
4806:
4032:
5347:
3348:
7160:
7107:
1535:
582:
7117:
implementation selected for Google's post-quantum experiment, uses
Peikert's scheme with variation in the error distribution.
5195:
2722:
7365:
7013:
3592:
3118:
1834:
759:
3524:
596:
189:
some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
6200:
6025:
1354:
805:
640:
423:
7126:
6338:
3302:
5677:
5229:
4984:
1763:
7737:
2148:
For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover
1203:
7538:
6137:
574:
61:
5900:
2120:. If the samples are from an LWE distribution, then the results of this calculation will be distributed according
299:
5531:
558:
7685:
7655:
7488:
7165:
141:
7665:
5983:
5409:
5277:
5090:
2877:
1313:
7572:
6617:
4171:
3648:
3484:
3688:
3174:
2488:
1396:
724:
7075:
2237:
2202:
1168:
465:
7342:. Lecture Notes in Computer Science. Vol. 8772. Springer International Publishing. pp. 197–219.
3976:
3801:
3745:
1073:
847:
247:
7701:
5595:
1491:
6518:{\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}
5673:). In 2009, Peikert proved a similar result assuming only the classical hardness of the related problem
7639:
7603:
7582:
7155:
3918:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}
3292:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}
884:
500:
6761:
5309:
5052:
4879:
3029:
2960:
2693:
2664:
2635:
2606:
2346:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }
2173:
2007:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }
1272:
389:
305:
195:
7732:
7680:
7150:
7145:
3023:
2989:
1687:
7598:
7348:
6885:
6090:
5633:
4692:
4099:
4072:
3952:
3928:
3568:
7095:
3064:
2807:
2140:, but if the samples are uniformly random, these quantities will be distributed uniformly as well.
6533:
5962:
5790:
4576:
4010:
3779:
3723:
2151:
2017:
1714:
1434:
1247:
702:
7706:
6980:
5734:
4619:
1736:
1460:
578:
7192:
Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography".
7343:
7338:
Peikert, Chris (2014-10-01). "Lattice
Cryptography for the Internet". In Mosca, Michele (ed.).
2933:
6742:{\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i},{\frac {x}{2}}+\sum _{i\in S}b_{i}\right)}
1063:{\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}
39:
7567:
7557:
7552:
7430:
5815:
5575:
4727:
4431:
1831:), the goal is to distinguish between noisy inner products and uniformly random samples from
91:
87:
5868:
4550:
4524:
6392:
5841:
5770:
4298:
4128:
are (up to a polynomial factor) as hard in the average case as they are in the worst case.
3098:
2123:
912:
682:
5674:
5192:
8:
5744:
1485:
7669:
7659:
7419:"A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem"
7325:
7300:
5123:. This implies the hardness for LWE. Although the proof of this assertion works for any
7371:
7266:
7219:
7201:
6960:
6940:
6912:
6865:
6795:
6571:
6248:
6169:
6117:
5166:
5146:
5126:
5032:
4672:
4652:
4504:
4484:
4464:
4325:
4207:
4148:
3078:
2857:
2837:
2787:
2583:
2563:
2543:
2523:
2468:
2039:
1904:
1884:
1111:
537:
281:
227:
222:
135:
117:
97:
6591:
7507:
7361:
7258:
7223:
569:
problem. Regev showed that the LWE problem is as hard to solve as several worst-case
4428:
is extended to sets by summing over function values at each element in the set. Let
7634:
7375:
7353:
7270:
7250:
7211:
5526:
570:
3474:{\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}
2113:{\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}
7357:
6937:: an algorithm for distinguishing between encryptions (with above parameters) of
6328:{\displaystyle \mathbf {a} _{1},\ldots ,\mathbf {a} _{m}\in \mathbb {Z} _{q}^{n}}
566:
7404:
7390:
5191:
Peikert proves that there is a probabilistic polynomial time reduction from the
7711:
7629:
6114:
is a probability distribution obtained by sampling a normal variable with mean
1105:
5809:. The setting of the parameters used in proofs of correctness and security is
2455:{\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}}
562:
7726:
7262:
4288:{\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }
2834:
Peikert showed that this reduction, with a small modification, works for any
7215:
7469:
Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01).
1760:
modulo one. The version of LWE considered in most of the results would be
634:
75:
7562:
7238:
7063:
4007:, with high probability, if we choose a polynomial number of values for
4914:
Regev then shows that there exists an efficient quantum algorithm for
1873:(practically, some discretized version of it). Regev showed that the
7470:
7254:
7451:
7418:
7206:
7237:
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (November 2013).
5506:{\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})}
4796:{\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}
2580:, it only takes polynomial time to guess every possible value for
379:{\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}
7120:
4974:{\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}
86:) is a mathematical problem that is widely used to create secure
981:{\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}
554:, or some close approximation thereof, with high probability.
7170:
6855:{\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}
4421:{\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}
2632:, we follow an analogous procedure for each other coordinate
1677:{\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}
1158:{\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }
7468:
4869:{\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}
4062:{\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}}
3685:. If we need to distinguish uniformly random samples from
1393:, given access to polynomially many samples of choice from
192:
More precisely, the LWE problem is defined as follows. Let
7094:
Peikert proposed a system that is secure even against any
5399:{\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}
3382:{\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}
2170:
one coordinate at a time. To obtain the first coordinate,
1591:{\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }
7236:
5218:{\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }}
3645:, could tell whether they were uniformly random or from
2777:{\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}
2462:. Send the transformed samples to the decision solver.
386:, and the input to the LWE problem is a sample of pairs
7239:"On Ideal Lattices and Learning with Errors over Rings"
7045:{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }
3638:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}
3164:{\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}
2485:
was correct, the transformation takes the distribution
1866:{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }
791:{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }
7537:
3551:{\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}
995:
626:{\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }
7326:
http://portal.acm.org/citation.cfm?id=1536414.1536461
7301:
http://portal.acm.org/citation.cfm?id=1060590.1060603
7016:
6983:
6963:
6943:
6915:
6888:
6868:
6818:
6798:
6764:
6658:
6620:
6594:
6574:
6536:
6415:
6395:
6341:
6271:
6251:
6203:
6172:
6140:
6120:
6093:
6028:
5986:
5965:
5903:
5871:
5844:
5818:
5793:
5773:
5747:
5680:
5636:
5598:
5578:
5534:
5456:
5412:
5350:
5312:
5280:
5232:
5198:
5169:
5149:
5129:
5093:
5055:
5035:
4987:
4920:
4882:
4809:
4763:
4730:
4695:
4675:
4655:
4622:
4579:
4553:
4527:
4507:
4487:
4467:
4434:
4348:
4328:
4301:
4230:
4210:
4174:
4151:
4102:
4075:
4035:
4013:
3979:
3955:
3931:
3838:
3804:
3782:
3748:
3726:
3691:
3651:
3595:
3571:
3527:
3487:
3395:
3351:
3305:
3212:
3177:
3121:
3101:
3081:
3032:
2992:
2963:
2936:
2880:
2860:
2840:
2810:
2790:
2725:
2696:
2667:
2638:
2609:
2586:
2566:
2546:
2526:
2491:
2471:
2359:
2275:
2240:
2205:
2176:
2154:
2126:
2062:
2042:
2020:
1936:
1907:
1887:
1837:
1766:
1739:
1717:
1690:
1604:
1538:
1494:
1463:
1437:
1399:
1357:
1316:
1275:
1250:
1206:
1171:
1134:
1114:
1076:
994:
938:
915:
887:
850:
808:
762:
727:
705:
685:
643:
599:
540:
503:
468:
426:
392:
337:
308:
284:
250:
230:
198:
144:
120:
100:
7417:
Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01).
6232:{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}
6080:{\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}
2854:
that is a product of distinct, small (polynomial in
1386:{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}
837:{\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}
672:{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}
455:{\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}
6382:{\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }
3335:{\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}
2143:
1924:
573:. Subsequently, the LWE problem has been used as a
34:
may be too technical for most readers to understand
7044:
7002:
6969:
6949:
6921:
6901:
6874:
6854:
6804:
6784:
6741:
6638:
6606:
6580:
6560:
6517:
6401:
6381:
6335:uniformly and independently. Choose error offsets
6327:
6257:
6231:
6178:
6158:
6126:
6106:
6079:
6014:
5971:
5951:
5887:
5857:
5830:
5801:
5779:
5759:
5717:{\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}
5716:
5665:
5622:
5584:
5564:
5505:
5442:
5398:
5336:
5298:
5267:{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}
5266:
5217:
5175:
5155:
5135:
5115:
5079:
5041:
5022:{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}
5021:
4973:
4903:
4868:
4795:
4749:
4716:
4681:
4661:
4641:
4601:
4565:
4539:
4513:
4493:
4473:
4453:
4420:
4334:
4314:
4287:
4216:
4196:
4157:
4112:
4085:
4061:
4021:
3999:
3965:
3941:
3917:
3824:
3790:
3768:
3734:
3712:
3677:
3637:
3581:
3550:
3513:
3473:
3381:
3334:
3291:
3198:
3163:
3107:
3087:
3047:
3014:
2978:
2949:
2922:
2866:
2846:
2823:
2796:
2776:
2711:
2682:
2653:
2624:
2592:
2572:
2552:
2532:
2512:
2477:
2454:
2345:
2261:
2226:
2191:
2162:
2132:
2112:
2048:
2028:
2006:
1913:
1893:
1865:
1801:{\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}
1800:
1752:
1725:
1703:
1676:
1590:
1524:
1476:
1449:
1420:
1385:
1343:
1295:
1258:
1236:
1192:
1157:
1120:
1096:
1062:
980:
921:
901:
870:
836:
790:
748:
713:
691:
671:
625:
546:
526:
489:
454:
412:
378:
323:
290:
270:
236:
213:
181:
126:
106:
2269:uniformly at random. Transform the given samples
331:. There exists a certain unknown linear function
7724:
2600:and use the solver to see which one is correct.
1237:{\displaystyle 1/q+\mathbb {Z} \in \mathbb {T} }
6159:{\displaystyle {\frac {\beta }{\sqrt {2\pi }}}}
7489:"Experimenting with Post-Quantum Cryptography"
7121:Ring learning with errors signature (RLWE-SIG)
565:for this work); it is a generalization of the
7523:
7405:http://portal.acm.org/citation.cfm?id=1374407
7391:http://portal.acm.org/citation.cfm?id=1374406
5952:{\displaystyle m=(1+\varepsilon )(n+1)\log q}
4757:. Regev shows that there is a reduction from
4461:denote the discrete Gaussian distribution on
7435:: CS1 maint: multiple names: authors list (
6841:
6825:
6555:
6543:
6470:
6447:
4616:(DGS) is defined as follows: An instance of
4273:
4265:
3912:
3898:
3875:
3839:
3632:
3596:
3286:
3272:
3249:
3213:
3158:
3122:
2449:
2360:
2312:
2276:
2107:
2089:
2066:
2063:
1973:
1937:
1012:
996:
961:
945:
7319:
7317:
7315:
7313:
7311:
7309:
5565:{\displaystyle \mathrm {GapSVP} _{\gamma }}
5143:, for creating a cryptosystem, the modulus
4093:will successfully distinguish the samples.
7530:
7516:
7054:
5728:
7347:
7294:
7292:
7290:
7288:
7286:
7284:
7282:
7280:
7205:
7133:Feige–Fiat–Shamir Identification protocol
7038:
7019:
6375:
6310:
6214:
5795:
3982:
3807:
3751:
3425:
3364:
3001:
3000:
2339:
2320:
2249:
2214:
2000:
1981:
1901:is a prime bounded by some polynomial in
1859:
1840:
1719:
1368:
1252:
1230:
1222:
1180:
1151:
1137:
1128:" is notation for the group homomorphism
1079:
895:
853:
819:
784:
765:
707:
699:be a fixed probability distribution over
654:
619:
609:
601:
477:
437:
366:
346:
311:
253:
201:
182:{\displaystyle y_{i}=f(\mathbf {x} _{i})}
62:Learn how and when to remove this message
46:, without removing the technical details.
7471:"Post-quantum key exchange - a new hope"
7306:
6015:{\displaystyle \chi =\Psi _{\alpha (n)}}
5443:{\displaystyle \zeta (n)\geq \gamma (n)}
5299:{\displaystyle \operatorname {poly} (n)}
5116:{\displaystyle \alpha q>2{\sqrt {n}}}
3058:
2923:{\displaystyle q=q_{1}q_{2}\cdots q_{t}}
2690:samples the same way, and transform our
2234:, and do the following. Choose a number
1344:{\displaystyle \mathrm {LWE} _{q,\phi }}
7452:"Lattice Cryptography for the Internet"
7449:
7337:
6639:{\displaystyle \operatorname {Enc} (x)}
4197:{\displaystyle \eta _{\varepsilon }(L)}
3776:, we could simply try different values
3678:{\displaystyle A_{\mathbf {s} ',\chi }}
3565:Then there would be some distinguisher
3514:{\displaystyle A_{\mathbf {s} ',\chi }}
7725:
7277:
7161:Ring learning with errors key exchange
7108:Ring learning with errors key exchange
5516:
4724:. The goal is to output a sample from
3713:{\displaystyle A_{\mathbf {s} ,\chi }}
3199:{\displaystyle A_{\mathbf {s} ,\chi }}
2513:{\displaystyle A_{\mathbf {s} ,\chi }}
1421:{\displaystyle A_{\mathbf {s} ,\phi }}
749:{\displaystyle A_{\mathbf {s} ,\phi }}
583:ring learning with errors key exchange
7511:
7191:
6190:The cryptosystem is then defined by:
5226:problem in the worst case to solving
2262:{\displaystyle r\in \mathbb {Z} _{q}}
2227:{\displaystyle k\in \mathbb {Z} _{q}}
1193:{\displaystyle 1\in \mathbb {Z} _{q}}
1108:(or more formally, this "division by
490:{\displaystyle y\in \mathbb {Z} _{q}}
44:make it understandable to non-experts
7187:
7185:
7166:Short integer solution (SIS) problem
7058:
6568:is done by choosing a random subset
4000:{\displaystyle \mathbb {Z} _{q}^{n}}
3825:{\displaystyle \mathbb {Z} _{q}^{n}}
3769:{\displaystyle \mathbb {Z} _{q}^{n}}
2014:. If the solver returns a candidate
1097:{\displaystyle \mathbb {Z} _{q}^{n}}
871:{\displaystyle \mathbb {Z} _{q}^{n}}
271:{\displaystyle \mathbb {Z} _{q}^{n}}
18:
16:Mathematical problem in cryptography
7416:
7127:Ring learning with errors signature
6977:can be used to distinguish between
5623:{\displaystyle \mathrm {SIVP} _{t}}
5186:
4131:
3742:is chosen uniformly at random from
1810:
1532:, that is, the density function is
1525:{\displaystyle \alpha ^{2}/(2\pi )}
844:from the uniform distribution over
13:
7539:Computational hardness assumptions
7010:and the uniform distribution over
6095:
5994:
5698:
5695:
5692:
5689:
5686:
5683:
5610:
5607:
5604:
5601:
5552:
5549:
5546:
5543:
5540:
5537:
5253:
5241:
5238:
5235:
5008:
4996:
4993:
4990:
4614:discrete Gaussian sampling problem
4105:
4078:
4054:
3958:
3934:
3574:
3543:
3403:
3354:
1787:
1775:
1772:
1769:
1692:
1325:
1322:
1319:
635:additive group on reals modulo one
557:The LWE problem was introduced by
14:
7749:
7182:
5838:, usually a prime number between
4262:
4136:
3798:sampled uniformly at random from
2560:is bounded by some polynomial in
1070:is the standard inner product in
902:{\displaystyle e\in \mathbb {T} }
527:{\displaystyle y=f(\mathbf {x} )}
7578:Decisional composite residuosity
7062:
6837:
6829:
6785:{\displaystyle (\mathbf {a} ,b)}
6769:
6682:
6466:
6452:
6421:
6295:
6274:
6205:
5337:{\displaystyle \alpha \in (0,1)}
5080:{\displaystyle \alpha \in (0,1)}
4904:{\displaystyle \gamma (n)\geq 1}
4269:
4045:
4037:
4015:
3894:
3880:
3862:
3847:
3784:
3728:
3698:
3659:
3619:
3604:
3530:
3495:
3320:
3312:
3268:
3254:
3236:
3221:
3184:
3145:
3130:
3048:{\displaystyle \mathbf {s} _{j}}
3035:
2979:{\displaystyle \mathbf {s} _{j}}
2966:
2728:
2712:{\displaystyle \mathbf {a} _{i}}
2699:
2683:{\displaystyle \mathbf {b} _{i}}
2670:
2654:{\displaystyle \mathbf {s} _{j}}
2641:
2625:{\displaystyle \mathbf {s} _{1}}
2612:
2520:to itself, and otherwise, since
2498:
2413:
2368:
2299:
2284:
2192:{\displaystyle \mathbf {s} _{1}}
2179:
2156:
2144:Solving search assuming decision
2097:
2085:
2071:
2022:
1960:
1945:
1925:Solving decision assuming search
1406:
1359:
1296:{\displaystyle (\mathbf {a} ,t)}
1280:
1244:), and the final addition is in
1008:
1000:
957:
949:
810:
734:
645:
517:
497:, so that with high probability
428:
413:{\displaystyle (\mathbf {x} ,y)}
397:
324:{\displaystyle \mathbb {Z} _{q}}
214:{\displaystyle \mathbb {Z} _{q}}
166:
23:
7481:
7462:
7113:application was filed in 2012.
7101:
6166:and reducing the result modulo
5767:and a probability distribution
3345:So, suppose there was some set
3015:{\displaystyle 0\mod q_{\ell }}
2996:
2874:) primes. The main idea is if
1823:version of the problem. In the
1819:problem described above is the
1704:{\displaystyle \Psi _{\alpha }}
7443:
7410:
7396:
7382:
7331:
7230:
7131:A RLWE version of the classic
6902:{\displaystyle {\frac {1}{2}}}
6779:
6765:
6633:
6627:
6601:
6595:
6495:
6416:
6107:{\displaystyle \Psi _{\beta }}
6074:
6047:
6038:
6032:
6007:
6001:
5937:
5925:
5922:
5910:
5666:{\displaystyle t=O(n/\alpha )}
5660:
5646:
5500:
5481:
5463:
5437:
5431:
5422:
5416:
5393:
5374:
5360:
5354:
5331:
5319:
5293:
5287:
5074:
5062:
4981:given access to an oracle for
4958:
4952:
4892:
4886:
4861:
4848:
4837:
4831:
4788:
4782:
4717:{\displaystyle r\geq \phi (L)}
4711:
4705:
4596:
4590:
4407:
4394:
4386:
4382:
4365:
4359:
4276:
4249:
4191:
4185:
4113:{\displaystyle {\mathcal {S}}}
4086:{\displaystyle {\mathcal {A}}}
3973:comprises a large fraction of
3966:{\displaystyle {\mathcal {S}}}
3942:{\displaystyle {\mathcal {A}}}
3901:
3842:
3629:
3599:
3582:{\displaystyle {\mathcal {A}}}
3538:
3468:
3462:
3441:
3419:
3409:
3397:
3275:
3216:
3155:
3125:
2771:
2741:
2446:
2435:
2426:
2405:
2381:
2363:
2309:
2279:
1970:
1940:
1663:
1650:
1642:
1638:
1621:
1615:
1577:
1571:
1555:
1549:
1519:
1510:
1290:
1276:
1147:
1104:, the division is done in the
521:
513:
407:
393:
361:
176:
161:
1:
7450:Peikert, Chris (2014-01-01).
7176:
6409:. The public key consists of
5737:based on the hardness of the
4029:, we will find one such that
2824:{\displaystyle j^{\text{th}}}
1881:versions are equivalent when
588:
7614:Computational Diffie–Hellman
7358:10.1007/978-3-319-11659-4_12
6561:{\displaystyle x\in \{0,1\}}
5972:{\displaystyle \varepsilon }
5802:{\displaystyle \mathbb {T} }
4602:{\displaystyle \rho _{r}(x)}
4022:{\displaystyle \mathbf {t} }
3791:{\displaystyle \mathbf {t} }
3735:{\displaystyle \mathbf {s} }
2957:, guess and check to see if
2661:. Namely, we transform our
2163:{\displaystyle \mathbf {s} }
2029:{\displaystyle \mathbf {s} }
1726:{\displaystyle \mathbb {T} }
1488:with zero mean and variance
1450:{\displaystyle \alpha >0}
1309:learning with errors problem
1259:{\displaystyle \mathbb {T} }
714:{\displaystyle \mathbb {T} }
221:denote the ring of integers
7:
7702:Exponential time hypothesis
7493:Google Online Security Blog
7139:
7003:{\displaystyle A_{s,\chi }}
6389:independently according to
6239:chosen uniformly at random.
4642:{\displaystyle DGS_{\phi }}
1753:{\displaystyle D_{\alpha }}
1477:{\displaystyle D_{\alpha }}
10:
7756:
7156:Lattice-based cryptography
7105:
6530:: The encryption of a bit
5959:for an arbitrary constant
4547:. The probability of each
3925:and feed these samples to
561:in 2005 (who won the 2018
7738:Post-quantum cryptography
7712:Planted clique conjecture
7694:
7681:Ring learning with errors
7648:
7622:
7609:Decisional Diffie–Hellman
7591:
7545:
7475:Cryptology ePrint Archive
7456:Cryptology ePrint Archive
7423:Cryptology ePrint Archive
7340:Post-Quantum Cryptography
7151:Ring learning with errors
7146:Post-quantum cryptography
3206:, it is easy to see that
3024:Chinese remainder theorem
2950:{\displaystyle q_{\ell }}
7096:chosen-ciphertext attack
5163:has to be polynomial in
3481:, and for distributions
3065:random self-reducibility
1733:obtained by considering
579:public-key cryptosystems
7707:Unique games conjecture
7656:Shortest vector problem
7630:External Diffie–Hellman
7216:10.1145/1568318.1568324
7055:CCA-secure cryptosystem
6134:and standard variation
5831:{\displaystyle q\geq 2}
5735:public-key cryptosystem
5729:Public-key cryptosystem
5585:{\displaystyle \gamma }
5306:samples for parameters
4750:{\displaystyle D_{L,r}}
4454:{\displaystyle D_{L,r}}
3075:problems for arbitrary
2719:samples by calculating
1711:be the distribution on
679:be a fixed vector. Let
7686:Short integer solution
7666:Closest vector problem
7046:
7004:
6971:
6951:
6923:
6903:
6876:
6856:
6806:
6786:
6743:
6640:
6608:
6582:
6562:
6519:
6403:
6383:
6329:
6259:
6233:
6180:
6160:
6128:
6108:
6081:
6016:
5973:
5953:
5889:
5888:{\displaystyle 2n^{2}}
5859:
5832:
5803:
5781:
5761:
5718:
5667:
5624:
5586:
5566:
5507:
5444:
5400:
5338:
5300:
5268:
5219:
5177:
5157:
5137:
5117:
5081:
5043:
5023:
4975:
4905:
4870:
4797:
4751:
4718:
4683:
4663:
4643:
4603:
4567:
4566:{\displaystyle x\in L}
4541:
4540:{\displaystyle r>0}
4515:
4495:
4475:
4455:
4422:
4336:
4316:
4289:
4218:
4198:
4159:
4114:
4087:
4063:
4023:
4001:
3967:
3943:
3919:
3826:
3792:
3770:
3736:
3714:
3679:
3639:
3583:
3552:
3515:
3475:
3383:
3336:
3293:
3200:
3165:
3109:
3089:
3049:
3016:
2980:
2951:
2924:
2868:
2848:
2825:
2798:
2778:
2713:
2684:
2655:
2626:
2594:
2574:
2554:
2534:
2514:
2479:
2456:
2353:as follows. Calculate
2347:
2263:
2228:
2193:
2164:
2134:
2114:
2050:
2030:
2008:
1915:
1895:
1867:
1802:
1754:
1727:
1705:
1678:
1592:
1526:
1478:
1451:
1422:
1387:
1345:
1297:
1260:
1238:
1194:
1159:
1122:
1098:
1064:
1038:
982:
923:
909:from the distribution
903:
872:
838:
792:
750:
715:
693:
673:
627:
548:
528:
491:
456:
414:
380:
325:
292:
272:
238:
215:
183:
128:
108:
94:of inferring a linear
7573:Quadratic residuosity
7553:Integer factorization
7047:
7005:
6972:
6952:
6924:
6904:
6877:
6857:
6807:
6787:
6744:
6641:
6609:
6583:
6563:
6520:
6404:
6402:{\displaystyle \chi }
6384:
6330:
6260:
6234:
6181:
6161:
6129:
6109:
6082:
6017:
5974:
5954:
5890:
5860:
5858:{\displaystyle n^{2}}
5833:
5804:
5782:
5780:{\displaystyle \chi }
5762:
5719:
5668:
5625:
5587:
5567:
5508:
5445:
5401:
5339:
5301:
5269:
5220:
5178:
5158:
5138:
5118:
5082:
5044:
5024:
4976:
4906:
4871:
4798:
4752:
4719:
4684:
4669:-dimensional lattice
4664:
4644:
4604:
4568:
4542:
4516:
4496:
4476:
4456:
4423:
4337:
4317:
4315:{\displaystyle L^{*}}
4290:
4219:
4199:
4160:
4145:-dimensional lattice
4115:
4088:
4064:
4024:
4002:
3968:
3944:
3920:
3827:
3793:
3771:
3737:
3715:
3680:
3640:
3589:, who, given samples
3584:
3553:
3516:
3476:
3384:
3337:
3294:
3201:
3166:
3110:
3108:{\displaystyle \chi }
3090:
3059:Average case hardness
3050:
3017:
2981:
2952:
2925:
2869:
2849:
2826:
2799:
2779:
2714:
2685:
2656:
2627:
2595:
2575:
2555:
2535:
2515:
2480:
2457:
2348:
2264:
2229:
2194:
2165:
2135:
2133:{\displaystyle \chi }
2115:
2051:
2031:
2009:
1916:
1896:
1868:
1803:
1755:
1728:
1706:
1679:
1593:
1527:
1479:
1452:
1423:
1388:
1346:
1298:
1261:
1239:
1195:
1160:
1123:
1099:
1065:
1018:
983:
924:
922:{\displaystyle \phi }
904:
873:
839:
798:obtained as follows.
793:
751:
716:
694:
692:{\displaystyle \phi }
674:
628:
549:
529:
492:
457:
415:
381:
326:
293:
273:
239:
216:
184:
129:
109:
92:computational problem
88:encryption algorithms
7676:Learning with errors
7014:
6981:
6961:
6941:
6913:
6886:
6866:
6816:
6796:
6762:
6758:: The decryption of
6656:
6618:
6592:
6572:
6534:
6413:
6393:
6339:
6269:
6249:
6201:
6197:: Private key is an
6170:
6138:
6118:
6091:
6026:
5984:
5963:
5901:
5869:
5842:
5816:
5791:
5771:
5745:
5678:
5634:
5596:
5576:
5532:
5454:
5410:
5348:
5310:
5278:
5230:
5196:
5167:
5147:
5127:
5091:
5053:
5033:
4985:
4918:
4880:
4807:
4761:
4728:
4693:
4673:
4653:
4620:
4577:
4551:
4525:
4505:
4485:
4465:
4432:
4346:
4326:
4299:
4228:
4208:
4204:denote the smallest
4172:
4149:
4100:
4073:
4033:
4011:
3977:
3953:
3929:
3836:
3802:
3780:
3746:
3724:
3689:
3649:
3593:
3569:
3525:
3485:
3393:
3349:
3303:
3210:
3175:
3119:
3099:
3079:
3030:
2990:
2961:
2934:
2878:
2858:
2838:
2808:
2788:
2723:
2694:
2665:
2636:
2607:
2584:
2564:
2544:
2524:
2489:
2469:
2357:
2273:
2238:
2203:
2174:
2152:
2124:
2060:
2040:
2018:
1934:
1905:
1885:
1835:
1764:
1737:
1715:
1688:
1602:
1536:
1492:
1484:the one-dimensional
1461:
1435:
1397:
1355:
1314:
1273:
1248:
1204:
1169:
1132:
1112:
1074:
992:
936:
913:
885:
848:
806:
760:
756:the distribution on
725:
703:
683:
641:
597:
538:
501:
466:
424:
390:
335:
306:
282:
248:
228:
196:
142:
118:
98:
80:learning with errors
7033:
6514:
6324:
6228:
5760:{\displaystyle m,q}
5517:Use in cryptography
4573:is proportional to
4167:smoothing parameter
4120:can exist, meaning
3996:
3821:
3765:
3439:
3378:
3022:, and then use the
2334:
1995:
1854:
1382:
1093:
867:
833:
779:
668:
575:hardness assumption
451:
360:
267:
138:from given samples
7599:Discrete logarithm
7583:Higher residuosity
7243:Journal of the ACM
7194:Journal of the ACM
7074:. You can help by
7042:
7017:
7000:
6967:
6947:
6919:
6899:
6872:
6852:
6802:
6782:
6739:
6723:
6679:
6636:
6614:and then defining
6604:
6578:
6558:
6515:
6494:
6399:
6379:
6325:
6308:
6255:
6229:
6212:
6176:
6156:
6124:
6104:
6077:
6012:
5969:
5949:
5885:
5855:
5828:
5799:
5777:
5757:
5714:
5663:
5620:
5582:
5562:
5503:
5440:
5396:
5334:
5296:
5264:
5215:
5173:
5153:
5133:
5113:
5077:
5039:
5019:
4971:
4901:
4866:
4793:
4747:
4714:
4679:
4659:
4639:
4599:
4563:
4537:
4511:
4491:
4471:
4451:
4418:
4332:
4312:
4285:
4214:
4194:
4155:
4110:
4083:
4059:
4019:
3997:
3980:
3963:
3939:
3915:
3822:
3805:
3788:
3766:
3749:
3732:
3710:
3675:
3635:
3579:
3548:
3511:
3471:
3423:
3379:
3362:
3332:
3289:
3196:
3161:
3105:
3085:
3045:
3012:
2976:
2947:
2920:
2864:
2844:
2821:
2794:
2774:
2709:
2680:
2651:
2622:
2590:
2570:
2550:
2530:
2510:
2475:
2452:
2343:
2318:
2259:
2224:
2189:
2160:
2130:
2110:
2046:
2026:
2004:
1979:
1911:
1891:
1863:
1838:
1798:
1750:
1723:
1701:
1674:
1588:
1522:
1474:
1447:
1418:
1383:
1366:
1341:
1293:
1256:
1234:
1190:
1155:
1118:
1094:
1077:
1060:
1059:
978:
919:
899:
868:
851:
834:
817:
788:
763:
746:
711:
689:
669:
652:
623:
544:
524:
487:
452:
435:
410:
376:
344:
321:
288:
278:denote the set of
268:
251:
234:
211:
179:
124:
104:
7720:
7719:
7695:Non-cryptographic
7367:978-3-319-11658-7
7092:
7091:
6970:{\displaystyle 1}
6950:{\displaystyle 0}
6922:{\displaystyle 1}
6897:
6875:{\displaystyle 0}
6805:{\displaystyle 0}
6708:
6703:
6664:
6581:{\displaystyle S}
6258:{\displaystyle m}
6179:{\displaystyle 1}
6154:
6153:
6127:{\displaystyle 0}
6063:
5733:Regev proposed a
5498:
5479:
5391:
5176:{\displaystyle n}
5156:{\displaystyle q}
5136:{\displaystyle q}
5111:
5042:{\displaystyle q}
4940:
4876:for any function
4826:
4777:
4682:{\displaystyle L}
4662:{\displaystyle n}
4514:{\displaystyle L}
4494:{\displaystyle r}
4474:{\displaystyle L}
4335:{\displaystyle L}
4217:{\displaystyle s}
4158:{\displaystyle L}
3299:are samples from
3115:. Given samples
3088:{\displaystyle q}
3063:Regev showed the
2867:{\displaystyle n}
2847:{\displaystyle q}
2818:
2797:{\displaystyle r}
2593:{\displaystyle k}
2573:{\displaystyle n}
2553:{\displaystyle q}
2533:{\displaystyle q}
2478:{\displaystyle k}
2049:{\displaystyle i}
1914:{\displaystyle n}
1894:{\displaystyle q}
1121:{\displaystyle q}
547:{\displaystyle f}
291:{\displaystyle n}
237:{\displaystyle q}
127:{\displaystyle f}
107:{\displaystyle n}
72:
71:
64:
7745:
7733:Machine learning
7635:Sub-group hiding
7546:Number theoretic
7532:
7525:
7518:
7509:
7508:
7503:
7502:
7500:
7499:
7485:
7479:
7478:
7466:
7460:
7459:
7447:
7441:
7440:
7434:
7426:
7414:
7408:
7400:
7394:
7386:
7380:
7379:
7351:
7335:
7329:
7321:
7304:
7296:
7275:
7274:
7234:
7228:
7227:
7209:
7189:
7087:
7084:
7066:
7059:
7051:
7049:
7048:
7043:
7041:
7032:
7027:
7022:
7009:
7007:
7006:
7001:
6999:
6998:
6976:
6974:
6973:
6968:
6956:
6954:
6953:
6948:
6928:
6926:
6925:
6920:
6908:
6906:
6905:
6900:
6898:
6890:
6881:
6879:
6878:
6873:
6861:
6859:
6858:
6853:
6848:
6840:
6832:
6811:
6809:
6808:
6803:
6791:
6789:
6788:
6783:
6772:
6748:
6746:
6745:
6740:
6738:
6734:
6733:
6732:
6722:
6704:
6696:
6691:
6690:
6685:
6678:
6645:
6643:
6642:
6637:
6613:
6611:
6610:
6607:{\displaystyle }
6605:
6587:
6585:
6584:
6579:
6567:
6565:
6564:
6559:
6524:
6522:
6521:
6516:
6513:
6508:
6493:
6492:
6477:
6469:
6461:
6460:
6455:
6443:
6442:
6430:
6429:
6424:
6408:
6406:
6405:
6400:
6388:
6386:
6385:
6380:
6378:
6370:
6369:
6351:
6350:
6334:
6332:
6331:
6326:
6323:
6318:
6313:
6304:
6303:
6298:
6283:
6282:
6277:
6264:
6262:
6261:
6256:
6238:
6236:
6235:
6230:
6227:
6222:
6217:
6208:
6185:
6183:
6182:
6177:
6165:
6163:
6162:
6157:
6155:
6146:
6142:
6133:
6131:
6130:
6125:
6113:
6111:
6110:
6105:
6103:
6102:
6086:
6084:
6083:
6078:
6064:
6059:
6057:
6021:
6019:
6018:
6013:
6011:
6010:
5978:
5976:
5975:
5970:
5958:
5956:
5955:
5950:
5894:
5892:
5891:
5886:
5884:
5883:
5864:
5862:
5861:
5856:
5854:
5853:
5837:
5835:
5834:
5829:
5808:
5806:
5805:
5800:
5798:
5786:
5784:
5783:
5778:
5766:
5764:
5763:
5758:
5723:
5721:
5720:
5715:
5713:
5712:
5701:
5672:
5670:
5669:
5664:
5656:
5629:
5627:
5626:
5621:
5619:
5618:
5613:
5591:
5589:
5588:
5583:
5571:
5569:
5568:
5563:
5561:
5560:
5555:
5527:lattice problems
5512:
5510:
5509:
5504:
5499:
5488:
5480:
5475:
5473:
5449:
5447:
5446:
5441:
5405:
5403:
5402:
5397:
5392:
5381:
5373:
5343:
5341:
5340:
5335:
5305:
5303:
5302:
5297:
5273:
5271:
5270:
5265:
5263:
5262:
5261:
5260:
5244:
5224:
5222:
5221:
5216:
5214:
5213:
5187:Peikert's result
5182:
5180:
5179:
5174:
5162:
5160:
5159:
5154:
5142:
5140:
5139:
5134:
5122:
5120:
5119:
5114:
5112:
5107:
5086:
5084:
5083:
5078:
5048:
5046:
5045:
5040:
5028:
5026:
5025:
5020:
5018:
5017:
5016:
5015:
4999:
4980:
4978:
4977:
4972:
4970:
4969:
4965:
4951:
4950:
4941:
4933:
4910:
4908:
4907:
4902:
4875:
4873:
4872:
4867:
4865:
4864:
4860:
4859:
4844:
4827:
4822:
4802:
4800:
4799:
4794:
4792:
4791:
4778:
4773:
4756:
4754:
4753:
4748:
4746:
4745:
4723:
4721:
4720:
4715:
4688:
4686:
4685:
4680:
4668:
4666:
4665:
4660:
4648:
4646:
4645:
4640:
4638:
4637:
4608:
4606:
4605:
4600:
4589:
4588:
4572:
4570:
4569:
4564:
4546:
4544:
4543:
4538:
4520:
4518:
4517:
4512:
4500:
4498:
4497:
4492:
4480:
4478:
4477:
4472:
4460:
4458:
4457:
4452:
4450:
4449:
4427:
4425:
4424:
4419:
4417:
4416:
4415:
4414:
4402:
4397:
4389:
4358:
4357:
4341:
4339:
4338:
4333:
4321:
4319:
4318:
4313:
4311:
4310:
4294:
4292:
4291:
4286:
4272:
4261:
4260:
4248:
4247:
4243:
4223:
4221:
4220:
4215:
4203:
4201:
4200:
4195:
4184:
4183:
4164:
4162:
4161:
4156:
4132:Hardness results
4119:
4117:
4116:
4111:
4109:
4108:
4092:
4090:
4089:
4084:
4082:
4081:
4068:
4066:
4065:
4060:
4058:
4057:
4048:
4040:
4028:
4026:
4025:
4020:
4018:
4006:
4004:
4003:
3998:
3995:
3990:
3985:
3972:
3970:
3969:
3964:
3962:
3961:
3948:
3946:
3945:
3940:
3938:
3937:
3924:
3922:
3921:
3916:
3908:
3897:
3889:
3888:
3883:
3871:
3870:
3865:
3856:
3855:
3850:
3831:
3829:
3828:
3823:
3820:
3815:
3810:
3797:
3795:
3794:
3789:
3787:
3775:
3773:
3772:
3767:
3764:
3759:
3754:
3741:
3739:
3738:
3733:
3731:
3719:
3717:
3716:
3711:
3709:
3708:
3701:
3684:
3682:
3681:
3676:
3674:
3673:
3666:
3662:
3644:
3642:
3641:
3636:
3628:
3627:
3622:
3613:
3612:
3607:
3588:
3586:
3585:
3580:
3578:
3577:
3557:
3555:
3554:
3549:
3547:
3546:
3537:
3533:
3520:
3518:
3517:
3512:
3510:
3509:
3502:
3498:
3480:
3478:
3477:
3472:
3455:
3444:
3438:
3433:
3428:
3422:
3417:
3412:
3407:
3406:
3400:
3388:
3386:
3385:
3380:
3377:
3372:
3367:
3358:
3357:
3341:
3339:
3338:
3333:
3331:
3330:
3323:
3315:
3298:
3296:
3295:
3290:
3282:
3271:
3263:
3262:
3257:
3245:
3244:
3239:
3230:
3229:
3224:
3205:
3203:
3202:
3197:
3195:
3194:
3187:
3170:
3168:
3167:
3162:
3154:
3153:
3148:
3139:
3138:
3133:
3114:
3112:
3111:
3106:
3094:
3092:
3091:
3086:
3054:
3052:
3051:
3046:
3044:
3043:
3038:
3021:
3019:
3018:
3013:
3011:
3010:
2986:is congruent to
2985:
2983:
2982:
2977:
2975:
2974:
2969:
2956:
2954:
2953:
2948:
2946:
2945:
2929:
2927:
2926:
2921:
2919:
2918:
2906:
2905:
2896:
2895:
2873:
2871:
2870:
2865:
2853:
2851:
2850:
2845:
2830:
2828:
2827:
2822:
2820:
2819:
2816:
2803:
2801:
2800:
2795:
2783:
2781:
2780:
2775:
2737:
2736:
2731:
2718:
2716:
2715:
2710:
2708:
2707:
2702:
2689:
2687:
2686:
2681:
2679:
2678:
2673:
2660:
2658:
2657:
2652:
2650:
2649:
2644:
2631:
2629:
2628:
2623:
2621:
2620:
2615:
2603:After obtaining
2599:
2597:
2596:
2591:
2579:
2577:
2576:
2571:
2559:
2557:
2556:
2551:
2539:
2537:
2536:
2531:
2519:
2517:
2516:
2511:
2509:
2508:
2501:
2484:
2482:
2481:
2476:
2461:
2459:
2458:
2453:
2442:
2422:
2421:
2416:
2377:
2376:
2371:
2352:
2350:
2349:
2344:
2342:
2333:
2328:
2323:
2308:
2307:
2302:
2293:
2292:
2287:
2268:
2266:
2265:
2260:
2258:
2257:
2252:
2233:
2231:
2230:
2225:
2223:
2222:
2217:
2198:
2196:
2195:
2190:
2188:
2187:
2182:
2169:
2167:
2166:
2161:
2159:
2139:
2137:
2136:
2131:
2119:
2117:
2116:
2111:
2106:
2105:
2100:
2088:
2080:
2079:
2074:
2055:
2053:
2052:
2047:
2035:
2033:
2032:
2027:
2025:
2013:
2011:
2010:
2005:
2003:
1994:
1989:
1984:
1969:
1968:
1963:
1954:
1953:
1948:
1920:
1918:
1917:
1912:
1900:
1898:
1897:
1892:
1872:
1870:
1869:
1864:
1862:
1853:
1848:
1843:
1811:Decision version
1807:
1805:
1804:
1799:
1797:
1796:
1795:
1794:
1778:
1759:
1757:
1756:
1751:
1749:
1748:
1732:
1730:
1729:
1724:
1722:
1710:
1708:
1707:
1702:
1700:
1699:
1683:
1681:
1680:
1675:
1673:
1672:
1671:
1670:
1658:
1653:
1645:
1614:
1613:
1597:
1595:
1594:
1589:
1584:
1570:
1569:
1548:
1547:
1531:
1529:
1528:
1523:
1509:
1504:
1503:
1483:
1481:
1480:
1475:
1473:
1472:
1456:
1454:
1453:
1448:
1427:
1425:
1424:
1419:
1417:
1416:
1409:
1392:
1390:
1389:
1384:
1381:
1376:
1371:
1362:
1350:
1348:
1347:
1342:
1340:
1339:
1328:
1302:
1300:
1299:
1294:
1283:
1269:Output the pair
1265:
1263:
1262:
1257:
1255:
1243:
1241:
1240:
1235:
1233:
1225:
1214:
1199:
1197:
1196:
1191:
1189:
1188:
1183:
1164:
1162:
1161:
1156:
1154:
1146:
1145:
1140:
1127:
1125:
1124:
1119:
1103:
1101:
1100:
1095:
1092:
1087:
1082:
1069:
1067:
1066:
1061:
1058:
1057:
1048:
1047:
1037:
1032:
1011:
1003:
987:
985:
984:
979:
968:
960:
952:
928:
926:
925:
920:
908:
906:
905:
900:
898:
877:
875:
874:
869:
866:
861:
856:
843:
841:
840:
835:
832:
827:
822:
813:
797:
795:
794:
789:
787:
778:
773:
768:
755:
753:
752:
747:
745:
744:
737:
720:
718:
717:
712:
710:
698:
696:
695:
690:
678:
676:
675:
670:
667:
662:
657:
648:
632:
630:
629:
624:
622:
617:
612:
604:
571:lattice problems
553:
551:
550:
545:
533:
531:
530:
525:
520:
496:
494:
493:
488:
486:
485:
480:
461:
459:
458:
453:
450:
445:
440:
431:
419:
417:
416:
411:
400:
385:
383:
382:
377:
375:
374:
369:
359:
354:
349:
330:
328:
327:
322:
320:
319:
314:
297:
295:
294:
289:
277:
275:
274:
269:
266:
261:
256:
243:
241:
240:
235:
220:
218:
217:
212:
210:
209:
204:
188:
186:
185:
180:
175:
174:
169:
154:
153:
133:
131:
130:
125:
113:
111:
110:
105:
67:
60:
56:
53:
47:
27:
26:
19:
7755:
7754:
7748:
7747:
7746:
7744:
7743:
7742:
7723:
7722:
7721:
7716:
7690:
7644:
7640:Decision linear
7618:
7592:Group theoretic
7587:
7541:
7536:
7506:
7497:
7495:
7487:
7486:
7482:
7467:
7463:
7448:
7444:
7428:
7427:
7415:
7411:
7401:
7397:
7387:
7383:
7368:
7349:10.1.1.800.4743
7336:
7332:
7322:
7307:
7297:
7278:
7255:10.1145/2535925
7235:
7231:
7190:
7183:
7179:
7142:
7123:
7110:
7104:
7088:
7082:
7079:
7072:needs expansion
7057:
7037:
7028:
7023:
7018:
7015:
7012:
7011:
6988:
6984:
6982:
6979:
6978:
6962:
6959:
6958:
6942:
6939:
6938:
6914:
6911:
6910:
6889:
6887:
6884:
6883:
6867:
6864:
6863:
6844:
6836:
6828:
6817:
6814:
6813:
6797:
6794:
6793:
6768:
6763:
6760:
6759:
6728:
6724:
6712:
6695:
6686:
6681:
6680:
6668:
6663:
6659:
6657:
6654:
6653:
6619:
6616:
6615:
6593:
6590:
6589:
6573:
6570:
6569:
6535:
6532:
6531:
6509:
6498:
6488:
6484:
6473:
6465:
6456:
6451:
6450:
6438:
6434:
6425:
6420:
6419:
6414:
6411:
6410:
6394:
6391:
6390:
6374:
6365:
6361:
6346:
6342:
6340:
6337:
6336:
6319:
6314:
6309:
6299:
6294:
6293:
6278:
6273:
6272:
6270:
6267:
6266:
6250:
6247:
6246:
6223:
6218:
6213:
6204:
6202:
6199:
6198:
6171:
6168:
6167:
6141:
6139:
6136:
6135:
6119:
6116:
6115:
6098:
6094:
6092:
6089:
6088:
6058:
6053:
6027:
6024:
6023:
5997:
5993:
5985:
5982:
5981:
5964:
5961:
5960:
5902:
5899:
5898:
5879:
5875:
5870:
5867:
5866:
5849:
5845:
5843:
5840:
5839:
5817:
5814:
5813:
5794:
5792:
5789:
5788:
5772:
5769:
5768:
5746:
5743:
5742:
5731:
5702:
5682:
5681:
5679:
5676:
5675:
5652:
5635:
5632:
5631:
5614:
5600:
5599:
5597:
5594:
5593:
5577:
5574:
5573:
5556:
5536:
5535:
5533:
5530:
5529:
5519:
5487:
5474:
5469:
5455:
5452:
5451:
5411:
5408:
5407:
5380:
5369:
5349:
5346:
5345:
5311:
5308:
5307:
5279:
5276:
5275:
5256:
5252:
5245:
5234:
5233:
5231:
5228:
5227:
5203:
5199:
5197:
5194:
5193:
5189:
5168:
5165:
5164:
5148:
5145:
5144:
5128:
5125:
5124:
5106:
5092:
5089:
5088:
5054:
5051:
5050:
5034:
5031:
5030:
5011:
5007:
5000:
4989:
4988:
4986:
4983:
4982:
4961:
4946:
4942:
4932:
4931:
4927:
4919:
4916:
4915:
4881:
4878:
4877:
4855:
4851:
4840:
4821:
4820:
4816:
4808:
4805:
4804:
4772:
4768:
4764:
4762:
4759:
4758:
4735:
4731:
4729:
4726:
4725:
4694:
4691:
4690:
4674:
4671:
4670:
4654:
4651:
4650:
4649:is given by an
4633:
4629:
4621:
4618:
4617:
4584:
4580:
4578:
4575:
4574:
4552:
4549:
4548:
4526:
4523:
4522:
4506:
4503:
4502:
4486:
4483:
4482:
4466:
4463:
4462:
4439:
4435:
4433:
4430:
4429:
4410:
4406:
4398:
4393:
4385:
4375:
4371:
4353:
4349:
4347:
4344:
4343:
4327:
4324:
4323:
4322:is the dual of
4306:
4302:
4300:
4297:
4296:
4268:
4256:
4252:
4239:
4235:
4231:
4229:
4226:
4225:
4209:
4206:
4205:
4179:
4175:
4173:
4170:
4169:
4150:
4147:
4146:
4139:
4134:
4104:
4103:
4101:
4098:
4097:
4077:
4076:
4074:
4071:
4070:
4053:
4052:
4044:
4036:
4034:
4031:
4030:
4014:
4012:
4009:
4008:
3991:
3986:
3981:
3978:
3975:
3974:
3957:
3956:
3954:
3951:
3950:
3933:
3932:
3930:
3927:
3926:
3904:
3893:
3884:
3879:
3878:
3866:
3861:
3860:
3851:
3846:
3845:
3837:
3834:
3833:
3816:
3811:
3806:
3803:
3800:
3799:
3783:
3781:
3778:
3777:
3760:
3755:
3750:
3747:
3744:
3743:
3727:
3725:
3722:
3721:
3697:
3696:
3692:
3690:
3687:
3686:
3658:
3657:
3656:
3652:
3650:
3647:
3646:
3623:
3618:
3617:
3608:
3603:
3602:
3594:
3591:
3590:
3573:
3572:
3570:
3567:
3566:
3542:
3541:
3529:
3528:
3526:
3523:
3522:
3494:
3493:
3492:
3488:
3486:
3483:
3482:
3451:
3440:
3434:
3429:
3424:
3418:
3413:
3408:
3402:
3401:
3396:
3394:
3391:
3390:
3373:
3368:
3363:
3353:
3352:
3350:
3347:
3346:
3319:
3311:
3310:
3306:
3304:
3301:
3300:
3278:
3267:
3258:
3253:
3252:
3240:
3235:
3234:
3225:
3220:
3219:
3211:
3208:
3207:
3183:
3182:
3178:
3176:
3173:
3172:
3149:
3144:
3143:
3134:
3129:
3128:
3120:
3117:
3116:
3100:
3097:
3096:
3080:
3077:
3076:
3061:
3039:
3034:
3033:
3031:
3028:
3027:
3006:
3002:
2991:
2988:
2987:
2970:
2965:
2964:
2962:
2959:
2958:
2941:
2937:
2935:
2932:
2931:
2914:
2910:
2901:
2897:
2891:
2887:
2879:
2876:
2875:
2859:
2856:
2855:
2839:
2836:
2835:
2815:
2811:
2809:
2806:
2805:
2789:
2786:
2785:
2732:
2727:
2726:
2724:
2721:
2720:
2703:
2698:
2697:
2695:
2692:
2691:
2674:
2669:
2668:
2666:
2663:
2662:
2645:
2640:
2639:
2637:
2634:
2633:
2616:
2611:
2610:
2608:
2605:
2604:
2585:
2582:
2581:
2565:
2562:
2561:
2545:
2542:
2541:
2525:
2522:
2521:
2497:
2496:
2492:
2490:
2487:
2486:
2470:
2467:
2466:
2438:
2417:
2412:
2411:
2372:
2367:
2366:
2358:
2355:
2354:
2338:
2329:
2324:
2319:
2303:
2298:
2297:
2288:
2283:
2282:
2274:
2271:
2270:
2253:
2248:
2247:
2239:
2236:
2235:
2218:
2213:
2212:
2204:
2201:
2200:
2199:, make a guess
2183:
2178:
2177:
2175:
2172:
2171:
2155:
2153:
2150:
2149:
2146:
2125:
2122:
2121:
2101:
2096:
2095:
2084:
2075:
2070:
2069:
2061:
2058:
2057:
2041:
2038:
2037:
2021:
2019:
2016:
2015:
1999:
1990:
1985:
1980:
1964:
1959:
1958:
1949:
1944:
1943:
1935:
1932:
1931:
1927:
1906:
1903:
1902:
1886:
1883:
1882:
1858:
1849:
1844:
1839:
1836:
1833:
1832:
1813:
1790:
1786:
1779:
1768:
1767:
1765:
1762:
1761:
1744:
1740:
1738:
1735:
1734:
1718:
1716:
1713:
1712:
1695:
1691:
1689:
1686:
1685:
1666:
1662:
1654:
1649:
1641:
1631:
1627:
1609:
1605:
1603:
1600:
1599:
1580:
1565:
1561:
1543:
1539:
1537:
1534:
1533:
1505:
1499:
1495:
1493:
1490:
1489:
1468:
1464:
1462:
1459:
1458:
1436:
1433:
1432:
1405:
1404:
1400:
1398:
1395:
1394:
1377:
1372:
1367:
1358:
1356:
1353:
1352:
1329:
1318:
1317:
1315:
1312:
1311:
1279:
1274:
1271:
1270:
1251:
1249:
1246:
1245:
1229:
1221:
1210:
1205:
1202:
1201:
1184:
1179:
1178:
1170:
1167:
1166:
1150:
1141:
1136:
1135:
1133:
1130:
1129:
1113:
1110:
1109:
1088:
1083:
1078:
1075:
1072:
1071:
1053:
1049:
1043:
1039:
1033:
1022:
1007:
999:
993:
990:
989:
964:
956:
948:
937:
934:
933:
914:
911:
910:
894:
886:
883:
882:
862:
857:
852:
849:
846:
845:
828:
823:
818:
809:
807:
804:
803:
783:
774:
769:
764:
761:
758:
757:
733:
732:
728:
726:
723:
722:
706:
704:
701:
700:
684:
681:
680:
663:
658:
653:
644:
642:
639:
638:
618:
613:
608:
600:
598:
595:
594:
591:
567:parity learning
539:
536:
535:
516:
502:
499:
498:
481:
476:
475:
467:
464:
463:
446:
441:
436:
427:
425:
422:
421:
396:
391:
388:
387:
370:
365:
364:
355:
350:
345:
336:
333:
332:
315:
310:
309:
307:
304:
303:
283:
280:
279:
262:
257:
252:
249:
246:
245:
229:
226:
225:
205:
200:
199:
197:
194:
193:
170:
165:
164:
149:
145:
143:
140:
139:
119:
116:
115:
99:
96:
95:
68:
57:
51:
48:
40:help improve it
37:
28:
24:
17:
12:
11:
5:
7753:
7752:
7741:
7740:
7735:
7718:
7717:
7715:
7714:
7709:
7704:
7698:
7696:
7692:
7691:
7689:
7688:
7683:
7678:
7673:
7663:
7652:
7650:
7646:
7645:
7643:
7642:
7637:
7632:
7626:
7624:
7620:
7619:
7617:
7616:
7611:
7606:
7604:Diffie-Hellman
7601:
7595:
7593:
7589:
7588:
7586:
7585:
7580:
7575:
7570:
7565:
7560:
7555:
7549:
7547:
7543:
7542:
7535:
7534:
7527:
7520:
7512:
7505:
7504:
7480:
7461:
7442:
7409:
7395:
7381:
7366:
7330:
7305:
7276:
7229:
7180:
7178:
7175:
7174:
7173:
7168:
7163:
7158:
7153:
7148:
7141:
7138:
7125:Main article:
7122:
7119:
7106:Main article:
7103:
7100:
7090:
7089:
7069:
7067:
7056:
7053:
7040:
7036:
7031:
7026:
7021:
6997:
6994:
6991:
6987:
6966:
6946:
6931:
6930:
6918:
6896:
6893:
6871:
6851:
6847:
6843:
6839:
6835:
6831:
6827:
6824:
6821:
6801:
6781:
6778:
6775:
6771:
6767:
6752:
6751:
6750:
6749:
6737:
6731:
6727:
6721:
6718:
6715:
6711:
6707:
6702:
6699:
6694:
6689:
6684:
6677:
6674:
6671:
6667:
6662:
6648:
6647:
6635:
6632:
6629:
6626:
6623:
6603:
6600:
6597:
6577:
6557:
6554:
6551:
6548:
6545:
6542:
6539:
6525:
6512:
6507:
6504:
6501:
6497:
6491:
6487:
6483:
6480:
6476:
6472:
6468:
6464:
6459:
6454:
6449:
6446:
6441:
6437:
6433:
6428:
6423:
6418:
6398:
6377:
6373:
6368:
6364:
6360:
6357:
6354:
6349:
6345:
6322:
6317:
6312:
6307:
6302:
6297:
6292:
6289:
6286:
6281:
6276:
6254:
6240:
6226:
6221:
6216:
6211:
6207:
6188:
6187:
6175:
6152:
6149:
6145:
6123:
6101:
6097:
6076:
6073:
6070:
6067:
6062:
6056:
6052:
6049:
6046:
6043:
6040:
6037:
6034:
6031:
6009:
6006:
6003:
6000:
5996:
5992:
5989:
5979:
5968:
5948:
5945:
5942:
5939:
5936:
5933:
5930:
5927:
5924:
5921:
5918:
5915:
5912:
5909:
5906:
5896:
5882:
5878:
5874:
5852:
5848:
5827:
5824:
5821:
5797:
5776:
5756:
5753:
5750:
5730:
5727:
5711:
5708:
5705:
5700:
5697:
5694:
5691:
5688:
5685:
5662:
5659:
5655:
5651:
5648:
5645:
5642:
5639:
5617:
5612:
5609:
5606:
5603:
5592:as above) and
5581:
5559:
5554:
5551:
5548:
5545:
5542:
5539:
5518:
5515:
5502:
5497:
5494:
5491:
5486:
5483:
5478:
5472:
5468:
5465:
5462:
5459:
5439:
5436:
5433:
5430:
5427:
5424:
5421:
5418:
5415:
5395:
5390:
5387:
5384:
5379:
5376:
5372:
5368:
5365:
5362:
5359:
5356:
5353:
5333:
5330:
5327:
5324:
5321:
5318:
5315:
5295:
5292:
5289:
5286:
5283:
5259:
5255:
5251:
5248:
5243:
5240:
5237:
5212:
5209:
5206:
5202:
5188:
5185:
5172:
5152:
5132:
5110:
5105:
5102:
5099:
5096:
5076:
5073:
5070:
5067:
5064:
5061:
5058:
5038:
5014:
5010:
5006:
5003:
4998:
4995:
4992:
4968:
4964:
4960:
4957:
4954:
4949:
4945:
4939:
4936:
4930:
4926:
4923:
4900:
4897:
4894:
4891:
4888:
4885:
4863:
4858:
4854:
4850:
4847:
4843:
4839:
4836:
4833:
4830:
4825:
4819:
4815:
4812:
4790:
4787:
4784:
4781:
4776:
4771:
4767:
4744:
4741:
4738:
4734:
4713:
4710:
4707:
4704:
4701:
4698:
4678:
4658:
4636:
4632:
4628:
4625:
4598:
4595:
4592:
4587:
4583:
4562:
4559:
4556:
4536:
4533:
4530:
4510:
4501:for a lattice
4490:
4470:
4448:
4445:
4442:
4438:
4413:
4409:
4405:
4401:
4396:
4392:
4388:
4384:
4381:
4378:
4374:
4370:
4367:
4364:
4361:
4356:
4352:
4331:
4309:
4305:
4284:
4281:
4278:
4275:
4271:
4267:
4264:
4259:
4255:
4251:
4246:
4242:
4238:
4234:
4213:
4193:
4190:
4187:
4182:
4178:
4154:
4138:
4137:Regev's result
4135:
4133:
4130:
4107:
4096:Thus, no such
4080:
4056:
4051:
4047:
4043:
4039:
4017:
3994:
3989:
3984:
3960:
3936:
3914:
3911:
3907:
3903:
3900:
3896:
3892:
3887:
3882:
3877:
3874:
3869:
3864:
3859:
3854:
3849:
3844:
3841:
3819:
3814:
3809:
3786:
3763:
3758:
3753:
3730:
3707:
3704:
3700:
3695:
3672:
3669:
3665:
3661:
3655:
3634:
3631:
3626:
3621:
3616:
3611:
3606:
3601:
3598:
3576:
3545:
3540:
3536:
3532:
3508:
3505:
3501:
3497:
3491:
3470:
3467:
3464:
3461:
3458:
3454:
3450:
3447:
3443:
3437:
3432:
3427:
3421:
3416:
3411:
3405:
3399:
3376:
3371:
3366:
3361:
3356:
3329:
3326:
3322:
3318:
3314:
3309:
3288:
3285:
3281:
3277:
3274:
3270:
3266:
3261:
3256:
3251:
3248:
3243:
3238:
3233:
3228:
3223:
3218:
3215:
3193:
3190:
3186:
3181:
3160:
3157:
3152:
3147:
3142:
3137:
3132:
3127:
3124:
3104:
3084:
3060:
3057:
3042:
3037:
3009:
3005:
2999:
2995:
2973:
2968:
2944:
2940:
2917:
2913:
2909:
2904:
2900:
2894:
2890:
2886:
2883:
2863:
2843:
2814:
2793:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2735:
2730:
2706:
2701:
2677:
2672:
2648:
2643:
2619:
2614:
2589:
2569:
2549:
2529:
2507:
2504:
2500:
2495:
2474:
2451:
2448:
2445:
2441:
2437:
2434:
2431:
2428:
2425:
2420:
2415:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2375:
2370:
2365:
2362:
2341:
2337:
2332:
2327:
2322:
2317:
2314:
2311:
2306:
2301:
2296:
2291:
2286:
2281:
2278:
2256:
2251:
2246:
2243:
2221:
2216:
2211:
2208:
2186:
2181:
2158:
2145:
2142:
2129:
2109:
2104:
2099:
2094:
2091:
2087:
2083:
2078:
2073:
2068:
2065:
2045:
2024:
2002:
1998:
1993:
1988:
1983:
1978:
1975:
1972:
1967:
1962:
1957:
1952:
1947:
1942:
1939:
1926:
1923:
1910:
1890:
1861:
1857:
1852:
1847:
1842:
1812:
1809:
1793:
1789:
1785:
1782:
1777:
1774:
1771:
1747:
1743:
1721:
1698:
1694:
1669:
1665:
1661:
1657:
1652:
1648:
1644:
1640:
1637:
1634:
1630:
1626:
1623:
1620:
1617:
1612:
1608:
1587:
1583:
1579:
1576:
1573:
1568:
1564:
1560:
1557:
1554:
1551:
1546:
1542:
1521:
1518:
1515:
1512:
1508:
1502:
1498:
1471:
1467:
1446:
1443:
1440:
1415:
1412:
1408:
1403:
1380:
1375:
1370:
1365:
1361:
1338:
1335:
1332:
1327:
1324:
1321:
1305:
1304:
1292:
1289:
1286:
1282:
1278:
1267:
1254:
1232:
1228:
1224:
1220:
1217:
1213:
1209:
1187:
1182:
1177:
1174:
1153:
1149:
1144:
1139:
1117:
1106:field of reals
1091:
1086:
1081:
1056:
1052:
1046:
1042:
1036:
1031:
1028:
1025:
1021:
1017:
1014:
1010:
1006:
1002:
998:
977:
974:
971:
967:
963:
959:
955:
951:
947:
944:
941:
930:
918:
897:
893:
890:
881:Pick a number
879:
865:
860:
855:
831:
826:
821:
816:
812:
802:Pick a vector
786:
782:
777:
772:
767:
743:
740:
736:
731:
709:
688:
666:
661:
656:
651:
647:
621:
616:
611:
607:
603:
590:
587:
581:, such as the
543:
523:
519:
515:
512:
509:
506:
484:
479:
474:
471:
449:
444:
439:
434:
430:
409:
406:
403:
399:
395:
373:
368:
363:
358:
353:
348:
343:
340:
318:
313:
287:
265:
260:
255:
233:
208:
203:
178:
173:
168:
163:
160:
157:
152:
148:
134:over a finite
123:
114:-ary function
103:
70:
69:
31:
29:
22:
15:
9:
6:
4:
3:
2:
7751:
7750:
7739:
7736:
7734:
7731:
7730:
7728:
7713:
7710:
7708:
7705:
7703:
7700:
7699:
7697:
7693:
7687:
7684:
7682:
7679:
7677:
7674:
7671:
7667:
7664:
7661:
7657:
7654:
7653:
7651:
7647:
7641:
7638:
7636:
7633:
7631:
7628:
7627:
7625:
7621:
7615:
7612:
7610:
7607:
7605:
7602:
7600:
7597:
7596:
7594:
7590:
7584:
7581:
7579:
7576:
7574:
7571:
7569:
7566:
7564:
7561:
7559:
7556:
7554:
7551:
7550:
7548:
7544:
7540:
7533:
7528:
7526:
7521:
7519:
7514:
7513:
7510:
7494:
7490:
7484:
7476:
7472:
7465:
7457:
7453:
7446:
7438:
7432:
7424:
7420:
7413:
7406:
7399:
7392:
7385:
7377:
7373:
7369:
7363:
7359:
7355:
7350:
7345:
7341:
7334:
7327:
7320:
7318:
7316:
7314:
7312:
7310:
7302:
7295:
7293:
7291:
7289:
7287:
7285:
7283:
7281:
7272:
7268:
7264:
7260:
7256:
7252:
7248:
7244:
7240:
7233:
7225:
7221:
7217:
7213:
7208:
7203:
7199:
7195:
7188:
7186:
7181:
7172:
7169:
7167:
7164:
7162:
7159:
7157:
7154:
7152:
7149:
7147:
7144:
7143:
7137:
7134:
7129:
7128:
7118:
7114:
7109:
7099:
7097:
7086:
7083:December 2009
7077:
7073:
7070:This section
7068:
7065:
7061:
7060:
7052:
7034:
7029:
7024:
6995:
6992:
6989:
6985:
6964:
6944:
6936:
6916:
6894:
6891:
6869:
6862:is closer to
6849:
6845:
6833:
6822:
6819:
6799:
6776:
6773:
6757:
6754:
6753:
6735:
6729:
6725:
6719:
6716:
6713:
6709:
6705:
6700:
6697:
6692:
6687:
6675:
6672:
6669:
6665:
6660:
6652:
6651:
6650:
6649:
6630:
6624:
6621:
6598:
6575:
6552:
6549:
6546:
6540:
6537:
6529:
6526:
6510:
6505:
6502:
6499:
6489:
6485:
6481:
6478:
6474:
6462:
6457:
6444:
6439:
6435:
6431:
6426:
6396:
6371:
6366:
6362:
6358:
6355:
6352:
6347:
6343:
6320:
6315:
6305:
6300:
6290:
6287:
6284:
6279:
6252:
6244:
6241:
6224:
6219:
6209:
6196:
6193:
6192:
6191:
6173:
6150:
6147:
6143:
6121:
6099:
6071:
6068:
6065:
6060:
6054:
6050:
6044:
6041:
6035:
6029:
6004:
5998:
5990:
5987:
5980:
5966:
5946:
5943:
5940:
5934:
5931:
5928:
5919:
5916:
5913:
5907:
5904:
5897:
5880:
5876:
5872:
5850:
5846:
5825:
5822:
5819:
5812:
5811:
5810:
5774:
5754:
5751:
5748:
5740:
5736:
5726:
5724:
5709:
5706:
5703:
5657:
5653:
5649:
5643:
5640:
5637:
5615:
5579:
5557:
5528:
5524:
5514:
5495:
5492:
5489:
5484:
5476:
5470:
5466:
5460:
5457:
5434:
5428:
5425:
5419:
5413:
5388:
5385:
5382:
5377:
5370:
5366:
5363:
5357:
5351:
5328:
5325:
5322:
5316:
5313:
5290:
5284:
5281:
5257:
5249:
5246:
5225:
5210:
5207:
5204:
5200:
5184:
5170:
5150:
5130:
5108:
5103:
5100:
5097:
5094:
5071:
5068:
5065:
5059:
5056:
5036:
5012:
5004:
5001:
4966:
4962:
4955:
4947:
4943:
4937:
4934:
4928:
4924:
4921:
4912:
4898:
4895:
4889:
4883:
4856:
4852:
4845:
4841:
4834:
4828:
4823:
4817:
4813:
4810:
4785:
4779:
4774:
4769:
4765:
4742:
4739:
4736:
4732:
4708:
4702:
4699:
4696:
4689:and a number
4676:
4656:
4634:
4630:
4626:
4623:
4615:
4610:
4593:
4585:
4581:
4560:
4557:
4554:
4534:
4531:
4528:
4508:
4488:
4468:
4446:
4443:
4440:
4436:
4411:
4403:
4399:
4390:
4379:
4376:
4372:
4368:
4362:
4354:
4350:
4329:
4307:
4303:
4282:
4279:
4257:
4253:
4244:
4240:
4236:
4232:
4211:
4188:
4180:
4176:
4168:
4152:
4144:
4129:
4127:
4123:
4094:
4049:
4041:
3992:
3987:
3909:
3905:
3890:
3885:
3872:
3867:
3857:
3852:
3817:
3812:
3761:
3756:
3705:
3702:
3693:
3670:
3667:
3663:
3653:
3624:
3614:
3609:
3563:
3561:
3534:
3506:
3503:
3499:
3489:
3465:
3459:
3456:
3452:
3448:
3445:
3435:
3430:
3414:
3374:
3369:
3359:
3343:
3327:
3324:
3316:
3307:
3283:
3279:
3264:
3259:
3246:
3241:
3231:
3226:
3191:
3188:
3179:
3150:
3140:
3135:
3102:
3082:
3074:
3070:
3066:
3056:
3040:
3025:
3007:
3003:
2997:
2993:
2971:
2942:
2938:
2915:
2911:
2907:
2902:
2898:
2892:
2888:
2884:
2881:
2861:
2841:
2832:
2812:
2791:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2738:
2733:
2704:
2675:
2646:
2617:
2601:
2587:
2567:
2547:
2527:
2505:
2502:
2493:
2472:
2465:If the guess
2463:
2443:
2439:
2432:
2429:
2423:
2418:
2408:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2378:
2373:
2335:
2330:
2325:
2315:
2304:
2294:
2289:
2254:
2244:
2241:
2219:
2209:
2206:
2184:
2141:
2127:
2102:
2092:
2081:
2076:
2043:
1996:
1991:
1986:
1976:
1965:
1955:
1950:
1922:
1908:
1888:
1880:
1876:
1855:
1850:
1845:
1830:
1826:
1822:
1818:
1808:
1791:
1783:
1780:
1745:
1741:
1696:
1667:
1659:
1655:
1646:
1635:
1632:
1628:
1624:
1618:
1610:
1606:
1585:
1581:
1574:
1566:
1562:
1558:
1552:
1544:
1540:
1516:
1513:
1506:
1500:
1496:
1487:
1469:
1465:
1444:
1441:
1438:
1429:
1413:
1410:
1401:
1378:
1373:
1363:
1336:
1333:
1330:
1310:
1287:
1284:
1268:
1226:
1218:
1215:
1211:
1207:
1185:
1175:
1172:
1142:
1115:
1107:
1089:
1084:
1054:
1050:
1044:
1040:
1034:
1029:
1026:
1023:
1019:
1015:
1004:
975:
972:
969:
965:
953:
942:
939:
931:
916:
891:
888:
880:
863:
858:
829:
824:
814:
801:
800:
799:
780:
775:
770:
741:
738:
729:
686:
664:
659:
649:
636:
614:
605:
586:
584:
580:
576:
572:
568:
564:
560:
555:
541:
510:
507:
504:
482:
472:
469:
447:
442:
432:
404:
401:
371:
356:
351:
341:
338:
316:
301:
285:
263:
258:
231:
224:
206:
190:
171:
158:
155:
150:
146:
137:
121:
101:
93:
89:
85:
81:
77:
66:
63:
55:
45:
41:
35:
32:This article
30:
21:
20:
7675:
7496:. Retrieved
7492:
7483:
7474:
7464:
7455:
7445:
7431:cite journal
7422:
7412:
7398:
7384:
7339:
7333:
7246:
7242:
7232:
7197:
7193:
7130:
7124:
7115:
7111:
7102:Key exchange
7093:
7080:
7076:adding to it
7071:
6934:
6932:
6755:
6527:
6242:
6194:
6189:
5738:
5732:
5522:
5520:
5190:
5029:for integer
4913:
4613:
4611:
4166:
4142:
4140:
4125:
4121:
4095:
3832:, calculate
3564:
3559:
3344:
3072:
3068:
3062:
2833:
2831:coordinate.
2784:, where the
2602:
2464:
2147:
2056:, calculate
1928:
1878:
1874:
1828:
1824:
1820:
1816:
1814:
1457:, denote by
1430:
1308:
1306:
721:. Denote by
592:
585:by Peikert.
556:
191:
83:
79:
76:cryptography
73:
58:
52:October 2018
49:
33:
7563:RSA problem
7249:(6): 1–35.
7200:(6): 1–40.
6195:Private key
3026:to recover
2930:, for each
1351:is to find
563:Gödel Prize
7727:Categories
7568:Strong RSA
7558:Phi-hiding
7498:2017-02-08
7207:2401.03703
7177:References
6929:otherwise.
6756:Decryption
6528:Encryption
6243:Public key
5087:such that
4224:such that
3562:was easy.
3389:such that
2804:is in the
2036:, for all
1684:, and let
1431:For every
593:Denote by
589:Definition
577:to create
559:Oded Regev
7344:CiteSeerX
7263:0004-5411
7224:207156623
7035:×
6996:χ
6842:⟩
6826:⟨
6823:−
6717:∈
6710:∑
6673:∈
6666:∑
6625:
6541:∈
6471:⟩
6448:⟨
6397:χ
6372:∈
6356:…
6306:∈
6288:…
6245:: Choose
6210:∈
6151:π
6144:β
6100:β
6096:Ψ
6069:
6042:∈
6030:α
5999:α
5995:Ψ
5988:χ
5967:ε
5944:
5920:ε
5823:≥
5775:χ
5710:γ
5704:ζ
5658:α
5580:γ
5558:γ
5493:
5485:ω
5467:ζ
5461:≥
5429:γ
5426:≥
5414:ζ
5386:
5378:α
5364:≥
5352:γ
5317:∈
5314:α
5285:
5258:α
5254:Ψ
5211:γ
5205:ζ
5095:α
5060:∈
5057:α
5013:α
5009:Ψ
4967:α
4948:ε
4944:η
4896:≥
4884:γ
4857:∗
4846:λ
4829:γ
4780:γ
4703:ϕ
4700:≥
4635:ϕ
4582:ρ
4558:∈
4521:and real
4481:of width
4404:α
4380:π
4377:−
4355:α
4351:ρ
4308:∗
4283:ε
4280:≤
4263:∖
4258:∗
4233:ρ
4181:ε
4177:η
4050:∈
3949:. Since
3899:⟩
3876:⟨
3706:χ
3671:χ
3539:←
3507:χ
3460:
3360:⊂
3328:χ
3273:⟩
3250:⟨
3192:χ
3103:χ
3008:ℓ
2943:ℓ
2908:⋯
2763:…
2751:…
2506:χ
2397:…
2336:×
2316:⊂
2245:∈
2210:∈
2128:χ
2093:−
2090:⟩
2067:⟨
1997:×
1977:⊂
1856:×
1827:version (
1792:α
1788:Ψ
1746:α
1697:α
1693:Ψ
1660:α
1636:π
1633:−
1611:α
1607:ρ
1586:α
1567:α
1563:ρ
1545:α
1517:π
1497:α
1470:α
1439:α
1414:ϕ
1364:∈
1337:ϕ
1227:∈
1176:∈
1148:⟶
1020:∑
1013:⟩
997:⟨
962:⟩
946:⟨
932:Evaluate
917:ϕ
892:∈
815:∈
781:×
742:ϕ
687:ϕ
650:∈
473:∈
433:∈
362:→
7649:Lattices
7623:Pairings
7140:See also
6882:than to
6265:vectors
6087:, where
3720:, where
3664:′
3535:′
3500:′
1875:decision
1825:decision
1486:Gaussian
1165:mapping
988:, where
420:, where
244:and let
7376:8123895
7271:1606347
3521:, with
3067:of the
637:. Let
300:vectors
38:Please
7374:
7364:
7346:
7269:
7261:
7222:
6909:, and
5274:using
5201:GapSVP
4766:GapSVP
4295:where
4165:, let
4141:For a
4069:, and
1879:search
1821:search
1598:where
223:modulo
7372:S2CID
7267:S2CID
7220:S2CID
7202:arXiv
7171:Kyber
5630:with
5572:(for
3171:from
302:over
7437:link
7362:ISBN
7259:ISSN
6957:and
6022:for
5865:and
5521:The
5450:and
5282:poly
5101:>
5049:and
4612:The
4532:>
4342:and
4126:DLWE
4124:and
3560:DLWE
3457:poly
3095:and
3073:DLWE
3071:and
1877:and
1829:DLWE
1815:The
1442:>
1307:The
633:the
462:and
136:ring
7670:gap
7660:gap
7354:doi
7251:doi
7212:doi
7078:.
6935:LWE
6812:if
6792:is
6622:Enc
6588:of
6066:log
5941:log
5787:on
5739:LWE
5523:LWE
5490:log
5383:log
4803:to
4770:100
4122:LWE
3069:LWE
2998:mod
1817:LWE
1200:to
84:LWE
74:In
42:to
7729::
7491:.
7473:.
7454:.
7433:}}
7429:{{
7421:.
7370:.
7360:.
7352:.
7308:^
7279:^
7265:.
7257:.
7247:60
7245:.
7241:.
7218:.
7210:.
7198:56
7196:.
7184:^
7098:.
6646:as
5513:.
5406:,
5344:,
5183:.
4911:.
4609:.
3558:,
3342:.
3055:.
2817:th
1921:.
1428:.
78:,
7672:)
7668:(
7662:)
7658:(
7531:e
7524:t
7517:v
7501:.
7477:.
7458:.
7439:)
7425:.
7407:.
7393:.
7378:.
7356::
7328:.
7303:.
7273:.
7253::
7226:.
7214::
7204::
7085:)
7081:(
7039:T
7030:n
7025:q
7020:Z
6993:,
6990:s
6986:A
6965:1
6945:0
6917:1
6895:2
6892:1
6870:0
6850:q
6846:/
6838:s
6834:,
6830:a
6820:b
6800:0
6780:)
6777:b
6774:,
6770:a
6766:(
6736:)
6730:i
6726:b
6720:S
6714:i
6706:+
6701:2
6698:x
6693:,
6688:i
6683:a
6676:S
6670:i
6661:(
6634:)
6631:x
6628:(
6602:]
6599:m
6596:[
6576:S
6556:}
6553:1
6550:,
6547:0
6544:{
6538:x
6511:m
6506:1
6503:=
6500:i
6496:)
6490:i
6486:e
6482:+
6479:q
6475:/
6467:s
6463:,
6458:i
6453:a
6445:=
6440:i
6436:b
6432:,
6427:i
6422:a
6417:(
6376:T
6367:m
6363:e
6359:,
6353:,
6348:1
6344:e
6321:n
6316:q
6311:Z
6301:m
6296:a
6291:,
6285:,
6280:1
6275:a
6253:m
6225:n
6220:q
6215:Z
6206:s
6186:.
6174:1
6148:2
6122:0
6075:)
6072:n
6061:n
6055:/
6051:1
6048:(
6045:o
6039:)
6036:n
6033:(
6008:)
6005:n
6002:(
5991:=
5947:q
5938:)
5935:1
5932:+
5929:n
5926:(
5923:)
5917:+
5914:1
5911:(
5908:=
5905:m
5895:.
5881:2
5877:n
5873:2
5851:2
5847:n
5826:2
5820:q
5796:T
5755:q
5752:,
5749:m
5707:,
5699:P
5696:V
5693:S
5690:p
5687:a
5684:G
5661:)
5654:/
5650:n
5647:(
5644:O
5641:=
5638:t
5616:t
5611:P
5608:V
5605:I
5602:S
5553:P
5550:V
5547:S
5544:p
5541:a
5538:G
5501:)
5496:n
5482:)
5477:n
5471:/
5464:(
5458:q
5438:)
5435:n
5432:(
5423:)
5420:n
5417:(
5394:)
5389:n
5375:(
5371:/
5367:n
5361:)
5358:n
5355:(
5332:)
5329:1
5326:,
5323:0
5320:(
5294:)
5291:n
5288:(
5250:,
5247:q
5242:E
5239:W
5236:L
5208:,
5171:n
5151:q
5131:q
5109:n
5104:2
5098:q
5075:)
5072:1
5069:,
5066:0
5063:(
5037:q
5005:,
5002:q
4997:E
4994:W
4991:L
4963:/
4959:)
4956:L
4953:(
4938:n
4935:2
4929:S
4925:G
4922:D
4899:1
4893:)
4890:n
4887:(
4862:)
4853:L
4849:(
4842:/
4838:)
4835:n
4832:(
4824:n
4818:S
4814:G
4811:D
4789:)
4786:n
4783:(
4775:n
4743:r
4740:,
4737:L
4733:D
4712:)
4709:L
4706:(
4697:r
4677:L
4657:n
4631:S
4627:G
4624:D
4597:)
4594:x
4591:(
4586:r
4561:L
4555:x
4535:0
4529:r
4509:L
4489:r
4469:L
4447:r
4444:,
4441:L
4437:D
4412:2
4408:)
4400:/
4395:|
4391:x
4387:|
4383:(
4373:e
4369:=
4366:)
4363:x
4360:(
4330:L
4304:L
4277:)
4274:}
4270:0
4266:{
4254:L
4250:(
4245:s
4241:/
4237:1
4212:s
4192:)
4189:L
4186:(
4153:L
4143:n
4106:S
4079:A
4055:S
4046:t
4042:+
4038:s
4016:t
3993:n
3988:q
3983:Z
3959:S
3935:A
3913:}
3910:q
3906:/
3902:)
3895:t
3891:,
3886:i
3881:a
3873:+
3868:i
3863:b
3858:,
3853:i
3848:a
3843:(
3840:{
3818:n
3813:q
3808:Z
3785:t
3762:n
3757:q
3752:Z
3729:s
3703:,
3699:s
3694:A
3668:,
3660:s
3654:A
3633:}
3630:)
3625:i
3620:b
3615:,
3610:i
3605:a
3600:(
3597:{
3575:A
3544:S
3531:s
3504:,
3496:s
3490:A
3469:)
3466:n
3463:(
3453:/
3449:1
3446:=
3442:|
3436:n
3431:q
3426:Z
3420:|
3415:/
3410:|
3404:S
3398:|
3375:n
3370:q
3365:Z
3355:S
3325:,
3321:t
3317:+
3313:s
3308:A
3287:}
3284:q
3280:/
3276:)
3269:t
3265:,
3260:i
3255:a
3247:+
3242:i
3237:b
3232:,
3227:i
3222:a
3217:(
3214:{
3189:,
3185:s
3180:A
3159:}
3156:)
3151:i
3146:b
3141:,
3136:i
3131:a
3126:(
3123:{
3083:q
3041:j
3036:s
3004:q
2994:0
2972:j
2967:s
2939:q
2916:t
2912:q
2903:2
2899:q
2893:1
2889:q
2885:=
2882:q
2862:n
2842:q
2813:j
2792:r
2772:)
2769:0
2766:,
2760:,
2757:r
2754:,
2748:,
2745:0
2742:(
2739:+
2734:i
2729:a
2705:i
2700:a
2676:i
2671:b
2647:j
2642:s
2618:1
2613:s
2588:k
2568:n
2548:q
2528:q
2503:,
2499:s
2494:A
2473:k
2450:}
2447:)
2444:q
2440:/
2436:)
2433:k
2430:r
2427:(
2424:+
2419:i
2414:b
2409:,
2406:)
2403:0
2400:,
2394:,
2391:0
2388:,
2385:r
2382:(
2379:+
2374:i
2369:a
2364:(
2361:{
2340:T
2331:n
2326:q
2321:Z
2313:}
2310:)
2305:i
2300:b
2295:,
2290:i
2285:a
2280:(
2277:{
2255:q
2250:Z
2242:r
2220:q
2215:Z
2207:k
2185:1
2180:s
2157:s
2108:}
2103:i
2098:b
2086:s
2082:,
2077:i
2072:a
2064:{
2044:i
2023:s
2001:T
1992:n
1987:q
1982:Z
1974:}
1971:)
1966:i
1961:b
1956:,
1951:i
1946:a
1941:(
1938:{
1909:n
1889:q
1860:T
1851:n
1846:q
1841:Z
1784:,
1781:q
1776:E
1773:W
1770:L
1742:D
1720:T
1668:2
1664:)
1656:/
1651:|
1647:x
1643:|
1639:(
1629:e
1625:=
1622:)
1619:x
1616:(
1582:/
1578:)
1575:x
1572:(
1559:=
1556:)
1553:x
1550:(
1541:D
1520:)
1514:2
1511:(
1507:/
1501:2
1466:D
1445:0
1411:,
1407:s
1402:A
1379:n
1374:q
1369:Z
1360:s
1334:,
1331:q
1326:E
1323:W
1320:L
1303:.
1291:)
1288:t
1285:,
1281:a
1277:(
1266:.
1253:T
1231:T
1223:Z
1219:+
1216:q
1212:/
1208:1
1186:q
1181:Z
1173:1
1152:T
1143:q
1138:Z
1116:q
1090:n
1085:q
1080:Z
1055:i
1051:s
1045:i
1041:a
1035:n
1030:1
1027:=
1024:i
1016:=
1009:s
1005:,
1001:a
976:e
973:+
970:q
966:/
958:s
954:,
950:a
943:=
940:t
929:,
896:T
889:e
878:,
864:n
859:q
854:Z
830:n
825:q
820:Z
811:a
785:T
776:n
771:q
766:Z
739:,
735:s
730:A
708:T
665:n
660:q
655:Z
646:s
620:Z
615:/
610:R
606:=
602:T
542:f
522:)
518:x
514:(
511:f
508:=
505:y
483:q
478:Z
470:y
448:n
443:q
438:Z
429:x
408:)
405:y
402:,
398:x
394:(
372:q
367:Z
357:n
352:q
347:Z
342::
339:f
317:q
312:Z
298:-
286:n
264:n
259:q
254:Z
232:q
207:q
202:Z
177:)
172:i
167:x
162:(
159:f
156:=
151:i
147:y
122:f
102:n
82:(
65:)
59:(
54:)
50:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
