129:
32:
235:" solution would be to try dividing 6895601 by many prime numbers until finding the answer. However, if one is told that 1931 is one of the numbers, one can find the answer by entering "6895601 Ă· 1931" into any calculator. This example is not a sturdy trapdoor function â modern computers can guess all of the possible answers within a second â but this sample problem could be improved by
308:(these are frequently used interchangeably, which is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.
1715:
266:
coined the term. Several function classes had been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the
1524:
223:
and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key
1314:
1883:
1821:
1147:
1519:
1403:
1030:
1967:
1925:
936:
842:
761:
1065:
1204:
874:
2007:
1987:
1759:
1739:
1423:
1354:
1334:
1244:
1224:
1175:
976:
956:
785:
732:
712:
301:
known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logarithms.
2598:
2308:
1710:{\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}
2726:
2721:
2450:
2629:
2623:
231:
An example of a simple mathematical trapdoor is "6895601 is the product of two prime numbers. What are those numbers?" A typical "
2160:
96:
1249:
68:
2747:
2301:
2063:
282:
families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of
1826:
1764:
75:
1070:
2365:
49:
2808:
2433:
2390:
115:
2355:
2345:
2294:
82:
2803:
2509:
2423:
2370:
682:
In the following two examples, we always assume that it is difficult to factorize a large composite number (see
2534:
1432:
53:
1359:
64:
2418:
981:
2675:
2608:
165:
1930:
1888:
180:
that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its
2772:
2665:
2514:
2428:
2350:
2046:
Bellare, M (June 1998). "Many-to-one trapdoor functions and their relation to public-key cryptosystems".
879:
764:
304:
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a
294:
670:
If each function in the collection above is a one-way permutation, then the collection is also called a
19:
This article is about the mathematical cryptography function. For the method of bypassing security, see
2524:
2413:
2395:
2231:
793:
290:
2777:
2757:
1718:
2660:
2716:
2487:
2174:
247:
2670:
2317:
189:
42:
2191:
2752:
2603:
2542:
2477:
2251:
2169:
184:) without special information, called the "trapdoor". Trapdoor functions are a special case of
177:
89:
737:
2618:
2375:
2332:
683:
236:
2268:
1035:
2529:
2340:
305:
20:
2152:
1180:
850:
8:
2635:
283:
2482:
2405:
2385:
2380:
2360:
2069:
1992:
1972:
1744:
1724:
1408:
1339:
1319:
1229:
1209:
1160:
961:
941:
770:
717:
697:
279:
268:
232:
2742:
2613:
2499:
2073:
2059:
2588:
2179:
2144:
2051:
2018:
321:
251:
185:
181:
275:
149:
2211:
2148:
255:
2797:
2183:
2782:
2762:
381:
are subsets of binary strings {0, 1}, satisfying the following conditions:
259:
243:
169:
2286:
2680:
2557:
274:
As of 2004, the best known trapdoor function (family) candidates are the
2706:
2438:
2055:
2050:. Lecture Notes in Computer Science. Vol. 1462. pp. 283â298.
128:
2460:
1316:, and kept confidential to the adversary. The problem is to compute
31:
2767:
2701:
2572:
2567:
2562:
2465:
2443:
199:
is a trapdoor function, then there exists some secret information
2593:
2552:
2122:
Goldwasser's lecture notes, 2.3.2; Lindell's notes, p. 17, Ex. 1.
220:
2711:
2547:
2504:
2472:
2455:
614:, for any PPT algorithm, the probability to correctly invert
228:
is the trapdoor and the padlock is the trapdoor function.
2640:
2494:
1309:{\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}
1152:
497:, there exists a PPT algorithm that correctly computes
2253:
1995:
1975:
1933:
1891:
1878:{\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}
1829:
1816:{\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}
1767:
1747:
1727:
1527:
1435:
1411:
1362:
1342:
1322:
1252:
1232:
1212:
1183:
1163:
1073:
1038:
984:
964:
944:
882:
853:
796:
773:
740:
720:
700:
293:(either modulo a prime or in a group defined over an
148:
can be efficiently computed, i.e., in probabilistic
385:There exists a probabilistic polynomial time (PPT)
271:. This turned out rather quickly to be unsuitable.
132:The idea of trapdoor function. A trapdoor function
56:. Unsourced material may be challenged and removed.
2001:
1981:
1961:
1919:
1877:
1815:
1753:
1733:
1709:
1513:
1417:
1397:
1348:
1328:
1308:
1238:
1218:
1198:
1169:
1142:{\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}
1141:
1059:
1024:
970:
950:
930:
868:
836:
779:
755:
726:
706:
2113:Pass's notes, def 56.1; Dodis's def 7, lecture 1.
594:). That is, given trapdoor, it is easy to invert.
464:, there also exists a PPT algorithm that outputs
2795:
1149:. Its hardness follows from the RSA assumption.
2302:
2143:
263:
152:. However, the computation of the inverse of
2316:
457:. Each trapdoor can be efficiently sampled.
237:using the product of two much larger primes
2309:
2295:
2173:
1721:for more details. Note that given primes
1514:{\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}
1135:
1134:
1120:
1119:
1095:
1094:
1009:
1008:
827:
826:
289:Functions related to the hardness of the
246:in the mid-1970s with the publication of
242:Trapdoor functions came to prominence in
116:Learn how and when to remove this message
1398:{\displaystyle a\equiv z^{2}{\pmod {n}}}
127:
2161:IEEE Transactions on Information Theory
2045:
1405:. The trapdoor is the factorization of
1025:{\displaystyle d=e^{-1}\mod {\phi (n)}}
938:can be computed. With this the inverse
156:is generally hard, unless the trapdoor
2796:
2209:
1425:. With the trapdoor, the solutions of
1177:be a large composite number such that
2290:
2229:
2095:Goldwasser's lecture notes, def. 2.16
248:asymmetric (or public-key) encryption
2630:NaccacheâStern knapsack cryptosystem
1962:{\displaystyle q\equiv 3{\pmod {4}}}
1920:{\displaystyle p\equiv 3{\pmod {4}}}
1153:Rabin's quadratic residue assumption
54:adding citations to reliable sources
25:
2266:
2048:Advances in Cryptology â CRYPTO '98
1951:
1909:
1867:
1805:
1699:
1671:
1643:
1615:
1587:
1552:
1387:
1298:
1270:
931:{\displaystyle \phi (n)=(p-1)(q-1)}
13:
2131:Goldwasser's lecture notes, 2.3.4.
14:
2820:
2249:
837:{\displaystyle f(x)=x^{e}\mod n.}
689:
140:can be generated by an algorithm
2189:
2153:"New directions in cryptography"
30:
2661:Discrete logarithm cryptography
1944:
1902:
1860:
1798:
1692:
1664:
1636:
1608:
1580:
1545:
1380:
1291:
1263:
1130:
1115:
1090:
1004:
822:
517:, there exists a PPT algorithm
41:needs additional citations for
2125:
2116:
2107:
2098:
2089:
2080:
2039:
2030:
1955:
1945:
1913:
1903:
1871:
1861:
1809:
1799:
1703:
1693:
1675:
1665:
1647:
1637:
1619:
1609:
1591:
1581:
1556:
1546:
1391:
1381:
1302:
1292:
1274:
1264:
1054:
1048:
1019:
1013:
925:
913:
910:
898:
892:
886:
806:
800:
750:
744:
1:
2213:Lecture Notes on Cryptography
2137:
1969:guarantee that the solutions
694:In this example, the inverse
389:algorithm Gen s.t. Gen(1) = (
311:
2676:Non-commutative cryptography
2104:Ostrovsky, pp. 6â10, def. 11
166:theoretical computer science
7:
2773:Identity-based cryptography
2666:Elliptic-curve cryptography
2270:Foundations of Cryptography
2233:Foundations of Cryptography
2012:
1246:are large primes such that
677:
486:can be efficiently sampled.
264:Diffie & Hellman (1976)
10:
2825:
291:discrete logarithm problem
195:In mathematical terms, if
18:
16:One-way cryptographic tool
2778:Post-quantum cryptography
2735:
2727:Post-Quantum Cryptography
2694:
2653:
2581:
2523:
2404:
2331:
2324:
1719:Chinese remainder theorem
440:is some polynomial. Each
2809:Cryptographic primitives
2193:A Course in Cryptography
2184:10.1109/TIT.1976.1055638
2024:
847:If the factorization of
765:Euler's totient function
756:{\displaystyle \phi (n)}
215:, it is easy to compute
2671:Hash-based cryptography
2318:Public-key cryptography
2086:Pass's Notes, def. 56.1
190:public-key cryptography
188:and are widely used in
2804:Theory of cryptography
2003:
1983:
1963:
1921:
1885:. Here the conditions
1879:
1817:
1755:
1735:
1711:
1515:
1419:
1399:
1350:
1330:
1310:
1240:
1220:
1200:
1171:
1143:
1061:
1060:{\displaystyle y=f(x)}
1026:
972:
952:
932:
870:
838:
781:
757:
728:
708:
161:
2333:Integer factorization
2009:can be well defined.
2004:
1984:
1964:
1922:
1880:
1818:
1756:
1736:
1712:
1516:
1420:
1400:
1351:
1331:
1311:
1241:
1221:
1201:
1172:
1144:
1062:
1027:
973:
953:
933:
871:
839:
782:
758:
729:
709:
684:Integer factorization
419:â {0, 1} satisfies |
131:
1993:
1973:
1931:
1889:
1827:
1765:
1745:
1725:
1525:
1433:
1409:
1360:
1340:
1320:
1250:
1230:
1210:
1199:{\displaystyle n=pq}
1181:
1161:
1071:
1036:
982:
962:
942:
880:
869:{\displaystyle n=pq}
851:
794:
771:
738:
718:
698:
672:trapdoor permutation
636:), find a pre-image
568:), and then we have
50:improve this article
21:Backdoor (computing)
2636:Three-pass protocol
2230:Ostrovsky, Rafail,
2210:Goldwasser, Shafi,
787:) is the trapdoor:
605:, without trapdoor
359:), in which all of
320:is a collection of
284:prime factorization
65:"Trapdoor function"
2406:Discrete logarithm
2056:10.1007/bfb0055735
2036:Ostrovsky, pp. 6â9
1999:
1979:
1959:
1917:
1875:
1813:
1751:
1731:
1707:
1511:
1415:
1395:
1346:
1326:
1306:
1236:
1216:
1196:
1167:
1139:
1057:
1022:
968:
948:
928:
866:
834:
777:
753:
724:
704:
269:subset sum problem
203:, such that given
162:
136:with its trapdoor
2791:
2790:
2743:Digital signature
2686:Trapdoor function
2649:
2648:
2366:GoldwasserâMicali
2267:Lindell, Yehuda,
2250:Dodis, Yevgeniy,
2065:978-3-540-64892-5
2002:{\displaystyle y}
1982:{\displaystyle x}
1856:
1794:
1754:{\displaystyle q}
1734:{\displaystyle p}
1418:{\displaystyle n}
1349:{\displaystyle a}
1329:{\displaystyle z}
1239:{\displaystyle q}
1219:{\displaystyle p}
1170:{\displaystyle n}
1032:, and then given
971:{\displaystyle e}
951:{\displaystyle d}
780:{\displaystyle n}
727:{\displaystyle e}
707:{\displaystyle d}
666:)) is negligible.
453:corresponding to
322:one-way functions
318:trapdoor function
186:one-way functions
174:trapdoor function
126:
125:
118:
100:
2816:
2632:
2533:
2528:
2488:signature scheme
2391:OkamotoâUchiyama
2329:
2328:
2311:
2304:
2297:
2288:
2287:
2283:
2282:
2280:
2275:
2263:
2262:
2260:
2246:
2245:
2243:
2238:
2226:
2225:
2223:
2218:
2206:
2205:
2203:
2198:
2186:
2177:
2157:
2132:
2129:
2123:
2120:
2114:
2111:
2105:
2102:
2096:
2093:
2087:
2084:
2078:
2077:
2043:
2037:
2034:
2019:One-way function
2008:
2006:
2005:
2000:
1988:
1986:
1985:
1980:
1968:
1966:
1965:
1960:
1958:
1926:
1924:
1923:
1918:
1916:
1884:
1882:
1881:
1876:
1874:
1858:
1857:
1852:
1841:
1822:
1820:
1819:
1814:
1812:
1796:
1795:
1790:
1779:
1760:
1758:
1757:
1752:
1740:
1738:
1737:
1732:
1716:
1714:
1713:
1708:
1706:
1678:
1650:
1622:
1594:
1578:
1577:
1559:
1543:
1542:
1520:
1518:
1517:
1512:
1429:can be given as
1424:
1422:
1421:
1416:
1404:
1402:
1401:
1396:
1394:
1378:
1377:
1355:
1353:
1352:
1347:
1335:
1333:
1332:
1327:
1315:
1313:
1312:
1307:
1305:
1277:
1245:
1243:
1242:
1237:
1225:
1223:
1222:
1217:
1205:
1203:
1202:
1197:
1176:
1174:
1173:
1168:
1148:
1146:
1145:
1140:
1114:
1113:
1089:
1088:
1066:
1064:
1063:
1058:
1031:
1029:
1028:
1023:
1003:
1002:
978:can be computed
977:
975:
974:
969:
957:
955:
954:
949:
937:
935:
934:
929:
875:
873:
872:
867:
843:
841:
840:
835:
821:
820:
786:
784:
783:
778:
762:
760:
759:
754:
733:
731:
730:
725:
713:
711:
710:
705:
477:. That is, each
121:
114:
110:
107:
101:
99:
58:
34:
26:
2824:
2823:
2819:
2818:
2817:
2815:
2814:
2813:
2794:
2793:
2792:
2787:
2731:
2695:Standardization
2690:
2645:
2628:
2577:
2525:Lattice/SVP/CVP
2519:
2400:
2346:BlumâGoldwasser
2320:
2315:
2278:
2276:
2273:
2258:
2256:
2241:
2239:
2236:
2221:
2219:
2216:
2201:
2199:
2196:
2155:
2140:
2135:
2130:
2126:
2121:
2117:
2112:
2108:
2103:
2099:
2094:
2090:
2085:
2081:
2066:
2044:
2040:
2035:
2031:
2027:
2015:
1994:
1991:
1990:
1974:
1971:
1970:
1943:
1932:
1929:
1928:
1901:
1890:
1887:
1886:
1859:
1842:
1840:
1836:
1828:
1825:
1824:
1797:
1780:
1778:
1774:
1766:
1763:
1762:
1746:
1743:
1742:
1726:
1723:
1722:
1691:
1663:
1635:
1607:
1579:
1573:
1569:
1544:
1538:
1534:
1526:
1523:
1522:
1434:
1431:
1430:
1410:
1407:
1406:
1379:
1373:
1369:
1361:
1358:
1357:
1341:
1338:
1337:
1321:
1318:
1317:
1290:
1262:
1251:
1248:
1247:
1231:
1228:
1227:
1211:
1208:
1207:
1182:
1179:
1178:
1162:
1159:
1158:
1155:
1106:
1102:
1084:
1080:
1072:
1069:
1068:
1037:
1034:
1033:
995:
991:
983:
980:
979:
963:
960:
959:
943:
940:
939:
881:
878:
877:
876:is known, then
852:
849:
848:
816:
812:
795:
792:
791:
772:
769:
768:
739:
736:
735:
719:
716:
715:
699:
696:
695:
692:
680:
661:
648:
631:
622:
613:
589:
576:
567:
554:
533:
505:
485:
476:
448:
427:
418:
401:
380:
371:
350:
341:
332:
314:
150:polynomial time
122:
111:
105:
102:
59:
57:
47:
35:
24:
17:
12:
11:
5:
2822:
2812:
2811:
2806:
2789:
2788:
2786:
2785:
2780:
2775:
2770:
2765:
2760:
2755:
2750:
2745:
2739:
2737:
2733:
2732:
2730:
2729:
2724:
2719:
2714:
2709:
2704:
2698:
2696:
2692:
2691:
2689:
2688:
2683:
2678:
2673:
2668:
2663:
2657:
2655:
2651:
2650:
2647:
2646:
2644:
2643:
2638:
2633:
2626:
2624:MerkleâHellman
2621:
2616:
2611:
2606:
2601:
2596:
2591:
2585:
2583:
2579:
2578:
2576:
2575:
2570:
2565:
2560:
2555:
2550:
2545:
2539:
2537:
2521:
2520:
2518:
2517:
2512:
2507:
2502:
2497:
2492:
2491:
2490:
2480:
2475:
2470:
2469:
2468:
2463:
2453:
2448:
2447:
2446:
2441:
2431:
2426:
2421:
2416:
2410:
2408:
2402:
2401:
2399:
2398:
2393:
2388:
2383:
2378:
2373:
2371:NaccacheâStern
2368:
2363:
2358:
2353:
2348:
2343:
2337:
2335:
2326:
2322:
2321:
2314:
2313:
2306:
2299:
2291:
2285:
2284:
2264:
2247:
2227:
2207:
2190:Pass, Rafael,
2187:
2175:10.1.1.37.9720
2168:(6): 644â654,
2139:
2136:
2134:
2133:
2124:
2115:
2106:
2097:
2088:
2079:
2064:
2038:
2028:
2026:
2023:
2022:
2021:
2014:
2011:
1998:
1978:
1957:
1954:
1950:
1947:
1942:
1939:
1936:
1915:
1912:
1908:
1905:
1900:
1897:
1894:
1873:
1870:
1866:
1863:
1855:
1851:
1848:
1845:
1839:
1835:
1832:
1811:
1808:
1804:
1801:
1793:
1789:
1786:
1783:
1777:
1773:
1770:
1761:, we can find
1750:
1730:
1705:
1702:
1698:
1695:
1690:
1687:
1684:
1681:
1677:
1674:
1670:
1667:
1662:
1659:
1656:
1653:
1649:
1646:
1642:
1639:
1634:
1631:
1628:
1625:
1621:
1618:
1614:
1611:
1606:
1603:
1600:
1597:
1593:
1590:
1586:
1583:
1576:
1572:
1568:
1565:
1562:
1558:
1555:
1551:
1548:
1541:
1537:
1533:
1530:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1414:
1393:
1390:
1386:
1383:
1376:
1372:
1368:
1365:
1345:
1325:
1304:
1301:
1297:
1294:
1289:
1286:
1283:
1280:
1276:
1273:
1269:
1266:
1261:
1258:
1255:
1235:
1215:
1195:
1192:
1189:
1186:
1166:
1154:
1151:
1138:
1133:
1129:
1126:
1123:
1118:
1112:
1109:
1105:
1101:
1098:
1093:
1087:
1083:
1079:
1076:
1067:, we can find
1056:
1053:
1050:
1047:
1044:
1041:
1021:
1018:
1015:
1012:
1007:
1001:
998:
994:
990:
987:
967:
947:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
865:
862:
859:
856:
845:
844:
833:
830:
825:
819:
815:
811:
808:
805:
802:
799:
776:
752:
749:
746:
743:
723:
703:
691:
690:RSA assumption
688:
679:
676:
668:
667:
657:
644:
627:
618:
609:
595:
585:
572:
563:
550:
529:
507:
501:
487:
481:
472:
458:
449:is called the
444:
423:
414:
397:
376:
367:
346:
337:
328:
313:
310:
295:elliptic curve
250:techniques by
124:
123:
38:
36:
29:
15:
9:
6:
4:
3:
2:
2821:
2810:
2807:
2805:
2802:
2801:
2799:
2784:
2781:
2779:
2776:
2774:
2771:
2769:
2766:
2764:
2761:
2759:
2756:
2754:
2751:
2749:
2746:
2744:
2741:
2740:
2738:
2734:
2728:
2725:
2723:
2720:
2718:
2715:
2713:
2710:
2708:
2705:
2703:
2700:
2699:
2697:
2693:
2687:
2684:
2682:
2679:
2677:
2674:
2672:
2669:
2667:
2664:
2662:
2659:
2658:
2656:
2652:
2642:
2639:
2637:
2634:
2631:
2627:
2625:
2622:
2620:
2617:
2615:
2612:
2610:
2607:
2605:
2602:
2600:
2597:
2595:
2592:
2590:
2587:
2586:
2584:
2580:
2574:
2571:
2569:
2566:
2564:
2561:
2559:
2556:
2554:
2551:
2549:
2546:
2544:
2541:
2540:
2538:
2536:
2531:
2526:
2522:
2516:
2513:
2511:
2508:
2506:
2503:
2501:
2498:
2496:
2493:
2489:
2486:
2485:
2484:
2481:
2479:
2476:
2474:
2471:
2467:
2464:
2462:
2459:
2458:
2457:
2454:
2452:
2449:
2445:
2442:
2440:
2437:
2436:
2435:
2432:
2430:
2427:
2425:
2422:
2420:
2417:
2415:
2412:
2411:
2409:
2407:
2403:
2397:
2396:SchmidtâSamoa
2394:
2392:
2389:
2387:
2384:
2382:
2379:
2377:
2374:
2372:
2369:
2367:
2364:
2362:
2359:
2357:
2356:DamgĂ„rdâJurik
2354:
2352:
2351:CayleyâPurser
2349:
2347:
2344:
2342:
2339:
2338:
2336:
2334:
2330:
2327:
2323:
2319:
2312:
2307:
2305:
2300:
2298:
2293:
2292:
2289:
2272:
2271:
2265:
2255:
2254:
2248:
2235:
2234:
2228:
2215:
2214:
2208:
2195:
2194:
2188:
2185:
2181:
2176:
2171:
2167:
2163:
2162:
2154:
2150:
2146:
2142:
2141:
2128:
2119:
2110:
2101:
2092:
2083:
2075:
2071:
2067:
2061:
2057:
2053:
2049:
2042:
2033:
2029:
2020:
2017:
2016:
2010:
1996:
1976:
1952:
1948:
1940:
1937:
1934:
1910:
1906:
1898:
1895:
1892:
1868:
1864:
1853:
1849:
1846:
1843:
1837:
1833:
1830:
1806:
1802:
1791:
1787:
1784:
1781:
1775:
1771:
1768:
1748:
1728:
1720:
1700:
1696:
1688:
1685:
1682:
1679:
1672:
1668:
1660:
1657:
1654:
1651:
1644:
1640:
1632:
1629:
1626:
1623:
1616:
1612:
1604:
1601:
1598:
1595:
1588:
1584:
1574:
1570:
1566:
1563:
1560:
1553:
1549:
1539:
1535:
1531:
1528:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1428:
1412:
1388:
1384:
1374:
1370:
1366:
1363:
1343:
1323:
1299:
1295:
1287:
1284:
1281:
1278:
1271:
1267:
1259:
1256:
1253:
1233:
1213:
1193:
1190:
1187:
1184:
1164:
1150:
1136:
1131:
1127:
1124:
1121:
1116:
1110:
1107:
1103:
1099:
1096:
1091:
1085:
1081:
1077:
1074:
1051:
1045:
1042:
1039:
1016:
1010:
1005:
999:
996:
992:
988:
985:
965:
945:
922:
919:
916:
907:
904:
901:
895:
889:
883:
863:
860:
857:
854:
831:
828:
823:
817:
813:
809:
803:
797:
790:
789:
788:
774:
766:
747:
741:
721:
701:
687:
685:
675:
673:
665:
660:
656:
652:
647:
643:
639:
635:
630:
626:
623:(i.e., given
621:
617:
612:
608:
604:
600:
596:
593:
588:
584:
580:
575:
571:
566:
562:
558:
553:
549:
545:
541:
537:
532:
528:
524:
521:s.t. for any
520:
516:
512:
508:
504:
500:
496:
492:
488:
484:
480:
475:
471:
467:
463:
459:
456:
452:
447:
443:
439:
435:
431:
426:
422:
417:
413:
410:â© {0, 1} and
409:
405:
400:
396:
392:
388:
384:
383:
382:
379:
375:
370:
366:
362:
358:
354:
349:
345:
340:
336:
331:
327:
323:
319:
309:
307:
302:
300:
296:
292:
287:
285:
281:
277:
272:
270:
265:
261:
257:
253:
249:
245:
240:
238:
234:
229:
227:
222:
219:. Consider a
218:
214:
210:
206:
202:
198:
193:
191:
187:
183:
179:
175:
171:
167:
159:
155:
151:
147:
143:
139:
135:
130:
120:
117:
109:
98:
95:
91:
88:
84:
81:
77:
74:
70:
67: â
66:
62:
61:Find sources:
55:
51:
45:
44:
39:This article
37:
33:
28:
27:
22:
2783:OpenPGP card
2763:Web of trust
2685:
2419:CramerâShoup
2277:, retrieved
2269:
2257:, retrieved
2252:
2240:, retrieved
2232:
2220:, retrieved
2212:
2200:, retrieved
2192:
2165:
2159:
2127:
2118:
2109:
2100:
2091:
2082:
2047:
2041:
2032:
1426:
1156:
846:
693:
681:
671:
669:
663:
658:
654:
650:
645:
641:
637:
633:
628:
624:
619:
615:
610:
606:
602:
598:
591:
586:
582:
578:
573:
569:
564:
560:
556:
551:
547:
543:
539:
535:
530:
526:
522:
518:
514:
510:
502:
498:
494:
490:
482:
478:
473:
469:
465:
461:
460:Given input
454:
450:
445:
441:
437:
436:), in which
433:
429:
424:
420:
415:
411:
407:
403:
398:
394:
390:
386:
377:
373:
368:
364:
360:
356:
352:
347:
343:
338:
334:
329:
325:
317:
315:
303:
298:
288:
273:
244:cryptography
241:
230:
225:
216:
212:
208:
204:
200:
196:
194:
173:
170:cryptography
163:
157:
153:
145:
141:
137:
133:
112:
103:
93:
86:
79:
72:
60:
48:Please help
43:verification
40:
2753:Fingerprint
2717:NSA Suite B
2681:RSA problem
2558:NTRUEncrypt
2279:17 December
2259:17 December
2242:27 November
2222:25 November
2202:27 November
2149:Hellman, M.
233:brute-force
2798:Categories
2707:IEEE P1363
2325:Algorithms
2145:Diffie, W.
2138:References
1356:such that
640:such that
312:Definition
262:. Indeed,
76:newspapers
2170:CiteSeerX
2074:215825522
1938:≡
1896:≡
1834:≡
1772:≡
1686:≡
1658:≡
1630:≡
1602:≡
1567:≡
1532:≡
1503:−
1494:−
1473:−
1461:−
1367:≡
1285:≡
1257:≡
1011:ϕ
997:−
920:−
905:−
884:ϕ
742:ϕ
160:is given.
106:July 2013
2768:Key size
2702:CRYPTREC
2619:McEliece
2573:RLWE-SIG
2568:RLWE-KEX
2563:NTRUSign
2376:Paillier
2151:(1976),
2013:See also
1521:, where
1206:, where
678:Examples
597:For any
509:For any
489:For any
451:trapdoor
387:sampling
333: :
306:backdoor
178:function
2614:Lamport
2594:CEILIDH
2553:NewHope
2500:Schnorr
2483:ElGamal
2461:Ed25519
2341:Benaloh
734:modulo
428:| <
402:) with
256:Hellman
221:padlock
182:inverse
90:scholar
2736:Topics
2712:NESSIE
2654:Theory
2582:Others
2439:X25519
2172:
2072:
2062:
1717:. See
1336:given
534:, let
297:) are
260:Merkle
258:, and
252:Diffie
211:) and
92:
85:
78:
71:
63:
2548:Kyber
2543:BLISS
2505:SPEKE
2473:ECMQV
2466:Ed448
2456:EdDSA
2451:ECDSA
2381:Rabin
2274:(PDF)
2237:(PDF)
2217:(PDF)
2197:(PDF)
2156:(PDF)
2070:S2CID
2025:Notes
280:Rabin
176:is a
97:JSTOR
83:books
2748:OAEP
2722:CNSA
2599:EPOC
2444:X448
2434:ECDH
2281:2015
2261:2015
2244:2015
2224:2015
2204:2015
2060:ISBN
1989:and
1927:and
1823:and
1741:and
1226:and
1157:Let
653:) =
581:) =
278:and
172:, a
168:and
69:news
2758:PKI
2641:XTR
2609:IES
2604:HFE
2535:SIS
2530:LWE
2515:STS
2510:SRP
2495:MQV
2478:EKE
2429:DSA
2414:BLS
2386:RSA
2361:GMR
2180:doi
2052:doi
1949:mod
1907:mod
1865:mod
1803:mod
1697:mod
1669:mod
1641:mod
1613:mod
1585:mod
1550:mod
1385:mod
1296:mod
1268:mod
1132:mod
1117:mod
1092:mod
1006:mod
958:of
824:mod
767:of
714:of
686:).
651:x'
638:x'
559:),
351:} (
299:not
276:RSA
164:In
142:Gen
52:by
2800::
2589:AE
2424:DH
2178:,
2166:22
2164:,
2158:,
2147:;
2068:.
2058:.
674:.
601:â
546:,
542:(
538:=
525:â
513:â
493:â
468:â
406:â
393:,
372:,
363:,
355:â
342:â
324:{
316:A
286:.
254:,
239:.
192:.
144:.
2532:/
2527:/
2310:e
2303:t
2296:v
2182::
2076:.
2054::
1997:y
1977:x
1956:)
1953:4
1946:(
1941:3
1935:q
1914:)
1911:4
1904:(
1899:3
1893:p
1872:)
1869:q
1862:(
1854:4
1850:1
1847:+
1844:q
1838:a
1831:y
1810:)
1807:p
1800:(
1792:4
1788:1
1785:+
1782:p
1776:a
1769:x
1749:q
1729:p
1704:)
1701:q
1694:(
1689:1
1683:d
1680:,
1676:)
1673:p
1666:(
1661:0
1655:d
1652:,
1648:)
1645:q
1638:(
1633:0
1627:c
1624:,
1620:)
1617:p
1610:(
1605:1
1599:c
1596:,
1592:)
1589:q
1582:(
1575:2
1571:y
1564:a
1561:,
1557:)
1554:p
1547:(
1540:2
1536:x
1529:a
1509:y
1506:d
1500:x
1497:c
1491:,
1488:y
1485:d
1482:+
1479:x
1476:c
1470:,
1467:y
1464:d
1458:x
1455:c
1452:,
1449:y
1446:d
1443:+
1440:x
1437:c
1427:z
1413:n
1392:)
1389:n
1382:(
1375:2
1371:z
1364:a
1344:a
1324:z
1303:)
1300:4
1293:(
1288:3
1282:q
1279:,
1275:)
1272:4
1265:(
1260:3
1254:p
1234:q
1214:p
1194:q
1191:p
1188:=
1185:n
1165:n
1137:n
1128:x
1125:=
1122:n
1111:d
1108:e
1104:x
1100:=
1097:n
1086:d
1082:y
1078:=
1075:x
1055:)
1052:x
1049:(
1046:f
1043:=
1040:y
1020:)
1017:n
1014:(
1000:1
993:e
989:=
986:d
966:e
946:d
926:)
923:1
917:q
914:(
911:)
908:1
902:p
899:(
896:=
893:)
890:n
887:(
864:q
861:p
858:=
855:n
832:.
829:n
818:e
814:x
810:=
807:)
804:x
801:(
798:f
775:n
763:(
751:)
748:n
745:(
722:e
702:d
664:x
662:(
659:k
655:f
649:(
646:k
642:f
634:x
632:(
629:k
625:f
620:k
616:f
611:k
607:t
603:K
599:k
592:x
590:(
587:k
583:f
579:y
577:(
574:k
570:f
565:k
561:t
557:x
555:(
552:k
548:f
544:k
540:A
536:y
531:k
527:D
523:x
519:A
515:K
511:k
506:.
503:k
499:f
495:K
491:k
483:k
479:D
474:k
470:D
466:x
462:k
455:k
446:k
442:t
438:p
434:n
432:(
430:p
425:k
421:t
416:k
412:t
408:K
404:k
399:k
395:t
391:k
378:k
374:R
369:k
365:D
361:K
357:K
353:k
348:k
344:R
339:k
335:D
330:k
326:f
226:t
217:x
213:t
209:x
207:(
205:f
201:t
197:f
158:t
154:f
146:f
138:t
134:f
119:)
113:(
108:)
104:(
94:·
87:·
80:·
73:·
46:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
