2168:
1041:
742:
1036:{\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}
733:
477:
343:
104:
522:
586:
277:
215:
1093:
2148:
1978:
1196:
1608:
1318:
650:
1142:
1736:
1831:
1731:
1460:
1639:
1633:
17:
2196:
1757:
1311:
1375:
1443:
1400:
1365:
1824:
1280:
1355:
1304:
1433:
1519:
2027:
1544:
1428:
1245:
665:
1817:
1685:
1618:
1360:
2143:
2098:
1911:
1782:
1675:
1524:
1438:
1423:
447:
285:
119:
61:
486:
2022:
1534:
1405:
1249:
35:
2138:
1787:
1767:
625:
530:
2128:
2118:
1973:
1726:
1497:
220:
158:
1049:
2123:
2113:
1916:
1876:
1869:
1859:
1854:
1680:
1327:
55:
31:
1864:
1762:
1613:
1552:
1487:
115:
28:
1147:
2171:
2017:
1963:
1628:
1385:
1342:
2133:
2057:
1539:
1350:
429:
1896:
1645:
1261:
Naccache, David; Stern, Jacques (1998). "A New Public Key
Cryptosystem Based on Higher Residues".
2002:
1986:
1933:
1670:
1492:
1415:
1395:
1390:
1370:
2062:
2052:
1923:
1752:
1695:
1623:
1509:
1276:
1241:
635:
1997:
1598:
1266:
1120:
2072:
1992:
1953:
1901:
1886:
39:
2190:
2153:
2108:
2067:
2047:
1943:
1906:
1881:
43:
2103:
1948:
1938:
1928:
1891:
1840:
1792:
1772:
136:
111:
2082:
1690:
1567:
2042:
2012:
2007:
1968:
1716:
1448:
1263:
Proceedings of the 5th ACM Conference on
Computer and Communications Security
2032:
1271:
1231:
can be recovered by a direct application of the
Chinese remainder theorem.
2077:
2037:
1777:
1711:
1582:
1577:
1572:
1453:
1603:
1562:
1958:
1721:
1557:
1514:
1482:
1475:
1470:
1465:
1244:
of the
Naccache–Stern cryptosystem rests on an extension of the
1813:
1300:
1650:
1504:
1117:
can be recovered by exhaustive search, i.e. by comparing
1979:
Cryptographically secure pseudorandom number generator
747:
1150:
1123:
1052:
745:
668:
638:
533:
489:
450:
288:
223:
161:
64:
1288:
728:{\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}
38:. The Naccache–Stern cryptosystem was discovered by
2091:
1847:
1745:
1704:
1663:
1591:
1533:
1414:
1341:
1334:
1190:
1136:
1087:
1035:
727:
644:
580:
516:
471:
337:
271:
209:
98:
472:{\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }
338:{\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}
99:{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
517:{\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }
1825:
1312:
8:
581:{\displaystyle E(m)=x^{\sigma }g^{m}\mod n}
440:This system allows encryption of a message
1832:
1818:
1810:
1338:
1319:
1305:
1297:
1293:
1289:
1270:
1180:
1171:
1155:
1149:
1128:
1122:
1079:
1074:
1073:
1057:
1051:
1025:
1024:
1012:
1003:
985:
980:
962:
961:
949:
940:
919:
909:
896:
888:
870:
869:
857:
848:
832:
820:
811:
795:
776:
767:
754:
746:
744:
721:
720:
708:
699:
686:
673:
667:
637:
574:
573:
563:
553:
532:
510:
509:
501:
497:
496:
488:
465:
464:
456:
452:
451:
449:
329:
319:
308:
287:
272:{\displaystyle v=\prod _{k/2+1}^{k}p_{i}}
263:
253:
238:
234:
222:
210:{\displaystyle u=\prod _{i=1}^{k/2}p_{i}}
201:
187:
183:
172:
160:
90:
82:
81:
73:
69:
68:
63:
1088:{\displaystyle m_{i}\equiv m\mod p_{i}}
7:
1640:Naccache–Stern knapsack cryptosystem
18:Naccache–Stern knapsack cryptosystem
1191:{\displaystyle g^{j\phi (n)/p_{i}}}
1020:
957:
865:
14:
58:, this scheme works in the group
2167:
2166:
1265:. CCS '98. ACM. pp. 59–66.
595:is an encryption of the message
413:and the private key is the pair
405:The public key is the numbers σ,
1671:Discrete logarithm cryptography
1069:
716:
569:
155:Divide the set in half and set
2028:Information-theoretic security
1168:
1162:
1000:
994:
937:
931:
925:
889:
845:
839:
808:
802:
764:
758:
696:
690:
543:
537:
87:
65:
1:
2197:Public-key encryption schemes
1246:quadratic residuosity problem
1686:Non-commutative cryptography
34:whose security rests on the
2144:Message authentication code
2099:Cryptographic hash function
1912:Cryptographic hash function
1783:Identity-based cryptography
1676:Elliptic-curve cryptography
659:, to decrypt, we calculate
428:=1 this is essentially the
25:Naccache–Stern cryptosystem
2213:
2023:Harvest now, decrypt later
1250:higher residuosity problem
607:To decrypt, we first find
110:is a product of two large
36:higher residuosity problem
15:
2162:
2139:Post-quantum cryptography
1809:
1788:Post-quantum cryptography
1737:Post-Quantum Cryptography
1296:
1292:
626:Chinese remainder theorem
2129:Quantum key distribution
2119:Authenticated encryption
1974:Random number generation
624:, and then we apply the
56:public key cryptosystems
16:Not to be confused with
2124:Public-key cryptography
2114:Symmetric-key algorithm
1917:Key derivation function
1877:Cryptographic primitive
1870:Authentication protocol
1860:Outline of cryptography
1855:History of cryptography
1681:Hash-based cryptography
1328:Public-key cryptography
1108:is chosen to be small,
645:{\displaystyle \sigma }
32:public-key cryptosystem
1865:Cryptographic protocol
1192:
1138:
1089:
1037:
729:
646:
582:
518:
473:
339:
324:
273:
258:
211:
196:
100:
2018:End-to-end encryption
1964:Cryptojacking malware
1343:Integer factorization
1272:10.1145/288090.288106
1193:
1139:
1137:{\displaystyle c_{i}}
1090:
1038:
730:
647:
583:
519:
474:
340:
304:
274:
230:
212:
168:
101:
2134:Quantum cryptography
2058:Trusted timestamping
1148:
1121:
1050:
743:
666:
636:
531:
487:
448:
430:Benaloh cryptosystem
347:Choose large primes
286:
221:
159:
62:
1897:Cryptographic nonce
1646:Three-pass protocol
655:Given a ciphertext
2003:Subliminal channel
1987:Pseudorandom noise
1934:Key (cryptography)
1416:Discrete logarithm
1223:is known for each
1188:
1134:
1085:
1033:
1031:
725:
642:
603:Message Decryption
578:
514:
469:
436:Message Encryption
335:
269:
207:
96:
2184:
2183:
2180:
2179:
2063:Key-based routing
2053:Trapdoor function
1924:Digital signature
1805:
1804:
1801:
1800:
1753:Digital signature
1696:Trapdoor function
1659:
1658:
1376:Goldwasser–Micali
1242:semantic security
131:Pick a family of
114:. This scheme is
50:Scheme Definition
2204:
2170:
2169:
1998:Insecure channel
1834:
1827:
1820:
1811:
1642:
1543:
1538:
1498:signature scheme
1401:Okamoto–Uchiyama
1339:
1321:
1314:
1307:
1298:
1294:
1290:
1286:
1274:
1197:
1195:
1194:
1189:
1187:
1186:
1185:
1184:
1175:
1143:
1141:
1140:
1135:
1133:
1132:
1094:
1092:
1091:
1086:
1084:
1083:
1062:
1061:
1042:
1040:
1039:
1034:
1032:
1019:
1018:
1017:
1016:
1007:
990:
989:
969:
956:
955:
954:
953:
944:
924:
923:
914:
913:
901:
900:
877:
864:
863:
862:
861:
852:
827:
826:
825:
824:
815:
783:
782:
781:
780:
771:
734:
732:
731:
726:
715:
714:
713:
712:
703:
678:
677:
651:
649:
648:
643:
587:
585:
584:
579:
568:
567:
558:
557:
523:
521:
520:
515:
513:
505:
500:
478:
476:
475:
470:
468:
460:
455:
385:Choose a random
344:
342:
341:
336:
334:
333:
323:
318:
278:
276:
275:
270:
268:
267:
257:
252:
242:
216:
214:
213:
208:
206:
205:
195:
191:
182:
105:
103:
102:
97:
95:
94:
85:
77:
72:
2212:
2211:
2207:
2206:
2205:
2203:
2202:
2201:
2187:
2186:
2185:
2176:
2158:
2087:
1843:
1838:
1797:
1741:
1705:Standardization
1700:
1655:
1638:
1587:
1535:Lattice/SVP/CVP
1529:
1410:
1356:Blum–Goldwasser
1330:
1325:
1283:
1260:
1258:
1238:
1222:
1210:
1176:
1151:
1146:
1145:
1124:
1119:
1118:
1116:
1107:
1075:
1053:
1048:
1047:
1030:
1029:
1008:
981:
976:
974:
967:
966:
945:
915:
905:
892:
884:
882:
875:
874:
853:
828:
816:
791:
789:
784:
772:
750:
741:
740:
704:
682:
669:
664:
663:
634:
633:
619:
605:
559:
549:
529:
528:
485:
484:
446:
445:
438:
355:such that both
325:
284:
283:
259:
219:
218:
197:
157:
156:
151:
144:
135:small distinct
128:
86:
60:
59:
52:
21:
12:
11:
5:
2210:
2208:
2200:
2199:
2189:
2188:
2182:
2181:
2178:
2177:
2175:
2174:
2163:
2160:
2159:
2157:
2156:
2151:
2149:Random numbers
2146:
2141:
2136:
2131:
2126:
2121:
2116:
2111:
2106:
2101:
2095:
2093:
2089:
2088:
2086:
2085:
2080:
2075:
2073:Garlic routing
2070:
2065:
2060:
2055:
2050:
2045:
2040:
2035:
2030:
2025:
2020:
2015:
2010:
2005:
2000:
1995:
1993:Secure channel
1990:
1984:
1983:
1982:
1971:
1966:
1961:
1956:
1954:Key stretching
1951:
1946:
1941:
1936:
1931:
1926:
1921:
1920:
1919:
1914:
1904:
1902:Cryptovirology
1899:
1894:
1889:
1887:Cryptocurrency
1884:
1879:
1874:
1873:
1872:
1862:
1857:
1851:
1849:
1845:
1844:
1839:
1837:
1836:
1829:
1822:
1814:
1807:
1806:
1803:
1802:
1799:
1798:
1796:
1795:
1790:
1785:
1780:
1775:
1770:
1765:
1760:
1755:
1749:
1747:
1743:
1742:
1740:
1739:
1734:
1729:
1724:
1719:
1714:
1708:
1706:
1702:
1701:
1699:
1698:
1693:
1688:
1683:
1678:
1673:
1667:
1665:
1661:
1660:
1657:
1656:
1654:
1653:
1648:
1643:
1636:
1634:Merkle–Hellman
1631:
1626:
1621:
1616:
1611:
1606:
1601:
1595:
1593:
1589:
1588:
1586:
1585:
1580:
1575:
1570:
1565:
1560:
1555:
1549:
1547:
1531:
1530:
1528:
1527:
1522:
1517:
1512:
1507:
1502:
1501:
1500:
1490:
1485:
1480:
1479:
1478:
1473:
1463:
1458:
1457:
1456:
1451:
1441:
1436:
1431:
1426:
1420:
1418:
1412:
1411:
1409:
1408:
1403:
1398:
1393:
1388:
1383:
1381:Naccache–Stern
1378:
1373:
1368:
1363:
1358:
1353:
1347:
1345:
1336:
1332:
1331:
1326:
1324:
1323:
1316:
1309:
1301:
1281:
1257:
1254:
1237:
1234:
1233:
1232:
1218:
1212:
1206:
1183:
1179:
1174:
1170:
1167:
1164:
1161:
1158:
1154:
1131:
1127:
1112:
1103:
1082:
1078:
1072:
1068:
1065:
1060:
1056:
1044:
1043:
1028:
1023:
1015:
1011:
1006:
1002:
999:
996:
993:
988:
984:
979:
975:
973:
970:
968:
965:
960:
952:
948:
943:
939:
936:
933:
930:
927:
922:
918:
912:
908:
904:
899:
895:
891:
887:
883:
881:
878:
876:
873:
868:
860:
856:
851:
847:
844:
841:
838:
835:
831:
823:
819:
814:
810:
807:
804:
801:
798:
794:
790:
788:
785:
779:
775:
770:
766:
763:
760:
757:
753:
749:
748:
737:
736:
724:
719:
711:
707:
702:
698:
695:
692:
689:
685:
681:
676:
672:
641:
615:
604:
601:
589:
588:
577:
572:
566:
562:
556:
552:
548:
545:
542:
539:
536:
525:
512:
508:
504:
499:
495:
492:
483:Pick a random
467:
463:
459:
454:
437:
434:
403:
402:
383:
372:
345:
332:
328:
322:
317:
314:
311:
307:
303:
300:
297:
294:
291:
280:
266:
262:
256:
251:
248:
245:
241:
237:
233:
229:
226:
204:
200:
194:
190:
186:
181:
178:
175:
171:
167:
164:
153:
149:
142:
127:
126:Key Generation
124:
93:
89:
84:
80:
76:
71:
67:
51:
48:
40:David Naccache
13:
10:
9:
6:
4:
3:
2:
2209:
2198:
2195:
2194:
2192:
2173:
2165:
2164:
2161:
2155:
2154:Steganography
2152:
2150:
2147:
2145:
2142:
2140:
2137:
2135:
2132:
2130:
2127:
2125:
2122:
2120:
2117:
2115:
2112:
2110:
2109:Stream cipher
2107:
2105:
2102:
2100:
2097:
2096:
2094:
2090:
2084:
2081:
2079:
2076:
2074:
2071:
2069:
2068:Onion routing
2066:
2064:
2061:
2059:
2056:
2054:
2051:
2049:
2048:Shared secret
2046:
2044:
2041:
2039:
2036:
2034:
2031:
2029:
2026:
2024:
2021:
2019:
2016:
2014:
2011:
2009:
2006:
2004:
2001:
1999:
1996:
1994:
1991:
1988:
1985:
1980:
1977:
1976:
1975:
1972:
1970:
1967:
1965:
1962:
1960:
1957:
1955:
1952:
1950:
1947:
1945:
1944:Key generator
1942:
1940:
1937:
1935:
1932:
1930:
1927:
1925:
1922:
1918:
1915:
1913:
1910:
1909:
1908:
1907:Hash function
1905:
1903:
1900:
1898:
1895:
1893:
1890:
1888:
1885:
1883:
1882:Cryptanalysis
1880:
1878:
1875:
1871:
1868:
1867:
1866:
1863:
1861:
1858:
1856:
1853:
1852:
1850:
1846:
1842:
1835:
1830:
1828:
1823:
1821:
1816:
1815:
1812:
1808:
1794:
1791:
1789:
1786:
1784:
1781:
1779:
1776:
1774:
1771:
1769:
1766:
1764:
1761:
1759:
1756:
1754:
1751:
1750:
1748:
1744:
1738:
1735:
1733:
1730:
1728:
1725:
1723:
1720:
1718:
1715:
1713:
1710:
1709:
1707:
1703:
1697:
1694:
1692:
1689:
1687:
1684:
1682:
1679:
1677:
1674:
1672:
1669:
1668:
1666:
1662:
1652:
1649:
1647:
1644:
1641:
1637:
1635:
1632:
1630:
1627:
1625:
1622:
1620:
1617:
1615:
1612:
1610:
1607:
1605:
1602:
1600:
1597:
1596:
1594:
1590:
1584:
1581:
1579:
1576:
1574:
1571:
1569:
1566:
1564:
1561:
1559:
1556:
1554:
1551:
1550:
1548:
1546:
1541:
1536:
1532:
1526:
1523:
1521:
1518:
1516:
1513:
1511:
1508:
1506:
1503:
1499:
1496:
1495:
1494:
1491:
1489:
1486:
1484:
1481:
1477:
1474:
1472:
1469:
1468:
1467:
1464:
1462:
1459:
1455:
1452:
1450:
1447:
1446:
1445:
1442:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1421:
1419:
1417:
1413:
1407:
1406:Schmidt–Samoa
1404:
1402:
1399:
1397:
1394:
1392:
1389:
1387:
1384:
1382:
1379:
1377:
1374:
1372:
1369:
1367:
1366:Damgård–Jurik
1364:
1362:
1361:Cayley–Purser
1359:
1357:
1354:
1352:
1349:
1348:
1346:
1344:
1340:
1337:
1333:
1329:
1322:
1317:
1315:
1310:
1308:
1303:
1302:
1299:
1295:
1291:
1287:
1284:
1282:1-58113-007-4
1278:
1273:
1268:
1264:
1255:
1253:
1251:
1248:known as the
1247:
1243:
1235:
1230:
1226:
1221:
1217:
1213:
1209:
1205:
1201:
1181:
1177:
1172:
1165:
1159:
1156:
1152:
1129:
1125:
1115:
1111:
1106:
1102:
1098:
1097:
1096:
1080:
1076:
1070:
1066:
1063:
1058:
1054:
1026:
1021:
1013:
1009:
1004:
997:
991:
986:
982:
977:
971:
963:
958:
950:
946:
941:
934:
928:
920:
916:
910:
906:
902:
897:
893:
885:
879:
871:
866:
858:
854:
849:
842:
836:
833:
829:
821:
817:
812:
805:
799:
796:
792:
786:
777:
773:
768:
761:
755:
751:
739:
738:
722:
717:
709:
705:
700:
693:
687:
683:
679:
674:
670:
662:
661:
660:
658:
653:
639:
631:
628:to calculate
627:
623:
618:
614:
610:
602:
600:
598:
594:
575:
570:
564:
560:
554:
550:
546:
540:
534:
526:
506:
502:
493:
490:
482:
481:
480:
461:
457:
444:in the group
443:
435:
433:
431:
427:
422:
420:
416:
412:
408:
400:
396:
392:
388:
384:
381:
377:
373:
371:+1 are prime.
370:
366:
362:
358:
354:
350:
346:
330:
326:
320:
315:
312:
309:
305:
301:
298:
295:
292:
289:
281:
264:
260:
254:
249:
246:
243:
239:
235:
231:
227:
224:
202:
198:
192:
188:
184:
179:
176:
173:
169:
165:
162:
154:
148:
141:
138:
134:
130:
129:
125:
123:
121:
117:
113:
109:
91:
78:
74:
57:
49:
47:
45:
44:Jacques Stern
41:
37:
33:
30:
26:
19:
2104:Block cipher
1949:Key schedule
1939:Key exchange
1929:Kleptography
1892:Cryptosystem
1841:Cryptography
1793:OpenPGP card
1773:Web of trust
1429:Cramer–Shoup
1380:
1262:
1259:
1239:
1228:
1224:
1219:
1215:
1207:
1203:
1199:
1113:
1109:
1104:
1100:
1045:
656:
654:
629:
621:
616:
612:
608:
606:
596:
592:
590:
441:
439:
425:
423:
418:
414:
410:
406:
404:
398:
397:has order φ(
394:
390:
386:
379:
375:
368:
364:
360:
356:
352:
348:
146:
139:
132:
107:
53:
24:
22:
2092:Mathematics
2083:Mix network
1763:Fingerprint
1727:NSA Suite B
1691:RSA problem
1568:NTRUEncrypt
116:homomorphic
29:homomorphic
2043:Ciphertext
2013:Decryption
2008:Encryption
1969:Ransomware
1717:IEEE P1363
1335:Algorithms
1256:References
1202:from 1 to
527:Calculate
393:such that
118:and hence
54:Like many
2033:Plaintext
1160:ϕ
1064:≡
992:ϕ
972:≡
929:ϕ
880:≡
837:ϕ
800:ϕ
797:σ
787:≡
756:ϕ
688:ϕ
680:≡
640:σ
620:for each
555:σ
494:∈
462:σ
306:∏
290:σ
232:∏
170:∏
120:malleable
92:∗
46:in 1998.
2191:Category
2172:Category
2078:Kademlia
2038:Codetext
1981:(CSPRNG)
1778:Key size
1712:CRYPTREC
1629:McEliece
1583:RLWE-SIG
1578:RLWE-KEX
1573:NTRUSign
1386:Paillier
1236:Security
1848:General
1624:Lamport
1604:CEILIDH
1563:NewHope
1510:Schnorr
1493:ElGamal
1471:Ed25519
1351:Benaloh
735:. Thus
363:+1 and
1959:Keygen
1746:Topics
1722:NESSIE
1664:Theory
1592:Others
1449:X25519
1279:
1099:Since
1046:where
137:primes
112:primes
106:where
1989:(PRN)
1558:Kyber
1553:BLISS
1515:SPEKE
1483:ECMQV
1476:Ed448
1466:EdDSA
1461:ECDSA
1391:Rabin
1214:Once
591:Then
424:When
145:,...,
27:is a
1758:OAEP
1732:CNSA
1609:EPOC
1454:X448
1444:ECDH
1277:ISBN
1240:The
1198:for
632:mod
611:mod
593:E(m)
401:)/4.
389:mod
374:Set
351:and
282:Set
217:and
42:and
23:The
1768:PKI
1651:XTR
1619:IES
1614:HFE
1545:SIS
1540:LWE
1525:STS
1520:SRP
1505:MQV
1488:EKE
1439:DSA
1424:BLS
1396:RSA
1371:GMR
1267:doi
1211:-1.
1144:to
1071:mod
1022:mod
959:mod
867:mod
718:mod
571:mod
359:= 2
2193::
1599:AE
1434:DH
1275:.
1252:.
1227:,
1095:.
652:.
599:.
479:.
432:.
421:.
380:pq
369:bv
367:=2
361:au
122:.
1833:e
1826:t
1819:v
1542:/
1537:/
1320:e
1313:t
1306:v
1285:.
1269::
1229:m
1225:i
1220:i
1216:m
1208:i
1204:p
1200:j
1182:i
1178:p
1173:/
1169:)
1166:n
1163:(
1157:j
1153:g
1130:i
1126:c
1114:i
1110:m
1105:i
1101:p
1081:i
1077:p
1067:m
1059:i
1055:m
1027:n
1014:i
1010:p
1005:/
1001:)
998:n
995:(
987:i
983:m
978:g
964:n
951:i
947:p
942:/
938:)
935:n
932:(
926:)
921:i
917:p
911:i
907:y
903:+
898:i
894:m
890:(
886:g
872:n
859:i
855:p
850:/
846:)
843:n
840:(
834:m
830:g
822:i
818:p
813:/
809:)
806:n
803:(
793:x
778:i
774:p
769:/
765:)
762:n
759:(
752:c
723:n
710:i
706:p
701:/
697:)
694:n
691:(
684:c
675:i
671:c
657:c
630:m
622:i
617:i
613:p
609:m
597:m
576:n
565:m
561:g
551:x
547:=
544:)
541:m
538:(
535:E
524:.
511:Z
507:n
503:/
498:Z
491:x
466:Z
458:/
453:Z
442:m
426:k
419:q
417:,
415:p
411:g
409:,
407:n
399:n
395:g
391:n
387:g
382:.
378:=
376:n
365:q
357:p
353:b
349:a
331:i
327:p
321:k
316:1
313:=
310:i
302:=
299:v
296:u
293:=
279:.
265:i
261:p
255:k
250:1
247:+
244:2
240:/
236:k
228:=
225:v
203:i
199:p
193:2
189:/
185:k
180:1
177:=
174:i
166:=
163:u
152:.
150:k
147:p
143:1
140:p
133:k
108:n
88:)
83:Z
79:n
75:/
70:Z
66:(
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.