72:
22:
506:) has been made towards showing that over many groups the DHP is almost as hard as the DLP. There is no proof to date that either the DHP or the DLP is a hard problem, except in generic groups (by Nechaev and Shoup). A proof that either problem is hard implies that
164:: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken.
949:
449:
278:
419:
392:
248:
221:
550:
have become popular, and in these groups the DDHP is easy, yet the CDHP is still assumed to be hard. For less significant variants of the DHP see the references.
362:
342:
302:
194:
451:. A fast means of solving the DHP would allow an eavesdropper to violate the privacy of the Diffie–Hellman key exchange and many of its variants, including
942:
101:
1152:
1033:
997:
935:
543:
839:
Biham, Eli; Boneh, Dan; Reingold, Omer (1999). "Breaking generalized Diffie–Hellman modulo a composite is no easier than factoring".
1028:
677:
in
Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 283–297, 1996.
641:
in
Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 268–282, 1996.
523:
38:
If the information is appropriate for the lead of the article, this information should also be included in the body of the article.
31:
821:
787:
750:
909:
958:
631:
123:
53:
94:
157:
1105:
1075:
1085:
992:
1121:
564:
495:
1059:
1002:
559:
522:
Many variants of the Diffie–Hellman problem have been considered. The most significant variant is the
479:
475:. The problem has survived scrutiny for a few decades and no "easy" solution has yet been publicized.
1100:
305:
84:
1018:
770:
733:
892:
88:
80:
853:
1126:
1157:
887:
848:
765:
728:
105:
987:
977:
972:
883:
877:
719:
97, (W. Fumy, ed.), Lecture Notes in
Computer Science 1233, Springer, pp. 256–266, 1997.
424:
253:
1095:
397:
370:
313:
226:
199:
682:
The equivalence between the DHP and DLP for elliptic curves used in practical applications
8:
798:
309:
1089:
1079:
723:
Bao, Feng; Deng, Robert H.; Zhu, Huafei (2003). "Variations of Diffie-Hellman
Problem".
915:
879:
Proceedings of the 3rd ACM conference on
Computer and communications security - CCS '96
827:
662:
452:
347:
327:
287:
179:
160:
and its derivatives. The motivation for this problem is that many security systems use
862:
927:
905:
872:
817:
783:
746:
605:
503:
161:
919:
831:
666:
1054:
897:
858:
809:
775:
738:
654:
597:
421:
exchanged as part of the protocol, and the two parties both compute the shared key
145:
808:. Lecture Notes in Computer Science. Vol. 2595. Springer. pp. 325–338.
742:
727:. Lecture Notes in Computer Science. Vol. 2836. Springer. pp. 301–312.
585:
1131:
1049:
764:. Lecture Notes in Computer Science. Vol. 1423. Springer. pp. 48–63.
321:
149:
658:
1146:
813:
609:
601:
478:
As of 2006, the most efficient means known to solve the DHP is to solve the
546:(CDHP) to more clearly distinguish it from the DDHP. Recently groups with
464:
317:
153:
901:
367:
For example, in the Diffie–Hellman key exchange, an eavesdropper observes
982:
779:
675:
Algorithms for black-box fields and their application to cryptotography
716:
645:
Maurer, Ueli M.; Wolf, Stefan (2000). "The Diffie–Hellman
Protocol".
499:
797:
Bresson, Emmanuel; Chevassut, Olivier; Pointcheval, David (2003).
692:
34:
contains information that is not included elsewhere in the article
873:"Diffie-Hellman key distribution extended to group communication"
547:
702:
Complexity of a determinate algorithm for the discrete logarithm
627:
624:
Diffie–Hellman is as strong as discrete log for certain primes
172:
The Diffie–Hellman problem is stated informally as follows:
796:
760:
Boneh, Dan (1998). "The
Decision Diffie-Hellman problem".
870:
Steiner, Michael; Tsudik, Gene; Waidner, Michael (1996).
713:
Lower bounds for discrete logarithms and related problems
957:
427:
400:
373:
350:
330:
290:
256:
229:
202:
182:
869:
725:
471:that the DHP is hard, and this is often called the
871:
838:
443:
413:
386:
356:
336:
296:
272:
242:
215:
188:
1144:
93:but its sources remain unclear because it lacks
494:. In fact, significant progress (by den Boer,
144:) is a mathematical problem first proposed by
943:
680:A. Muzereau, N. P. Smart and F. Vercauteran,
583:
458:
156:and serves as the theoretical basis of the
950:
936:
722:
644:
891:
852:
769:
732:
124:Learn how and when to remove this message
54:Learn how and when to remove this message
806:SAC 2002: Selected Areas in Cryptography
590:IEEE Transactions on Information Theory
1145:
584:Diffie, W.; Hellman, M. (1976-11-01).
167:
931:
759:
762:ANTS 1998: Algorithmic Number Theory
544:computational Diffie–Hellman problem
530:from a random group element, given
65:
15:
799:"The Group Diffie-Hellman Problems"
542:. Sometimes the DHP is called the
13:
1153:Computational hardness assumptions
959:Computational hardness assumptions
691:D. R. L. Brown and R. P. Gallant,
14:
1169:
694:The Static Diffie–Hellman Problem
634:403, Springer, p. 530, 1988.
632:Lecture Notes in Computer Science
524:decisional Diffie–Hellman problem
517:
998:Decisional composite residuosity
586:"New directions in cryptography"
526:(DDHP), which is to distinguish
70:
20:
647:Designs, Codes and Cryptography
841:Information Processing Letters
577:
364:are randomly chosen integers.
1:
863:10.1016/S0020-0190(99)00047-2
688:, pp. 50–72, 2004. See .
570:
1034:Computational Diffie–Hellman
743:10.1007/978-3-540-39927-8_28
715:in Advances in Cryptology –
708:(2), pp. 165–172, 1994.
626:in Advances in Cryptology –
467:, for certain groups, it is
7:
1122:Exponential time hypothesis
673:D. Boneh and R. J. Lipton,
565:Elliptic-curve cryptography
553:
158:Diffie–Hellman key exchange
10:
1174:
637:U. M. Maurer and S. Wolf,
560:Discrete logarithm problem
480:discrete logarithm problem
1132:Planted clique conjecture
1114:
1101:Ring learning with errors
1068:
1042:
1029:Decisional Diffie–Hellman
1011:
965:
473:Diffie–Hellman assumption
814:10.1007/3-540-36492-7_21
684:, LMS J. Comput. Math.,
602:10.1109/TIT.1976.1055638
482:(DLP), which is to find
459:Computational complexity
79:This article includes a
1127:Unique games conjecture
1076:Shortest vector problem
1050:External Diffie–Hellman
697:, IACR ePrint 2004/306.
659:10.1023/A:1008302122286
250:, what is the value of
108:more precise citations.
1106:Short integer solution
1086:Closest vector problem
704:, Mathematical Notes,
445:
444:{\displaystyle g^{xy}}
415:
388:
358:
338:
298:
274:
273:{\displaystyle g^{xy}}
244:
217:
190:
138:Diffie–Hellman problem
993:Quadratic residuosity
973:Integer factorization
902:10.1145/238168.238182
639:Diffie–Hellman oracle
446:
416:
414:{\displaystyle g^{y}}
389:
387:{\displaystyle g^{x}}
359:
339:
299:
275:
245:
243:{\displaystyle g^{y}}
218:
216:{\displaystyle g^{x}}
191:
1096:Learning with errors
425:
398:
371:
348:
328:
314:multiplicative group
288:
254:
227:
200:
180:
168:Problem description
1019:Discrete logarithm
1003:Higher residuosity
780:10.1007/bfb0054851
453:ElGamal encryption
441:
411:
384:
354:
334:
294:
270:
240:
213:
196:and the values of
186:
152:in the context of
81:list of references
1140:
1139:
1115:Non-cryptographic
823:978-3-540-00622-0
789:978-3-540-64657-0
752:978-3-540-20150-2
612:– via IEEE.
357:{\displaystyle y}
337:{\displaystyle x}
297:{\displaystyle g}
189:{\displaystyle g}
176:Given an element
162:one-way functions
134:
133:
126:
64:
63:
56:
1165:
1055:Sub-group hiding
966:Number theoretic
952:
945:
938:
929:
928:
923:
895:
882:. ACM. pp.
875:
866:
856:
835:
803:
793:
773:
756:
736:
670:
653:(2/3): 147–171.
614:
613:
581:
450:
448:
447:
442:
440:
439:
420:
418:
417:
412:
410:
409:
393:
391:
390:
385:
383:
382:
363:
361:
360:
355:
343:
341:
340:
335:
303:
301:
300:
295:
279:
277:
276:
271:
269:
268:
249:
247:
246:
241:
239:
238:
222:
220:
219:
214:
212:
211:
195:
193:
192:
187:
146:Whitfield Diffie
129:
122:
118:
115:
109:
104:this article by
95:inline citations
74:
73:
66:
59:
52:
48:
45:
39:
24:
23:
16:
1173:
1172:
1168:
1167:
1166:
1164:
1163:
1162:
1143:
1142:
1141:
1136:
1110:
1064:
1060:Decision linear
1038:
1012:Group theoretic
1007:
961:
956:
926:
912:
824:
801:
790:
771:10.1.1.461.9971
753:
734:10.1.1.104.3007
700:V. I. Nechaev,
618:
617:
582:
578:
573:
556:
520:
461:
432:
428:
426:
423:
422:
405:
401:
399:
396:
395:
378:
374:
372:
369:
368:
349:
346:
345:
329:
326:
325:
312:(typically the
289:
286:
285:
261:
257:
255:
252:
251:
234:
230:
228:
225:
224:
207:
203:
201:
198:
197:
181:
178:
177:
170:
130:
119:
113:
110:
99:
85:related reading
75:
71:
60:
49:
43:
40:
37:
29:This article's
25:
21:
12:
11:
5:
1171:
1161:
1160:
1155:
1138:
1137:
1135:
1134:
1129:
1124:
1118:
1116:
1112:
1111:
1109:
1108:
1103:
1098:
1093:
1083:
1072:
1070:
1066:
1065:
1063:
1062:
1057:
1052:
1046:
1044:
1040:
1039:
1037:
1036:
1031:
1026:
1024:Diffie-Hellman
1021:
1015:
1013:
1009:
1008:
1006:
1005:
1000:
995:
990:
985:
980:
975:
969:
967:
963:
962:
955:
954:
947:
940:
932:
925:
924:
911:978-0897918299
910:
893:10.1.1.35.9717
867:
836:
822:
794:
788:
757:
751:
720:
709:
698:
689:
678:
671:
642:
635:
619:
616:
615:
596:(6): 644–654.
575:
574:
572:
569:
568:
567:
562:
555:
552:
519:
518:Other variants
516:
460:
457:
438:
435:
431:
408:
404:
381:
377:
353:
333:
322:elliptic curve
293:
282:
281:
267:
264:
260:
237:
233:
210:
206:
185:
169:
166:
150:Martin Hellman
132:
131:
89:external links
78:
76:
69:
62:
61:
28:
26:
19:
9:
6:
4:
3:
2:
1170:
1159:
1158:Finite fields
1156:
1154:
1151:
1150:
1148:
1133:
1130:
1128:
1125:
1123:
1120:
1119:
1117:
1113:
1107:
1104:
1102:
1099:
1097:
1094:
1091:
1087:
1084:
1081:
1077:
1074:
1073:
1071:
1067:
1061:
1058:
1056:
1053:
1051:
1048:
1047:
1045:
1041:
1035:
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1016:
1014:
1010:
1004:
1001:
999:
996:
994:
991:
989:
986:
984:
981:
979:
976:
974:
971:
970:
968:
964:
960:
953:
948:
946:
941:
939:
934:
933:
930:
921:
917:
913:
907:
903:
899:
894:
889:
885:
881:
880:
874:
868:
864:
860:
855:
854:10.1.1.39.110
850:
846:
842:
837:
833:
829:
825:
819:
815:
811:
807:
800:
795:
791:
785:
781:
777:
772:
767:
763:
758:
754:
748:
744:
740:
735:
730:
726:
721:
718:
714:
710:
707:
703:
699:
696:
695:
690:
687:
683:
679:
676:
672:
668:
664:
660:
656:
652:
648:
643:
640:
636:
633:
629:
625:
622:B. den Boer,
621:
620:
611:
607:
603:
599:
595:
591:
587:
580:
576:
566:
563:
561:
558:
557:
551:
549:
545:
541:
537:
533:
529:
525:
515:
513:
510: ≠
509:
505:
501:
497:
493:
489:
485:
481:
476:
474:
470:
466:
456:
454:
436:
433:
429:
406:
402:
379:
375:
365:
351:
331:
323:
319:
315:
311:
307:
291:
265:
262:
258:
235:
231:
208:
204:
183:
175:
174:
173:
165:
163:
159:
155:
151:
147:
143:
139:
128:
125:
117:
107:
103:
97:
96:
90:
86:
82:
77:
68:
67:
58:
55:
47:
35:
33:
27:
18:
17:
1023:
878:
847:(2): 83–87.
844:
840:
805:
761:
724:
712:
705:
701:
693:
685:
681:
674:
650:
646:
638:
623:
593:
589:
579:
539:
535:
531:
527:
521:
511:
507:
491:
487:
483:
477:
472:
468:
465:cryptography
462:
366:
318:finite field
283:
171:
154:cryptography
141:
137:
135:
120:
114:October 2017
111:
100:Please help
92:
50:
41:
32:lead section
30:
983:RSA problem
324:group) and
106:introducing
1147:Categories
988:Strong RSA
978:Phi-hiding
711:V. Shoup,
571:References
284:Formally,
888:CiteSeerX
849:CiteSeerX
766:CiteSeerX
729:CiteSeerX
717:EUROCRYPT
610:0018-9448
306:generator
44:June 2023
1069:Lattices
1043:Pairings
920:13919278
832:14425909
667:42734334
554:See also
548:pairings
498:, Wolf,
308:of some
469:assumed
102:improve
918:
908:
890:
851:
830:
820:
786:
768:
749:
731:
665:
628:CRYPTO
608:
538:, and
504:Lipton
496:Maurer
486:given
320:or an
916:S2CID
884:31–37
828:S2CID
802:(PDF)
663:S2CID
500:Boneh
316:of a
310:group
304:is a
87:, or
906:ISBN
818:ISBN
784:ISBN
747:ISBN
630:88,
606:ISSN
502:and
490:and
394:and
344:and
223:and
148:and
136:The
1090:gap
1080:gap
898:doi
859:doi
810:doi
776:doi
739:doi
655:doi
598:doi
463:In
142:DHP
1149::
914:.
904:.
896:.
886:.
876:.
857:.
845:70
843:.
826:.
816:.
804:.
782:.
774:.
745:.
737:.
706:55
661:.
651:19
649:.
604:.
594:22
592:.
588:.
534:,
514:.
512:NP
455:.
91:,
83:,
1092:)
1088:(
1082:)
1078:(
951:e
944:t
937:v
922:.
900::
865:.
861::
834:.
812::
792:.
778::
755:.
741::
686:7
669:.
657::
600::
540:g
536:g
532:g
528:g
508:P
492:g
488:g
484:x
437:y
434:x
430:g
407:y
403:g
380:x
376:g
352:y
332:x
292:g
280:?
266:y
263:x
259:g
236:y
232:g
209:x
205:g
184:g
140:(
127:)
121:(
116:)
112:(
98:.
57:)
51:(
46:)
42:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.