Hisoblashning qattiqligini taxmin qilish - Computational hardness assumption

Yilda hisoblash murakkabligi nazariyasi, a hisoblash qattiqligini taxmin qilish ma'lum bir muammoni samarali echib bo'lmaydigan gipotezadir (qaerda samarali odatda "in" ma'nosini anglatadi polinom vaqti "). Qanday qilib har qanday foydali muammo uchun (shartsiz) qattiqlikni qanday isbotlash mumkinligi ma'lum emas. Buning o'rniga kompyuter olimlari ishonadilar. qisqartirish rasmiy ravishda yangi yoki murakkab muammoning qattiqligini yaxshiroq tushunilgan muammo haqidagi hisoblash qattiqligining taxminiga bog'lash.

Hisoblash qattiqligining taxminlari alohida ahamiyatga ega kriptografiya. Kriptografiyaning asosiy maqsadi yaratishdir kriptografik ibtidoiylar bilan ishonchli xavfsizlik. Ba'zi hollarda kriptografik protokollarga ega ekanligi aniqlanadi axborot nazariy xavfsizligi; The bir martalik pad keng tarqalgan misoldir. Biroq, axborotning nazariy xavfsizligiga har doim ham erishish mumkin emas; bunday hollarda kriptograflar hisoblash xavfsizligiga qaytadilar. Taxminan aytganda, bu ushbu tizimlarning xavfsizligini anglatadi har qanday raqiblar hisoblash uchun cheklangan deb taxmin qilish, barcha dushmanlar amalda bo'lgani kabi.

Hisoblashning qattiqligi haqidagi taxminlar algoritm dizaynerlarini boshqarish uchun ham foydalidir: oddiy algoritm yaxshi o'rganilgan hisoblash qattiqligi haqidagi taxminni rad etishi mumkin emas. P ≠ NP.

Qattiqlik haqidagi taxminlarni taqqoslash

Kompyuter olimlari qaysi qattiqlik taxminlari ishonchli ekanligini baholashning turli usullariga ega.

Qattiqlik haqidagi taxminlarning kuchliligi

Biz bu taxminni aytamiz ${displaystyle A}$ bu kuchliroq taxminlardan ko'ra ${displaystyle B}$ qachon ${displaystyle A}$ nazarda tutadi ${displaystyle B}$ (va aksincha, noto'g'ri yoki ma'lum emas). Boshqacha qilib aytganda, hatto taxmin bo'lsa ham ${displaystyle A}$ yolg'on edi, taxmin ${displaystyle B}$ hali ham haqiqat bo'lishi mumkin va taxminlarga asoslangan kriptografik protokollar ${displaystyle B}$ Shunday qilib, kriptografik protokollarni tuzishda, xavfsizlikni eng zaif mumkin bo'lgan taxminlar.

O'rtacha holat va eng yomon taxminlar

An o'rtacha holat taxminlarga ko'ra, ma'lum bir muammo ba'zi bir aniq tarqatish holatlarida aksariyat hollarda qiyin bo'ladi, a eng yomon holat taxmin faqat muammoni qiyin deb aytadi biroz misollar. Muayyan muammo uchun o'rtacha qattiqlik eng yomon qattiqlikni anglatadi, shuning uchun o'rtacha holatdagi qattiqlikni taxmin qilish bir xil muammo uchun eng yomon qattiqlik taxminidan kuchliroqdir. Bundan tashqari, hatto beqiyos muammolar uchun ham, shunga o'xshash taxmin Eksponent vaqt gipotezasi ko'pincha an-dan afzal deb hisoblanadi o'rtacha holat bo'yicha taxmin kabi ekilgan klik gipotezasi.^[1]Ammo shuni yodda tutingki, aksariyat kriptografik dasturlarda muammoning qandaydir qiyin misoli borligini bilish (ya'ni muammo eng yomon holatda qiyin) foydasiz, chunki bu bizga qattiq misollarni yaratish usulini bermaydi.^[2] Yaxshiyamki, kriptografiyada qo'llaniladigan ko'plab o'rtacha taxminlar (shu jumladan RSA, alohida jurnal va ba'zilari panjara bilan bog'liq muammolar ) eng yomon holatdagi taxminlarga asoslanib, eng yomon holatdan o'rtacha holatgacha qisqartirish orqali amalga oshiriladi.^[3]

Soxtalashtirish

