Xatolar bilan o'rganish - Learning with errors

Xatolar bilan o'rganish (LWE) bo'ladi hisoblash muammosi chiziqli xulosa chiqarish ${ displaystyle n}$ -ary funktsiyasi ${ displaystyle f}$ berilgan namunalardan cheklangan halqa ustida ${ displaystyle y_ {i} = f ( mathbf {x} _ {i})}$ LWE muammosini hal qilish qiyin deb taxmin qilinmoqda, ularning ba'zilari xato bo'lishi mumkin.^[1] va shu bilan foydali bo'lishi mumkin kriptografiya.

Aniqrog'i, LWE muammosi quyidagicha ta'riflanadi. Ruxsat bering ${ displaystyle mathbb {Z} _ {q}}$ butun sonlarning halqasini belgilang modul ${ displaystyle q}$ va ruxsat bering ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ to'plamini belgilang ${ displaystyle n}$ -vektorlar ustida ${ displaystyle mathbb {Z} _ {q}}$ . Muayyan noma'lum chiziqli funktsiya mavjud ${ displaystyle f: mathbb {Z} _ {q} ^ {n} rightarrow mathbb {Z} _ {q}}$ va LWE muammosiga kirish juftlik namunasi ${ displaystyle ( mathbf {x}, y)}$ , qayerda ${ displaystyle mathbf {x} in mathbb {Z} _ {q} ^ {n}}$ va ${ displaystyle y in mathbb {Z} _ {q}}$ , shuning uchun yuqori ehtimollik bilan ${ displaystyle y = f ( mathbf {x})}$ . Bundan tashqari, tenglikdan og'ish ba'zi ma'lum shovqin modellariga muvofiq. Muammo funktsiyani topishni talab qiladi ${ displaystyle f}$ , yoki katta ehtimollik bilan ularning taxminan yaqinlashuvi.

