2666:). The solution proposed by Ishai and Kushilevitz uses the parallel invocations of 1-2 oblivious transfer while making use of a special model of private protocols. Later on, other solutions that are based on secret sharing were published – one by Bhavani Shankar, Kannan Srinathan, and
74:
oblivious transfer" where the user gets exactly one database element without the server getting to know which element was queried, and without the user knowing anything about the other elements that were not retrieved. The latter notion of oblivious transfer is a strengthening of
1240:
88:
Further work has revealed oblivious transfer to be a fundamental and important problem in cryptography. It is considered one of the critical problems in the field, because of the importance of the applications that can be built based on it. In particular, it is
1083:
2650:. The sender should remain oblivious of the selection made by the receiver, while the receiver cannot learn the value of the messages outside the subset of messages that he chose to obtain. The collection
2714:, it has been shown that quantum oblivious transfer cannot be implemented with unconditional security, i.e. the security of quantum oblivious transfer protocols cannot be guaranteed only from the laws of
2214:
2142:
2514:
oblivious transfer imposes an additional privacy requirement for the database: namely, that the receiver learn at most one of the database entries. On the other hand, PIR requires communication
1111:
952:
2403:
2302:
1391:
1926:
1857:
947:
1765:
864:
1308:
1106:
2452:
2804:. "Equivalence between two flavours of oblivious transfer". In Advances in Cryptology – CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 350–354. Springer, 1988
1261:
730:
605:
504:
1603:
1497:
1423:
801:
646:
584:
420:
2997:
Bhavani
Shankar, Kannan Srinathan and C. Pandu Rangan. "Alternative protocols for generalized oblivious transfer". In Proc. of ICDCN’08, LNCS 4904, pages 304–309, 2008.
97:: that is, given an implementation of oblivious transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive.
2047:
2020:
1953:
1703:
1653:
1450:
915:
690:
531:
483:
2526:
oblivious transfer has no such requirement. However, assuming single server PIR is a sufficient assumption in order to construct 1-out-of-2 Oblivious
Transfer.
753:
2988:
Yuval Ishai and Eyal
Kushilevitz. "Private simultaneous messages protocols with applications." In Proc. of ISTCS’97, IEEE Computer Society, pages 174–184, 1997.
2322:
2237:
2067:
1993:
1973:
1788:
1676:
1626:
1560:
1540:
1520:
940:
888:
780:
456:
2943:. In Edgar R.Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16, pages 818–829. ACM Press, October 2016.
2626:
Oblivious transfer is a special case of generalized oblivious transfer, which was presented by Ishai and
Kushilevitz. In that setting, the sender has a set
2611:
messages may be received simultaneously ("non-adaptively"), or they may be requested consecutively, with each request based on previous messages received.
2899:
EUROCRYPT '01 Proceedings of the
International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, pages 119–135
2574:
2960:
2588:
2538:
2877:
2554:
46:
1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin's oblivious transfer scheme is based on the
2841:
Eyal
Kushilevitz, Rafail Ostrovsky: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. FOCS 1997: 364-373
2570:
2976:
2854:
2550:
2479:
oblivious transfer protocol can be defined as a natural generalization of a 1-out-of-2 oblivious transfer protocol. Specifically, a sender has
2881:
2558:
3082:
3006:
Tamir Tassa. "Generalized oblivious transfer by secret sharing". Designs, Codes and
Cryptography, Volume 58:1, pages 11–21, January 2011.
2979:. "Oblivious transfer with adaptive queries." In Advances in Cryptology – CRYPTO ’99, volume 1666 of LNCS, pages 573–590. Springer, 1999.
2813:
2577:, proposed an efficient 1-n oblivious transfer protocol which requires roughly 4x the cost of 1-2 oblivious transfer in amortized setting.
3010:
2566:
2963:. "All-or-nothing disclosure of secrets." In Advances in Cryptology – CRYPTO ’86, volume 263 of LNCS, pages 234–238. Springer, 1986.
31:) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains
2764:. "How to exchange secrets with oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
2892:
2816:. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988.
2861:
2776:
2690:. Unfortunately it took more than ten years to be published. Even though this primitive was equivalent to what was later called
3025:
Stephen
Wiesner, "Conjugate coding", Sigact News, vol. 15, no. 1, 1983, pp. 78–88; original manuscript written circa 1970.
2327:
1078:{\displaystyle {\begin{aligned}k_{0}&=(v-x_{0})^{d}{\bmod {N}}\\k_{1}&=(v-x_{1})^{d}{\bmod {N}}\end{aligned}}}
3119:
2832:, Rafail Ostrovsky: Single Database Private Information Retrieval Implies Oblivious Transfer. EUROCRYPT 2000: 122-138
2147:
2075:
1862:
1793:
2768:
2936:
2242:
1331:
1708:
807:
2732:
1235:{\displaystyle {\begin{aligned}m'_{0}=(m_{0}+k_{0}){\bmod {N}}\\m'_{1}=(m_{1}+k_{1}){\bmod {N}}\end{aligned}}}
2742:
2507:
94:
76:
67:
2408:
2789:
1499:
and wants to send exactly one of them to Bob. Bob does not want Alice to know which one he receives.
2711:
1267:
2654:
is monotone decreasing, in the sense that it is closed under containment (i.e., if a given subset
1246:
697:
590:
489:
3036:
1975:
and the other will be a meaningless random value. However since Alice does not know the value of
1568:
1462:
786:
611:
549:
385:
3007:
203:) = 1 with overwhelming probability, which ensures that there are 4 square roots of
251:
90:
1398:
3058:
2737:
2707:
2687:
2025:
1998:
1931:
1681:
1631:
1428:
893:
2889:
8:
669:
510:
462:
3062:
2858:
735:
340:. The protocol of Even, Goldreich, and Lempel (which the authors attribute partially to
3074:
3048:
2307:
2222:
2052:
1978:
1958:
1773:
1661:
1611:
1545:
1525:
1505:
925:
873:
765:
441:
323:, and wants to ensure that the receiver only learns one. Bob, the receiver, has a bit
2788:
S. Even, O. Goldreich, and A. Lempel, "A Randomized
Protocol for Signing Contracts",
290:
3078:
2956:
2801:
2584:
82:
3066:
2761:
2542:
266:
129:
105:
In Rabin's oblivious transfer protocol, the sender generates an RSA public modulus
39:
2537:
communication was first constructed (as a generalization of single-server PIR) by
2458:
3014:
2952:
2940:
2896:
2865:
2772:
2715:
2703:
2679:
2667:
2580:
47:
85:
showed that Rabin's oblivious transfer is equivalent to 1–2 oblivious transfer.
2934:"Efficient batched oblivious prf with applications to private set intersection"
63:
59:
2817:
32:
3113:
3070:
2885:
2562:
2495:, while the sender wants to ensure that the receiver receive only one of the
341:
2910:"A New Protocol for Conditional Disclosure of Secrets And Its Applications"
122:
20:
2932:
Vladimir
Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu (2017).
2909:
3053:
2727:
2686:
in his seminal paper "Conjugate Coding", which was the starting point of
55:
43:
309:
In a 1–2 oblivious transfer protocol, Alice the sender has two messages
2933:
2829:
344:) is general, but can be instantiated using RSA encryption as follows.
2765:
2972:
2850:
2634:
messages, and the transfer constraints are specified by a collection
2546:
2534:
2515:
2072:
She combines the two secret messages with each of the possible keys,
1605:
and sends them to Bob along with her public modulus and exponent.
42:. In this form, the sender sends a message to the receiver with
297:
has four square roots, the probability that the receiver learns
50:
cryptosystem. A more useful form of oblivious transfer called
38:
The first form of oblivious transfer was introduced in 1981 by
2766:
Scanned handwriting + typed version on eprint.iacr.org archive
2491:-th among the sender's messages, without the sender learning
2435:
2386:
2285:
2197:
2125:
1909:
1840:
1748:
1374:
1219:
1160:
1062:
1002:
847:
54:
or "1 out of 2 oblivious transfer", was developed later by
2599:
oblivious transfer, wherein the receiver obtains a set of
2702:
Protocols for oblivious transfer can be implemented with
2642:. The receiver may obtain any subset of the messages in
1502:
Alice generates an RSA key pair, comprising the modulus
2694:, Wiesner did not see its application to cryptography.
100:
2411:
2330:
2310:
2245:
2225:
2150:
2078:
2055:
2028:
2001:
1981:
1961:
1934:
1865:
1796:
1776:
1711:
1684:
1664:
1634:
1614:
1571:
1548:
1528:
1508:
1465:
1431:
1401:
1334:
1270:
1249:
1109:
950:
928:
896:
876:
810:
789:
768:
738:
700:
672:
614:
593:
552:
513:
492:
465:
444:
436:
Generate RSA key pair and send public portion to Bob
388:
3106:
Helger Lipmaa's collection of Web links on the topic
2890:
Priced Oblivious Transfer: How to Sell Digital Goods
2446:
2398:{\displaystyle k_{1-b}=(v-x_{1-b})^{d}{\bmod {N}}}
2397:
2316:
2296:
2231:
2208:
2136:
2061:
2041:
2014:
1987:
1967:
1947:
1920:
1851:
1782:
1759:
1697:
1670:
1647:
1620:
1597:
1554:
1534:
1514:
1491:
1444:
1417:
1385:
1302:
1255:
1234:
1077:
934:
909:
882:
858:
795:
774:
747:
724:
684:
640:
599:
578:
525:
498:
477:
450:
414:
144: − 1). The sender encrypts the message
2614:
3111:
2545:. More efficient constructions were proposed by
35:as to what piece (if any) has been transferred.
2209:{\displaystyle m'_{1}=(m_{1}+k_{1}){\bmod {N}}}
2137:{\displaystyle m'_{0}=(m_{0}+k_{0}){\bmod {N}}}
1995:that Bob chose, she cannot determine which of
1921:{\displaystyle k_{1}=(v-x_{1})^{d}{\bmod {N}}}
1852:{\displaystyle k_{0}=(v-x_{0})^{d}{\bmod {N}}}
285:, the receiver will have no information about
2697:
79:, in which the database is not kept private.
719:
707:
3037:"Insecurity of quantum secure computations"
2912:. In Jonathan Katz and Moti Yung, editors,
2818:Paper at ACM portal (subscription required)
2297:{\displaystyle m_{b}=(m'_{b}-k){\bmod {N}}}
1790:with both of her random values to produce:
1386:{\displaystyle m_{b}=(m'_{b}-k){\bmod {N}}}
1760:{\displaystyle v=(x_{b}+k^{e}){\bmod {N}}}
859:{\displaystyle v=(x_{b}+k^{e}){\bmod {N}}}
289:beyond the encryption of it. Since every
3052:
2487:, and the receiver wishes to receive the
304:
2792:, Volume 28, Issue 6, pg. 637–647, 1985.
2483:messages, and the receiver has an index
3112:
2506:oblivious transfer is incomparable to
1565:She also generates two random values,
2908:Sven Laur and Helger Lipmaa (2007).
2447:{\displaystyle (m_{1-b}){\bmod {N}}}
2591:further generalized this notion to
101:Rabin's oblivious transfer protocol
13:
3034:
2510:(PIR). On the one hand, 1-out-of-
2304:. However, since he does not know
66:, in order to build protocols for
14:
3131:
3100:
2918:Lecture Notes in Computer Science
2533:oblivious transfer protocol with
1628:to be either 0 or 1, and selects
942:, but Alice does not know which.
70:. It is generalized to "1 out of
2923:: 207–225. Springer, Heidelberg.
2706:. In contrast to other tasks in
2607:message collection. The set of
269:for more details). However, if
3085:from the original on 2019-07-21
3028:
3019:
3000:
2991:
2982:
2966:
2946:
2926:
2859:Oblivious Polynomial Evaluation
2662:, so are all of the subsets of
2646:that appears in the collection
250:, the receiver will be able to
214:The sender finds a square root
2902:
2871:
2844:
2835:
2822:
2807:
2795:
2782:
2755:
2733:Secure multi-party computation
2682:introduced a primitive called
2670:, and another by Tamir Tassa.
2615:Generalized oblivious transfer
2431:
2412:
2376:
2350:
2281:
2259:
2193:
2167:
2121:
2095:
1899:
1879:
1830:
1810:
1744:
1718:
1370:
1348:
1250:
1215:
1189:
1156:
1130:
1052:
1032:
992:
972:
843:
817:
790:
594:
493:
1:
2775:. Typed version available on
2748:
2743:Private information retrieval
2508:private information retrieval
2216:, and sends them both to Bob.
1658:Bob generates a random value
1303:{\displaystyle m'_{0},m'_{1}}
542:Generate two random messages
195:to the sender. Note that gcd(
95:secure multiparty computation
77:private information retrieval
68:secure multiparty computation
16:Type of cryptography protocol
1256:{\displaystyle \Rightarrow }
725:{\displaystyle b\in \{0,1\}}
600:{\displaystyle \Rightarrow }
499:{\displaystyle \Rightarrow }
179:The receiver picks a random
7:
2721:
2239:, so he is able to compute
1598:{\displaystyle x_{0},x_{1}}
1492:{\displaystyle m_{0},m_{1}}
796:{\displaystyle \Leftarrow }
641:{\displaystyle x_{0},x_{1}}
579:{\displaystyle x_{0},x_{1}}
415:{\displaystyle m_{0},m_{1}}
10:
3136:
2698:Quantum oblivious transfer
2673:
2638:of permissible subsets of
1767:, which he sends to Alice.
1099:Send both messages to Bob
870:Compute the encryption of
2790:Communications of the ACM
1542:and the private exponent
354:
352:
349:
3120:Cryptographic primitives
3071:10.1103/PhysRevA.56.1154
2712:quantum key distribution
2405:and so cannot determine
1459:Alice has two messages,
922:One of these will equal
652:Receive random messages
2828:Giovanni Di Crescenzo,
2678:In the early seventies
2463:oblivious transfer and
336:without Alice learning
2692:1–2 oblivious transfer
2448:
2399:
2318:
2298:
2233:
2210:
2138:
2063:
2043:
2016:
1989:
1969:
1949:
1922:
1853:
1784:
1761:
1699:
1672:
1649:
1622:
1599:
1556:
1536:
1522:, the public exponent
1516:
1493:
1446:
1419:
1418:{\displaystyle m'_{b}}
1387:
1314:Receive both messages
1304:
1257:
1236:
1079:
936:
911:
884:
860:
797:
776:
749:
726:
686:
642:
601:
580:
527:
500:
479:
452:
416:
327:and wishes to receive
305:1–2 oblivious transfer
257:and therefore decrypt
234:If the receiver finds
52:1–2 oblivious transfer
2658:is in the collection
2449:
2400:
2319:
2299:
2234:
2211:
2139:
2064:
2044:
2042:{\displaystyle k_{1}}
2017:
2015:{\displaystyle k_{0}}
1990:
1970:
1950:
1948:{\displaystyle k_{b}}
1923:
1854:
1785:
1762:
1700:
1698:{\displaystyle x_{b}}
1673:
1650:
1648:{\displaystyle x_{b}}
1623:
1600:
1557:
1537:
1517:
1494:
1452:he selected earlier.
1447:
1445:{\displaystyle x_{b}}
1425:since he knows which
1420:
1388:
1305:
1258:
1237:
1080:
937:
912:
910:{\displaystyle x_{b}}
885:
861:
798:
777:
750:
727:
687:
643:
602:
581:
528:
501:
480:
453:
417:
3008:Paper at openu.ac.il
2738:Zero-knowledge proof
2708:quantum cryptography
2688:quantum cryptography
2409:
2328:
2324:, he cannot compute
2308:
2243:
2223:
2148:
2076:
2053:
2026:
1999:
1979:
1959:
1932:
1863:
1794:
1774:
1709:
1682:
1662:
1632:
1612:
1569:
1546:
1526:
1506:
1463:
1429:
1399:
1332:
1268:
1247:
1107:
948:
926:
894:
874:
808:
787:
766:
736:
732:and generate random
698:
670:
612:
591:
550:
511:
490:
463:
442:
386:
380:Messages to be sent
3063:1997PhRvA..56.1154L
2522:, whereas 1-out-of-
2274:
2163:
2091:
1414:
1363:
1299:
1283:
1185:
1126:
685:{\displaystyle k,b}
537:Receive public key
526:{\displaystyle N,e}
478:{\displaystyle N,e}
3035:Lo, H.-K. (1997).
3013:2011-04-01 at the
2939:2017-07-11 at the
2895:2016-03-27 at the
2864:2017-08-12 at the
2771:2021-11-23 at the
2603:messages from the
2471:oblivious transfer
2444:
2395:
2314:
2294:
2262:
2229:
2206:
2151:
2134:
2079:
2059:
2039:
2012:
1985:
1965:
1945:
1918:
1849:
1780:
1757:
1695:
1668:
1645:
1618:
1595:
1552:
1532:
1512:
1489:
1442:
1415:
1402:
1383:
1351:
1300:
1287:
1271:
1253:
1232:
1230:
1173:
1114:
1075:
1073:
932:
917:and send to Alice
907:
880:
856:
793:
772:
748:{\displaystyle k.}
745:
722:
682:
638:
597:
576:
523:
496:
475:
448:
412:
183: modulo
125:, and an exponent
25:oblivious transfer
2777:Dousti's homepage
2575:Kolesnikov et al.
2317:{\displaystyle d}
2232:{\displaystyle k}
2062:{\displaystyle k}
1988:{\displaystyle b}
1968:{\displaystyle k}
1955:will be equal to
1783:{\displaystyle v}
1678:uses it to blind
1671:{\displaystyle k}
1621:{\displaystyle b}
1555:{\displaystyle d}
1535:{\displaystyle e}
1515:{\displaystyle N}
1456:
1455:
1395:Bob decrypts the
935:{\displaystyle k}
883:{\displaystyle k}
775:{\displaystyle v}
451:{\displaystyle d}
291:quadratic residue
160:The sender sends
3127:
3094:
3093:
3091:
3090:
3056:
3054:quant-ph/9611031
3047:(2): 1154–1162.
3032:
3026:
3023:
3017:
3004:
2998:
2995:
2989:
2986:
2980:
2970:
2964:
2961:Jean-Marc Robert
2950:
2944:
2930:
2924:
2906:
2900:
2875:
2869:
2848:
2842:
2839:
2833:
2826:
2820:
2811:
2805:
2799:
2793:
2786:
2780:
2762:Michael O. Rabin
2759:
2543:Rafail Ostrovsky
2539:Eyal Kushilevitz
2453:
2451:
2450:
2445:
2443:
2442:
2430:
2429:
2404:
2402:
2401:
2396:
2394:
2393:
2384:
2383:
2374:
2373:
2346:
2345:
2323:
2321:
2320:
2315:
2303:
2301:
2300:
2295:
2293:
2292:
2270:
2255:
2254:
2238:
2236:
2235:
2230:
2215:
2213:
2212:
2207:
2205:
2204:
2192:
2191:
2179:
2178:
2159:
2143:
2141:
2140:
2135:
2133:
2132:
2120:
2119:
2107:
2106:
2087:
2068:
2066:
2065:
2060:
2048:
2046:
2045:
2040:
2038:
2037:
2021:
2019:
2018:
2013:
2011:
2010:
1994:
1992:
1991:
1986:
1974:
1972:
1971:
1966:
1954:
1952:
1951:
1946:
1944:
1943:
1927:
1925:
1924:
1919:
1917:
1916:
1907:
1906:
1897:
1896:
1875:
1874:
1858:
1856:
1855:
1850:
1848:
1847:
1838:
1837:
1828:
1827:
1806:
1805:
1789:
1787:
1786:
1781:
1766:
1764:
1763:
1758:
1756:
1755:
1743:
1742:
1730:
1729:
1704:
1702:
1701:
1696:
1694:
1693:
1677:
1675:
1674:
1669:
1654:
1652:
1651:
1646:
1644:
1643:
1627:
1625:
1624:
1619:
1604:
1602:
1601:
1596:
1594:
1593:
1581:
1580:
1561:
1559:
1558:
1553:
1541:
1539:
1538:
1533:
1521:
1519:
1518:
1513:
1498:
1496:
1495:
1490:
1488:
1487:
1475:
1474:
1451:
1449:
1448:
1443:
1441:
1440:
1424:
1422:
1421:
1416:
1410:
1392:
1390:
1389:
1384:
1382:
1381:
1359:
1344:
1343:
1309:
1307:
1306:
1301:
1295:
1279:
1262:
1260:
1259:
1254:
1241:
1239:
1238:
1233:
1231:
1227:
1226:
1214:
1213:
1201:
1200:
1181:
1168:
1167:
1155:
1154:
1142:
1141:
1122:
1084:
1082:
1081:
1076:
1074:
1070:
1069:
1060:
1059:
1050:
1049:
1024:
1023:
1010:
1009:
1000:
999:
990:
989:
964:
963:
941:
939:
938:
933:
916:
914:
913:
908:
906:
905:
889:
887:
886:
881:
865:
863:
862:
857:
855:
854:
842:
841:
829:
828:
802:
800:
799:
794:
781:
779:
778:
773:
754:
752:
751:
746:
731:
729:
728:
723:
691:
689:
688:
683:
647:
645:
644:
639:
637:
636:
624:
623:
606:
604:
603:
598:
585:
583:
582:
577:
575:
574:
562:
561:
532:
530:
529:
524:
505:
503:
502:
497:
484:
482:
481:
476:
457:
455:
454:
449:
421:
419:
418:
413:
411:
410:
398:
397:
347:
346:
267:Rabin encryption
230:to the receiver.
176:to the receiver.
140: − 1)(
130:relatively prime
40:Michael O. Rabin
3135:
3134:
3130:
3129:
3128:
3126:
3125:
3124:
3110:
3109:
3103:
3098:
3097:
3088:
3086:
3033:
3029:
3024:
3020:
3015:Wayback Machine
3005:
3001:
2996:
2992:
2987:
2983:
2971:
2967:
2953:Gilles Brassard
2951:
2947:
2941:Wayback Machine
2931:
2927:
2907:
2903:
2897:Wayback Machine
2876:
2872:
2866:Wayback Machine
2849:
2845:
2840:
2836:
2827:
2823:
2812:
2808:
2800:
2796:
2787:
2783:
2773:Wayback Machine
2760:
2756:
2751:
2724:
2716:quantum physics
2704:quantum systems
2700:
2680:Stephen Wiesner
2676:
2668:C. Pandu Rangan
2617:
2473:
2438:
2434:
2419:
2415:
2410:
2407:
2406:
2389:
2385:
2379:
2375:
2363:
2359:
2335:
2331:
2329:
2326:
2325:
2309:
2306:
2305:
2288:
2284:
2266:
2250:
2246:
2244:
2241:
2240:
2224:
2221:
2220:
2200:
2196:
2187:
2183:
2174:
2170:
2155:
2149:
2146:
2145:
2128:
2124:
2115:
2111:
2102:
2098:
2083:
2077:
2074:
2073:
2054:
2051:
2050:
2033:
2029:
2027:
2024:
2023:
2006:
2002:
2000:
1997:
1996:
1980:
1977:
1976:
1960:
1957:
1956:
1939:
1935:
1933:
1930:
1929:
1912:
1908:
1902:
1898:
1892:
1888:
1870:
1866:
1864:
1861:
1860:
1843:
1839:
1833:
1829:
1823:
1819:
1801:
1797:
1795:
1792:
1791:
1775:
1772:
1771:
1770:Alice combines
1751:
1747:
1738:
1734:
1725:
1721:
1710:
1707:
1706:
1689:
1685:
1683:
1680:
1679:
1663:
1660:
1659:
1639:
1635:
1633:
1630:
1629:
1613:
1610:
1609:
1589:
1585:
1576:
1572:
1570:
1567:
1566:
1547:
1544:
1543:
1527:
1524:
1523:
1507:
1504:
1503:
1483:
1479:
1470:
1466:
1464:
1461:
1460:
1436:
1432:
1430:
1427:
1426:
1406:
1400:
1397:
1396:
1377:
1373:
1355:
1339:
1335:
1333:
1330:
1329:
1291:
1275:
1269:
1266:
1265:
1248:
1245:
1244:
1229:
1228:
1222:
1218:
1209:
1205:
1196:
1192:
1177:
1170:
1169:
1163:
1159:
1150:
1146:
1137:
1133:
1118:
1110:
1108:
1105:
1104:
1072:
1071:
1065:
1061:
1055:
1051:
1045:
1041:
1025:
1019:
1015:
1012:
1011:
1005:
1001:
995:
991:
985:
981:
965:
959:
955:
951:
949:
946:
945:
927:
924:
923:
901:
897:
895:
892:
891:
875:
872:
871:
850:
846:
837:
833:
824:
820:
809:
806:
805:
788:
785:
784:
767:
764:
763:
737:
734:
733:
699:
696:
695:
671:
668:
667:
632:
628:
619:
615:
613:
610:
609:
592:
589:
588:
570:
566:
557:
553:
551:
548:
547:
512:
509:
508:
491:
488:
487:
464:
461:
460:
443:
440:
439:
406:
402:
393:
389:
387:
384:
383:
335:
322:
315:
307:
281: mod
222: mod
207: mod
191: mod
172: mod
103:
17:
12:
11:
5:
3133:
3123:
3122:
3108:
3107:
3102:
3101:External links
3099:
3096:
3095:
3027:
3018:
2999:
2990:
2981:
2965:
2957:Claude Crépeau
2945:
2925:
2901:
2878:William Aiello
2870:
2843:
2834:
2821:
2806:
2802:Claude Crépeau
2794:
2781:
2753:
2752:
2750:
2747:
2746:
2745:
2740:
2735:
2730:
2723:
2720:
2699:
2696:
2675:
2672:
2616:
2613:
2555:William Aiello
2472:
2457:
2456:
2455:
2441:
2437:
2433:
2428:
2425:
2422:
2418:
2414:
2392:
2388:
2382:
2378:
2372:
2369:
2366:
2362:
2358:
2355:
2352:
2349:
2344:
2341:
2338:
2334:
2313:
2291:
2287:
2283:
2280:
2277:
2273:
2269:
2265:
2261:
2258:
2253:
2249:
2228:
2217:
2203:
2199:
2195:
2190:
2186:
2182:
2177:
2173:
2169:
2166:
2162:
2158:
2154:
2131:
2127:
2123:
2118:
2114:
2110:
2105:
2101:
2097:
2094:
2090:
2086:
2082:
2070:
2058:
2036:
2032:
2009:
2005:
1984:
1964:
1942:
1938:
1915:
1911:
1905:
1901:
1895:
1891:
1887:
1884:
1881:
1878:
1873:
1869:
1846:
1842:
1836:
1832:
1826:
1822:
1818:
1815:
1812:
1809:
1804:
1800:
1779:
1768:
1754:
1750:
1746:
1741:
1737:
1733:
1728:
1724:
1720:
1717:
1714:
1692:
1688:
1667:
1656:
1642:
1638:
1617:
1606:
1592:
1588:
1584:
1579:
1575:
1563:
1551:
1531:
1511:
1500:
1486:
1482:
1478:
1473:
1469:
1454:
1453:
1439:
1435:
1413:
1409:
1405:
1393:
1380:
1376:
1372:
1369:
1366:
1362:
1358:
1354:
1350:
1347:
1342:
1338:
1327:
1325:
1323:
1321:
1319:
1316:
1315:
1312:
1310:
1298:
1294:
1290:
1286:
1282:
1278:
1274:
1263:
1252:
1242:
1225:
1221:
1217:
1212:
1208:
1204:
1199:
1195:
1191:
1188:
1184:
1180:
1176:
1172:
1171:
1166:
1162:
1158:
1153:
1149:
1145:
1140:
1136:
1132:
1129:
1125:
1121:
1117:
1113:
1112:
1102:
1100:
1096:
1095:
1093:
1091:
1089:
1087:
1085:
1068:
1064:
1058:
1054:
1048:
1044:
1040:
1037:
1034:
1031:
1028:
1026:
1022:
1018:
1014:
1013:
1008:
1004:
998:
994:
988:
984:
980:
977:
974:
971:
968:
966:
962:
958:
954:
953:
943:
931:
919:
918:
904:
900:
879:
868:
866:
853:
849:
845:
840:
836:
832:
827:
823:
819:
816:
813:
803:
792:
782:
771:
761:
759:
756:
755:
744:
741:
721:
718:
715:
712:
709:
706:
703:
692:
681:
678:
675:
665:
663:
661:
659:
657:
654:
653:
650:
648:
635:
631:
627:
622:
618:
607:
596:
586:
573:
569:
565:
560:
556:
545:
543:
539:
538:
535:
533:
522:
519:
516:
506:
495:
485:
474:
471:
468:
458:
447:
437:
433:
432:
430:
428:
426:
424:
422:
409:
405:
401:
396:
392:
381:
377:
376:
373:
370:
367:
364:
361:
357:
356:
353:
351:
331:
320:
313:
306:
303:
232:
231:
212:
177:
102:
99:
83:Claude Crépeau
64:Abraham Lempel
60:Oded Goldreich
15:
9:
6:
4:
3:
2:
3132:
3121:
3118:
3117:
3115:
3105:
3104:
3084:
3080:
3076:
3072:
3068:
3064:
3060:
3055:
3050:
3046:
3042:
3038:
3031:
3022:
3016:
3012:
3009:
3003:
2994:
2985:
2978:
2974:
2969:
2962:
2958:
2954:
2949:
2942:
2938:
2935:
2929:
2922:
2919:
2915:
2911:
2905:
2898:
2894:
2891:
2887:
2886:Omer Reingold
2883:
2879:
2874:
2867:
2863:
2860:
2856:
2852:
2847:
2838:
2831:
2825:
2819:
2815:
2810:
2803:
2798:
2791:
2785:
2778:
2774:
2770:
2767:
2763:
2758:
2754:
2744:
2741:
2739:
2736:
2734:
2731:
2729:
2726:
2725:
2719:
2717:
2713:
2709:
2705:
2695:
2693:
2689:
2685:
2681:
2671:
2669:
2665:
2661:
2657:
2653:
2649:
2645:
2641:
2637:
2633:
2629:
2625:
2621:
2612:
2610:
2606:
2602:
2598:
2594:
2590:
2586:
2582:
2578:
2576:
2572:
2571:Helger Lipmaa
2568:
2564:
2563:Omer Reingold
2560:
2556:
2552:
2548:
2544:
2540:
2536:
2532:
2527:
2525:
2521:
2517:
2513:
2509:
2505:
2500:
2498:
2494:
2490:
2486:
2482:
2478:
2470:
2466:
2462:
2439:
2426:
2423:
2420:
2416:
2390:
2380:
2370:
2367:
2364:
2360:
2356:
2353:
2347:
2342:
2339:
2336:
2332:
2311:
2289:
2278:
2275:
2271:
2267:
2263:
2256:
2251:
2247:
2226:
2218:
2201:
2188:
2184:
2180:
2175:
2171:
2164:
2160:
2156:
2152:
2129:
2116:
2112:
2108:
2103:
2099:
2092:
2088:
2084:
2080:
2071:
2056:
2034:
2030:
2007:
2003:
1982:
1962:
1940:
1936:
1913:
1903:
1893:
1889:
1885:
1882:
1876:
1871:
1867:
1844:
1834:
1824:
1820:
1816:
1813:
1807:
1802:
1798:
1777:
1769:
1752:
1739:
1735:
1731:
1726:
1722:
1715:
1712:
1705:by computing
1690:
1686:
1665:
1657:
1640:
1636:
1615:
1607:
1590:
1586:
1582:
1577:
1573:
1564:
1549:
1529:
1509:
1501:
1484:
1480:
1476:
1471:
1467:
1458:
1457:
1437:
1433:
1411:
1407:
1403:
1394:
1378:
1367:
1364:
1360:
1356:
1352:
1345:
1340:
1336:
1328:
1326:
1324:
1322:
1320:
1318:
1317:
1313:
1311:
1296:
1292:
1288:
1284:
1280:
1276:
1272:
1264:
1243:
1223:
1210:
1206:
1202:
1197:
1193:
1186:
1182:
1178:
1174:
1164:
1151:
1147:
1143:
1138:
1134:
1127:
1123:
1119:
1115:
1103:
1101:
1098:
1097:
1094:
1092:
1090:
1088:
1086:
1066:
1056:
1046:
1042:
1038:
1035:
1029:
1027:
1020:
1016:
1006:
996:
986:
982:
978:
975:
969:
967:
960:
956:
944:
929:
921:
920:
902:
898:
890:, blind with
877:
869:
867:
851:
838:
834:
830:
825:
821:
814:
811:
804:
783:
769:
762:
760:
758:
757:
742:
739:
716:
713:
710:
704:
701:
693:
679:
676:
673:
666:
664:
662:
660:
658:
656:
655:
651:
649:
633:
629:
625:
620:
616:
608:
587:
571:
567:
563:
558:
554:
546:
544:
541:
540:
536:
534:
520:
517:
514:
507:
486:
472:
469:
466:
459:
445:
438:
435:
434:
431:
429:
427:
425:
423:
407:
403:
399:
394:
390:
382:
379:
378:
374:
371:
368:
365:
362:
359:
358:
348:
345:
343:
342:Silvio Micali
339:
334:
330:
326:
319:
312:
302:
300:
296:
292:
288:
284:
280:
276:
272:
268:
264:
260:
256:
253:
249:
245:
241:
237:
229:
225:
221:
217:
213:
210:
206:
202:
198:
194:
190:
186:
182:
178:
175:
171:
167:
163:
159:
158:
157:
155:
151:
147:
143:
139:
135:
131:
128:
124:
123:prime numbers
120:
116:
112:
108:
98:
96:
92:
86:
84:
80:
78:
73:
69:
65:
61:
57:
53:
49:
45:
41:
36:
34:
30:
26:
22:
3087:. Retrieved
3044:
3041:Phys. Rev. A
3040:
3030:
3021:
3002:
2993:
2984:
2977:Benny Pinkas
2968:
2948:
2928:
2920:
2917:
2913:
2904:
2873:
2855:Benny Pinkas
2846:
2837:
2824:
2809:
2797:
2784:
2757:
2701:
2691:
2684:multiplexing
2683:
2677:
2663:
2659:
2655:
2651:
2647:
2643:
2639:
2635:
2631:
2627:
2623:
2619:
2618:
2608:
2604:
2600:
2596:
2592:
2579:
2551:Benny Pinkas
2530:
2528:
2523:
2519:
2511:
2503:
2501:
2496:
2492:
2488:
2484:
2480:
2476:
2474:
2468:
2464:
2460:
2049:is equal to
337:
332:
328:
324:
317:
310:
308:
298:
294:
286:
282:
278:
274:
270:
262:
258:
254:
247:
243:
239:
235:
233:
227:
223:
219:
215:
208:
204:
200:
196:
192:
188:
184:
180:
173:
169:
165:
161:
153:
149:
145:
141:
137:
133:
126:
118:
114:
110:
106:
104:
87:
81:
71:
51:
37:
28:
24:
21:cryptography
18:
2882:Yuval Ishai
2728:k-anonymity
2573:. In 2017,
2559:Yuval Ishai
2475:A 1-out-of-
261:to recover
238:is neither
56:Shimon Even
44:probability
3089:2019-07-21
2830:Tal Malkin
2814:Joe Kilian
2749:References
2499:messages.
2219:Bob knows
1608:Bob picks
226:and sends
187:and sends
121:are large
2973:Moni Naor
2868:31st STOC
2851:Moni Naor
2567:Sven Laur
2547:Moni Naor
2535:sublinear
2529:1-out-of-
2516:sublinear
2502:1-out-of-
2459:1-out-of-
2424:−
2368:−
2357:−
2340:−
2276:−
1886:−
1817:−
1365:−
1251:⇒
1039:−
979:−
791:⇐
705:∈
595:⇒
494:⇒
375:Calculus
360:Calculus
33:oblivious
3114:Category
3083:Archived
3079:17813922
3011:Archived
2937:Archived
2893:Archived
2862:Archived
2857:(1990).
2769:Archived
2722:See also
2581:Brassard
2467:-out-of-
2272:′
2161:′
2089:′
1412:′
1361:′
1297:′
1281:′
1183:′
1124:′
301:is 1/2.
91:complete
3059:Bibcode
2888:(2001)
2710:, like
2674:Origins
2585:Crépeau
1928:. Now
694:Choose
372:Secret
369:Public
366:Public
363:Secret
293:modulo
246:modulo
3077:
2589:Robert
350:Alice
252:factor
168:, and
113:where
62:, and
3075:S2CID
3049:arXiv
265:(see
242:nor −
23:, an
2975:and
2959:and
2921:4521
2914:ACNS
2884:and
2853:and
2587:and
2569:and
2561:and
2549:and
2541:and
2144:and
2022:and
1859:and
355:Bob
316:and
277:or −
152:mod
134:λ(N)
117:and
93:for
3067:doi
2630:of
2518:in
2436:mod
2387:mod
2286:mod
2198:mod
2126:mod
1910:mod
1841:mod
1749:mod
1375:mod
1220:mod
1161:mod
1063:mod
1003:mod
848:mod
273:is
218:of
148:as
136:= (
132:to
48:RSA
19:In
3116::
3081:.
3073:.
3065:.
3057:.
3045:56
3043:.
3039:.
2955:,
2916:,
2880:,
2718:.
2583:,
2565:,
2557:,
2553:,
164:,
156:.
111:pq
58:,
29:OT
3092:.
3069::
3061::
3051::
2779:.
2664:B
2660:A
2656:B
2652:A
2648:A
2644:U
2640:U
2636:A
2632:n
2628:U
2624:n
2622:-
2620:k
2609:k
2605:n
2601:k
2597:n
2595:-
2593:k
2531:n
2524:n
2520:n
2512:n
2504:n
2497:n
2493:i
2489:i
2485:i
2481:n
2477:n
2469:n
2465:k
2461:n
2454:.
2440:N
2432:)
2427:b
2421:1
2417:m
2413:(
2391:N
2381:d
2377:)
2371:b
2365:1
2361:x
2354:v
2351:(
2348:=
2343:b
2337:1
2333:k
2312:d
2290:N
2282:)
2279:k
2268:b
2264:m
2260:(
2257:=
2252:b
2248:m
2227:k
2202:N
2194:)
2189:1
2185:k
2181:+
2176:1
2172:m
2168:(
2165:=
2157:1
2153:m
2130:N
2122:)
2117:0
2113:k
2109:+
2104:0
2100:m
2096:(
2093:=
2085:0
2081:m
2069:.
2057:k
2035:1
2031:k
2008:0
2004:k
1983:b
1963:k
1941:b
1937:k
1914:N
1904:d
1900:)
1894:1
1890:x
1883:v
1880:(
1877:=
1872:1
1868:k
1845:N
1835:d
1831:)
1825:0
1821:x
1814:v
1811:(
1808:=
1803:0
1799:k
1778:v
1753:N
1745:)
1740:e
1736:k
1732:+
1727:b
1723:x
1719:(
1716:=
1713:v
1691:b
1687:x
1666:k
1655:.
1641:b
1637:x
1616:b
1591:1
1587:x
1583:,
1578:0
1574:x
1562:.
1550:d
1530:e
1510:N
1485:1
1481:m
1477:,
1472:0
1468:m
1438:b
1434:x
1408:b
1404:m
1379:N
1371:)
1368:k
1357:b
1353:m
1349:(
1346:=
1341:b
1337:m
1293:1
1289:m
1285:,
1277:0
1273:m
1224:N
1216:)
1211:1
1207:k
1203:+
1198:1
1194:m
1190:(
1187:=
1179:1
1175:m
1165:N
1157:)
1152:0
1148:k
1144:+
1139:0
1135:m
1131:(
1128:=
1120:0
1116:m
1067:N
1057:d
1053:)
1047:1
1043:x
1036:v
1033:(
1030:=
1021:1
1017:k
1007:N
997:d
993:)
987:0
983:x
976:v
973:(
970:=
961:0
957:k
930:k
903:b
899:x
878:k
852:N
844:)
839:e
835:k
831:+
826:b
822:x
818:(
815:=
812:v
770:v
743:.
740:k
720:}
717:1
714:,
711:0
708:{
702:b
680:b
677:,
674:k
634:1
630:x
626:,
621:0
617:x
572:1
568:x
564:,
559:0
555:x
521:e
518:,
515:N
473:e
470:,
467:N
446:d
408:1
404:m
400:,
395:0
391:m
338:b
333:b
329:m
325:b
321:1
318:m
314:0
311:m
299:m
295:N
287:m
283:N
279:x
275:x
271:y
263:m
259:m
255:N
248:N
244:x
240:x
236:y
228:y
224:N
220:x
216:y
211:.
209:N
205:x
201:N
199:,
197:x
193:N
189:x
185:N
181:x
174:N
170:m
166:e
162:N
154:N
150:m
146:m
142:q
138:p
127:e
119:q
115:p
109:=
107:N
72:n
27:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.