23:) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.
240:
675:
s and repeating the above procedure many times, and only providing the majority winner as an answer, we can drive the error rate down very low.
243:
schemes (where a weak private device uses a strong public device without revealing its data) are easily exemplified by random self-reductions.
489:
is random self-reducible. The discussion below considers the case where the matrix entries are drawn from a finite field
158:
is as hard on average as it is in the worst case. This approach contains two key restrictions. First the generation of
302:| is the input size), then there is a randomized polynomial time algorithm for discrete logarithm for all inputs.
766:
466:
256:
236:
216:) can use randomization to ensure that privacy. In fact, the only provably secure cryptographic system (the
32:
231:
utilizes the fact that certain number-theoretic functions are randomly self-reducible. This includes
633:
232:
426:
264:
125:
671:
If we do so, we run the risk of being wrong 1/3 of the time, but by picking multiple random
689:
8:
132:
is the same (within polynomial factors) as the worst-case randomized complexity of
252:
91:) can be computed in polynomial time, given the coin-toss sequence from the mapping,
747:
462:
260:
457:. Calculating the permanent of a matrix is a difficult computational task—
600:) of them. Then with probability of approximately two-thirds, we can calculate
117:). Therefore, taking the average with respect to the induced distribution on
760:
477:) for most matrices implies the existence of a random program that computes
228:
217:
146:
is distributed uniformly over the entire set of elements in the domain of
685:
700:
61:). In a random self-reduction, an arbitrary worst-case instance
47:
573:
Suppose we know a program that computes the correct value of
389:, and its logarithm can be computed with probability 1/poly(
212:
Problems that require some privacy in the data (typically
207:
190:) is known. Second, it is not necessary that the points
500:, and where all arithmetic is performed in that field.
42:
can be reduced in polynomial time to the evaluation of
534:, by composing those linear functions with the degree
139:
One special case of note is when each random instance
267:
of a matrix are each random self-reducible problems.
57:, then it is self-reducible (this is also known as a
688:
problem is non-adaptively random self-reducible the
263:
inversion problem, and the problem of computing the
624:+ 1 values, we can solve for the coefficients of
417:|) and the discrete logarithm is self-reducible.
758:
750:On the Random-self-reducibility of Complete Sets
286:|. If a deterministic polynomial time algorithm
172:is performed non-adaptively. This means that
290:computes the discrete logarithm for a 1/poly(
485:) for all matrices. This demonstrates that
220:) has its security relying totally on the
596:---specifically, 1 − 1/(3
733:M. Abadi, J. Feigenbaum, and J. Kilian,
538:multivariate polynomial that calculates
420:
224:of the key data supplied to the system.
449:is a multivariate polynomial of degree
365:to be distributed uniformly on {0,...,|
69:is mapped to a random set of instances
759:
522:. Since all the entries of any matrix
208:Application in cryptographic protocols
270:
735:On Hiding Information from an Oracle
703:problem is random self-reducible in
469:). Moreover, the ability to compute
59:non-adaptive uniform self-reduction
13:
14:
778:
566:(0) is equal to the permanent of
377:is also distributed uniformly on
294:) fraction of all inputs (where
678:
393:) in polynomial time. Then log
429:of a matrix, it is clear that
237:pseudorandom number generation
1:
737:, J. Comput. Syst. Sci., 1989
727:
369:| − 1}, then
257:quadratic residuosity problem
235:and cryptographically strong
26:
425:Given the definition of the
7:
748:J. Feigenbaum, L. Fortnow,
589:matrices with entries from
246:
10:
783:
204:be uniformly distributed.
515:matrix with entries from
620:+ 1. Once we have those
546:) we get another degree
530:are linear functions of
233:probabilistic encryption
83:. This is done so that
38:evaluating any instance
17:Random self-reducibility
660:(0), which is equal to
656:) exactly, we evaluate
278:: Given a cyclic group
150:that have a length of |
126:average-case complexity
742:Around the PCP Theorem
333:, the discrete log of
214:cryptographic problems
767:Randomized algorithms
554:, which we will call
461:has been shown to be
421:Permanent of a matrix
690:polynomial hierarchy
453:over the entries in
385:is independent of
309:of a cyclic group
305:Given a generator
271:Discrete logarithm
253:discrete logarithm
325:| }, and an
179:is picked before
154:|. In this case
65:in the domain of
774:
648:). Once we know
782:
781:
777:
776:
775:
773:
772:
771:
757:
756:
730:
722:
718:
695:
681:
636:(remember that
594:
520:
496:for some prime
494:
423:
405:
396:
341:is the integer
273:
249:
241:instance-hiding
210:
202:
196:
189:
178:
170:
164:
144:
122:
115:
105:
81:
75:
55:
46:on one or more
29:
12:
11:
5:
780:
770:
769:
755:
754:
745:
738:
729:
726:
725:
724:
720:
716:
697:
693:
692:collapses to Σ
680:
677:
592:
550:polynomial on
518:
492:
422:
419:
401:
394:
272:
269:
248:
245:
209:
206:
200:
194:
187:
176:
168:
162:
142:
120:
113:
103:
79:
73:
53:
28:
25:
9:
6:
4:
3:
2:
779:
768:
765:
764:
762:
753:
751:
746:
743:
739:
736:
732:
731:
714:
710:
706:
702:
698:
691:
687:
683:
682:
676:
674:
669:
667:
663:
659:
655:
651:
647:
644:) has degree
643:
639:
635:
634:interpolation
631:
627:
623:
619:
615:
611:
607:
603:
599:
595:
588:
584:
580:
576:
571:
569:
565:
561:
557:
553:
549:
545:
541:
537:
533:
529:
525:
521:
514:
510:
506:
501:
499:
495:
488:
484:
480:
476:
472:
468:
464:
460:
456:
452:
448:
444:
440:
436:
432:
428:
418:
416:
412:
408:
404:
399:
392:
388:
384:
381:. Therefore
380:
376:
372:
368:
364:
360:
356:
352:
348:
344:
340:
336:
332:
328:
324:
320:
316:
312:
308:
303:
301:
297:
293:
289:
285:
281:
277:
268:
266:
262:
258:
255:problem, the
254:
244:
242:
238:
234:
230:
227:The field of
225:
223:
219:
215:
205:
203:
193:
186:
182:
175:
171:
161:
157:
153:
149:
145:
137:
135:
131:
127:
123:
116:
109:
102:
98:
94:
90:
86:
82:
72:
68:
64:
60:
56:
49:
45:
41:
37:
34:
24:
22:
18:
749:
741:
734:
712:
708:
704:
679:Consequences
672:
670:
665:
661:
657:
653:
649:
645:
641:
637:
629:
625:
621:
617:
613:
609:
605:
601:
597:
590:
586:
582:
578:
574:
572:
567:
563:
562:). Clearly,
559:
555:
551:
547:
543:
539:
535:
531:
527:
523:
516:
512:
508:
507:be a random
504:
502:
497:
490:
486:
482:
478:
474:
470:
458:
454:
450:
446:
442:
438:
434:
430:
424:
414:
410:
406:
402:
397:
390:
386:
382:
378:
374:
370:
366:
362:
358:
354:
350:
346:
342:
338:
337:to the base
334:
330:
326:
322:
318:
314:
310:
306:
304:
299:
295:
291:
287:
283:
279:
275:
274:
250:
229:cryptography
226:
221:
218:one-time pad
213:
211:
198:
191:
184:
180:
173:
166:
159:
155:
151:
147:
140:
138:
133:
129:
118:
111:
107:
100:
96:
92:
88:
84:
77:
70:
66:
62:
58:
51:
43:
39:
35:
30:
20:
16:
15:
686:NP-complete
581:) for most
463:#P-complete
413:(mod |
740:S. Arora,
728:References
616:= 1,2,...,
437:) for any
222:randomness
50:instances
27:Definition
701:CoNP-hard
427:permanent
313:= {
282:of size |
265:permanent
239:. Also,
31:If for a
761:Category
715:) then Σ
632:) using
361:. Take
353:|) with
247:Examples
106:), ...,
33:function
445:matrix
298:= log |
276:Theorem
197:, ...,
165:, ...,
76:, ...,
752:, 1991
744:, 1996
684:If an
612:) for
349:< |
321:< |
317:| 0 ≤
259:, the
124:, the
95:, and
48:random
707:(log
699:If a
467:proof
400:≡ log
345:(0 ≤
662:PERM
602:PERM
585:-by-
575:PERM
540:PERM
511:-by-
503:Let
487:PERM
479:PERM
471:PERM
459:PERM
441:-by-
431:PERM
251:The
719:= Π
668:).
261:RSA
128:of
21:RSR
763::
610:kX
608:+
570:.
528:kX
526:+
409:-
407:xg
383:xg
373:=
371:xg
357:=
329:∈
136:.
723:.
721:2
717:2
713:n
711:/
709:n
705:O
696:.
694:3
673:X
666:M
664:(
658:p
654:k
652:(
650:p
646:n
642:k
640:(
638:p
630:k
628:(
626:p
622:n
618:n
614:k
606:M
604:(
598:n
593:p
591:F
587:n
583:n
579:A
577:(
568:M
564:p
560:k
558:(
556:p
552:k
548:n
544:M
542:(
536:n
532:k
524:M
519:p
517:F
513:n
509:n
505:X
498:p
493:p
491:F
483:M
481:(
475:M
473:(
465:(
455:M
451:n
447:M
443:n
439:n
435:M
433:(
415:G
411:B
403:g
398:x
395:g
391:n
387:x
379:G
375:g
367:G
363:B
359:g
355:x
351:G
347:k
343:k
339:g
335:x
331:G
327:x
323:G
319:i
315:g
311:G
307:g
300:G
296:n
292:n
288:A
284:G
280:G
201:k
199:y
195:1
192:y
188:1
185:y
183:(
181:f
177:2
174:y
169:k
167:y
163:1
160:y
156:f
152:x
148:f
143:i
141:y
134:f
130:f
121:i
119:y
114:k
112:y
110:(
108:f
104:1
101:y
99:(
97:f
93:x
89:x
87:(
85:f
80:k
78:y
74:1
71:y
67:f
63:x
54:i
52:y
44:f
40:x
36:f
19:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.