403:, Boyen and Shacham (2002) as a means to improve the efficiency of a signature scheme. The assumption was formally defined by Ballard, Green, de Medeiros and Monrose (2005), and full details of a proposed implementation were advanced in that work. Evidence for the validity of this assumption is the proof by Verheul (2001) and Galbraith and Rotger (2004) of the non-existence of
407:
in two specific elliptic curve subgroups which possess an efficiently computable pairing. As pairings and distortion maps are currently the only known means to solve the DDH problem in elliptic curve groups, it is believed that the DDH assumption therefore holds in these subgroups, while pairings
261:
391:
within a GDH group. Because the DDH assumption holds within at least one of a pair of XDH groups, these groups can be used to construct pairing-based protocols which allow for ElGamal-style encryption and other novel cryptographic techniques.
90:
387:(to name a few). However, the ease of computing DDH within a GDH group can also be an obstacle when constructing cryptosystems; for example, it is not possible to use DDH-based cryptosystems such as
478:
354:
299:
168:
137:
180:
451:
E.R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, in B. Pfitzmann (ed.) EUROCRYPT 2001, Springer LNCS 2045 (2001) 195–210.
438:
Lucas
Ballard, Matthew Green, Breno de Medeiros, Fabian Monrose. Correlation-Resistant Storage via Keyword-Searchable Encryption. E-print archive (2005/417), 2005. (
471:
562:
105:
101:
681:
526:
464:
557:
368:
318:
267:
686:
445:
Steven D Galbraith, Victor Rotger. Easy
Decision Diffie–Hellman Groups. LMS Journal of Computation and Mathematics, August 2004. (
41:
691:
487:
24:
634:
418:
35:
of elliptic curves which have useful properties for cryptography. Specifically, XDH implies the existence of two distinct
521:
650:
28:
552:
588:
531:
360:
97:
629:
380:
655:
363:
cryptographic protocols. In certain elliptic curve subgroups, the existence of an efficiently-computable
256:{\displaystyle e(\cdot ,\cdot ):{\mathbb {G} }_{1}\times {\mathbb {G} }_{2}\rightarrow {\mathbb {G} }_{T}}
516:
506:
501:
372:
328:
273:
142:
111:
624:
404:
36:
547:
388:
396:
384:
583:
375:(GDH) groups, facilitate a variety of novel cryptographic protocols, including tri-partite
618:
614:
608:
604:
432:
660:
452:
675:
456:
417:
Mike Scott. Authenticated ID-based exchange and remote log-in with simple token and
395:
In practice, it is believed that the XDH assumption may hold in certain subgroups of
376:
364:
174:
511:
399:
elliptic curves. This notion was first proposed by Scott (2002), and later by
428:
400:
446:
32:
431:, Xavier Boyen, Hovav Shacham. Short Group Signatures. CRYPTO 2004. (
439:
422:
85:{\displaystyle \langle {\mathbb {G} }_{1},{\mathbb {G} }_{2}\rangle }
16:
Computational hardness assumption used in elliptic curve cryptography
460:
408:
are still feasible between elements in distinct groups.
331:
276:
183:
145:
114:
44:
643:
597:
571:
540:
494:
367:(pairing) can allow for practical solutions to the
31:. The XDH assumption holds if there exist certain
348:
293:
255:
162:
131:
84:
21:external Diffie–Hellman (XDH) assumption
472:
106:computational co-Diffie–Hellman problem
8:
79:
45:
479:
465:
457:
102:computational Diffie–Hellman problem
340:
335:
334:
333:
330:
309:. A stronger version of the assumption (
285:
280:
279:
278:
275:
247:
242:
241:
240:
230:
225:
224:
223:
213:
208:
207:
206:
182:
154:
149:
148:
147:
144:
123:
118:
117:
116:
113:
73:
68:
67:
66:
56:
51:
50:
49:
43:
305:The above formulation is referred to as
371:problem. These groups, referred to as
268:decisional Diffie–Hellman problem
173:There exists an efficiently computable
421:. E-print archive (2002/164), 2002. (
7:
359:The XDH assumption is used in some
682:Computational hardness assumptions
488:Computational hardness assumptions
349:{\displaystyle {\mathbb {G} }_{2}}
294:{\displaystyle {\mathbb {G} }_{1}}
163:{\displaystyle {\mathbb {G} }_{2}}
132:{\displaystyle {\mathbb {G} }_{1}}
14:
25:computational hardness assumption
527:Decisional composite residuosity
92:with the following properties:
236:
199:
187:
1:
563:Computational Diffie–Hellman
687:Elliptic curve cryptography
651:Exponential time hypothesis
29:elliptic curve cryptography
708:
692:Pairing-based cryptography
98:discrete logarithm problem
661:Planted clique conjecture
630:Ring learning with errors
558:Decisional Diffie–Hellman
381:identity based encryption
373:gap Diffie–Hellman
270:(DDH) is intractable in
656:Unique games conjecture
605:Shortest vector problem
579:External Diffie–Hellman
108:are all intractable in
635:Short integer solution
615:Closest vector problem
350:
295:
257:
164:
133:
86:
522:Quadratic residuosity
502:Integer factorization
351:
296:
258:
165:
134:
87:
625:Learning with errors
329:
274:
181:
143:
112:
42:
548:Discrete logarithm
532:Higher residuosity
346:
291:
253:
160:
129:
82:
669:
668:
644:Non-cryptographic
385:secret handshakes
699:
584:Sub-group hiding
495:Number theoretic
481:
474:
467:
458:
355:
353:
352:
347:
345:
344:
339:
338:
300:
298:
297:
292:
290:
289:
284:
283:
262:
260:
259:
254:
252:
251:
246:
245:
235:
234:
229:
228:
218:
217:
212:
211:
169:
167:
166:
161:
159:
158:
153:
152:
138:
136:
135:
130:
128:
127:
122:
121:
91:
89:
88:
83:
78:
77:
72:
71:
61:
60:
55:
54:
707:
706:
702:
701:
700:
698:
697:
696:
672:
671:
670:
665:
639:
593:
589:Decision linear
567:
541:Group theoretic
536:
490:
485:
414:
405:distortion maps
332:
327:
326:
325:intractable in
277:
272:
271:
239:
222:
205:
179:
178:
146:
141:
140:
115:
110:
109:
104:(CDH), and the
65:
48:
40:
39:
17:
12:
11:
5:
705:
703:
695:
694:
689:
684:
674:
673:
667:
666:
664:
663:
658:
653:
647:
645:
641:
640:
638:
637:
632:
627:
622:
612:
601:
599:
595:
594:
592:
591:
586:
581:
575:
573:
569:
568:
566:
565:
560:
555:
553:Diffie-Hellman
550:
544:
542:
538:
537:
535:
534:
529:
524:
519:
514:
509:
504:
498:
496:
492:
491:
486:
484:
483:
476:
469:
461:
455:
454:
449:
443:
436:
426:
413:
410:
343:
337:
307:asymmetric XDH
303:
302:
288:
282:
264:
250:
244:
238:
233:
227:
221:
216:
210:
204:
201:
198:
195:
192:
189:
186:
171:
157:
151:
126:
120:
81:
76:
70:
64:
59:
53:
47:
15:
13:
10:
9:
6:
4:
3:
2:
704:
693:
690:
688:
685:
683:
680:
679:
677:
662:
659:
657:
654:
652:
649:
648:
646:
642:
636:
633:
631:
628:
626:
623:
620:
616:
613:
610:
606:
603:
602:
600:
596:
590:
587:
585:
582:
580:
577:
576:
574:
570:
564:
561:
559:
556:
554:
551:
549:
546:
545:
543:
539:
533:
530:
528:
525:
523:
520:
518:
515:
513:
510:
508:
505:
503:
500:
499:
497:
493:
489:
482:
477:
475:
470:
468:
463:
462:
459:
453:
450:
447:
444:
441:
437:
434:
430:
427:
424:
420:
416:
415:
411:
409:
406:
402:
398:
393:
390:
386:
382:
378:
374:
370:
366:
362:
361:pairing-based
357:
341:
324:
320:
316:
312:
311:symmetric XDH
308:
286:
269:
265:
248:
231:
219:
214:
202:
196:
193:
190:
184:
176:
172:
155:
124:
107:
103:
99:
95:
94:
93:
74:
62:
57:
38:
34:
30:
26:
22:
578:
394:
377:key exchange
365:bilinear map
358:
322:
314:
310:
306:
304:
175:bilinear map
20:
18:
512:RSA problem
317:) holds if
100:(DLP), the
676:Categories
517:Strong RSA
507:Phi-hiding
412:References
177:(pairing)
429:Dan Boneh
237:→
220:×
197:⋅
191:⋅
80:⟩
46:⟨
33:subgroups
598:Lattices
572:Pairings
440:pdf file
433:pdf file
423:pdf file
27:used in
389:ElGamal
383:, and
37:groups
401:Boneh
313:, or
23:is a
323:also
315:SXDH
266:The
139:and
96:The
19:The
619:gap
609:gap
419:PIN
397:MNT
369:DDH
321:is
319:DDH
678::
379:,
356:.
621:)
617:(
611:)
607:(
480:e
473:t
466:v
448:)
442:)
435:)
425:)
342:2
336:G
301:.
287:1
281:G
263:.
249:T
243:G
232:2
226:G
215:1
209:G
203::
200:)
194:,
188:(
185:e
170:.
156:2
150:G
125:1
119:G
75:2
69:G
63:,
58:1
52:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.