Hisoblash qattiqligining taxmin qilinadigan xususiyatidir qalbakilashtirish ya'ni, agar taxmin yolg'on bo'lsa, unda buni isbotlash mumkin edi. Naor (2003) kriptografik soxtalashtirishning rasmiy tushunchasini kiritdi.^[4]Taxminan hisob-kitoblarga ko'ra, qattiqlik haqidagi taxminlar soxtalashtirilishi mumkin, agar u qiyinchiliklar nuqtai nazaridan shakllantirilishi mumkin bo'lsa: raqib va ​​samarali tekshiruvchi o'rtasidagi interaktiv protokol, bu erda samarali raqib tekshiruvchini qabul qilishga ishontirishi mumkin, agar taxmin faqat shunday bo'lsa. yolg'on.

Kriptografik qattiqlikning umumiy taxminlari

Amalda juda ko'p kriptografik qattiqlik taxminlari mavjud. Bu eng keng tarqalgan va ulardan foydalanadigan ba'zi bir kriptografik protokollarning ro'yxati.

Butun sonni faktorizatsiya qilish

Berilgan kompozit raqam ${displaystyle n}$va xususan, ikkita katta sonning hosilasi ${displaystyle n = pcdot q}$, butun sonni faktorizatsiya qilish muammosi topishdir ${displaystyle p}$ va ${displaystyle q}$ (umuman olganda, tub sonlarni toping ${displaystyle p_ {1}, nuqta, p_ {k}}$ shu kabi ${displaystyle n = prod _ {i} p_ {i}}$Vakolat hajmida vaqt polinomida ishlaydigan tamsayı faktorizatsiyasi algoritmini topish katta ochiq muammo (${displaystyle log (n)}$Ko'pgina kriptografik protokollarning xavfsizligi tamsayı faktorizatsiyasi qiyin (ya'ni polinom vaqtida echib bo'lmaydi) degan taxminga asoslanadi. Xavfsizligi ushbu taxminga teng bo'lgan kriptosistemalarga quyidagilar kiradi Rabin kriptotizimi va Okamoto – Uchiyama kriptosistemasi.Bir qancha kriptotizimlar kabi kuchli taxminlarga tayanadi RSA, Qoldiq bilan bog'liq muammolar va Yashirish.

RSA muammosi

Kompozit raqam berilgan ${displaystyle n}$, ko'rsatkich ${displaystyle e}$ va raqam ${displaystyle c: = m ^ {e} (mathrm {mod}; n)}$, RSA muammoni topish ${displaystyle m}$.Masala qiyin deb taxmin qilinmoqda, ammo faktorizatsiyasini hisobga olgan holda osonlashadi ${displaystyle n}$. In RSA kriptosistemasi, ${displaystyle (n, e)}$ bo'ladi ochiq kalit, ${displaystyle c}$ bu xabarni shifrlash ${displaystyle m}$va faktorizatsiya ${displaystyle n}$ parolini hal qilish uchun ishlatiladigan maxfiy kalit.

Qatlamlilik muammolari

Kompozit raqam berilgan ${displaystyle n}$ va butun sonlar ${displaystyle y, d}$, qoldiq muammosi mavjudligini aniqlash (alternativa, toping) ${displaystyle x}$ shu kabi

${displaystyle x ^ {d} equiv y {pmod {n}}.}$

Muhim maxsus holatlarga quyidagilar kiradi Kvadratik qoldiq muammosi va Qarorli kompozitsion qoldiq muammosi.RSA misolida bo'lgani kabi, bu muammo (va uning alohida holatlari) qiyin deb taxmin qilinadi, ammo faktorizatsiyani hisobga olgan holda osonlashadi. ${displaystyle n}$Qoldiqlik muammolarining qattiqligiga tayanadigan ba'zi bir kriptosistemalarga quyidagilar kiradi:

• Goldwasser-Micali kriptosistemasi (kvadratik redisduosity muammosi)
• Blum Blum Shub generatori (kvadratik redisduosity muammosi)
• Paillier kriptosistemasi (hal qiluvchi kompozit qoldiq muammosi)
• Benaloh kriptosistemasi (yuqori qoldiq muammosi)
• Nakkache-Stern kriptosistemasi (yuqori qoldiq muammosi)

Phi-maxfiy taxmin

Kompozit raqam uchun ${displaystyle m}$, uni qanday samarali hisoblash kerakligi ma'lum emas Eylerning totient funktsiyasi ${displaystyle phi (m)}$. Phi-ni yashirish haqidagi taxmin, uni hisoblash qiyin deb taxmin qiladi ${displaystyle phi (m)}$va bundan tashqari har qanday asosiy omillarni hisoblash ${displaystyle phi (m)}$ qiyin. Ushbu taxmin Cachin-Micali-Stadler-da ishlatiladi PIR protokol.^[5]

Jurnalning diskret muammosi (DLP)

Berilgan elementlar ${displaystyle a}$ va ${displaystyle b}$ dan guruh ${displaystyle G}$, diskret jurnal muammosi butun sonni so'raydi ${displaystyle k}$ shu kabi ${displaystyle a = b ^ {k}}$.Jurnalning diskret muammosini tamsayı faktorizatsiyasi bilan taqqoslash mumkinligi ma'lum emas, ammo ularning hisoblash murakkabliklari chambarchas bog'liq.

Jurnalning diskret muammosi bilan bog'liq ko'pgina kriptografik protokollar kuchliroqdir Diffie-Hellman taxminlari: berilgan guruh elementlari ${displaystyle g, g ^ {a}, g ^ {b}}$, qayerda ${displaystyle g}$ generator va ${displaystyle a, b}$ tasodifiy tamsayılar, ularni topish qiyin ${displaystyle g ^ {acdot b}}$. Ushbu taxminni ishlatadigan protokollarning namunalari asl nusxasini o'z ichiga oladi Diffie-Hellman kalit almashinuvi, shuningdek ElGamal shifrlash (bu hali kuchliroqqa tayanadi Qaror Diffie-Hellman (DDH) variant).

Ko'p chiziqli xaritalar

A ko'p chiziqli xarita funktsiya ${displaystyle e: G_ {1}, nuqta, G_ {n} qorong'i G_ {T}}$ (qayerda ${displaystyle G_ {1}, nuqta, G_ {n}, G_ {T}}$ bor guruhlar ) har qanday kishi uchun ${displaystyle g_ {1}, nuqta, G_ {1} da g_ {n}, nuqta G_ {n}}$ va ${displaystyle a_ {1}, nuqta, a_ {n}}$,

${displaystyle e (g_ {1} ^ {a_ {1}}, nuqtalar, g_ {n} ^ {a_ {n}}) = e (g_ {1}, nuqtalar, g_ {n}) ^ {a_ {1 } cdots a_ {n}}}$.

Kriptografik dasturlar uchun guruhlar tuzish kerak ${displaystyle G_ {1}, nuqta, G_ {n}, G_ {T}}$ va xarita ${displaystyle e}$ xarita va guruh operatsiyalari bajarilishi kerak ${displaystyle G_ {1}, nuqta, G_ {n}, G_ {T}}$ samarali hisoblash mumkin, ammo diskret jurnal muammosi ${displaystyle G_ {1}, nuqta, G_ {n}}$ hali ham qiyin.^[6]Ba'zi ilovalar yanada kuchli taxminlarni talab qiladi, masalan. Diffie-Hellman taxminlarining ko'p qirrali analoglari.

Maxsus ish uchun ${displaystyle n = 2}$, bilinear xaritalar ishonchli xavfsizlik bilan qurilgan Vayl juftligi va Tate juftligi.^[7]Uchun ${displaystyle n> 2}$ so'nggi yillarda ko'plab qurilishlar taklif qilingan, ammo ularning aksariyati buzilgan va hozirda xavfsiz nomzod haqida kelishuv mavjud emas.^[8]

Ko'p chiziqli qattiqlik taxminlariga tayanadigan ba'zi kriptosistemalar quyidagilarni o'z ichiga oladi:

• Boneh-Franklin sxemasi (yarqiragan Diffie-Hellman)
• Boneh-Lin-Shacham (yarqiragan Diffie-Hellman)
• Garg-Gentri-Halevi-Raykova-Sahai-Uoters nomzodi ajratib bo'lmaydigan obfuskatsiya va funktsional shifrlash (ko'p qirrali jumboq)^[9]

