1570:
In 2016, the
Extended Tower Number Field Sieve algorithm allowed to reduce the complexity of finding discrete logarithm in some resulting groups of pairings. There are several variants of the multiple and extended tower number field sieve algorithm expanding the applicability and improving the
486:
1571:
complexity of the algorithm. A unified description of all such algorithms with further improvements was published in 2019. In view of these advances, several works provided revised concrete estimates on the key sizes of secure pairing-based cryptosystems.
1449:
1552:
322:
335:
84:
1278:
744:
128:
786:
692:
1141:
650:
596:
192:
518:
1071:
1476:
1313:
1098:
1021:
994:
844:
817:
243:
1505:
1201:
1181:
1161:
1041:
967:
943:
923:
903:
547:
263:
216:
152:
946:
875:
1694:
Menezes, Alfred J. Menezes; Okamato, Tatsuaki; Vanstone, Scott A. (1993). "Reducing
Elliptic Curve Logarithms to Logarithms in a Finite Field".
1810:
1678:
1605:
1900:
1895:
1318:
1514:, pairings have also been used to construct many cryptographic systems for which no other efficient implementation is known, such as
855:
If symmetric, pairings can be used to reduce a hard problem in one group to a different, usually easier problem in another group.
268:
1564:
1540:
481:{\displaystyle \forall a,b\in \mathbb {F} _{q}^{*},P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}}
1722:"NICT, Kyushu University and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography"
871:
1519:
30:
1515:
1073:, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given
1526:
1206:
490:
703:
1533:
104:
1665:. Lecture Notes in Computer Science. Vol. 2248. Berlin, Heidelberg: Springer. pp. 514–532.
751:
657:
1522:
schemes. Thus, the security level of some pairing friendly elliptic curves have been later reduced.
24:
1794:
Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography
1103:
1854:
615:
561:
157:
878:
can be easily solved using the pairing function. The first group is sometimes referred to as a
1846:
1806:
1674:
1601:
1556:
603:
1658:
1588:
Koblitz, Neal; Menezes, Alfred (2005). "Pairing-Based cryptography at high security levels".
497:
1838:
1798:
1771:
1703:
1666:
1634:
1593:
1046:
1454:
1286:
1076:
999:
972:
822:
795:
221:
1481:
882:
because of the assumed difference in difficulty between these two problems in the group.
1797:, Lecture Notes in Computer Science, vol. 10311, Springer-Verlag, pp. 83–108,
1875:
1186:
1166:
1146:
1026:
952:
928:
908:
888:
532:
248:
201:
137:
1889:
1858:
1721:
1511:
1760:"A unified polynomial selection method for the (tower) number field sieve algorithm"
867:
863:
859:
698:
609:
Some researchers classify pairing instantiations into three (or more) basic types:
328:
195:
131:
87:
1563:
improved the previous bound for successfully computing a discrete logarithm on a
1539:
Pairing-based cryptography relies on hardness assumptions separate from e.g. the
1802:
1741:"Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case"
1842:
1792:
1639:
1622:
1850:
1670:
1826:
526:
1776:
1759:
1532:
A contemporary example of using bilinear pairings is exemplified in the
1597:
1560:
20:
1707:
1592:. Lecture Notes in Computer Science. Vol. 3796. pp. 13–36.
1740:
905:
be a non-degenerate, efficiently computable, bilinear pairing. Let
98:
The following definition is commonly used in most academic papers.
1880:
606:
from two elements of one group to an element from a second group.
1444:{\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}=e(g,g)^{z}=e(g,g^{z})}
1553:
National
Institute of Information and Communications Technology
1621:
Galbraith, Steven; Paterson, Kenneth; Smart, Nigel (2008).
1791:
Menezes, Alfred; Sarkar, Palash; Singh, Shashank (2016),
1543:, which is older and has been studied for a longer time.
558:
If the same group is used for the first two groups (i.e.
1484:
1457:
1321:
1289:
1209:
1189:
1169:
1149:
1106:
1079:
1049:
1029:
1002:
975:
955:
931:
911:
891:
825:
798:
754:
706:
660:
618:
564:
535:
500:
338:
271:
251:
224:
204:
160:
140:
107:
33:
1825:
Barbulescu, Razvan; Duquesne, Sylvain (2019-10-01).
317:{\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}
1499:
1470:
1443:
1307:
1272:
1195:
1175:
1155:
1135:
1092:
1065:
1035:
1015:
988:
961:
937:
917:
897:
838:
811:
780:
738:
686:
644:
590:
541:
512:
480:
316:
257:
237:
210:
186:
146:
122:
78:
874:are believed to be infeasible while the simpler
1657:Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001).
265:written multiplicatively. A pairing is a map:
1764:Advances in the Mathematics of Communications
324:, which satisfies the following properties:
8:
1827:"Updating Key Size Estimations for Pairings"
79:{\displaystyle e:G_{1}\times G_{2}\to G_{T}}
1525:Pairing-based cryptography is used in the
1775:
1739:Kim, Taechan; Barbulescu, Razvan (2015).
1638:
1483:
1462:
1456:
1432:
1407:
1376:
1345:
1332:
1320:
1288:
1273:{\displaystyle e(g^{x},g^{y})=e(g,g^{z})}
1261:
1233:
1220:
1208:
1188:
1168:
1148:
1124:
1111:
1105:
1084:
1078:
1054:
1048:
1028:
1007:
1001:
980:
974:
954:
930:
910:
890:
830:
824:
803:
797:
772:
759:
753:
730:
717:
705:
678:
665:
659:
636:
623:
617:
582:
569:
563:
534:
499:
469:
403:
384:
365:
360:
356:
355:
337:
308:
295:
282:
270:
250:
229:
223:
203:
178:
165:
159:
139:
114:
110:
109:
106:
70:
57:
44:
32:
1758:Sarkar, Palash; Singh, Shashank (2019).
1659:"Short Signatures from the Weil Pairing"
1696:IEEE Transactions on Information Theory
1663:Advances in Cryptology — ASIACRYPT 2001
1580:
858:For example, in groups equipped with a
23:between elements of two cryptographic
1876:Lecture on Pairing-Based Cryptography
7:
1652:
1650:
1023:. Intuitively, the pairing function
872:computational Diffie–Hellman problem
739:{\displaystyle \phi :G_{2}\to G_{1}}
1527:KZG cryptographic commitment scheme
339:
14:
876:decisional Diffie–Hellman problem
123:{\displaystyle \mathbb {F} _{q}}
27:to a third group with a mapping
1283:By using the bilinear property
781:{\displaystyle G_{1}\neq G_{2}}
687:{\displaystyle G_{1}\neq G_{2}}
1438:
1419:
1404:
1391:
1373:
1360:
1351:
1325:
1267:
1248:
1239:
1213:
945:. Consider an instance of the
723:
301:
245:another cyclic group of order
63:
1:
1623:"Pairings for Cryptographers"
1627:Discrete Applied Mathematics
1565:supersingular elliptic curve
1561:Fujitsu Laboratories Limited
1136:{\displaystyle g^{z}=g^{xy}}
1901:Elliptic curve cryptography
1803:10.1007/978-3-319-61273-7_5
1567:from 676 bits to 923 bits.
1541:elliptic-curve cryptography
645:{\displaystyle G_{1}=G_{2}}
591:{\displaystyle G_{1}=G_{2}}
187:{\displaystyle G_{1},G_{2}}
1917:
1896:Pairing-based cryptography
1520:attribute-based encryption
525:There exists an efficient
17:Pairing-based cryptography
1843:10.1007/s00145-018-9280-5
1745:Cryptology ePrint Archive
1640:10.1016/j.dam.2007.12.010
1516:identity-based encryption
1100:, we may check to see if
1043:does not help us compute
870:, generalizations of the
598:), the pairing is called
1671:10.1007/3-540-45682-1_30
1661:. In Boyd, Colin (ed.).
1478:is a prime order group,
86:to construct or analyze
1726:Press release from NICT
1590:Cryptography and Coding
513:{\displaystyle e\neq 1}
1881:Ben Lynn's PBC Library
1501:
1472:
1445:
1315:times, we see that if
1309:
1274:
1197:
1177:
1157:
1137:
1094:
1067:
1066:{\displaystyle g^{xy}}
1037:
1017:
990:
963:
939:
919:
899:
840:
813:
792:homomorphisms between
790:efficiently computable
782:
740:
696:efficiently computable
688:
646:
592:
543:
514:
482:
318:
259:
239:
212:
188:
148:
124:
80:
1831:Journal of Cryptology
1534:BLS digital signature
1510:While first used for
1502:
1473:
1471:{\displaystyle G_{T}}
1446:
1310:
1308:{\displaystyle x+y+z}
1275:
1203:, by testing whether
1198:
1178:
1158:
1143:without knowledge of
1138:
1095:
1093:{\displaystyle g^{z}}
1068:
1038:
1018:
1016:{\displaystyle g^{y}}
991:
989:{\displaystyle g^{x}}
964:
940:
920:
900:
851:Usage in cryptography
841:
839:{\displaystyle G_{2}}
814:
812:{\displaystyle G_{1}}
783:
741:
689:
647:
593:
544:
515:
483:
319:
260:
240:
238:{\displaystyle G_{T}}
213:
189:
149:
125:
81:
1500:{\displaystyle xy=z}
1482:
1455:
1319:
1287:
1207:
1187:
1167:
1147:
1104:
1077:
1047:
1027:
1000:
973:
953:
929:
909:
889:
823:
796:
752:
704:
658:
616:
562:
533:
498:
336:
269:
249:
222:
202:
158:
138:
105:
31:
1777:10.3934/amc.2019028
370:
1598:10.1007/11586821_2
1497:
1468:
1441:
1305:
1270:
1193:
1173:
1153:
1133:
1090:
1063:
1033:
1013:
986:
959:
935:
925:be a generator of
915:
895:
836:
809:
778:
736:
684:
642:
588:
539:
510:
478:
354:
314:
255:
235:
208:
184:
144:
120:
76:
1812:978-3-319-61272-0
1708:10.1109/18.259647
1680:978-3-540-45682-7
1633:(16): 3113–3121.
1607:978-3-540-30276-6
1557:Kyushu University
1551:In June 2012 the
1196:{\displaystyle z}
1176:{\displaystyle y}
1156:{\displaystyle x}
1036:{\displaystyle e}
962:{\displaystyle g}
938:{\displaystyle G}
918:{\displaystyle g}
898:{\displaystyle e}
788:and there are no
542:{\displaystyle e}
414:
258:{\displaystyle q}
211:{\displaystyle q}
147:{\displaystyle q}
1908:
1863:
1862:
1837:(4): 1298–1336.
1822:
1816:
1815:
1788:
1782:
1781:
1779:
1755:
1749:
1748:
1736:
1730:
1729:
1728:. June 18, 2012.
1718:
1712:
1711:
1702:(5): 1639–1646.
1691:
1685:
1684:
1654:
1645:
1644:
1642:
1618:
1612:
1611:
1585:
1506:
1504:
1503:
1498:
1477:
1475:
1474:
1469:
1467:
1466:
1450:
1448:
1447:
1442:
1437:
1436:
1412:
1411:
1384:
1383:
1350:
1349:
1337:
1336:
1314:
1312:
1311:
1306:
1279:
1277:
1276:
1271:
1266:
1265:
1238:
1237:
1225:
1224:
1202:
1200:
1199:
1194:
1182:
1180:
1179:
1174:
1162:
1160:
1159:
1154:
1142:
1140:
1139:
1134:
1132:
1131:
1116:
1115:
1099:
1097:
1096:
1091:
1089:
1088:
1072:
1070:
1069:
1064:
1062:
1061:
1042:
1040:
1039:
1034:
1022:
1020:
1019:
1014:
1012:
1011:
995:
993:
992:
987:
985:
984:
968:
966:
965:
960:
944:
942:
941:
936:
924:
922:
921:
916:
904:
902:
901:
896:
860:bilinear mapping
845:
843:
842:
837:
835:
834:
818:
816:
815:
810:
808:
807:
787:
785:
784:
779:
777:
776:
764:
763:
745:
743:
742:
737:
735:
734:
722:
721:
694:but there is an
693:
691:
690:
685:
683:
682:
670:
669:
651:
649:
648:
643:
641:
640:
628:
627:
597:
595:
594:
589:
587:
586:
574:
573:
548:
546:
545:
540:
519:
517:
516:
511:
487:
485:
484:
479:
477:
476:
468:
464:
442:
438:
412:
408:
407:
389:
388:
369:
364:
359:
323:
321:
320:
315:
313:
312:
300:
299:
287:
286:
264:
262:
261:
256:
244:
242:
241:
236:
234:
233:
217:
215:
214:
209:
193:
191:
190:
185:
183:
182:
170:
169:
153:
151:
150:
145:
129:
127:
126:
121:
119:
118:
113:
85:
83:
82:
77:
75:
74:
62:
61:
49:
48:
19:is the use of a
1916:
1915:
1911:
1910:
1909:
1907:
1906:
1905:
1886:
1885:
1872:
1867:
1866:
1824:
1823:
1819:
1813:
1790:
1789:
1785:
1757:
1756:
1752:
1738:
1737:
1733:
1720:
1719:
1715:
1693:
1692:
1688:
1681:
1656:
1655:
1648:
1620:
1619:
1615:
1608:
1587:
1586:
1582:
1577:
1549:
1480:
1479:
1458:
1453:
1452:
1428:
1403:
1372:
1341:
1328:
1317:
1316:
1285:
1284:
1257:
1229:
1216:
1205:
1204:
1185:
1184:
1165:
1164:
1145:
1144:
1120:
1107:
1102:
1101:
1080:
1075:
1074:
1050:
1045:
1044:
1025:
1024:
1003:
998:
997:
976:
971:
970:
951:
950:
927:
926:
907:
906:
887:
886:
853:
826:
821:
820:
799:
794:
793:
768:
755:
750:
749:
726:
713:
702:
701:
674:
661:
656:
655:
632:
619:
614:
613:
578:
565:
560:
559:
556:
531:
530:
496:
495:
454:
450:
449:
422:
418:
399:
380:
334:
333:
304:
291:
278:
267:
266:
247:
246:
225:
220:
219:
200:
199:
198:of prime order
174:
161:
156:
155:
136:
135:
108:
103:
102:
96:
66:
53:
40:
29:
28:
12:
11:
5:
1914:
1912:
1904:
1903:
1898:
1888:
1887:
1884:
1883:
1878:
1871:
1870:External links
1868:
1865:
1864:
1817:
1811:
1783:
1770:(3): 435–455.
1750:
1731:
1713:
1686:
1679:
1646:
1613:
1606:
1579:
1578:
1576:
1573:
1548:
1545:
1496:
1493:
1490:
1487:
1465:
1461:
1451:, then, since
1440:
1435:
1431:
1427:
1424:
1421:
1418:
1415:
1410:
1406:
1402:
1399:
1396:
1393:
1390:
1387:
1382:
1379:
1375:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1348:
1344:
1340:
1335:
1331:
1327:
1324:
1304:
1301:
1298:
1295:
1292:
1269:
1264:
1260:
1256:
1253:
1250:
1247:
1244:
1241:
1236:
1232:
1228:
1223:
1219:
1215:
1212:
1192:
1172:
1152:
1130:
1127:
1123:
1119:
1114:
1110:
1087:
1083:
1060:
1057:
1053:
1032:
1010:
1006:
983:
979:
958:
934:
914:
894:
852:
849:
848:
847:
833:
829:
806:
802:
775:
771:
767:
762:
758:
747:
733:
729:
725:
720:
716:
712:
709:
681:
677:
673:
668:
664:
653:
639:
635:
631:
626:
622:
585:
581:
577:
572:
568:
555:
554:Classification
552:
551:
550:
538:
523:
520:
509:
506:
503:
493:
491:Non-degeneracy
488:
475:
472:
467:
463:
460:
457:
453:
448:
445:
441:
437:
434:
431:
428:
425:
421:
417:
411:
406:
402:
398:
395:
392:
387:
383:
379:
376:
373:
368:
363:
358:
353:
350:
347:
344:
341:
331:
311:
307:
303:
298:
294:
290:
285:
281:
277:
274:
254:
232:
228:
207:
181:
177:
173:
168:
164:
143:
117:
112:
95:
92:
73:
69:
65:
60:
56:
52:
47:
43:
39:
36:
13:
10:
9:
6:
4:
3:
2:
1913:
1902:
1899:
1897:
1894:
1893:
1891:
1882:
1879:
1877:
1874:
1873:
1869:
1860:
1856:
1852:
1848:
1844:
1840:
1836:
1832:
1828:
1821:
1818:
1814:
1808:
1804:
1800:
1796:
1795:
1787:
1784:
1778:
1773:
1769:
1765:
1761:
1754:
1751:
1746:
1742:
1735:
1732:
1727:
1723:
1717:
1714:
1709:
1705:
1701:
1697:
1690:
1687:
1682:
1676:
1672:
1668:
1664:
1660:
1653:
1651:
1647:
1641:
1636:
1632:
1628:
1624:
1617:
1614:
1609:
1603:
1599:
1595:
1591:
1584:
1581:
1574:
1572:
1568:
1566:
1562:
1558:
1554:
1547:Cryptanalysis
1546:
1544:
1542:
1537:
1535:
1530:
1528:
1523:
1521:
1517:
1513:
1512:cryptanalysis
1508:
1494:
1491:
1488:
1485:
1463:
1459:
1433:
1429:
1425:
1422:
1416:
1413:
1408:
1400:
1397:
1394:
1388:
1385:
1380:
1377:
1369:
1366:
1363:
1357:
1354:
1346:
1342:
1338:
1333:
1329:
1322:
1302:
1299:
1296:
1293:
1290:
1281:
1262:
1258:
1254:
1251:
1245:
1242:
1234:
1230:
1226:
1221:
1217:
1210:
1190:
1170:
1150:
1128:
1125:
1121:
1117:
1112:
1108:
1085:
1081:
1058:
1055:
1051:
1030:
1008:
1004:
981:
977:
956:
948:
932:
912:
892:
883:
881:
877:
873:
869:
865:
861:
856:
850:
831:
827:
804:
800:
791:
773:
769:
765:
760:
756:
748:
731:
727:
718:
714:
710:
707:
700:
697:
679:
675:
671:
666:
662:
654:
637:
633:
629:
624:
620:
612:
611:
610:
607:
605:
601:
583:
579:
575:
570:
566:
553:
536:
528:
524:
522:Computability
521:
507:
504:
501:
494:
492:
489:
473:
470:
465:
461:
458:
455:
451:
446:
443:
439:
435:
432:
429:
426:
423:
419:
415:
409:
404:
400:
396:
393:
390:
385:
381:
377:
374:
371:
366:
361:
351:
348:
345:
342:
332:
330:
327:
326:
325:
309:
305:
296:
292:
288:
283:
279:
275:
272:
252:
230:
226:
205:
197:
196:cyclic groups
194:two additive
179:
175:
171:
166:
162:
141:
133:
115:
99:
93:
91:
89:
88:cryptographic
71:
67:
58:
54:
50:
45:
41:
37:
34:
26:
22:
18:
1834:
1830:
1820:
1793:
1786:
1767:
1763:
1753:
1744:
1734:
1725:
1716:
1699:
1695:
1689:
1662:
1630:
1626:
1616:
1589:
1583:
1569:
1550:
1538:
1531:
1524:
1509:
1282:
884:
879:
868:Tate pairing
864:Weil pairing
862:such as the
857:
854:
789:
699:homomorphism
695:
608:
599:
557:
132:finite field
100:
97:
16:
15:
947:CDH problem
529:to compute
329:Bilinearity
134:over prime
1890:Categories
1575:References
94:Definition
1859:253635514
1851:1432-1378
880:Gap Group
766:≠
724:→
708:ϕ
672:≠
602:and is a
600:symmetric
527:algorithm
505:≠
397:∈
378:∈
367:∗
352:∈
340:∀
302:→
289:×
90:systems.
64:→
51:×
1555:(NICT),
1536:scheme.
1280:holds.
604:mapping
21:pairing
1857:
1849:
1809:
1677:
1604:
1559:, and
1183:, and
413:
25:groups
1855:S2CID
130:be a
1847:ISSN
1807:ISBN
1675:ISBN
1602:ISBN
885:Let
819:and
218:and
101:Let
1839:doi
1799:doi
1772:doi
1704:doi
1667:doi
1635:doi
1631:156
1594:doi
1518:or
866:or
1892::
1853:.
1845:.
1835:32
1833:.
1829:.
1805:,
1768:13
1766:.
1762:.
1743:.
1724:.
1700:39
1698:.
1673:.
1649:^
1629:.
1625:.
1600:.
1529:.
1507:.
1163:,
996:,
949:,
154:,
1861:.
1841::
1801::
1780:.
1774::
1747:.
1710:.
1706::
1683:.
1669::
1643:.
1637::
1610:.
1596::
1495:z
1492:=
1489:y
1486:x
1464:T
1460:G
1439:)
1434:z
1430:g
1426:,
1423:g
1420:(
1417:e
1414:=
1409:z
1405:)
1401:g
1398:,
1395:g
1392:(
1389:e
1386:=
1381:y
1378:x
1374:)
1370:g
1367:,
1364:g
1361:(
1358:e
1355:=
1352:)
1347:y
1343:g
1339:,
1334:x
1330:g
1326:(
1323:e
1303:z
1300:+
1297:y
1294:+
1291:x
1268:)
1263:z
1259:g
1255:,
1252:g
1249:(
1246:e
1243:=
1240:)
1235:y
1231:g
1227:,
1222:x
1218:g
1214:(
1211:e
1191:z
1171:y
1151:x
1129:y
1126:x
1122:g
1118:=
1113:z
1109:g
1086:z
1082:g
1059:y
1056:x
1052:g
1031:e
1009:y
1005:g
982:x
978:g
969:,
957:g
933:G
913:g
893:e
846:.
832:2
828:G
805:1
801:G
774:2
770:G
761:1
757:G
746:;
732:1
728:G
719:2
715:G
711::
680:2
676:G
667:1
663:G
652:;
638:2
634:G
630:=
625:1
621:G
584:2
580:G
576:=
571:1
567:G
549:.
537:e
508:1
502:e
474:b
471:a
466:)
462:Q
459:,
456:P
452:(
447:e
444:=
440:)
436:Q
433:b
430:,
427:P
424:a
420:(
416:e
410::
405:2
401:G
394:Q
391:,
386:1
382:G
375:P
372:,
362:q
357:F
349:b
346:,
343:a
310:T
306:G
297:2
293:G
284:1
280:G
276::
273:e
253:q
231:T
227:G
206:q
180:2
176:G
172:,
167:1
163:G
142:q
116:q
111:F
72:T
68:G
59:2
55:G
46:1
42:G
38::
35:e
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.