Hisoblangan Diffie-Hellman taxminlari - Computational Diffie–Hellman assumption - Wikipedia

The hisoblash Diffie-Hellman (CDH) taxmin a hisoblash qattiqligini taxmin qilish haqida Diffie-Hellman muammosi.[1]CDH gumoni hisoblash muammosini o'z ichiga oladi alohida logaritma yilda tsiklik guruhlar. CDH muammosi eshitish vositasining hujumini tasvirlaydi Diffie-Hellman kalit almashinuvi[2] almashinadigan maxfiy kalitni olish uchun protokol.

Ta'rif

A ni ko'rib chiqing tsiklik guruh G tartibq. CDH taxminida ta'kidlanganidek

tasodifiy tanlangan generator uchun g va tasodifiy

bu hisoblash qiyin emas qiymatini hisoblash uchun

Diskret logaritmalar bilan bog'liqlik

CDH taxminlari bilan juda bog'liq diskret logaritma taxminlari. Agar hisoblash alohida logaritma (tayanch g ) ichida G oson edi, keyin CDH muammosi osongina echilishi mumkin edi:

Berilgan

samarali hisoblash mumkin quyidagi tarzda:

  • hisoblash ning alohida jurnalini olish orqali asoslash ;
  • hisoblash daraja bo'yicha: ;

Hisoblash alohida logaritma CDH muammosini hal qilishning yagona ma'lum usuli. Ammo bu aslida yagona usul ekanligiga dalil yo'q. Jurnalning diskret taxminining CDH taxminiga teng keladimi yoki yo'qligini aniqlash ochiq muammo hisoblanadi, ammo ba'zi bir maxsus holatlarda buni shunday ko'rsatish mumkin.[3][4]

Qaror Diffie-Hellman taxminiga aloqadorlik

CDH taxminlari a kuchsizroq taxminiga ko'ra Qaror Diffie-Hellman taxmin (DDH taxmin). Agar hisoblash bo'lsa dan oson edi (CDH muammosi), keyin DDH muammosini ahamiyatsiz hal qilish mumkin edi.

CDH muammosidan tuzilgan ko'plab kriptografik sxemalar aslida DDH muammosining qattiqligiga bog'liq. The semantik xavfsizlik ning Diffie-Hellman kalit almashinuvi xavfsizligi bilan bir qatorda ElGamal shifrlash DDH muammosining qattiqligiga ishonish.

Kuchli DDH gipotezasi mavjud bo'lmagan guruhlarning aniq konstruktsiyalari mavjud, ammo zaifroq CDH gumonlari hali ham oqilona faraz bo'lib tuyuladi.[5]

Hisoblangan Diffie-Hellman taxminining o'zgarishi

CDH muammosining quyidagi o'zgarishlari o'rganilib, CDH muammosiga teng ekanligi isbotlangan:[6]

  • Kvadrat hisoblash Diffie-Hellman muammosi (SCDH): kirishda , hisoblash ;[7]
  • Teskari hisoblash Diffie-Hellman muammosi (InvCDH): kirishda , hisoblash ;[8]
  • Bo'linadigan hisoblash Diffie-Hellman (DCDH): Kirishda , hisoblash ;

Mahsulot guruhlarida hisoblash Diffie-Hellman taxminining o'zgarishi

Ruxsat bering va ikkita tsiklik guruh bo'ling.

  • Diffi-Xellman (birgalikda CDH) hisoblash muammosi: berilgan va , hisoblash ;[9]

Adabiyotlar

  1. ^ Bellare, Mixir; Rogaway, Fillip (2005), Zamonaviy kriptografiyaga kirish (PDF)
  2. ^ Diffi, Uitfild; Hellman, Martin (1976), Kriptografiyaning yangi yo'nalishlari (PDF)
  3. ^ den Boer, Bert (1988), "Diffie-Hellman ba'zi bir vaqtlar uchun diskret jurnal kabi kuchli" (PDF), Diffie-Hellman, ma'lum bir sonlar uchun diskret log kabi kuchli, Kompyuter fanidan ma'ruza matnlari, 403, 530-539 betlar, doi:10.1007/0-387-34799-2_38, ISBN  978-0-387-97196-4
  4. ^ Maurer, Ueli M. (1994), Diffie-Hellman protokolini buzish va diskret logaritmalarni hisoblashning tengligiga, CiteSeerX  10.1.1.26.530
  5. ^ Jou, Antuan; Nguyen, Kim (2003), "Diffie-Hellman qarorini kriptografik guruhlarda hisoblash Diffie-Hellmandan ajratish", Kriptologiya jurnali, 16 (4): 239–247, doi:10.1007 / s00145-003-0052-4
  6. ^ Bao, Fen; Deng, Robert X.; Zhu, Huafei (2003), Diffie-Hellman muammosining o'zgarishi (PDF)
  7. ^ Burmester, Mayk; Desmedt, Yvo; Seberry, Jeniffer (1998), "Cheklangan vaqt oralig'idagi teng kalitli garov (yoki, muddati tugashini kriptografik tarzda qanday kuchaytirish kerak) kengaytirilgan abstrakt" (PDF), Cheklangan vaqt oralig'ida (yoki, muddati tugashini kriptografik usulda qanday bajarish kerak) teng kalitli eskro, Kompyuter fanidan ma'ruza matnlari, 1514, 380-391 betlar, doi:10.1007/3-540-49649-1_30, ISBN  978-3-540-65109-3
  8. ^ Pfitsmann, Brigit; Sadegi, Ahmad-Rizo (2000), "To'g'ridan-to'g'ri rad etmaslik bilan anonim barmoq izlari" (PDF), Kriptologiya sohasidagi yutuqlar - ASIACRYPT 2000, Kompyuter fanidan ma'ruza matnlari, 1976, 401-414 betlar, doi:10.1007/3-540-44448-3_31, ISBN  978-3-540-41404-9
  9. ^ Bonex, Dan; Lin, Ben; Shacham, Xovav (2004), Vayl juftligidan olingan qisqa imzolar (PDF), 17, 297-319-betlar