Panjara muammolari

Panjaralardagi eng asosiy hisoblash muammosi bu Eng qisqa vektor muammosi (SVP): panjara berilgan ${displaystyle L}$, nolga teng bo'lmagan eng qisqa vektorni toping ${displaystyle vin L}$.Kriptotizimlarning aksariyati SVP variantlarida, masalan, kuchli taxminlarni talab qiladi Eng qisqa mustaqil vektor muammosi (SIVP), GapSVP,^[10] yoki Unique-SVP.^[11]

Kriptografiyada eng foydali panjara qattiqligining taxminlari bu uchun Xatolar bilan o'rganish (LWE) muammosi: berilgan namunalar ${displaystyle (x, y)}$, qayerda ${displaystyle y = f (x)}$ ba'zi bir chiziqli funktsiyalar uchun ${displaystyle f (cdot)}$, o'rganish oson ${displaystyle f (cdot)}$ chiziqli algebra yordamida. LWE muammosida algoritmga kiritishda xatolar mavjud, ya'ni har bir juftlik uchun ${displaystyle yeq f (x)}$ kichik ehtimollik bilan. Xatolar muammoni echib bo'lmaydigan deb hisoblaydi (tegishli parametrlar uchun); Xususan, SVP variantlaridan o'rtacha holatgacha eng yomon holatlarda pasayishlar mavjud.^[12]

