447:, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed
419:. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any such algorithm will only perform negligibly better than if one were to just guess.
326:
148:
98:
369:
417:
445:
189:
569:
455:
that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.
535:
176:
103:
53:
161:(which usually refers to the length of the input); we say they are computationally indistinguishable if for any
162:
31:
334:
151:
470:
42:
if no efficient algorithm can tell the difference between them except with negligible probability.
396:
553:
155:
17:
542:, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007
532:. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
451:. If the polynomial-time algorithm can generate samples in polynomial time, or has access to a
519:
513:
166:
503:
539:
529:
499:
484:
430:
516:, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513
563:
523:
509:
452:
35:
321:{\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}-\Pr _{x\gets E_{n}}\right|.}
487:(2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.
549:
548:
This article incorporates material from computationally indistinguishable on
169:
375:
s behavior does not significantly change when given samples according to
471:
27:
In computer science, relationship between two families of distributions
427:
Implicit in the definition is the condition that the algorithm,
143:{\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N} }}
93:{\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N} }}
107:
57:
526:. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
433:
399:
337:
192:
106:
56:
439:
411:
363:
320:
142:
92:
554:Creative Commons Attribution/Share-Alike License
264:
214:
449:indistinguishable by polynomial-time sampling
8:
371:. In other words, every efficient algorithm
122:
108:
72:
58:
480:
478:
432:
398:
355:
342:
336:
278:
267:
228:
217:
191:
133:
132:
125:
115:
105:
83:
82:
75:
65:
55:
463:
7:
38:, two families of distributions are
406:
364:{\displaystyle D_{n}\approx E_{n}}
25:
40:computationally indistinguishable
18:Computationally indistinguishable
570:Algorithmic information theory
552:, which is licensed under the
403:
307:
298:
292:
286:
271:
257:
248:
242:
236:
221:
202:
196:
175:, the following quantity is a
1:
504:Introduction to Cryptography
412:{\displaystyle n\to \infty }
586:
32:computational complexity
441:
413:
365:
322:
152:distribution ensembles
144:
94:
442:
414:
366:
323:
145:
95:
431:
397:
335:
190:
104:
54:
177:negligible function
508:Donald Beaver and
437:
409:
361:
318:
285:
235:
156:security parameter
140:
139:
90:
89:
440:{\displaystyle A}
263:
213:
46:Formal definition
16:(Redirected from
577:
520:Shafi Goldwasser
488:
482:
473:
468:
446:
444:
443:
438:
418:
416:
415:
410:
393:in the limit as
370:
368:
367:
362:
360:
359:
347:
346:
327:
325:
324:
319:
314:
310:
284:
283:
282:
234:
233:
232:
149:
147:
146:
141:
138:
137:
136:
120:
119:
99:
97:
96:
91:
88:
87:
86:
70:
69:
21:
585:
584:
580:
579:
578:
576:
575:
574:
560:
559:
546:
514:Phillip Rogaway
496:
491:
483:
476:
469:
465:
461:
429:
428:
425:
423:Related notions
395:
394:
392:
383:
351:
338:
333:
332:
274:
224:
212:
208:
188:
187:
167:polynomial time
121:
111:
102:
101:
71:
61:
52:
51:
48:
28:
23:
22:
15:
12:
11:
5:
583:
581:
573:
572:
562:
561:
544:
543:
540:Yehuda Lindell
533:
530:Oded Goldreich
527:
517:
506:
500:Yehuda Lindell
495:
494:External links
492:
490:
489:
474:
462:
460:
457:
436:
424:
421:
408:
405:
402:
388:
379:
358:
354:
350:
345:
341:
329:
328:
317:
313:
309:
306:
303:
300:
297:
294:
291:
288:
281:
277:
273:
270:
266:
262:
259:
256:
253:
250:
247:
244:
241:
238:
231:
227:
223:
220:
216:
211:
207:
204:
201:
198:
195:
165:probabilistic
135:
131:
128:
124:
118:
114:
110:
85:
81:
78:
74:
68:
64:
60:
47:
44:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
582:
571:
568:
567:
565:
558:
557:
555:
551:
541:
537:
536:Jonathan Katz
534:
531:
528:
525:
524:Silvio Micali
521:
518:
515:
511:
510:Silvio Micali
507:
505:
501:
498:
497:
493:
486:
485:Goldreich, O.
481:
479:
475:
472:
467:
464:
458:
456:
454:
453:random oracle
450:
434:
422:
420:
400:
391:
387:
382:
378:
374:
356:
352:
348:
343:
339:
315:
311:
304:
301:
295:
289:
279:
275:
268:
260:
254:
251:
245:
239:
229:
225:
218:
209:
205:
199:
193:
186:
185:
184:
182:
178:
174:
171:
168:
164:
160:
157:
154:indexed by a
153:
129:
126:
116:
112:
79:
76:
66:
62:
45:
43:
41:
37:
33:
19:
547:
545:
466:
448:
426:
389:
385:
380:
376:
372:
330:
180:
172:
158:
49:
39:
36:cryptography
29:
163:non-uniform
550:PlanetMath
459:References
407:∞
404:→
349:≈
272:←
261:−
222:←
194:δ
170:algorithm
130:∈
80:∈
564:Category
331:denoted
150:be two
522:and
512:and
100:and
50:Let
34:and
384:or
179:in
30:In
566::
538:,
502:.
477:^
373:A'
265:Pr
215:Pr
183::
556:.
435:A
401:n
390:n
386:E
381:n
377:D
357:n
353:E
344:n
340:D
316:.
312:|
308:]
305:1
302:=
299:)
296:x
293:(
290:A
287:[
280:n
276:E
269:x
258:]
255:1
252:=
249:)
246:x
243:(
240:A
237:[
230:n
226:D
219:x
210:|
206:=
203:)
200:n
197:(
181:n
173:A
159:n
134:N
127:n
123:}
117:n
113:E
109:{
84:N
77:n
73:}
67:n
63:D
59:{
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.