263:. He wrote a refutation of their first paper "Another look at 'provable security'" that he titled "On post-modern cryptography". Goldreich wrote: "... we point out some of the fundamental philosophical flaws that underlie the said article and some of its misconceptions regarding theoretical research in cryptography in the last quarter of a century." In his essay Goldreich argued that the rigorous analysis methodology of provable security is the only one compatible with science, and that Koblitz and Menezes are "reactionary (i.e., they play to the hands of the opponents of progress)".
25:
248:
reference to the paper in which the researchers reported on flaws: V. Shoup; A. J. Menezes; A. Jha and M. Nandi; D. Galindo; T. Iwata, K. Ohashi, and K. Minematsu; M. Nandi; J.-S. Coron and D. Naccache; D. Chakraborty, V. Hernández-Jiménez, and P. Sarkar; P. Gaži and U. Maurer; S. A. Kakvi and E. Kiltz; and T. Holenstein, R. Künzler, and S. Tessaro.
255:
models of security; and serve to distract researchers' attention from the need for "old-fashioned" (non-mathematical) testing and analysis. Their series of papers supporting these claims have been controversial in the community. Among the researchers who have rejected the viewpoint of
Koblitz–Menezes is
254:
and
Menezes have written that provable security results for important cryptographic protocols frequently have fallacies in the proofs; are often interpreted in a misleading manner, giving false assurances; typically rely upon strong assumptions that may turn out to be false; are based on unrealistic
187:
model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources. The proof of security (called a "reduction") is that these security requirements are met provided the assumptions about the adversary's access to the
247:
Several researchers have found mathematical fallacies in proofs that had been used to make claims about the security of important protocols. In the following partial list of such researchers, their names are followed by first a reference to the original paper with the purported proof and then a
275:
wrote letters responding to
Koblitz's article, which were published in the November 2007 and January 2008 issues of the journal. Katz, who is coauthor of a highly regarded cryptography textbook, called Koblitz's article "snobbery at its purest"; and Wigderson, who is a permanent member of the
130:, both of which can rely on proofs to show the security of a particular approach. As with the cryptographic setting, this involves an attacker model and a model of the system. For example, code can be verified to match the intended functionality, described by a model: this can be done through
219:
There are several lines of research in provable security. One is to establish the "correct" definition of security for a given, intuitively understood task. Another is to suggest constructions and proofs based on general assumptions as much as possible, for instance the existence of a
326:" is the name given to provable security reductions where one quantifies security by computing precise bounds on computational effort, rather than an asymptotic bound which is guaranteed to hold for "sufficiently large" values of the
266:
In 2007, Koblitz published "The Uneasy
Relationship Between Mathematics and Cryptography", which contained some controversial statements about provable security and other topics. Researchers Oded Goldreich, Boaz Barak,
119:
or other implementation-specific attacks, because they are usually impossible to model without implementing the system (and thus, the proof only applies to this implementation).
302:, recommended the Koblitz-Menezes paper "The brave new world of bodacious assumptions in cryptography" to the audience at the RSA Conference 2010 Cryptographers Panel.
54:
314:
defined objects. Instead, practice-oriented provable security is concerned with concrete objects of cryptographic practice, such as hash functions,
1119:
Holenstein, Thomas; Künzler, Robin; Tessaro, Stefano (2011), "The equivalence of the random oracle model and the ideal cipher model, revisited",
1447:
1103:
1068:
1033:
998:
963:
895:
853:
820:
785:
751:
716:
682:
642:
534:
508:
437:
366:
1084:
Coron, Jean-Sébastien; Patarin, Jacques; Seurin, Yannick (2008). "The Random Oracle Model and the Ideal Cipher Model Are
Equivalent".
268:
1414:
1247:
1169:
1146:
189:
76:
944:
Bellare, Mihir; Rogaway, Phillip (2006). "The
Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs".
801:
Bellare, Mihir; Garray, Juan A.; Rabin, Tal (1998). "Fast batch verification for modular exponentiation and digital signatures".
1625:
112:
1605:
1482:
205:
277:
111:
model (also referred to as attacker model): the aim of the proof is to show that the attacker must solve the underlying
37:
47:
41:
33:
665:
McGrew, David A.; Viega, John (2004), "The
Security and Performance of the Galois/Counter Mode (GCM) of Operation",
160:
156:
140:): the security here depends not only on the correctness of the attacker model, but also on the model of the code.
58:
299:
184:
164:
108:
876:
McGrew, David A.; Fluhrer, Scott R. (2007), "The
Security of the Extended Codebook (XCB) Mode of Operation",
131:
697:
Iwata, Tetsu; Ohashi, Keisuke; Minematsu, Kazuhiko (2012). "Breaking and
Repairing GCM Security Proofs".
489:
Bellare, Mihir; Pietrzak, Krzysztof; Rogaway, Phillip (2005). "Improved
Security Analyses for CBC MACs".
1583:
1572:
Rogaway, Phillip. "Practice-Oriented Provable Security and the Social Construction of Cryptography".
148:
549:
Jha, Ashwin; Nandi, Mridul (2016), "Revisiting structure graphs: Applications to CBC-MAC and EMAC",
311:
209:
116:
1550:
1460:
1282:
1152:
1124:
927:
859:
648:
566:
472:
401:
327:
152:
127:
100:
1049:
Kakvi, Saqib A.; Kiltz, Eike (2012). "Optimal Security Proofs for Full Domain Hash, Revisited".
616:
610:
115:
in order to break the security of the modelled system. Such a proof generally does not consider
910:
Chakraborty, Debrup; Hernández-Jiménez, Vicente; Sarkar, Palash (2015), "Another look at XCB",
1443:
1410:
1243:
1163:
1142:
1099:
1064:
1029:
994:
959:
891:
849:
816:
781:
747:
712:
678:
638:
530:
504:
433:
362:
323:
319:
201:
144:
93:
1014:
Coron, Jean-Sébastien (2002). "Optimal Security Proofs for PSS and Other Signature Schemes".
1435:
1272:
1196:
1134:
1089:
1054:
1019:
984:
949:
919:
881:
841:
806:
771:
737:
732:
Ristenpart, Thomas; Rogaway, Phillip (2007), "How to Enrich the Message Space of a Cipher",
702:
670:
628:
620:
592:
558:
522:
494:
462:
423:
391:
352:
221:
193:
1598:
1475:
136:
583:
Boneh, Dan; Franklin, Matthew (2003), "Identity-based encryption from the Weil pairing",
283:
318:, and protocols as they are deployed and used. Practice oriented provable security uses
1515:
291:
287:
256:
1380:
1352:
1324:
1619:
272:
213:
197:
123:
1185:"Critical perspectives on provable security: Fifteen years of 'Another look' papers"
931:
863:
570:
476:
405:
1576:
1286:
1156:
315:
251:
225:
176:
104:
652:
418:
Krawczyk, Hugo (2005). "HMQV: A High-Performance Secure Diffie-Hellman Protocol".
1574:
Unpublished Essay Corresponding to an Invited Talk at EUROCRYPT 2009. May 6, 2009
1453:
1263:
Koblitz, Neal; Menezes, Alfred J. (2007), "Another look at "provable security"",
1059:
886:
776:
674:
310:
Classical provable security primarily aimed at studying the relationship between
298:, former Technical Director of the Information Assurance Directorate of the U.S.
1439:
1094:
989:
742:
707:
229:
1540:
1277:
923:
596:
396:
322:
to analyse practical constructions with fixed key sizes. "Exact security" or "
295:
236:
1024:
609:
Galindo, David (2005), "Boneh-Franklin Identity Based Encryption Revisited",
1138:
1496:
232:, since the existence of one-way functions is not known to follow from the
1121:
Proceedings of the forty-third annual ACM symposium on Theory of computing
845:
562:
347:
Bellare, Mihir; Rogaway, Phillip (1995). "Optimal asymmetric encryption".
467:
1430:
Damgård, I. (2007). "A "proof-reading" of Some Issues in Cryptography".
1201:
1184:
954:
624:
526:
499:
428:
1545:
1053:. Lecture Notes in Computer Science. Vol. 7237. pp. 537–553.
1018:. Lecture Notes in Computer Science. Vol. 2332. pp. 272–287.
948:. Lecture Notes in Computer Science. Vol. 4004. pp. 409–426.
880:, Lecture Notes in Computer Science, vol. 4876, pp. 311–327,
840:, Lecture Notes in Computer Science, vol. 1560, pp. 197–203,
811:
805:. Lecture Notes in Computer Science. Vol. 1403. pp. 236–250.
770:. Lecture Notes in Computer Science. Vol. 8874. pp. 478–490.
736:, Lecture Notes in Computer Science, vol. 4593, pp. 101–118,
669:, Lecture Notes in Computer Science, vol. 3348, pp. 343–355,
521:, Lecture Notes in Computer Science, vol. 4052, pp. 168–179,
493:. Lecture Notes in Computer Science. Vol. 3621. pp. 527–545.
422:. Lecture Notes in Computer Science. Vol. 3621. pp. 546–566.
357:
766:
Nandi, Mridul (2014). "XLS is Not a Strong Pseudorandom Permutation".
633:
208:. Some proofs of security are in given theoretical models such as the
107:. In such a proof, the capabilities of the attacker are defined by an
96:
that can be proved. It is used in different ways by different fields.
983:. Lecture Notes in Computer Science. Vol. 5912. pp. 37–51.
701:. Lecture Notes in Computer Science. Vol. 7417. pp. 31–49.
351:. Lecture Notes in Computer Science. Vol. 950. pp. 92–111.
1434:. Lecture Notes in Computer Science. Vol. 4596. pp. 2–11.
1088:. Lecture Notes in Computer Science. Vol. 5157. pp. 1–20.
192:
hold. An early example of such requirements and proof was given by
143:
Finally, the term provable security is sometimes used by sellers of
122:
Outside of cryptography, the term is often used in conjunction with
1302:
134:. These techniques are sometimes used for evaluating products (see
1129:
979:
Gaži, Peter; Maurer, Ueli (2009). "Cascade Encryption Revisited".
290:
at ICALP 2007 on the technical issues, and it was recommended by
159:. As these products are typically not subject to scrutiny, many
1516:"The brave new world of bodacious assumptions in cryptography"
1325:"The uneasy relationship between mathematics and cryptography"
615:, Lecture Notes in Computer Science, vol. 3580, pp.
18:
190:
assumptions about the hardness of certain computational tasks
183:
if its security requirements can be stated formally in an
1217:
517:
Pietrzak, Krzysztof (2006), "A Tight Bound for EMAC",
1541:"RSA Conference 2010 USA: The Cryptographers Panel"
453:Menezes, Alfred J. (2007), "Another look at HMQV",
147:that are attempting to sell security products like
46:but its sources remain unclear because it lacks
836:Coron, Jean-Sébastien; Naccache, David (1999),
188:system are satisfied and some clearly stated
8:
280:in Princeton, accused Koblitz of "slander".
382:Shoup, Victor (2002), "OAEP reconsidered",
1514:Koblitz, Neal; Menezes, Alfred J. (2010),
163:consider this type of claim to be selling
1276:
1200:
1189:Advances in Mathematics of Communications
1128:
1093:
1058:
1023:
988:
953:
885:
810:
775:
741:
706:
632:
498:
466:
427:
395:
356:
77:Learn how and when to remove this message
1405:Katz, Jonathan; Lindell, Yehuda (2008).
1375:
1373:
1347:
1345:
1297:
1295:
1183:Koblitz, Neal; Menezes, Alfred (2019).
1051:Advances in Cryptology – EUROCRYPT 2012
1016:Advances in Cryptology — EUROCRYPT 2002
981:Advances in Cryptology – ASIACRYPT 2009
946:Advances in Cryptology - EUROCRYPT 2006
768:Advances in Cryptology – ASIACRYPT 2014
667:Progress in Cryptology - INDOCRYPT 2004
339:
259:, a leading theoretician and author of
1593:
1592:
1581:
1470:
1469:
1458:
1161:
803:Advances in Cryptology — EUROCRYPT'98
349:Advances in Cryptology — EUROCRYPT'94
228:is to establish such proofs based on
7:
1086:Advances in Cryptology – CRYPTO 2008
699:Advances in Cryptology – CRYPTO 2012
491:Advances in Cryptology – CRYPTO 2005
420:Advances in Cryptology – CRYPTO 2005
216:are represented by an idealization.
1432:Automata, Languages and Programming
1407:Introduction to Modern Cryptography
1218:"Another look at provable security"
612:Automata, Languages and Programming
519:Automata, Languages and Programming
306:Practice-oriented provable security
1215:These papers are all available at
551:Journal of Mathematical Cryptology
455:Journal of Mathematical Cryptology
204:and the construction based on the
14:
23:
1553:from the original on 2021-12-22
912:Cryptography and Communications
92:refers to any type or level of
1242:. Cambridge University Press.
878:Selected Areas in Cryptography
1:
1303:"On post-modern cryptography"
1168:: CS1 maint: date and year (
294:as a good in-depth analysis.
206:quadratic residuosity problem
1060:10.1007/978-3-642-29011-4_32
887:10.1007/978-3-540-77360-3_20
777:10.1007/978-3-662-45611-8_25
675:10.1007/978-3-540-30556-9_27
278:Institute for Advanced Study
1440:10.1007/978-3-540-73420-8_2
1240:Foundations of Cryptography
1095:10.1007/978-3-540-85174-5_1
990:10.1007/978-3-642-10366-7_3
743:10.1007/978-3-540-74619-5_7
708:10.1007/978-3-642-32009-5_3
261:Foundations of Cryptography
212:, where real cryptographic
157:intrusion detection systems
1642:
1409:. Chapman & Hall/CRC.
1278:10.1007/s00145-005-0432-z
924:10.1007/s12095-015-0127-8
597:10.1137/S0097539701398521
585:SIAM Journal on Computing
397:10.1007/s00145-002-0133-9
1523:Notices Amer. Math. Soc.
1388:Notices Amer. Math. Soc.
1360:Notices Amer. Math. Soc.
1332:Notices Amer. Math. Soc.
1238:Goldreich, Oded (2003).
1025:10.1007/3-540-46035-7_18
734:Fast Software Encryption
300:National Security Agency
99:Usually, this refers to
32:This section includes a
16:Computer security method
1604:CS1 maint: postscript (
1481:CS1 maint: postscript (
1381:"Letters to the Editor"
1353:"Letters to the Editor"
1139:10.1145/1993636.1993650
838:Public Key Cryptography
61:more precise citations.
1626:Theory of cryptography
1323:Koblitz, Neal (2007),
103:, which are common in
1366:(12): 1454–1455, 2007
1265:Journal of Cryptology
846:10.1007/3-540-49162-7
563:10.1515/jmc-2016-0030
384:Journal of Cryptology
271:, Hugo Krawczyk, and
468:10.1515/JMC.2007.004
161:security researchers
117:side-channel attacks
1202:10.3934/amc.2019034
955:10.1007/11761679_25
625:10.1007/11523468_64
527:10.1007/11787006_15
500:10.1007/11535218_32
429:10.1007/11535218_33
210:random oracle model
101:mathematical proofs
1497:"Shtetl-Optimized"
1123:, pp. 89–98,
812:10.1007/BFb0054130
358:10.1007/BFb0053428
328:security parameter
153:antivirus software
128:security by design
34:list of references
1594:|postscript=
1591:External link in
1503:. September 2007.
1501:scottaaronson.com
1471:|postscript=
1468:External link in
1449:978-3-540-73419-2
1105:978-3-540-85173-8
1070:978-3-642-29010-7
1035:978-3-540-43553-2
1000:978-3-642-10365-0
965:978-3-540-34546-6
897:978-3-540-77359-7
855:978-3-540-65644-9
822:978-3-540-64518-4
787:978-3-662-45607-1
753:978-3-540-74617-1
718:978-3-642-32008-8
684:978-3-540-24130-0
644:978-3-540-27580-0
536:978-3-540-35907-4
510:978-3-540-28114-6
439:978-3-540-28114-6
368:978-3-540-60176-0
324:concrete security
320:concrete security
202:semantic security
181:provable security
145:security software
94:computer security
90:Provable security
87:
86:
79:
1633:
1610:
1609:
1602:
1596:
1595:
1589:
1587:
1579:
1569:
1563:
1562:
1560:
1558:
1537:
1531:
1530:
1520:
1511:
1505:
1504:
1493:
1487:
1486:
1479:
1473:
1472:
1466:
1464:
1456:
1427:
1421:
1420:
1402:
1396:
1395:
1385:
1377:
1368:
1367:
1357:
1349:
1340:
1339:
1329:
1320:
1314:
1313:
1311:
1309:
1299:
1290:
1289:
1280:
1260:
1254:
1253:
1235:
1229:
1228:
1226:
1224:
1213:
1207:
1206:
1204:
1180:
1174:
1173:
1167:
1159:
1132:
1116:
1110:
1109:
1097:
1081:
1075:
1074:
1062:
1046:
1040:
1039:
1027:
1011:
1005:
1004:
992:
976:
970:
969:
957:
941:
935:
934:
907:
901:
900:
889:
873:
867:
866:
833:
827:
826:
814:
798:
792:
791:
779:
763:
757:
756:
745:
729:
723:
722:
710:
694:
688:
687:
662:
656:
655:
636:
606:
600:
599:
580:
574:
573:
557:(3–4): 157–180,
546:
540:
539:
514:
502:
486:
480:
479:
470:
450:
444:
443:
431:
415:
409:
408:
399:
379:
373:
372:
360:
344:
235:
222:one-way function
82:
75:
71:
68:
62:
57:this section by
48:inline citations
27:
26:
19:
1641:
1640:
1636:
1635:
1634:
1632:
1631:
1630:
1616:
1615:
1614:
1613:
1603:
1590:
1580:
1571:
1570:
1566:
1556:
1554:
1539:
1538:
1534:
1518:
1513:
1512:
1508:
1495:
1494:
1490:
1480:
1467:
1457:
1450:
1429:
1428:
1424:
1417:
1404:
1403:
1399:
1383:
1379:
1378:
1371:
1355:
1351:
1350:
1343:
1327:
1322:
1321:
1317:
1307:
1305:
1301:
1300:
1293:
1262:
1261:
1257:
1250:
1237:
1236:
1232:
1222:
1220:
1216:
1214:
1210:
1182:
1181:
1177:
1160:
1149:
1118:
1117:
1113:
1106:
1083:
1082:
1078:
1071:
1048:
1047:
1043:
1036:
1013:
1012:
1008:
1001:
978:
977:
973:
966:
943:
942:
938:
909:
908:
904:
898:
875:
874:
870:
856:
835:
834:
830:
823:
800:
799:
795:
788:
765:
764:
760:
754:
731:
730:
726:
719:
696:
695:
691:
685:
664:
663:
659:
645:
608:
607:
603:
582:
581:
577:
548:
547:
543:
537:
516:
511:
488:
487:
483:
452:
451:
447:
440:
417:
416:
412:
381:
380:
376:
369:
346:
345:
341:
336:
308:
245:
233:
179:, a system has
173:
171:In cryptography
137:Common Criteria
132:static checking
83:
72:
66:
63:
52:
38:related reading
28:
24:
17:
12:
11:
5:
1639:
1637:
1629:
1628:
1618:
1617:
1612:
1611:
1564:
1532:
1506:
1488:
1448:
1422:
1415:
1397:
1394:(1): 6–7, 2008
1369:
1341:
1315:
1291:
1255:
1248:
1230:
1208:
1195:(4): 517–558.
1175:
1147:
1111:
1104:
1076:
1069:
1041:
1034:
1006:
999:
971:
964:
936:
918:(4): 439–468,
902:
896:
868:
854:
828:
821:
793:
786:
758:
752:
724:
717:
689:
683:
657:
643:
601:
591:(3): 586–615,
575:
541:
535:
509:
481:
445:
438:
410:
390:(4): 223–249,
374:
367:
338:
337:
335:
332:
312:asymptotically
307:
304:
292:Scott Aaronson
288:position paper
286:later wrote a
257:Oded Goldreich
244:
241:
214:hash functions
172:
169:
85:
84:
67:September 2018
42:external links
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1638:
1627:
1624:
1623:
1621:
1607:
1600:
1585:
1578:
1575:
1568:
1565:
1552:
1548:
1547:
1542:
1536:
1533:
1528:
1524:
1517:
1510:
1507:
1502:
1498:
1492:
1489:
1484:
1477:
1462:
1455:
1451:
1445:
1441:
1437:
1433:
1426:
1423:
1418:
1416:9781584885511
1412:
1408:
1401:
1398:
1393:
1389:
1382:
1376:
1374:
1370:
1365:
1361:
1354:
1348:
1346:
1342:
1337:
1333:
1326:
1319:
1316:
1304:
1298:
1296:
1292:
1288:
1284:
1279:
1274:
1270:
1266:
1259:
1256:
1251:
1249:9780521791724
1245:
1241:
1234:
1231:
1219:
1212:
1209:
1203:
1198:
1194:
1190:
1186:
1179:
1176:
1171:
1165:
1158:
1154:
1150:
1148:9781450306911
1144:
1140:
1136:
1131:
1126:
1122:
1115:
1112:
1107:
1101:
1096:
1091:
1087:
1080:
1077:
1072:
1066:
1061:
1056:
1052:
1045:
1042:
1037:
1031:
1026:
1021:
1017:
1010:
1007:
1002:
996:
991:
986:
982:
975:
972:
967:
961:
956:
951:
947:
940:
937:
933:
929:
925:
921:
917:
913:
906:
903:
899:
893:
888:
883:
879:
872:
869:
865:
861:
857:
851:
847:
843:
839:
832:
829:
824:
818:
813:
808:
804:
797:
794:
789:
783:
778:
773:
769:
762:
759:
755:
749:
744:
739:
735:
728:
725:
720:
714:
709:
704:
700:
693:
690:
686:
680:
676:
672:
668:
661:
658:
654:
650:
646:
640:
635:
630:
626:
622:
618:
614:
613:
605:
602:
598:
594:
590:
586:
579:
576:
572:
568:
564:
560:
556:
552:
545:
542:
538:
532:
528:
524:
520:
512:
506:
501:
496:
492:
485:
482:
478:
474:
469:
464:
460:
456:
449:
446:
441:
435:
430:
425:
421:
414:
411:
407:
403:
398:
393:
389:
385:
378:
375:
370:
364:
359:
354:
350:
343:
340:
333:
331:
329:
325:
321:
317:
316:block ciphers
313:
305:
303:
301:
297:
293:
289:
285:
281:
279:
274:
273:Avi Wigderson
270:
269:Jonathan Katz
264:
262:
258:
253:
249:
243:Controversies
242:
240:
238:
231:
227:
223:
217:
215:
211:
207:
203:
199:
195:
191:
186:
182:
178:
170:
168:
166:
162:
158:
154:
150:
146:
141:
139:
138:
133:
129:
125:
124:secure coding
120:
118:
114:
110:
106:
102:
97:
95:
91:
81:
78:
70:
60:
56:
50:
49:
43:
39:
35:
30:
21:
20:
1584:cite journal
1573:
1567:
1555:. Retrieved
1544:
1535:
1526:
1522:
1509:
1500:
1491:
1431:
1425:
1406:
1400:
1391:
1387:
1363:
1359:
1338:(8): 972–979
1335:
1331:
1318:
1306:. Retrieved
1268:
1264:
1258:
1239:
1233:
1221:. Retrieved
1211:
1192:
1188:
1178:
1120:
1114:
1085:
1079:
1050:
1044:
1015:
1009:
980:
974:
945:
939:
915:
911:
905:
877:
871:
837:
831:
802:
796:
767:
761:
733:
727:
698:
692:
666:
660:
611:
604:
588:
584:
578:
554:
550:
544:
518:
490:
484:
458:
454:
448:
419:
413:
387:
383:
377:
348:
342:
309:
284:Ivan Damgård
282:
265:
260:
250:
246:
226:open problem
218:
180:
177:cryptography
174:
142:
135:
121:
113:hard problem
105:cryptography
98:
89:
88:
73:
64:
53:Please help
45:
1271:(1): 3–37,
185:adversarial
109:adversarial
59:introducing
634:2066/33216
334:References
296:Brian Snow
237:conjecture
224:. A major
194:Goldwasser
1529:: 357–365
1461:cite book
1130:1011.1264
461:: 47–64,
149:firewalls
1620:Category
1577:preprint
1551:Archived
1454:preprint
1308:12 April
1223:12 April
1164:citation
932:17251595
864:11711093
571:33121117
477:15540513
406:26919974
165:snakeoil
1557:9 April
1546:YouTube
1452:.
1287:7601573
1157:2960550
617:791–802
252:Koblitz
55:improve
1446:
1413:
1285:
1246:
1155:
1145:
1102:
1067:
1032:
997:
962:
930:
894:
862:
852:
819:
784:
750:
715:
681:
653:605011
651:
641:
569:
533:
515:; and
507:
475:
436:
404:
365:
234:P ≠ NP
230:P ≠ NP
198:Micali
1519:(PDF)
1384:(PDF)
1356:(PDF)
1328:(PDF)
1283:S2CID
1153:S2CID
1125:arXiv
928:S2CID
860:S2CID
649:S2CID
567:S2CID
473:S2CID
402:S2CID
40:, or
1606:link
1599:help
1559:2018
1483:link
1476:help
1444:ISBN
1411:ISBN
1310:2018
1244:ISBN
1225:2018
1170:link
1143:ISBN
1100:ISBN
1065:ISBN
1030:ISBN
995:ISBN
960:ISBN
892:ISBN
850:ISBN
817:ISBN
782:ISBN
748:ISBN
713:ISBN
679:ISBN
639:ISBN
531:ISBN
505:ISBN
434:ISBN
363:ISBN
200:for
196:and
155:and
126:and
1436:doi
1273:doi
1197:doi
1135:doi
1090:doi
1055:doi
1020:doi
985:doi
950:doi
920:doi
882:doi
842:doi
807:doi
772:doi
738:doi
703:doi
671:doi
629:hdl
621:doi
593:doi
559:doi
523:doi
495:doi
463:doi
424:doi
392:doi
353:doi
175:In
1622::
1588::
1586:}}
1582:{{
1549:.
1543:.
1527:57
1525:,
1521:,
1499:.
1465::
1463:}}
1459:{{
1442:.
1392:55
1390:,
1386:,
1372:^
1364:54
1362:,
1358:,
1344:^
1336:54
1334:,
1330:,
1294:^
1281:,
1269:20
1267:,
1193:13
1191:.
1187:.
1166:}}
1162:{{
1151:,
1141:,
1133:,
1098:.
1063:.
1028:.
993:.
958:.
926:,
914:,
890:,
858:,
848:,
815:.
780:.
746:,
711:.
677:,
647:,
637:,
627:,
619:,
589:32
587:,
565:,
555:10
553:,
529:,
503:.
471:,
457:,
432:.
400:,
388:15
386:,
361:.
330:.
239:.
167:.
151:,
44:,
36:,
1608:)
1601:)
1597:(
1561:.
1485:)
1478:)
1474:(
1438::
1419:.
1312:.
1275::
1252:.
1227:.
1205:.
1199::
1172:)
1137::
1127::
1108:.
1092::
1073:.
1057::
1038:.
1022::
1003:.
987::
968:.
952::
922::
916:7
884::
844::
825:.
809::
790:.
774::
740::
721:.
705::
673::
631::
623::
595::
561::
525::
513:.
497::
465::
459:1
442:.
426::
394::
371:.
355::
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.