LWE muammosi tomonidan kiritilgan Oded Regev 2005 yilda^[2] (2018 yilda kim g'olib chiqdi Gödel mukofoti bu ish uchun), bu ning umumlashtirilishi tenglikni o'rganish muammo. Regev shuni ko'rsatdiki, LWE muammosi bir nechta eng yomon holatlardagidek hal qilinishi qiyin panjara bilan bog'liq muammolar. Keyinchalik, LWE muammosi a sifatida ishlatilgan qattiqlik taxmin yaratmoq ochiq kalitli kriptosistemalar,^[2]^[3] kabi kalitlarni almashtirish bilan xatolarni o'rganish Peikert tomonidan.^[4]

Ta'rif

Belgilash ${ displaystyle mathbb {T} = mathbb {R} / mathbb {Z}}$ The reals bo'yicha qo'shimchalar guruhi modulli. Ruxsat bering ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ sobit vektor bo'lsin ${ displaystyle phi}$ ehtimollik taqsimoti aniqlangan bo'lishi kerak ${ displaystyle mathbb {T}}$ .Qayd eting ${ displaystyle A _ { mathbf {s}, phi}}$ tarqatish ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$ quyidagicha olingan.

Vektorni tanlang ${ displaystyle mathbf {a} in mathbb {Z} _ {q} ^ {n}}$ forma taqsimotidan ${ displaystyle mathbf {a} in mathbb {Z} _ {q} ^ {n}}$ ,
Raqam tanlang ${ displaystyle e in mathbb {T}}$ tarqatishdan ${ displaystyle phi}$ ,
Baholang ${ displaystyle t = langle mathbf {a}, mathbf {s} rangle / q + e}$ , qayerda ${ displaystyle textstyle langle mathbf {a}, mathbf {s} rangle = sum _ {i = 1} ^ {n} a_ {i} s_ {i}}$ standart ichki mahsulotdir ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ , bo'linish reallar maydoni (yoki rasmiy ravishda, bu "bo'linish tomonidan ${ displaystyle q}$ "bu guruh homomorfizmi uchun belgi ${ displaystyle mathbb {Z} _ {q} longrightarrow mathbb {T}}$ xaritalash ${ displaystyle 1 in mathbb {Z} _ {q}}$ ga ${ displaystyle 1 / q + mathbb {Z} in mathbb {T}}$ ) va oxirgi qo'shilish ${ displaystyle mathbb {T}}$ .
Juftlikni chiqaring ${ displaystyle ( mathbf {a}, t)}$ .

The xatolar bilan o'rganish ${ displaystyle mathrm {LWE} _ {q, phi}}$ topishdir ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ , polinomial ravishda tanlangan ko'plab namunalarga kirish huquqi berilgan ${ displaystyle A _ { mathbf {s}, phi}}$ .

Har bir kishi uchun ${ displaystyle alpha> 0}$ , bilan belgilanadi ${ displaystyle D _ { alpha}}$ bir o'lchovli Gauss nolinchi o'rtacha va dispersiya bilan ${ displaystyle alpha ^ {2} / (2 pi)}$ , ya'ni zichlik funktsiyasi ${ displaystyle D _ { alpha} (x) = rho _ { alpha} (x) / alfa}$ qayerda ${ displaystyle rho _ { alpha} (x) = e ^ {- pi (| x | / alpha) ^ {2}}}$ va ruxsat bering ${ displaystyle Psi _ { alpha}}$ tarqatish bo'lishi mumkin ${ displaystyle mathbb {T}}$ ko'rib chiqish natijasida olingan ${ displaystyle D _ { alpha}}$ modulli. Ko'pgina natijalarda ko'rib chiqilgan LWE versiyasi shunday bo'ladi ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$

Qaror versiyasi

The LWE Yuqorida tavsiflangan muammo qidirmoq muammoning versiyasi. In qaror versiya (DLWE), maqsadi shovqinli ichki mahsulotlar va bir xil tasodifiy namunalarni ajratishdir ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$ (amalda uning ba'zi bir diskretlangan versiyasi). Regev^[2] ekanligini ko'rsatdi qaror va qidirmoq versiyalari qachon teng ${ displaystyle q}$ in ba'zi bir polinomlar bilan chegaralangan tub son ${ displaystyle n}$ .

Qidiruvni nazarda tutgan holda qarorni hal qilish

Intuitiv ravishda, agar bizda qidiruv muammosi uchun protsedura mavjud bo'lsa, qarorning versiyasini osongina echish mumkin: faqat qaror muammosi uchun kiritilgan namunalarni qidirish muammosi uchun echuvchiga etkazing. Berilgan namunalarni belgilang ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) } subset mathbb {Z} _ {q} ^ {n} times mathbb {T} }$ . Agar hal qiluvchi nomzodni qaytarsa ${ displaystyle mathbf {s}}$ , Barcha uchun ${ displaystyle i}$ , hisoblang ${ displaystyle { langle mathbf {a} _ {i}, mathbf {s} rangle - mathbf {b} _ {i} }}$ . Agar namunalar LWE taqsimotidan olingan bo'lsa, unda ushbu hisoblash natijalari bo'yicha taqsimlanadi ${ displaystyle chi}$ , ammo namunalar bir xil tasodifiy bo'lsa, bu miqdorlar ham bir xil taqsimlanadi.

Qaror qabul qilingan holda qidiruvni hal qilish

Qaror muammosini hal qiladigan boshqa yo'nalish uchun qidiruv versiyasini quyidagicha hal qilish mumkin: Qayta tiklash ${ displaystyle mathbf {s}}$ bir vaqtning o'zida bitta koordinata. Birinchi koordinatani olish uchun, ${ displaystyle mathbf {s} _ {1}}$ , taxmin qiling ${ displaystyle k in Z_ {q}}$ va quyidagilarni bajaring. Raqam tanlang ${ displaystyle r in mathbb {Z} _ {q}}$ bir xil tasodifiy. Berilgan namunalarni o'zgartiring ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) } subset mathbb {Z} _ {q} ^ {n} times mathbb {T} }$ quyidagicha. Hisoblang ${ displaystyle {( mathbf {a} _ {i} + (r, 0, ldots, 0), mathbf {b} _ {i} + (rk) / q) }}$ . O'zgartirilgan namunalarni qaror echimiga yuboring.

Agar taxmin bo'lsa ${ displaystyle k}$ to'g'ri edi, transformatsiya taqsimotni oladi ${ displaystyle A _ { mathbf {s}, chi}}$ o'ziga, aks holda, buyon ${ displaystyle q}$ asosiy hisoblanadi, uni bir xil taqsimlashga olib boradi. Shunday qilib, juda kichik ehtimollik bilan xatoga yo'l qo'ygan qaror muammosi uchun polinom-vaqt echuvchisi berilgan, chunki ${ displaystyle q}$ ba'zi bir polinomlar bilan chegaralangan ${ displaystyle n}$ uchun har qanday mumkin bo'lgan qiymatni taxmin qilish uchun faqat polinom vaqt talab etiladi ${ displaystyle k}$ va qaysi biri to'g'ri ekanligini ko'rish uchun hal qilgichdan foydalaning.

Qabul qilgandan keyin ${ displaystyle mathbf {s} _ {1}}$ , biz bir-birimizga o'xshash koordinatalar protsedurasiga amal qilamiz ${ displaystyle mathbf {s} _ {j}}$ . Aynan biz o'zimizni o'zgartiramiz ${ displaystyle mathbf {b} _ {i}}$ namunalarni xuddi shunday qilib oling va biznikini o'zgartiring ${ displaystyle mathbf {a} _ {i}}$ hisoblash yo'li bilan namunalar ${ displaystyle mathbf {a} _ {i} + (0, ldots, r, ldots, 0)}$ , qaerda ${ displaystyle r}$ ichida ${ displaystyle j ^ { text {th}}}$ muvofiqlashtirish.^[2]

Peikert^[3] kichik qisqartirish bilan ushbu pasayish har qanday narsaga mos kelishini ko'rsatdi ${ displaystyle q}$ bu aniq, kichik (polinom in ${ displaystyle n}$ ) tub sonlar. Asosiy g'oya - agar ${ displaystyle q = q_ {1} q_ {2} cdots q_ {t}}$ , har biriga ${ displaystyle q _ { ell}}$ , taxmin qiling va yo'qligini tekshiring ${ displaystyle mathbf {s} _ {j}}$ ga mos keladi ${ displaystyle 0 mod q _ { ell}}$ va undan keyin foydalaning Xitoyning qolgan teoremasi tiklanmoq ${ displaystyle mathbf {s} _ {j}}$ .

O'rtacha ishning qattiqligi

Regev^[2] ko'rsatdi tasodifiy o'z-o'zini kamaytirish ning LWE va DLWE o'zboshimchalik uchun muammolar ${ displaystyle q}$ va ${ displaystyle chi}$ . Berilgan namunalar ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) }}$ dan ${ displaystyle A _ { mathbf {s}, chi}}$ , buni ko'rish oson ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i} + langle mathbf {a} _ {i}, mathbf {t} rangle) / q } }$ dan namunalar ${ displaystyle A _ { mathbf {s} + mathbf {t}, chi}}$ .