Kvant kompyuterlari uchun Faktoring va Diskret jurnal muammolari oson, ammo panjara muammolari qiyin deb taxmin qilinadi.^[13]Bu ba'zi qiladi panjara asosidagi kriptosistemalar nomzodlar kvantdan keyingi kriptografiya.

Qo'rqinchli muammolarning qattiqligiga ishonadigan ba'zi kriptosistemalarga quyidagilar kiradi:

• NTRU (ikkalasi ham Shifrlash va NTRUSign )
• Ko'pchilik nomzodlar to'liq homomorfik shifrlash

Kriptografik bo'lmagan qattiqlik haqidagi taxminlar

Kriptografik dasturlari bilan bir qatorda, qattiqlik haqidagi taxminlar ham qo'llaniladi hisoblash murakkabligi nazariyasi so'zsiz isbotlash qiyin bo'lgan matematik bayonotlar uchun dalillarni taqdim etish. Ushbu dasturlarda, qattiqlik taxminining o'zi haqiqat ekanligini isbotlash o'rniga, ba'zi bir murakkablik-nazariy bayonotlarni nazarda tutishini isbotlaydi. Ushbu turdagi eng taniqli taxmin - bu taxmin P ≠ NP,^[14] lekin boshqalarga quyidagilar kiradi eksponent vaqt haqidagi gipoteza,^[15] The ekilgan klik gipotezasi, va noyob o'yinlar gumoni.^[16]

${displaystyle C}$- qattiq muammolar

Ko'pchilik eng yomon holat hisoblash muammolari qiyin yoki hatto teng ekanligi ma'lum to'liq kimdir uchun murakkablik sinfi ${displaystyle C}$, jumladan Qattiq-qattiq (lekin ko'pincha PSPACE-qiyin, PPAD-qattiq, va boshqalar.). Bu shuni anglatadiki, ular hech bo'lmaganda sinfdagi har qanday muammo kabi qiyin ${displaystyle C}$. Agar muammo bo'lsa ${displaystyle C}$- qattiq (polinom vaqtini qisqartirishga nisbatan), agar hisoblash qattiqligi taxmin qilinmasa, uni polinom vaqt algoritmi bilan hal qilish mumkin emas ${displaystyle Peq C}$ yolg'ondir.

Eksponent vaqt gipotezasi (ETH) va uning variantlari

Eksponent vaqt gipotezasi (ETH) - bu a mustahkamlash ning ${displaystyle Peq NP}$ qattiqlik gipotezasi, bu taxminlar nafaqat buni amalga oshiradi Mantiqiy ma'qullik muammosi ko'p polinomli vaqt algoritmiga ega emas, shuningdek, eksponent vaqtni talab qiladi (${displaystyle 2 ^ {Omega (n)}}$).^[17] Deb nomlanuvchi yanada kuchli taxmin Kuchli eksponent vaqt gipotezasi (SETH) buni taxmin qilmoqda ${displaystyle k}$-SAT talab qiladi ${displaystyle 2 ^ {(1-varepsilon _ {k}) n}}$ vaqt, qayerda ${displaystyle lim _ {kightarrow infty} varepsilon _ {k} = 0}$. ETH, SETH va shu bilan bog'liq hisoblash qattiqligining taxminlari nozik murakkablik natijalarini chiqarishga imkon beradi, masalan. polinom vaqtini ajratadigan natijalar kvazi-polinom vaqt,^[1] yoki hatto ${displaystyle n ^ {1.99}}$ ga qarshi ${displaystyle n ^ {2}}$.^[18]Bunday taxminlar ham foydalidir parametrlangan murakkablik.^[19]

Qattiqligicha bo'yicha o'rtacha taxminlar

