2853:
1862:
2068:
1588:
1442:
1542:
668:, does not hold in this case, new assumptions are needed to build cryptography in symmetric bilinear groups. The DLIN assumption is a modification of Diffie-Hellman type assumptions to thwart the above attack.
994:
1131:
532:
2282:
112:
887:
365:
2833:
2663:
296:
1857:{\displaystyle m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x})^{a}\cdot (v^{y})^{b})^{-1}.}
620:
1911:
1287:
1580:
146:
2275:
571:
1919:
206:
1313:
655:
415:
1241:
1188:
1161:
1017:
226:
173:
834:
2501:
2137:
1037:
808:
784:
764:
744:
724:
694:
385:
258:
2366:
2881:
2330:
2268:
2361:
303:
32:
2158:
1321:
2115:. They prove this signature fulfills the additional requirements of unforgeability, anonymity, and traceability required of a group signature.
2886:
2166:
2153:
Since its definition in 2004, the
Decision Linear assumption has seen a variety of other applications. These include the construction of a
2891:
1191:
1454:
2494:
2291:
24:
895:
1045:
2074:
2712:
2643:
2438:
1548:
423:
2325:
2487:
2154:
2828:
2783:
2586:
2454:
2119:
28:
2356:
2707:
2335:
2162:
237:
36:
2206:
2108:
2823:
2433:
787:
49:
2813:
2803:
2658:
665:
839:
309:
2808:
2798:
2591:
2551:
2544:
2529:
2524:
2459:
1208:
2596:
2539:
2856:
2702:
2648:
2320:
2310:
2305:
263:
2818:
2742:
2428:
2104:
704:
576:
2571:
1870:
1246:
2687:
2671:
2613:
2351:
2252:
2235:
661:
2063:{\displaystyle m'=m\cdot h^{a+b}\cdot (h^{a}\cdot h^{b})^{-1}=m\cdot (h^{a+b}\cdot h^{-a-b})=m.}
117:
2747:
2737:
2603:
2112:
2077:
540:
178:
2682:
2534:
2387:
1292:
625:
390:
1214:
1166:
1139:
1002:
211:
151:
2422:
2418:
2412:
2408:
2223:
Efficient pseudorandom functions from the decisional linear assumption and weaker variants
2118:
Their proof relies on not only the DLIN assumption but also another assumption called the
2089:
1554:
813:
2193:
1211:
scheme by analogy to ElGamal encryption. In this scheme, a public key is the generators
2757:
2677:
2633:
2576:
2561:
2464:
2382:
2122:
2093:
1022:
793:
769:
749:
729:
709:
679:
370:
243:
2875:
2838:
2793:
2752:
2732:
2623:
2581:
2556:
2260:
2222:
2142:
2788:
2628:
2618:
2608:
2566:
2510:
2218:
701:
697:
299:
2103:
Their protocol first uses linear encryption in order to define a special type of
2767:
2315:
2092:. The signatures are called "short group signatures" because, with a standard
2727:
2697:
2692:
2653:
2717:
2248:
2189:
40:
1437:{\displaystyle c:=(c_{1},\,c_{2},\,c_{3})=(u^{a},\,v^{b},\,m\cdot h^{a+b})}
2762:
2722:
2638:
31:. In particular, the DLIN assumption is useful in settings where the
1448:
To decrypt the ciphertext, the private key can be used to compute
2236:
Bilinear
Entropy Expansion from the Decisional Linear Assumption
2097:
2483:
2264:
1537:{\displaystyle m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}.}
989:{\displaystyle D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).}
660:
Since this cryptographic assumption, essential to building
1126:{\displaystyle D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).}
2088:
Boneh, Boyen, and
Shacham also use DLIN in a scheme for
527:{\displaystyle e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).}
2664:
Cryptographically secure pseudorandom number generator
2125:
1922:
1873:
1591:
1557:
1457:
1324:
1295:
1249:
1217:
1169:
1142:
1048:
1025:
1005:
898:
842:
816:
796:
772:
752:
732:
712:
682:
628:
579:
543:
426:
393:
373:
312:
302:. This map gives an efficient algorithm to solve the
266:
246:
214:
181:
154:
120:
52:
2475:
39:). The Decision Linear assumption was introduced by
2776:
2517:
2447:
2401:
2375:
2344:
2298:
2131:
2062:
1905:
1856:
1574:
1536:
1436:
1307:
1281:
1235:
1182:
1155:
1125:
1031:
1011:
988:
881:
828:
802:
778:
758:
738:
718:
688:
649:
614:
565:
526:
409:
379:
359:
290:
252:
220:
200:
167:
140:
106:
1582:when both parties follow the protocol, note that
46:Informally the DLIN assumption states that given
2111:is applied to transform the proof system into a
417:. This follows by using the pairing: note that
2495:
2276:
1243:. The private key is two exponents such that
8:
876:
843:
175:random exponents, it is hard to distinguish
1315:with the public key to create a ciphertext
1136:The Decision Linear assumption states that
107:{\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}
2502:
2488:
2480:
2476:
2283:
2269:
2261:
33:decisional Diffie–Hellman assumption
2247:Benoît Libert, Thomas Peters, Marc Joye,
2124:
2080:assuming that the DLIN assumption holds.
2033:
2014:
1989:
1979:
1966:
1944:
1921:
1891:
1878:
1872:
1842:
1832:
1822:
1806:
1796:
1771:
1749:
1739:
1729:
1713:
1703:
1678:
1656:
1646:
1641:
1628:
1623:
1607:
1590:
1556:
1522:
1512:
1507:
1494:
1489:
1473:
1456:
1419:
1408:
1399:
1394:
1385:
1366:
1361:
1352:
1347:
1338:
1323:
1294:
1267:
1254:
1248:
1216:
1174:
1168:
1147:
1141:
1113:
1104:
1099:
1090:
1085:
1078:
1071:
1053:
1047:
1024:
1004:
968:
963:
954:
949:
940:
935:
928:
921:
903:
897:
866:
859:
852:
841:
815:
795:
771:
751:
731:
711:
681:
627:
603:
590:
578:
554:
542:
509:
481:
450:
437:
425:
398:
392:
372:
350:
341:
336:
327:
322:
311:
265:
245:
213:
208:from an independent random group element
186:
180:
161:
153:
134:
127:
119:
95:
90:
81:
76:
69:
62:
51:
1547:To check that this encryption scheme is
882:{\displaystyle \{1,\,2,\,\dots ,\,p-1\}}
2234:Lucas Kowalczyk, Allison Bishop Lewko:
2177:
1019:be another uniformly random element of
360:{\displaystyle (g,\,g^{a},\,g^{b},\,h)}
35:does not hold (as is often the case in
2096:, they can be represented in only 250
2185:
2183:
2181:
2167:non-interactive zero-knowledge proofs
7:
1207:Boneh, Boyen, and Shacham define a
2882:Computational hardness assumptions
2292:Computational hardness assumptions
14:
2139:-strong Diffie-Hellman assumption
1192:computationally indistinguishable
25:computational hardness assumption
21:Decision Linear (DLIN) assumption
16:Computational hardness assumption
2852:
2851:
2331:Decisional composite residuosity
2165:scheme, and a special class of
1289:. Encryption combines a message
836:be uniformly random elements of
291:{\displaystyle e:G\times G\to T}
2192:, Xavier Boyen, Hovav Shacham:
2713:Information-theoretic security
2048:
2007:
1986:
1959:
1839:
1829:
1815:
1803:
1789:
1786:
1746:
1736:
1722:
1710:
1696:
1693:
1653:
1616:
1519:
1482:
1431:
1378:
1372:
1331:
1117:
1062:
1039:. Define another distribution
980:
912:
644:
632:
615:{\displaystyle e(g^{a},g^{b})}
609:
583:
518:
496:
478:
465:
456:
430:
354:
313:
282:
101:
53:
1:
2253:Compactly Hiding Linear Spans
1906:{\displaystyle u^{x}=v^{y}=h}
1282:{\displaystyle u^{x}=v^{y}=h}
2367:Computational Diffie–Hellman
2887:Elliptic curve cryptography
2829:Message authentication code
2784:Cryptographic hash function
2587:Cryptographic hash function
2455:Exponential time hypothesis
260:is equipped with a pairing
29:elliptic curve cryptography
2908:
2892:Pairing-based cryptography
2708:Harvest now, decrypt later
2196:. CRYPTO 2004: 41–55
2163:attribute-based encryption
2159:Naor-Reingold construction
238:pairing-based cryptography
148:random group elements and
37:pairing-based cryptography
2847:
2824:Post-quantum cryptography
2479:
2465:Planted clique conjecture
2434:Ring learning with errors
2362:Decisional Diffie–Hellman
2255:. ASIACRYPT 2015: 681-707
1867:Then using the fact that
367:, it is easy to check if
304:decisional Diffie-Hellman
141:{\displaystyle u,\,v,\,h}
2814:Quantum key distribution
2804:Authenticated encryption
2659:Random number generation
2073:Further, this scheme is
889:. Define a distribution
566:{\displaystyle h=g^{ab}}
2809:Public-key cryptography
2799:Symmetric-key algorithm
2592:Key derivation function
2552:Cryptographic primitive
2545:Authentication protocol
2530:Outline of cryptography
2525:History of cryptography
2460:Unique games conjecture
2409:Shortest vector problem
2383:External Diffie–Hellman
201:{\displaystyle h^{x+y}}
2597:Secure Hash Algorithms
2540:Cryptographic protocol
2439:Short integer solution
2419:Closest vector problem
2238:. CRYPTO 2015: 524-541
2217:Allison Bishop Lewko,
2207:Intro to Bilinear Maps
2194:Short Group Signatures
2141:. It is proven in the
2133:
2084:Short group signatures
2064:
1907:
1858:
1576:
1538:
1438:
1309:
1308:{\displaystyle m\in G}
1283:
1237:
1184:
1157:
1127:
1033:
1013:
990:
883:
830:
804:
780:
760:
740:
720:
690:
651:
650:{\displaystyle e(g,h)}
616:
567:
528:
411:
410:{\displaystyle g^{ab}}
381:
361:
306:problem. Given input
292:
254:
222:
202:
169:
142:
108:
43:, Boyen, and Shacham.
2703:End-to-end encryption
2649:Cryptojacking malware
2326:Quadratic residuosity
2306:Integer factorization
2157:that generalizes the
2155:pseudorandom function
2134:
2109:Fiat–Shamir heuristic
2065:
1908:
1859:
1577:
1539:
1439:
1310:
1284:
1238:
1236:{\displaystyle u,v,h}
1209:public key encryption
1185:
1183:{\displaystyle D_{2}}
1158:
1156:{\displaystyle D_{1}}
1128:
1034:
1014:
1012:{\displaystyle \eta }
991:
884:
831:
805:
781:
761:
741:
721:
691:
652:
617:
568:
529:
412:
382:
362:
293:
255:
223:
221:{\displaystyle \eta }
203:
170:
168:{\displaystyle x,\,y}
143:
109:
2819:Quantum cryptography
2743:Trusted timestamping
2429:Learning with errors
2123:
2105:zero-knowledge proof
1920:
1871:
1589:
1575:{\displaystyle m'=m}
1555:
1455:
1322:
1293:
1247:
1215:
1167:
1140:
1046:
1023:
1003:
896:
840:
814:
794:
786:be uniformly random
770:
750:
730:
710:
680:
626:
577:
541:
424:
391:
371:
310:
264:
244:
212:
179:
152:
118:
50:
2572:Cryptographic nonce
2225:. CCS 2009: 112-120
2143:random oracle model
1651:
1633:
1517:
1499:
829:{\displaystyle a,b}
2688:Subliminal channel
2672:Pseudorandom noise
2614:Key (cryptography)
2352:Discrete logarithm
2336:Higher residuosity
2205:John Bethencourt:
2149:Other applications
2129:
2060:
1903:
1854:
1637:
1619:
1572:
1534:
1503:
1485:
1434:
1305:
1279:
1233:
1180:
1153:
1123:
1029:
1009:
986:
879:
826:
800:
776:
756:
736:
716:
686:
662:ElGamal encryption
647:
612:
573:, then the values
563:
524:
407:
377:
357:
288:
250:
218:
198:
165:
138:
104:
2869:
2868:
2865:
2864:
2748:Key-based routing
2738:Trapdoor function
2604:Digital signature
2473:
2472:
2448:Non-cryptographic
2132:{\displaystyle q}
2113:digital signature
1203:Linear encryption
1032:{\displaystyle G}
803:{\displaystyle G}
779:{\displaystyle h}
759:{\displaystyle v}
739:{\displaystyle u}
719:{\displaystyle p}
689:{\displaystyle G}
672:Formal definition
380:{\displaystyle h}
253:{\displaystyle G}
2899:
2855:
2854:
2683:Insecure channel
2535:Classical cipher
2504:
2497:
2490:
2481:
2477:
2388:Sub-group hiding
2299:Number theoretic
2285:
2278:
2271:
2262:
2256:
2245:
2239:
2232:
2226:
2215:
2209:
2203:
2197:
2187:
2138:
2136:
2135:
2130:
2090:group signatures
2069:
2067:
2066:
2061:
2047:
2046:
2025:
2024:
1997:
1996:
1984:
1983:
1971:
1970:
1955:
1954:
1930:
1912:
1910:
1909:
1904:
1896:
1895:
1883:
1882:
1863:
1861:
1860:
1855:
1850:
1849:
1837:
1836:
1827:
1826:
1811:
1810:
1801:
1800:
1782:
1781:
1757:
1756:
1744:
1743:
1734:
1733:
1718:
1717:
1708:
1707:
1689:
1688:
1664:
1663:
1650:
1645:
1632:
1627:
1612:
1611:
1599:
1581:
1579:
1578:
1573:
1565:
1543:
1541:
1540:
1535:
1530:
1529:
1516:
1511:
1498:
1493:
1478:
1477:
1465:
1443:
1441:
1440:
1435:
1430:
1429:
1404:
1403:
1390:
1389:
1371:
1370:
1357:
1356:
1343:
1342:
1314:
1312:
1311:
1306:
1288:
1286:
1285:
1280:
1272:
1271:
1259:
1258:
1242:
1240:
1239:
1234:
1189:
1187:
1186:
1181:
1179:
1178:
1162:
1160:
1159:
1154:
1152:
1151:
1132:
1130:
1129:
1124:
1109:
1108:
1095:
1094:
1058:
1057:
1038:
1036:
1035:
1030:
1018:
1016:
1015:
1010:
995:
993:
992:
987:
979:
978:
959:
958:
945:
944:
908:
907:
888:
886:
885:
880:
835:
833:
832:
827:
809:
807:
806:
801:
785:
783:
782:
777:
765:
763:
762:
757:
745:
743:
742:
737:
725:
723:
722:
717:
695:
693:
692:
687:
656:
654:
653:
648:
621:
619:
618:
613:
608:
607:
595:
594:
572:
570:
569:
564:
562:
561:
533:
531:
530:
525:
517:
516:
489:
488:
455:
454:
442:
441:
416:
414:
413:
408:
406:
405:
386:
384:
383:
378:
366:
364:
363:
358:
346:
345:
332:
331:
297:
295:
294:
289:
259:
257:
256:
251:
227:
225:
224:
219:
207:
205:
204:
199:
197:
196:
174:
172:
171:
166:
147:
145:
144:
139:
113:
111:
110:
105:
100:
99:
86:
85:
2907:
2906:
2902:
2901:
2900:
2898:
2897:
2896:
2872:
2871:
2870:
2861:
2843:
2772:
2513:
2508:
2474:
2469:
2443:
2397:
2393:Decision linear
2371:
2345:Group theoretic
2340:
2294:
2289:
2259:
2246:
2242:
2233:
2229:
2216:
2212:
2204:
2200:
2188:
2179:
2175:
2151:
2121:
2120:
2086:
2029:
2010:
1985:
1975:
1962:
1940:
1923:
1918:
1917:
1887:
1874:
1869:
1868:
1838:
1828:
1818:
1802:
1792:
1767:
1745:
1735:
1725:
1709:
1699:
1674:
1652:
1603:
1592:
1587:
1586:
1558:
1553:
1552:
1518:
1469:
1458:
1453:
1452:
1415:
1395:
1381:
1362:
1348:
1334:
1320:
1319:
1291:
1290:
1263:
1250:
1245:
1244:
1213:
1212:
1205:
1200:
1170:
1165:
1164:
1143:
1138:
1137:
1100:
1086:
1049:
1044:
1043:
1021:
1020:
1001:
1000:
964:
950:
936:
899:
894:
893:
838:
837:
812:
811:
792:
791:
768:
767:
748:
747:
728:
727:
708:
707:
678:
677:
674:
657:will be equal.
624:
623:
599:
586:
575:
574:
550:
539:
538:
505:
477:
446:
433:
422:
421:
394:
389:
388:
369:
368:
337:
323:
308:
307:
262:
261:
242:
241:
234:
210:
209:
182:
177:
176:
150:
149:
116:
115:
91:
77:
48:
47:
17:
12:
11:
5:
2905:
2903:
2895:
2894:
2889:
2884:
2874:
2873:
2867:
2866:
2863:
2862:
2860:
2859:
2848:
2845:
2844:
2842:
2841:
2836:
2834:Random numbers
2831:
2826:
2821:
2816:
2811:
2806:
2801:
2796:
2791:
2786:
2780:
2778:
2774:
2773:
2771:
2770:
2765:
2760:
2758:Garlic routing
2755:
2750:
2745:
2740:
2735:
2730:
2725:
2720:
2715:
2710:
2705:
2700:
2695:
2690:
2685:
2680:
2678:Secure channel
2675:
2669:
2668:
2667:
2656:
2651:
2646:
2641:
2636:
2634:Key stretching
2631:
2626:
2621:
2616:
2611:
2606:
2601:
2600:
2599:
2594:
2589:
2579:
2577:Cryptovirology
2574:
2569:
2564:
2562:Cryptocurrency
2559:
2554:
2549:
2548:
2547:
2537:
2532:
2527:
2521:
2519:
2515:
2514:
2509:
2507:
2506:
2499:
2492:
2484:
2471:
2470:
2468:
2467:
2462:
2457:
2451:
2449:
2445:
2444:
2442:
2441:
2436:
2431:
2426:
2416:
2405:
2403:
2399:
2398:
2396:
2395:
2390:
2385:
2379:
2377:
2373:
2372:
2370:
2369:
2364:
2359:
2357:Diffie-Hellman
2354:
2348:
2346:
2342:
2341:
2339:
2338:
2333:
2328:
2323:
2318:
2313:
2308:
2302:
2300:
2296:
2295:
2290:
2288:
2287:
2280:
2273:
2265:
2258:
2257:
2240:
2227:
2210:
2198:
2176:
2174:
2171:
2150:
2147:
2128:
2094:security level
2085:
2082:
2071:
2070:
2059:
2056:
2053:
2050:
2045:
2042:
2039:
2036:
2032:
2028:
2023:
2020:
2017:
2013:
2009:
2006:
2003:
2000:
1995:
1992:
1988:
1982:
1978:
1974:
1969:
1965:
1961:
1958:
1953:
1950:
1947:
1943:
1939:
1936:
1933:
1929:
1926:
1902:
1899:
1894:
1890:
1886:
1881:
1877:
1865:
1864:
1853:
1848:
1845:
1841:
1835:
1831:
1825:
1821:
1817:
1814:
1809:
1805:
1799:
1795:
1791:
1788:
1785:
1780:
1777:
1774:
1770:
1766:
1763:
1760:
1755:
1752:
1748:
1742:
1738:
1732:
1728:
1724:
1721:
1716:
1712:
1706:
1702:
1698:
1695:
1692:
1687:
1684:
1681:
1677:
1673:
1670:
1667:
1662:
1659:
1655:
1649:
1644:
1640:
1636:
1631:
1626:
1622:
1618:
1615:
1610:
1606:
1602:
1598:
1595:
1571:
1568:
1564:
1561:
1545:
1544:
1533:
1528:
1525:
1521:
1515:
1510:
1506:
1502:
1497:
1492:
1488:
1484:
1481:
1476:
1472:
1468:
1464:
1461:
1446:
1445:
1433:
1428:
1425:
1422:
1418:
1414:
1411:
1407:
1402:
1398:
1393:
1388:
1384:
1380:
1377:
1374:
1369:
1365:
1360:
1355:
1351:
1346:
1341:
1337:
1333:
1330:
1327:
1304:
1301:
1298:
1278:
1275:
1270:
1266:
1262:
1257:
1253:
1232:
1229:
1226:
1223:
1220:
1204:
1201:
1199:
1196:
1177:
1173:
1150:
1146:
1134:
1133:
1122:
1119:
1116:
1112:
1107:
1103:
1098:
1093:
1089:
1084:
1081:
1077:
1074:
1070:
1067:
1064:
1061:
1056:
1052:
1028:
1008:
997:
996:
985:
982:
977:
974:
971:
967:
962:
957:
953:
948:
943:
939:
934:
931:
927:
924:
920:
917:
914:
911:
906:
902:
878:
875:
872:
869:
865:
862:
858:
855:
851:
848:
845:
825:
822:
819:
799:
775:
755:
735:
715:
685:
673:
670:
646:
643:
640:
637:
634:
631:
611:
606:
602:
598:
593:
589:
585:
582:
560:
557:
553:
549:
546:
535:
534:
523:
520:
515:
512:
508:
504:
501:
498:
495:
492:
487:
484:
480:
476:
473:
470:
467:
464:
461:
458:
453:
449:
445:
440:
436:
432:
429:
404:
401:
397:
376:
356:
353:
349:
344:
340:
335:
330:
326:
321:
318:
315:
287:
284:
281:
278:
275:
272:
269:
249:
233:
230:
217:
195:
192:
189:
185:
164:
160:
157:
137:
133:
130:
126:
123:
103:
98:
94:
89:
84:
80:
75:
72:
68:
65:
61:
58:
55:
15:
13:
10:
9:
6:
4:
3:
2:
2904:
2893:
2890:
2888:
2885:
2883:
2880:
2879:
2877:
2858:
2850:
2849:
2846:
2840:
2839:Steganography
2837:
2835:
2832:
2830:
2827:
2825:
2822:
2820:
2817:
2815:
2812:
2810:
2807:
2805:
2802:
2800:
2797:
2795:
2794:Stream cipher
2792:
2790:
2787:
2785:
2782:
2781:
2779:
2775:
2769:
2766:
2764:
2761:
2759:
2756:
2754:
2753:Onion routing
2751:
2749:
2746:
2744:
2741:
2739:
2736:
2734:
2733:Shared secret
2731:
2729:
2726:
2724:
2721:
2719:
2716:
2714:
2711:
2709:
2706:
2704:
2701:
2699:
2696:
2694:
2691:
2689:
2686:
2684:
2681:
2679:
2676:
2673:
2670:
2665:
2662:
2661:
2660:
2657:
2655:
2652:
2650:
2647:
2645:
2642:
2640:
2637:
2635:
2632:
2630:
2627:
2625:
2624:Key generator
2622:
2620:
2617:
2615:
2612:
2610:
2607:
2605:
2602:
2598:
2595:
2593:
2590:
2588:
2585:
2584:
2583:
2582:Hash function
2580:
2578:
2575:
2573:
2570:
2568:
2565:
2563:
2560:
2558:
2557:Cryptanalysis
2555:
2553:
2550:
2546:
2543:
2542:
2541:
2538:
2536:
2533:
2531:
2528:
2526:
2523:
2522:
2520:
2516:
2512:
2505:
2500:
2498:
2493:
2491:
2486:
2485:
2482:
2478:
2466:
2463:
2461:
2458:
2456:
2453:
2452:
2450:
2446:
2440:
2437:
2435:
2432:
2430:
2427:
2424:
2420:
2417:
2414:
2410:
2407:
2406:
2404:
2400:
2394:
2391:
2389:
2386:
2384:
2381:
2380:
2378:
2374:
2368:
2365:
2363:
2360:
2358:
2355:
2353:
2350:
2349:
2347:
2343:
2337:
2334:
2332:
2329:
2327:
2324:
2322:
2319:
2317:
2314:
2312:
2309:
2307:
2304:
2303:
2301:
2297:
2293:
2286:
2281:
2279:
2274:
2272:
2267:
2266:
2263:
2254:
2250:
2244:
2241:
2237:
2231:
2228:
2224:
2220:
2214:
2211:
2208:
2202:
2199:
2195:
2191:
2186:
2184:
2182:
2178:
2172:
2170:
2168:
2164:
2160:
2156:
2148:
2146:
2144:
2140:
2126:
2116:
2114:
2110:
2106:
2101:
2099:
2095:
2091:
2083:
2081:
2079:
2076:
2057:
2054:
2051:
2043:
2040:
2037:
2034:
2030:
2026:
2021:
2018:
2015:
2011:
2004:
2001:
1998:
1993:
1990:
1980:
1976:
1972:
1967:
1963:
1956:
1951:
1948:
1945:
1941:
1937:
1934:
1931:
1927:
1924:
1916:
1915:
1914:
1900:
1897:
1892:
1888:
1884:
1879:
1875:
1851:
1846:
1843:
1833:
1823:
1819:
1812:
1807:
1797:
1793:
1783:
1778:
1775:
1772:
1768:
1764:
1761:
1758:
1753:
1750:
1740:
1730:
1726:
1719:
1714:
1704:
1700:
1690:
1685:
1682:
1679:
1675:
1671:
1668:
1665:
1660:
1657:
1647:
1642:
1638:
1634:
1629:
1624:
1620:
1613:
1608:
1604:
1600:
1596:
1593:
1585:
1584:
1583:
1569:
1566:
1562:
1559:
1550:
1531:
1526:
1523:
1513:
1508:
1504:
1500:
1495:
1490:
1486:
1479:
1474:
1470:
1466:
1462:
1459:
1451:
1450:
1449:
1426:
1423:
1420:
1416:
1412:
1409:
1405:
1400:
1396:
1391:
1386:
1382:
1375:
1367:
1363:
1358:
1353:
1349:
1344:
1339:
1335:
1328:
1325:
1318:
1317:
1316:
1302:
1299:
1296:
1276:
1273:
1268:
1264:
1260:
1255:
1251:
1230:
1227:
1224:
1221:
1218:
1210:
1202:
1197:
1195:
1193:
1175:
1171:
1148:
1144:
1120:
1114:
1110:
1105:
1101:
1096:
1091:
1087:
1082:
1079:
1075:
1072:
1068:
1065:
1059:
1054:
1050:
1042:
1041:
1040:
1026:
1006:
983:
975:
972:
969:
965:
960:
955:
951:
946:
941:
937:
932:
929:
925:
922:
918:
915:
909:
904:
900:
892:
891:
890:
873:
870:
867:
863:
860:
856:
853:
849:
846:
823:
820:
817:
797:
789:
773:
753:
733:
713:
706:
703:
699:
683:
671:
669:
667:
663:
658:
641:
638:
635:
629:
604:
600:
596:
591:
587:
580:
558:
555:
551:
547:
544:
521:
513:
510:
506:
502:
499:
493:
490:
485:
482:
474:
471:
468:
462:
459:
451:
447:
443:
438:
434:
427:
420:
419:
418:
402:
399:
395:
374:
351:
347:
342:
338:
333:
328:
324:
319:
316:
305:
301:
285:
279:
276:
273:
270:
267:
247:
239:
236:In symmetric
231:
229:
215:
193:
190:
187:
183:
162:
158:
155:
135:
131:
128:
124:
121:
96:
92:
87:
82:
78:
73:
70:
66:
63:
59:
56:
44:
42:
38:
34:
30:
26:
22:
2789:Block cipher
2629:Key schedule
2619:Key exchange
2609:Kleptography
2567:Cryptosystem
2511:Cryptography
2392:
2243:
2230:
2219:Brent Waters
2213:
2201:
2152:
2117:
2102:
2087:
2072:
1866:
1546:
1447:
1206:
1198:Applications
1135:
998:
698:cyclic group
675:
659:
536:
387:is equal to
235:
45:
20:
18:
2777:Mathematics
2768:Mix network
2316:RSA problem
2107:. Then the
2876:Categories
2728:Ciphertext
2698:Decryption
2693:Encryption
2654:Ransomware
2321:Strong RSA
2311:Phi-hiding
2173:References
788:generators
666:signatures
240:the group
232:Motivation
2718:Plaintext
2249:Moti Yung
2190:Dan Boneh
2041:−
2035:−
2027:⋅
2005:⋅
1991:−
1973:⋅
1957:⋅
1938:⋅
1844:−
1813:⋅
1784:⋅
1765:⋅
1751:−
1720:⋅
1691:⋅
1672:⋅
1658:−
1635:⋅
1614:⋅
1524:−
1501:⋅
1480:⋅
1413:⋅
1300:∈
1115:η
1007:η
871:−
861:…
537:Thus, if
298:which is
283:→
277:×
216:η
2857:Category
2763:Kademlia
2723:Codetext
2666:(CSPRNG)
2644:Machines
2402:Lattices
2376:Pairings
1928:′
1597:′
1563:′
1463:′
300:bilinear
27:used in
2518:General
2075:IND-CPA
1913:yields
1551:, i.e.
1549:correct
114:, with
2639:Keygen
2161:, an
2078:secure
810:. Let
766:, and
726:. Let
2674:(PRN)
2098:bytes
705:order
702:prime
696:be a
41:Boneh
23:is a
1190:are
1163:and
999:Let
676:Let
664:and
622:and
19:The
2423:gap
2413:gap
2169:.
790:of
700:of
2878::
2251::
2221::
2180:^
2145:.
2100:.
1467::=
1329::=
1194:.
746:,
228:.
2503:e
2496:t
2489:v
2425:)
2421:(
2415:)
2411:(
2284:e
2277:t
2270:v
2127:q
2058:.
2055:m
2052:=
2049:)
2044:b
2038:a
2031:h
2022:b
2019:+
2016:a
2012:h
2008:(
2002:m
1999:=
1994:1
1987:)
1981:b
1977:h
1968:a
1964:h
1960:(
1952:b
1949:+
1946:a
1942:h
1935:m
1932:=
1925:m
1901:h
1898:=
1893:y
1889:v
1885:=
1880:x
1876:u
1852:.
1847:1
1840:)
1834:b
1830:)
1824:y
1820:v
1816:(
1808:a
1804:)
1798:x
1794:u
1790:(
1787:(
1779:b
1776:+
1773:a
1769:h
1762:m
1759:=
1754:1
1747:)
1741:y
1737:)
1731:b
1727:v
1723:(
1715:x
1711:)
1705:a
1701:u
1697:(
1694:(
1686:b
1683:+
1680:a
1676:h
1669:m
1666:=
1661:1
1654:)
1648:y
1643:2
1639:c
1630:x
1625:1
1621:c
1617:(
1609:3
1605:c
1601:=
1594:m
1570:m
1567:=
1560:m
1532:.
1527:1
1520:)
1514:y
1509:2
1505:c
1496:x
1491:1
1487:c
1483:(
1475:3
1471:c
1460:m
1444:.
1432:)
1427:b
1424:+
1421:a
1417:h
1410:m
1406:,
1401:b
1397:v
1392:,
1387:a
1383:u
1379:(
1376:=
1373:)
1368:3
1364:c
1359:,
1354:2
1350:c
1345:,
1340:1
1336:c
1332:(
1326:c
1303:G
1297:m
1277:h
1274:=
1269:y
1265:v
1261:=
1256:x
1252:u
1231:h
1228:,
1225:v
1222:,
1219:u
1176:2
1172:D
1149:1
1145:D
1121:.
1118:)
1111:,
1106:b
1102:v
1097:,
1092:a
1088:u
1083:,
1080:h
1076:,
1073:v
1069:,
1066:u
1063:(
1060:=
1055:2
1051:D
1027:G
984:.
981:)
976:b
973:+
970:a
966:h
961:,
956:b
952:v
947:,
942:a
938:u
933:,
930:h
926:,
923:v
919:,
916:u
913:(
910:=
905:1
901:D
877:}
874:1
868:p
864:,
857:,
854:2
850:,
847:1
844:{
824:b
821:,
818:a
798:G
774:h
754:v
734:u
714:p
684:G
645:)
642:h
639:,
636:g
633:(
630:e
610:)
605:b
601:g
597:,
592:a
588:g
584:(
581:e
559:b
556:a
552:g
548:=
545:h
522:.
519:)
514:b
511:a
507:g
503:,
500:g
497:(
494:e
491:=
486:b
483:a
479:)
475:g
472:,
469:g
466:(
463:e
460:=
457:)
452:b
448:g
444:,
439:a
435:g
431:(
428:e
403:b
400:a
396:g
375:h
355:)
352:h
348:,
343:b
339:g
334:,
329:a
325:g
320:,
317:g
314:(
286:T
280:G
274:G
271::
268:e
248:G
194:y
191:+
188:x
184:h
163:y
159:,
156:x
136:h
132:,
129:v
125:,
122:u
102:)
97:y
93:v
88:,
83:x
79:u
74:,
71:h
67:,
64:v
60:,
57:u
54:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