Shunday qilib, ba'zi bir to'plam bor edi deylik ${ displaystyle { mathcal {S}} subset mathbb {Z} _ {q} ^ {n}}$ shu kabi ${ displaystyle | { mathcal {S}} | / | mathbb {Z} _ {q} ^ {n} | = 1 / operator nomi {poly} (n)}$ va tarqatish uchun ${ displaystyle A _ { mathbf {s} ', chi}}$ , bilan ${ displaystyle mathbf {s} ' leftarrow { mathcal {S}}}$ , DLWE oson edi.

Keyin ba'zi bir farqlovchi narsa bo'lar edi ${ displaystyle { mathcal {A}}}$ , kim, namunalarni bergan ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) }}$ , ular bir xil tasodifiymi yoki yo'qligini bilib olishlari mumkin ${ displaystyle A _ { mathbf {s} ', chi}}$ . Agar bir xil tasodifiy namunalarni ajratish kerak bo'lsa ${ displaystyle A _ { mathbf {s}, chi}}$ , qayerda ${ displaystyle mathbf {s}}$ dan tasodifiy ravishda bir xil tanlanadi ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ , biz shunchaki turli xil qadriyatlarni sinab ko'rishimiz mumkin ${ displaystyle mathbf {t}}$ dan tasodifiy bir xil namuna olingan ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ , hisoblang ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i} + langle mathbf {a} _ {i}, mathbf {t} rangle) / q } }$ va ushbu namunalarni oziqlantirish ${ displaystyle { mathcal {A}}}$ . Beri ${ displaystyle { mathcal {S}}}$ ning katta qismini o'z ichiga oladi ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ , katta ehtimollik bilan, uchun qiymatlarning polinom sonini tanlasak ${ displaystyle mathbf {t}}$ , biz ulardan birini topamiz ${ displaystyle mathbf {s} + mathbf {t} in { mathcal {S}}}$ va ${ displaystyle { mathcal {A}}}$ namunalarni muvaffaqiyatli ajratib turadi.