Masalan, ba'zi bir hisoblash muammolari misollarning ma'lum bir taqsimotida o'rtacha darajada qiyin deb taxmin qilinadi, masalan ekilgan klik Muammo, kirish tasodifiy grafik, namuna olish yo'li bilan Erdős-Rényi tasodifiy grafigi va keyin tasodifiy "ekish" ${displaystyle k}$-klik, ya'ni birlashtiruvchi ${displaystyle k}$ bir xil tasodifiy tugunlar (qaerda ${displaystyle 2log _ {2} nll kll {sqrt {n}}}$) va maqsad ekilganlarni topishdir ${displaystyle k}$-klik (bu noyob w.h.p.).^[20]Yana bir muhim misol Feyg tasodifiy holatlar haqida hisoblashning qattiqligi haqidagi faraz bo'lgan gipoteza 3-SAT (bandlarning o'zgaruvchilarga ma'lum nisbatini saqlab qolish uchun namuna olingan).^[21]O'rtacha hisoblash qattiqligining taxminlari statistikaga o'xshash dasturlarda o'rtacha qattiqlikni isbotlash uchun foydalidir, bu erda ma'lumotlar bo'yicha tabiiy taqsimot mavjud.^[22]Bundan tashqari, ekilgan klik qattiqligining taxminlari boshqa muammolarning polinom va kvazi-polinomlarning eng yomon vaqt murakkabligini ajratish uchun ham ishlatilgan,^[23]ga o'xshash Eksponent vaqt gipotezasi.

Noyob o'yinlar

The Noyob yorliqli qopqoq muammo - bu cheklovni qondirish muammosi, bu erda har bir cheklash ${displaystyle C}$ ikkita o'zgaruvchini o'z ichiga oladi ${displaystyle x, y}$va har bir qiymati uchun ${displaystyle x}$ bor noyob ning qiymati ${displaystyle y}$ bu qondiradi ${displaystyle C}$Barcha cheklovlarni qondirish mumkinligini aniqlash oson, ammo Noyob o'yin gumoni (UGC) deyarli barcha cheklovlar mavjudligini aniqlaydigan postulat (${displaystyle (1-varepsilon)}$-fraktsiya, har qanday doimiy uchun ${displaystyle varepsilon> 0}$) qoniqtirishi mumkin yoki ularning deyarli hech biri (${displaystyle varepsilon}$-fraktsiya) qondirilishi mumkin NP-qattiq.^[16]Yaqinlashish muammolari ko'pincha NP-qattiq UGC-ni nazarda tutganligi ma'lum; bunday muammolar UG-hard deb nomlanadi. Xususan, agar UGC mavjud bo'lsa, a semidefinite dasturlash ko'plab muhim muammolar uchun optimal taxminiy kafolatlariga erishadigan algoritm.^[24]

Kichik to'plamni kengaytirish

Unique Label Cover muammosi bilan chambarchas bog'liq Kichik to'plamni kengaytirish (SSE) muammo: Grafik berilgan ${displaystyle G = (V, E)}$, kichkina tepaliklar to'plamini toping (o'lchamdagi) ${displaystyle n / log (n)}$) kimniki chekka kengayish minimal. Ma'lumki, agar SSE-ni taxmin qilish qiyin bo'lsa, unda Unique Label Cover ham xuddi shunday. Shuning uchun Kichik to'plamni kengaytirish gipotezasiSSE-ni taxmin qilish qiyin deb taxmin qiladigan bu noyob o'yin gumoniga qaraganda kuchliroq (ammo chambarchas bog'liq) taxmindir.^[25]Ba'zi bir yaqinlashish muammolari SSE-qattiq ekanligi ma'lum^[26] (ya'ni kamida SSE ga yaqinlashish kabi qiyin).

3SUM gumoni

To'plami berilgan ${displaystyle n}$ raqamlar, 3SUM muammosi, yig'indisi nolga teng bo'lgan raqamlarning uchligi bormi yoki yo'qligini so'raydi. 3SUM uchun kvadratik vaqt algoritmi mavjud va hech qanday algoritm 3SUMni "chinakam subkvadratik vaqtda" hal qila olmaydi deb taxmin qilingan: 3SUM taxmin yo'qligi haqidagi hisoblash qattiqligining taxminidir ${displaystyle O (n ^ {2-varepsilon})}$- 3SUM uchun vaqt algoritmlari (har qanday doimiy uchun ${displaystyle varepsilon> 0}$Ushbu taxmin, asosan, dan bir nechta muammolar uchun kvadratik pastki chegaralarni isbotlash uchun foydalidir hisoblash geometriyasi.^[27]

Shuningdek qarang

• Xavfsizlik darajasi

Adabiyotlar