Postkvant kriptografiya — kriptografiyaning bir sohasi bo‘lib, u kvant kompyuterlari va kvant hujumlari paydo bo‘lganda ham dolzarbligini saqlab qoladi. Kvant kompyuterlari an’anaviy kriptografik algoritmlarni hisoblash tezligi bo‘yicha klassik kompyuter arxitekturalaridan ancha ustun bo‘lgani sababli zamonaviy kriptografik tizimlar kriptografik hujumlarga nisbatan zaiflashishi mumkin. An’anaviy ochiq kalitli kriptotizimlarning aksariyati butun sonlarni ko‘paytuvchilarga ajratish yoki diskret logarifmni hisoblash masalalariga tayanadi. Bunday masalalarni Shor algoritmidan foydalanadigan yetarlicha katta kvant kompyuterlarida oson yechish mumkin bo‘ladi. Hozir ko‘plab kriptograflar kvant hisoblashlariga bog‘liq bo‘lmagan, ya’ni kvant hujumlariga bardoshli algoritmlarni ishlab chiqmoqda.
Hisoblash jihatidan murakkab masalalarga asoslangan an’anaviy kriptotizimlar ham mavjud. Ular yuqorida tilga olingan tizimlardan bir qator muhim jihatlari bilan farqlanadi va ularga asos bo‘lgan masalalarni yechish ancha qiyin. Bunday tizimlar kvant hisoblashlariga bog‘liq emas, shuning uchun ular kvantga bardoshli (quantum-resistant) yoki «postkvant» kriptotizimlar deb hisoblanadi.
Postkvant kriptografiya esa kvant kriptografiyasidan farq qiladi. Kvant kriptografiyasi aloqa kanallarini kvant fizikasi tamoyillari asosida himoyalash usullarini o‘rganadi.
Algoritmlar
Postkvant kriptografik usullar kriptografiyani kvant hujumlaridan himoya qilishi mumkin. Kvant kompyuteri aksariyat an’anaviy algoritmlarni (RSA, DSA, ECDSA) buzib yuborsa ham, yuqori hisoblash tezligi kriptografiyani butunlay yo‘q qila olmaydi. Chunki postkvant kriptografiya kvant hujumlari muammosini hal etishga qaratilgan, asosan, beshta turli yondashuvga tayanadi.
Xesh-funksiyalarga asoslangan kriptografiya
Bunga klassik misol — Merkle imzosi, ya’ni xesh daraxtiga asoslangan ochiq kalitli imzo sxemasi. Ralf Charlz Merkle ushbu raqamli imzo algoritmini 1979-yilda RSA va DSA raqamli imzolariga muqobil qiziqarli yechim sifatida taklif qilgan. Merkle sxemasining asosiy kamchiligi shundaki, ochiq kalit uchun xesh-funksiya asosida hosil qilinadigan imzolar soni tegishli yopiq kalitlar to‘plami bilan cheklanadi. Shu sababli kvant kompyuterlari ta’siriga bardoshli kriptografiyaga ehtiyoj paydo bo‘lgunicha bunday imzolarga qiziqish past bo‘lgan.
Xatolarni tuzatuvchi kodlarga asoslangan kriptografiya
Bu postkvant kriptotizimlar uchun eng istiqbolli yo‘nalishlardan biridir. Shifrlash sxemalarining klassik misollari — McEliece va Niederreiter.
Panjara tuzilmalariga asoslangan kriptografiya
Shifrlash sxemalarining klassik misollariga Ring-Learning with Errors (halqalarda xatolar bilan o‘rganish) yoki avvalroq yaratilgan NTRU, GGH hamda Michchanchoning kriptotizimi.
Ko‘p o‘zgaruvchili kvadratik tizimlarga asoslangan kriptografiya
Eng qiziqarli sxemalardan biri — Jak Patarenning ochiq kalitli HFE imzosi. U 1996-yilda Matsumoto va Imai takliflarini umumlashtirish sifatida taqdim etilgan.
Maxfiy kalit bilan shifrlash
Bunga yorqin misol — Rijndael shifri. U 1998-yilda taklif etilgan va keyinchalik AES (Advanced Encryption Standard — ilg‘or shifrlash standarti) deb qayta nomlangan.
Supersingulyar izogeniyadan foydalangan holda shifrlash
Bu Diffi–Xellman protokolining supersingulyar izogeniyalar grafigi bo‘ylab harakatlanishga asoslangan muqobilidir. U ikki yoki undan ortiq tomonning tinglashdan himoyalanmagan aloqa kanali orqali umumiy maxfiy kalitni hosil qilishiga imkon beradi. Biroq bu turdagi kriptotizimlarga qarshi samarali hujum ma’lum bo‘lgani uchun protokol xavfsiz deb hisoblanmaydi.
RSAga qarshi kriptografik hujumlarga misollar
1978-yilda RSA ochiq kalitli kriptografik algoritmini ishlab chiquvchilar chop etgan hujjatda (RSA nomi qisqartma bo‘lib, Rivest, Shamir va Adleman familiyalaridan olingan) Richard Shreppelning[ingl.] «linear sieve» («chiziqli elak») deb nomlangan yangi algoritmi tilga olingan. U istalgan RSA modulini, uzunligi bit bo‘lganda, ta oddiy amal yordamida ko‘paytuvchilarga ajratgan. Demak, bu algoritm kamida ta oddiy amal talab qilishi uchun uzunligi hech bo‘lmaganda bit bo‘lishi kerak. Chunki ifodasi muayyan kattalikning ga yaqinlashishini bildiradi ( bo‘lganda). Shuning uchun modulining uzunligini chekli qiymati uchun to‘g‘ri tanlashda «linear sieve» algoritmining tezligi batafsilroq tahlil qilinishi lozim.
1988-yilda Jon Pollard[ingl.] ko‘paytuvchilarga ajratishning yangi algoritmini taklif qildi. Bu usul umumiy sonlar maydoni elagi usuli deb ataladi. Ushbu algoritm RSA-moduli ning bit uzunligi bo‘lganda, uni ta oddiy amal bilan ko‘paytuvchilarga ajratgan. Demak, uzunligini kamida bit qilib tanlash kerak, shunda algoritm kamida ta oddiy amal talab qiladi.
2008-yildan boshlab klassik kompyuter arxitekturalarida ko‘paytuvchilarga ajratishning eng tez algoritmlari kamida ta oddiy amalni talab qiladi. qiymatlarida va tafsilotlarida ayrim yaxshilanishlar bo‘lgan, biroq optimal ekanini va modul uzunligini taxminan bit etib tanlash klassik kompyuterlarda amalga oshiriladigan barcha ehtimoliy hujumlarga bardosh berishini taxmin qilish qiyin emas.
1994-yilda Piter Shor RSA-modulini ko‘paytuvchilarga ajratish algoritmini taklif qildi. Bu algoritm RSA-moduli ning bit uzunligi bo‘lganda, (aniqrog‘i, ) kubit amallarini bajaradi. Buning uchun taxminan kubitli kvant kompyuteri (va klassik kompyuterda oz miqdordagi yordamchi hisoblashlar) kerak bo‘ladi. Shor algoritmini hisobga olganda, modulning bitlarda ifodalangan uzunligini kamida bit deb tanlashga to‘g‘ri keladi. Bu bizni qiziqtiradigan barcha amaliy holatlar uchun haddan tashqari katta qiymatdir. Bu yerda xavfsizlik parametri — .
Kriptografik usullarning amaliy qo‘llanilishi
Kvant hujumlariga bardoshli algoritmlar juda kam. Kriptografik mustahkamlik darajasi yuqoriroq bo‘lishiga qaramay, postkvant algoritmlar hozirgi kriptotizimlarni (RSA, DSA, ECDSA va boshqalar) butunlay siqib chiqara olmaydi.
Ochiq kalitli kriptotizimlarga, xususan, McEliece shifrlash algoritmiga qarshi hujumlarni ko‘rib chiqaylik. Bu algoritm ikkilik Goppa kodlaridan foydalanadi. Dastlab Robert Makelis[ingl.] uzunligi bo‘lgan kodlarni ta oddiy amal yordamida buzish mumkinligini ko‘rsatuvchi ishlarni taqdim etgan. Demak, kamida bit bo‘lishi kerakki, algoritmni buzish uchun kamida ta oddiy amal talab etilsin. Keyingi bir nechta tadqiqotda hujum uchun zarur amallar soni gacha kamaytirildi, ammo qiymati dan ancha kichik bo‘ladi, agar katta bo‘lsa. Shu sababli takomillashtirilgan hujumlar hamon ta oddiy amalni talab qiladi. Kvant kompyuterlaridan foydalanish esa faqat doimiysini kamaytiradi, bu esa algoritmni buzish uchun zarur amallar sonini juda oz miqdorda qisqartiradi.
Agar McEliece shifrlash tizimi shunchalik yaxshi himoyalangan bo‘lsa, nega u RSA o‘rnini egallamayapti? Buning sababi samaradorlik, xususan, kalitning o‘lchamidir. McEliece ochiq kaliti taxminan ≈ bitdan iborat, RSA ochiq kaliti uchun esa taxminan bit yetarli. Agar bo‘lsa, bitli McEliece kaliti bitli RSA kalitidan kichik bo‘ladi. Biroq amaliy xavfsizlik darajalarida, masalan, kabi holatlarda RSA ochiq kaliti bir necha ming bit bo‘lishi mumkin, McEliece kaliti esa deyarli bir million bitga yetadi.
PQCrypto konferensiyasi
2006-yildan buyon postkvant kriptografiyaga bag‘ishlangan konferensiyalar turkumi o‘tkazib kelinmoqda.
- PQCrypto 2006. Lyoven katolik universiteti, Belgiya, 23–26-may
- PQCrypto 2008. Sinsinnati universiteti, AQSh, 17–19-oktabr
- PQCrypto 2010. Darmshtadt, Germaniya, 25–28-may
- PQCrypto 2011. Taybey, Tayvan, 29-noyabr – 2-dekabr
- PQCrypto 2013. Limoj, Fransiya, 4–7-iyun
- PQCrypto 2014. Vaterloo universiteti, Kanada, 1–3-oktabr
- PQCrypto 2016. Dastlabki reja: Fukuoka, Yaponiya, 2016-yil fevral
Havolalar
- PQCrypto — postkvant kriptografiya konferensiyasi
- Postkvant kriptografiya. — Springer, 2008. — B. 245. — ISBN 978-3-540-88701-0.
- ETSI: Kvant xavfsizligi (ingl.)
- NISTning postkvant kriptografiya loyihasi (ingl.)
- PQCrypto: foydalanish va joriy etish (ingl.)