Shunday qilib, bunday emas ${ displaystyle { mathcal {S}}}$ mavjud bo'lishi mumkin, ma'no LWE va DLWE eng yomon holatda bo'lgani kabi o'rtacha holatda ham (polinom omiliga qadar).

Qattiqlik paydo bo'ladi

Regevning natijasi

Uchun n- o'lchovli panjara ${ displaystyle L}$ , ruxsat bering yumshatuvchi parametr ${ displaystyle eta _ { varepsilon} (L)}$ eng kichikni belgilang ${ displaystyle s}$ shu kabi ${ displaystyle rho _ {1 / s} (L ^ {*} setminus { mathbf {0} }) leq varepsilon}$ qayerda ${ displaystyle L ^ {*}}$ ning dualidir ${ displaystyle L}$ va ${ displaystyle rho _ { alpha} (x) = e ^ {- pi (| x | / alpha) ^ {2}}}$ to'plamdagi har bir elementdagi funktsiya qiymatlarini yig'ish orqali to'plamlarga kengaytiriladi. Ruxsat bering ${ displaystyle D_ {L, r}}$ diskret Gauss taqsimotini belgilang ${ displaystyle L}$ kengligi ${ displaystyle r}$ panjara uchun ${ displaystyle L}$ va haqiqiy ${ displaystyle r> 0}$ . Har birining ehtimoli ${ displaystyle x in L}$ ga mutanosib ${ displaystyle rho _ {r} (x)}$ .

The diskret Gauss namuna olish muammosi(DGS) quyidagicha aniqlanadi: ning misoli ${ displaystyle DGS _ { phi}}$ tomonidan berilgan ${ displaystyle n}$ - o'lchovli panjara ${ displaystyle L}$ va raqam ${ displaystyle r geq phi (L)}$ . Maqsad - dan namunani chiqarish ${ displaystyle D_ {L, r}}$ . Regev-dan pasayish mavjudligini ko'rsatadi ${ displaystyle operatorname {GapSVP} _ {100 { sqrt {n}} gamma (n)}}$ ga ${ displaystyle DGS _ {{ sqrt {n}} gamma (n) / lambda (L ^ {*})}}$ har qanday funktsiya uchun ${ displaystyle gamma (n)}$ .

Keyin Regev samarali kvant algoritmi mavjudligini ko'rsatadi ${ displaystyle DGS _ {{ sqrt {2n}} eta _ { varepsilon} (L) / alpha}}$ uchun oracle-ga kirish huquqi berilgan ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$ butun son uchun ${ displaystyle q}$ va ${ displaystyle alfa in (0,1)}$ shu kabi ${ displaystyle alpha q> 2 { sqrt {n}}}$ . Bu LWE uchun qattiqlikni anglatadi. Garchi ushbu tasdiqning isboti har qanday kishi uchun ishlaydi ${ displaystyle q}$ , kriptosistemani yaratish uchun ${ displaystyle q}$ ichida polinom bo'lishi kerak ${ displaystyle n}$ .

Peikertning natijasi

