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