66:
794:
223:
25:
168:
395:
Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any
400:
available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e. an adversarial strategy) matching the upper bound, hence the name exact security.
392:- it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the resource requirement of the scheme being greater than desired.
186:
495:
538:
380:: it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any
388:. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the
711:
Yang, Jian; Guo, Qian; Johansson, Thomas; Lentmaier, Michael (3 Mar 2021). "Revisiting the
Concrete Security of Goldreich's Pseudorandom Generator".
831:
621:
568:
385:
83:
38:
661:
381:
324:
306:
204:
149:
52:
287:
130:
850:
259:
102:
449:
244:
237:
87:
266:
109:
530:
455:
In 2017, a thesis showed that lattice point enumeration and lattice block reduction algorithms could be used to attack
855:
425:
cryptosystems were proposed, which were shown to be approximately as difficult to break as the original cryptosystems.
456:
273:
116:
824:
354:
350:
759:
349:
is a practice-oriented approach that aims to give more precise estimates of the computational complexities of
255:
98:
233:
76:
463:
44:
470:, where instances with parameter values previously claimed to have 128-bit security were solved in about
462:
In 2021, "guess-and-determine" and "guess-and-decode"-type attacks were demonstrated against a proposed
817:
594:
445:
506:
774:
736:
712:
667:
510:
422:
418:
389:
501:
In addition, a software tool named the "Foundational
Cryptography Framework", which embeds into
280:
123:
657:
617:
414:
373:
769:
764:
649:
609:
473:
605:
561:
509:
proofs of concrete security. For example, it is able to verify the concrete security of
801:
502:
362:
844:
397:
671:
638:
338:
358:
222:
65:
653:
613:
760:
https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf
686:
409:
Concrete security estimates have been applied to cryptographic algorithms:
793:
357:
would allow. It quantifies the security of a cryptosystem by bounding the
595:"The Exact Security of Digital Signatures-How to Sign with RSA and Rabin"
779:
735:
Petcher, Adam (14 Oct 2014). "The
Foundational Cryptography Framework".
646:
Proceedings 38th Annual
Symposium on Foundations of Computer Science
637:
Bellare, Mihir; Desai, A.; Jokipii, E.; Rogaway, Philip (Oct 1997).
717:
741:
361:
of success for an adversary running for a fixed amount of time.
775:
https://www.baigneres.net/downloads/2007_provable_security.pdf
467:
216:
161:
59:
18:
448:
algorithms were proved approximately equivalent in various
765:
https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf
687:"On the Concrete Security of Lattice-Based Cryptography"
805:
639:"A concrete security treatment of symmetric encryption"
452:
such as CBC, CTR, and XOR (a stateless variant of CBC).
182:
604:. Lecture Notes in Computer Science. Vol. 1070.
476:
177:
may be too technical for most readers to understand
90:. Unsourced material may be challenged and removed.
489:
825:
8:
428:In 1997, some notions of concrete security (
53:Learn how and when to remove these messages
832:
818:
740:
716:
481:
475:
365:with precise analyses are referred to as
325:Learn how and when to remove this message
307:Learn how and when to remove this message
205:Learn how and when to remove this message
189:, without removing the technical details.
150:Learn how and when to remove this message
593:Bellare, Mihir; Rogaway, Philip (1996).
800:This cryptography-related article is a
522:
602:Advances in Cryptology — EUROCRYPT '96
243:Please improve this article by adding
780:https://eprint.iacr.org/2020/1213.pdf
187:make it understandable to non-experts
7:
790:
788:
770:https://eprint.iacr.org/2006/278.pdf
730:
728:
88:adding citations to reliable sources
434:real-or-random indistinguishability
430:left-or-right indistinguishability
14:
562:"Lectures 2+3: Provable Security"
531:"Modern symmetric-key Encryption"
382:computationally bounded adversary
34:This article has multiple issues.
792:
221:
166:
64:
23:
574:from the original on 2017-02-15
541:from the original on 2017-09-10
450:block cipher modes of operation
75:needs additional citations for
42:or discuss these issues on the
1:
245:secondary or tertiary sources
804:. You can help Knowledge by
872:
787:
457:lattice-based cryptography
685:Walter, Michael (2017).
654:10.1109/SFCS.1997.646128
614:10.1007/3-540-68339-9_34
438:find-then-guess security
851:Theory of cryptography
535:University of Maryland
491:
490:{\displaystyle 2^{78}}
464:pseudorandom generator
355:polynomial equivalence
232:relies excessively on
16:Cryptographic analysis
492:
413:In 1996, schemes for
648:. pp. 394–403.
608:. pp. 399–416.
474:
446:symmetric encryption
84:improve this article
256:"Concrete security"
99:"Concrete security"
856:Cryptography stubs
511:ElGamal encryption
487:
415:digital signatures
390:security parameter
813:
812:
623:978-3-540-68339-1
442:semantic-security
374:provable security
343:concrete security
335:
334:
327:
317:
316:
309:
291:
215:
214:
207:
160:
159:
152:
134:
57:
863:
834:
827:
820:
796:
789:
747:
746:
744:
732:
723:
722:
720:
708:
702:
701:
699:
697:
682:
676:
675:
643:
634:
628:
627:
599:
590:
584:
583:
581:
579:
573:
566:
557:
551:
550:
548:
546:
527:
496:
494:
493:
488:
486:
485:
330:
323:
312:
305:
301:
298:
292:
290:
249:
225:
217:
210:
203:
199:
196:
190:
170:
169:
162:
155:
148:
144:
141:
135:
133:
92:
68:
60:
49:
27:
26:
19:
871:
870:
866:
865:
864:
862:
861:
860:
841:
840:
839:
838:
785:
756:
751:
750:
734:
733:
726:
710:
709:
705:
695:
693:
684:
683:
679:
664:
641:
636:
635:
631:
624:
606:Springer-Verlag
597:
592:
591:
587:
577:
575:
571:
564:
559:
558:
554:
544:
542:
529:
528:
524:
519:
507:formally verify
477:
472:
471:
407:
372:Traditionally,
363:Security proofs
331:
320:
319:
318:
313:
302:
296:
293:
250:
248:
242:
238:primary sources
226:
211:
200:
194:
191:
183:help improve it
180:
171:
167:
156:
145:
139:
136:
93:
91:
81:
69:
28:
24:
17:
12:
11:
5:
869:
867:
859:
858:
853:
843:
842:
837:
836:
829:
822:
814:
811:
810:
797:
783:
782:
777:
772:
767:
762:
755:
754:External links
752:
749:
748:
724:
703:
677:
662:
629:
622:
585:
560:Kamara, Seny.
552:
521:
520:
518:
515:
499:
498:
484:
480:
460:
453:
426:
406:
403:
347:exact security
333:
332:
315:
314:
229:
227:
220:
213:
212:
174:
172:
165:
158:
157:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
868:
857:
854:
852:
849:
848:
846:
835:
830:
828:
823:
821:
816:
815:
809:
807:
803:
798:
795:
791:
786:
781:
778:
776:
773:
771:
768:
766:
763:
761:
758:
757:
753:
743:
738:
731:
729:
725:
719:
714:
707:
704:
692:
688:
681:
678:
673:
669:
665:
663:0-8186-8197-7
659:
655:
651:
647:
640:
633:
630:
625:
619:
615:
611:
607:
603:
596:
589:
586:
570:
563:
556:
553:
540:
536:
532:
526:
523:
516:
514:
512:
508:
505:, is able to
504:
482:
478:
469:
465:
461:
458:
454:
451:
447:
443:
439:
435:
431:
427:
424:
420:
417:based on the
416:
412:
411:
410:
404:
402:
399:
393:
391:
387:
383:
379:
375:
370:
368:
364:
360:
356:
352:
348:
344:
340:
329:
326:
311:
308:
300:
289:
286:
282:
279:
275:
272:
268:
265:
261:
258: –
257:
253:
252:Find sources:
246:
240:
239:
235:
230:This article
228:
224:
219:
218:
209:
206:
198:
188:
184:
178:
175:This article
173:
164:
163:
154:
151:
143:
132:
129:
125:
122:
118:
115:
111:
108:
104:
101: –
100:
96:
95:Find sources:
89:
85:
79:
78:
73:This article
71:
67:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
806:expanding it
799:
784:
706:
694:. Retrieved
691:UC San Diego
690:
680:
645:
632:
601:
588:
576:. Retrieved
555:
543:. Retrieved
534:
525:
500:
441:
437:
433:
429:
408:
394:
377:
371:
366:
346:
342:
339:cryptography
336:
321:
303:
294:
284:
277:
270:
263:
251:
231:
201:
192:
176:
146:
137:
127:
120:
113:
106:
94:
82:Please help
77:verification
74:
50:
43:
37:
36:Please help
33:
497:operations.
359:probability
353:tasks than
351:adversarial
845:Categories
718:2103.02668
517:References
386:negligible
378:asymptotic
267:newspapers
234:references
110:newspapers
39:improve it
742:1410.3735
45:talk page
672:42604387
569:Archived
539:Archived
405:Examples
367:concrete
297:May 2021
195:May 2021
140:May 2021
398:oracles
281:scholar
181:Please
124:scholar
670:
660:
620:
444:) for
440:, and
283:
276:
269:
262:
254:
126:
119:
112:
105:
97:
737:arXiv
713:arXiv
696:6 May
668:S2CID
642:(PDF)
598:(PDF)
578:6 May
572:(PDF)
565:(PDF)
545:6 May
423:Rabin
288:JSTOR
274:books
131:JSTOR
117:books
802:stub
698:2021
658:ISBN
618:ISBN
580:2021
547:2021
421:and
260:news
103:news
650:doi
610:doi
503:Coq
468:NC0
466:in
419:RSA
384:is
376:is
345:or
337:In
236:to
185:to
86:by
847::
727:^
689:.
666:.
656:.
644:.
616:.
600:.
567:.
537:.
533:.
513:.
483:78
436:,
432:,
369:.
341:,
247:.
48:.
833:e
826:t
819:v
808:.
745:.
739::
721:.
715::
700:.
674:.
652::
626:.
612::
582:.
549:.
479:2
459:.
328:)
322:(
310:)
304:(
299:)
295:(
285:·
278:·
271:·
264:·
241:.
208:)
202:(
197:)
193:(
179:.
153:)
147:(
142:)
138:(
128:·
121:·
114:·
107:·
80:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