Peikert buni tasdiqlaydi^[3] vaqtidan ehtimollik polinomining qisqarishi borligini ${ displaystyle operator nomi {GapSVP} _ { zeta, gamma}}$ eng yomon holatda muammo hal qilish ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$ foydalanish ${ displaystyle operatorname {poly} (n)}$ parametrlar uchun namunalar ${ displaystyle alfa in (0,1)}$ , ${ displaystyle gamma (n) geq n / ( alfa { sqrt { log n}})}$ , ${ displaystyle zeta (n) geq gamma (n)}$ va ${ displaystyle q geq ( zeta / { sqrt {n}}) omega { sqrt { log n}})}$ .

Kriptografiyada foydalaning

The LWE muammo bir nechta qurilishda ishlatiladigan ko'p qirrali muammo bo'lib xizmat qiladi^[2]^[3]^[5]^[6] kriptotizimlar. 2005 yilda Regev^[2] LWE ning qaror versiyasi kvantning qattiqligini qabul qilish qiyinligini ko'rsatdi panjara bilan bog'liq muammolar ${ displaystyle mathrm {GapSVP} _ { gamma}}$ (uchun ${ displaystyle gamma}$ yuqoridagi kabi) va ${ displaystyle mathrm {SIVP} _ {t}}$ bilan ${ displaystyle t = O (n / alfa)}$ ). 2009 yilda Peikert^[3] shunga o'xshash muammoning faqat klassik qattiqligini hisobga olgan holda shunga o'xshash natijani isbotladi ${ displaystyle mathrm {GapSVP} _ { zeta, gamma}}$ . Peikert natijasining kamchiligi shundaki, u o'zini osonroq (SIVP bilan taqqoslaganda) GapSVP muammosining nostandart versiyasiga asoslanadi.

Ochiq kalitli kriptotizim

Regev^[2] taklif qilingan ochiq kalitli kriptotizim qattiqligining asosida LWE muammo. Kriptotizim, shuningdek xavfsizlik va to'g'riligining isboti butunlay klassik. Tizim xarakterlanadi ${ displaystyle m, q}$ va ehtimollik taqsimoti ${ displaystyle chi}$ kuni ${ displaystyle mathbb {T}}$ . To'g'ri va xavfsizlikni isbotlashda ishlatiladigan parametrlarni sozlash

${ displaystyle q geq 2}$ , odatda orasidagi asosiy son ${ displaystyle n ^ {2}}$ va ${ displaystyle 2n ^ {2}}$ .
${ displaystyle m = (1+ varepsilon) (n + 1) log q}$ ixtiyoriy doimiy uchun ${ displaystyle varepsilon}$
${ displaystyle chi = Psi _ { alfa (n)}}$ uchun ${ displaystyle alpha (n) in o (1 / { sqrt {n}} log n)}$ , qayerda ${ displaystyle Psi _ { beta}}$ o'rtacha o'zgaruvchidan namuna olish orqali olingan ehtimollik taqsimoti ${ displaystyle 0}$ va standart o'zgarish ${ displaystyle { frac { beta} { sqrt {2 pi}}}}$ va natija modulini kamaytirish ${ displaystyle 1}$ .

Keyin kriptotizim quyidagicha aniqlanadi:

Shaxsiy kalit: Shaxsiy kalit - bu ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ tasodifiy bir xil tanlangan.
Ochiq kalit: Tanlang ${ displaystyle m}$ vektorlar ${ displaystyle mathbf {a} _ {1}, ldots, mathbf {a} _ {m} in mathbb {Z} _ {q} ^ {n}}$ bir xil va mustaqil ravishda. Xatolarni bartaraf etishni tanlang ${ displaystyle e_ {1}, ldots, e_ {m} in mathbb {T}}$ mustaqil ravishda ${ displaystyle chi}$ . Ochiq kalit quyidagilardan iborat ${ displaystyle ( mathbf {a} _ {i}, b_ {i} = langle mathbf {a} _ {i}, mathbf {s} rangle / q + e_ {i}) _ {i = 1} ^ {m}}$
Shifrlash: Bitni shifrlash ${ displaystyle x in {0,1 }}$ tasodifiy pastki to'plamni tanlash orqali amalga oshiriladi ${ displaystyle S}$ ning ${ displaystyle [m]}$ va keyin belgilash ${ displaystyle operatorname {Enc} (x)}$ kabi

{ displaystyle left ( sum _ {i in S} mathbf {a} _ {i}, { frac {x} {2}} + sum _ {i in S} b_ {i} o'ngda)}

Parolni hal qilish: Ning parolini hal qilish ${ displaystyle ( mathbf {a}, b)}$ bu ${ displaystyle 0}$ agar ${ displaystyle b- langle mathbf {a}, mathbf {s} rangle / q}$ ga yaqinroq ${ displaystyle 0}$ dan ko'ra ${ displaystyle { frac {1} {2}}}$ va ${ displaystyle 1}$ aks holda.

To'g'ri ekanligining isboti parametrlarni tanlash va ba'zi ehtimollarni tahlil qilishdan kelib chiqadi. Xavfsizlikning isboti - qaror versiyasiga qisqartirish LWE: ning (yuqoridagi parametrlari bilan) ning shifrlashlarini ajratish algoritmi ${ displaystyle 0}$ va ${ displaystyle 1}$ orasidagi farqni aniqlash uchun ishlatilishi mumkin ${ displaystyle A_ {s, chi}}$ va yagona taqsimot ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$

CCA bilan himoyalangan kriptosistema

Peikert^[3] hech kimga qarshi bo'lmagan tizimni taklif qildi shifrlangan matn hujumi.

Kalit almashinuvi

Kalit almashinuvi uchun LWE va Ring LWE dan foydalanish g'oyasi Tsintai Din tomonidan 2011 yilda Tsintsinati universitetida taklif qilingan va taqdim etilgan. Ushbu g'oya matritsani ko'paytirishning assotsiativligidan kelib chiqadi va xatolar xavfsizlikni ta'minlash uchun ishlatiladi. Qog'oz^[7] 2012 yilda vaqtinchalik patent talabnomasi berilgandan so'ng paydo bo'ldi.

LWE muammosini hal qilishning qattiqligi asosida protokolning xavfsizligi tasdiqlangan. 2014 yilda Peikert kalitlarni tashish sxemasini taqdim etdi^[8] Dingning xuddi shu asosiy g'oyasidan kelib chiqqan holda, Ding konstruktsiyasida yaxlitlash uchun qo'shimcha 1-bitli signal yuborishning yangi g'oyasi ham qo'llaniladi. "Yangi umid" ni amalga oshirish^[9] Google-ning kvantdan keyingi tajribasi uchun tanlangan,^[10] xatolarni taqsimlash o'zgarishi bilan Peikert sxemasidan foydalanadi.

Shuningdek qarang

Adabiyotlar

^ Regev, Oded (2009). "Panjaralarda, xatolar, tasodifiy chiziqli kodlar va kriptografiya bilan o'rganish". ACM jurnali. 56 (6): 1–40. doi:10.1145/1568318.1568324.
^ ^a ^b ^v ^d ^e ^f ^g ^h Oded Regev, "Raqamlar, xatolar bilan o'rganish, tasodifiy chiziqli kodlar va kriptografiya to'g'risida", Hisoblash nazariyasi bo'yicha o'ttiz ettinchi yillik ACM simpoziumi materiallari (Baltimor, MD, AQSh: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
^ ^a ^b ^v ^d ^e ^f Kris Peikert, "Eng yomon vektorli muammolardan ochiq kalit kriptotizimlar: kengaytirilgan mavhum", "41-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi ishlarida (Bethesda, MD, AQSh: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
^ Peikert, Kris (2014-10-01). "Internet uchun panjara kriptografiyasi". Moskada, Mishel (tahrir). Kvantdan keyingi kriptografiya. Kompyuter fanidan ma'ruza matnlari. 8772. Springer International Publishing. 197-219-betlar. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.
^ Kris Peikert va Brent Uoterlar, "Yo'qotilgan qopqoq funktsiyalari va ularning qo'llanilishi", 40-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi (Viktoriya, Britaniya Kolumbiyasi, Kanada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.
^ Kreyg Gentri, Kris Peikert va Vinod Vaikuntanatan, "Qattiq panjaralar va yangi kriptografik inshootlar uchun qopqoqlar", 40-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi ishlarida (Viktoriya, Britaniya Kolumbiyasi, Kanada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.
^ Lin, Jintai Ding, Sian Xie, Xiaodong (2012-01-01). "Xatolar bilan o'rganish asosida oddiy almashinuvda xavfsiz kalit almashinish sxemasi". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ Peikert, Kris (2014-01-01). "Internet uchun qafasli kriptografiya". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ Alkim, Erdem; Ducas, Leo; Pyppelmann, Tomas; Shvabe, Piter (2015-01-01). "Post-kvant kalitlari almashinuvi - yangi umid". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
^ "Post-kvant kriptografiyasi bilan tajriba". Google Onlayn xavfsizlik blogi. Olingan 2017-02-08.

[1] Regev, Oded (2009). "Panjaralarda, xatolar, tasodifiy chiziqli kodlar va kriptografiya bilan o'rganish". ACM jurnali. 56 (6): 1–40. doi:10.1145/1568318.1568324.

[regev05-2] v ^d ^e ^f ^g ^h Oded Regev, "Raqamlar, xatolar bilan o'rganish, tasodifiy chiziqli kodlar va kriptografiya to'g'risida", Hisoblash nazariyasi bo'yicha o'ttiz ettinchi yillik ACM simpoziumi materiallari (Baltimor, MD, AQSh: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.

[peikert09-3] v ^d ^e ^f Kris Peikert, "Eng yomon vektorli muammolardan ochiq kalit kriptotizimlar: kengaytirilgan mavhum", "41-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi ishlarida (Bethesda, MD, AQSh: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.

[4] Peikert, Kris (2014-10-01). "Internet uchun panjara kriptografiyasi". Moskada, Mishel (tahrir). Kvantdan keyingi kriptografiya. Kompyuter fanidan ma'ruza matnlari. 8772. Springer International Publishing. 197-219-betlar. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.

[5] Kris Peikert va Brent Uoterlar, "Yo'qotilgan qopqoq funktsiyalari va ularning qo'llanilishi", 40-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi (Viktoriya, Britaniya Kolumbiyasi, Kanada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.

[6] Kreyg Gentri, Kris Peikert va Vinod Vaikuntanatan, "Qattiq panjaralar va yangi kriptografik inshootlar uchun qopqoqlar", 40-yillik kompyuterlar nazariyasi bo'yicha ACM simpoziumi ishlarida (Viktoriya, Britaniya Kolumbiyasi, Kanada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.

[7] Lin, Jintai Ding, Sian Xie, Xiaodong (2012-01-01). "Xatolar bilan o'rganish asosida oddiy almashinuvda xavfsiz kalit almashinish sxemasi". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[8] Peikert, Kris (2014-01-01). "Internet uchun qafasli kriptografiya". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[9] Alkim, Erdem; Ducas, Leo; Pyppelmann, Tomas; Shvabe, Piter (2015-01-01). "Post-kvant kalitlari almashinuvi - yangi umid". Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)

[10] "Post-kvant kriptografiyasi bilan tajriba". Google Onlayn xavfsizlik blogi. Olingan 2017-02-08.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Hisoblashning qattiqligi haqidagi taxminlar
Sonlar nazariyasi	Butun sonni faktorizatsiya qilish Yashirish RSA muammosi Kuchli RSA Kvadratik qoldiq Qarorli kompozitsion qoldiq Yuqori qoldiq
Guruh nazariy	Diskret logarifma Diffie-Xellman Qaror Diffie-Hellman Hisoblash Diffie-Hellman
Juftliklar	Tashqi Diffie-Hellman Kichik guruh yashirinish Qaror chiziqli
Panjaralar	Eng qisqa vektor muammosi (bo'shliq ) Eng yaqin vektor muammosi (bo'shliq ) Xatolar bilan o'rganish Xatolar bilan ringni o'rganish Qisqa tamsayıli echim
Kriptografik bo'lmagan	Eksponensial vaqt gipotezasi Noyob o'yinlar gumoni Ekilgan klik gipotezasi