Mavzu: Gomomorfik shifrlash algoritmlari, Gomomorfik shifrlash Algoritmlarining qo'llanish sohalari

6.To'liq Gomomorfik shifrlash sxemalari

2009 yilda Gentri to'liq homomorfik kriptosistemaning birinchi ishonchli qurilishini tasvirlab berdi
qo'shishni ham, ko'paytirishni ham qo'llab-quvvatlaydi (Gentry, 2009). Gentrining taklifi to'liq
Gomomorfik shifrlash - nazariyasi va qo'llanilishi
http://dx.doi.org/10.5772/56687
15
homomorfik shifrlash bir necha bosqichlardan iborat: Birinchidan, u bir oz homomor tuzadi shifrlangan ma'lumotlar bo'yicha past darajali polinomlarni baholashni qo'llab-quvvatlovchi phic sxemasi. Keyingi, u
parol hal qilish tartibini siqib chiqaradi, shunda u past darajali polinom sifatida ifodalanishi mumkin
sxemasi tomonidan qo'llab-quvvatlanadi va nihoyat, u to'liq olish uchun yuklash rejimini o'zgartirishni qo'llaydi
gomomorfik sxema. Ushbu sxemaning muhim yondashuvi a ni yaratish va o'rnatishdir parol hal qilish protsedurasi yordamida etarlicha yuqori darajadagi polinomlarni baholashi mumkin bo'lgan jarayon bu juda past darajadagi polinom sifatida ifodalanishi mumkin. Bir marta polinomlar darajasi sxema bo'yicha baholanishi mumkin bo'lgan parol hal qilish polinomining darajasi a ga oshadi Ikkita omil, sxema bootstrappable deb nomlanadi va keyinchalik uni to'liq o'zgartirishi mumkin gomomorfik sxema.
Yuklab olish mumkin bo'lgan sxemani ishlab chiqish uchun Gentri biroz homomorfik sxemani taqdim etdi
(Gentry, 2009), bu taxminan GGH (Goldreich, Goldwasser, Halevi) tip sxemasi.
(Goldreich va boshq., 1997; Micciancio, 2001) ideal panjaralar ustida. Keyinchalik Gentri buni an bilan isbotladi tegishli tugmachalarni ishlab chiqarish protsedurasi, ushbu sxemaning xavfsizligini ideal panjara konstruktsiyalaridagi ba'zi bir panjara muammolarining eng yomon qattiqligigacha kamaytirish mumkin (Gentry, 2010). Shu vaqtdan beri
biroz homomorfik sxema ochib bo'lmaydigan, Gentri transformatsiyani tasvirlab berdi parolni echish tartibini siqib, parol hal qilish polinomining darajasini pasaytiradi (Gentry, 2009). Bu ochiq kalitga, ichidagi maxfiy kalit haqida qo'shimcha ko'rsatma qo'shish orqali amalga oshiriladi
siyrak kichik yig'indisi muammosi shakli (SSSP). Ochiq kalit katta vektorlar to'plami bilan kengaytirilgan
Shunday qilib, ularning sirli kalitiga qo'shiladigan juda kam qism mavjud. A asosiy sxemaning shifrlangan matnini ushbu qo'shimcha maslahat va
keyin qayta ishlangan shifrlangan matnni past darajadagi polinom bilan parolini ochish va shu bilan erishish mumkin ochiladigan sxema.
Gentrining qurilishi juda katta ahamiyatga ega - maxfiy kalit, hattoki uning shaxsiy kalit versiyasida ham
sxema tasodifiy ideal panjaraning qisqa asosidir. Bilan jamoat va maxfiy asoslarning juftlarini yaratish
eng yomon holatdan o'rtacha holatgacha qisqartirishga to'g'ri keladigan taqsimotlar texnik jihatdan juda murakkab. Samaradorligini oshirishga katta ilmiy tadqiqotlar o'tkazildi uni amalga oshirish (Gentry & Halevi, 2011; Smart & Vercauteren, 2010).
Kriptografiyada ideal panjaralardan foydalanadigan parallel ish liniyasi NTRUdan boshlanadi kriptosistema (Xoffshteyn va boshq., 1998). Ushbu yondashuv samarali kripto uchun ideal panjaralardan foydalanadi. grafik konstruktsiyalar. Oddiy panjaralarga nisbatan ideal panjaralarning qo'shimcha tuzilishi, ularning namoyishini yanada kuchliroq qiladi va tezroq hisoblash imkonini beradi. Tomonidan motivatsiya qilingan
Micciancio (Micciancio, 2007) asari, juda ko'p ish (Peikert & Rosen, 2006;
Lyubashevskiy va Micciancio, 2006; Peikert & Rosen, 2007 yil; Lyubashevskiy va boshq., 2008; Lyba‐
shevsky & Micciancio, 2008) turli xil kriptografik vositalarning samarali konstruktsiyalarini ishlab chiqardi
xavfsizligi rasmiy ravishda qisqa vektorli muammolarning qattiqligiga kamaytirilishi mumkin bo'lgan ibtidoiylar ideal panjaralarda (Brakerski & Vaikuntanathan, 2011).
Lyubashevskiy va boshq. (Lyubashevskiy va boshq., 2010) halqalarni o'rganishda xatolar mavjud
(RLWE)
xatolarni taxmin qilish bilan Regevni o'rganishning hal qiluvchi hamkori bo'lgan taxmin (Regev, 2005). Qisqacha aytganda, polinomial ravishda ko'p miqdordagi namunalar berilgan shaklning halqasi (ai
, ai s + ei
), bu erda s - tasodifiy maxfiy uzuk elementi, ai
Lar tarqatiladi
ringda bir xil tasodifiy va ei
kichik halqa elementlari bo'lib, buning iloji bo'lmaydi
16 Kriptografiya nazariyasi va amaliyoti va tarmoq xavfsizligi protokollari va texnologiyalari namunalarning ushbu ketma-ketligini halqa elementlarining tasodifiy juftliklaridan ajratish uchun raqib. The
mualliflar ushbu oddiy taxminni eng samarali tarzda eng yomon darajaga tushirish mumkinligini ko'rsatdilar
ideal panjaralardagi qisqa vektorli muammolarning ishning qattiqligi. Qanday qilib ular ham ko'rsatib berishdi
Regevning ochiq kalitli shifrlash sxemasi uchun juda samarali uzuk hamkasbini qurish (Regev, 2005), shuningdek (Gentry) da taqdim etilgan identifikatsiyaga asoslangan shifrlash sxemasining hamkori
va boshq., 2008) (Regev, 2005). Taqdim etilgan sxema
(Lyubashevskiy va boshq., 2010) juda oqlangan va samarali, chunki u hech kimga bog'liq emas ideal panjaralar bo'yicha murakkab hisoblashlar.
Brakerski va Vaikuntanatan yuqoridagi masalalar yaqinlashadimi degan tabiiy savol tug'dirdi (ya'ni ideal panjaralar va RLWE) samarali foydalanilishi mumkin, shunda ikkalasining ham foydasi bo'ladi
yondashuvlarga bir vaqtning o'zida erishish mumkin - ya'ni tdagi funktsional quvvat u bitta qo'l (ya'ni ideal panjara yondashuvi) va boshqasining soddaligi va samaradorligi (ya'ni RLWE).
Ular haqiqatan ham buni amalga oshirish mumkinligini ko'rsatdilar (Brakerski va
Vaikuntanathan, 2011). Ularda mavjud
RLWE asosida bir oz gomomorfik shifrlash sxemasini tuzdi. Sxema soddaligi va samaradorligini, shuningdek ideal panjaralarga nisbatan eng yomon munosabatni meros qilib oladi.
Bundan tashqari, sxema kalitlarga bog'liq xabarlar xavfsizligiga (KDM xavfsizligi, shuningdek, ma'lum) ega
ko'prikli funktsiyalarni ishonchli tarzda shifrlashi mumkinligi sababli (dairesel xavfsizlik) o'z maxfiy kalitining aniqlangan halqasi). Sxemaning ushbu xususiyatining kontekstdagi ahamiyati homomorfik shifrlash mualliflar tomonidan aniq tushuntirilgan. Mualliflar buni ta'kidlaydilar to'liq homomorfik shifrlashning barcha ma'lum konstruktsiyalari yuklash usulini qo'llaydi Bu sxemaning ochiq kalitini maksimal chuqurlik bilan chiziqli ravishda o'sishga majbur qiladi davrlar. Bu sxemadan foydalanish va samaradorlik jihatidan katta kamchilik.
Shu bilan birga, ochiq kalitning kattaligi elektron chuqurligidan mustaqil ravishda amalga oshirilishi mumkin, agar
ozgina gomomorfik sxema o'zining maxfiy kalitini ishonchli tarzda shifrlashi mumkin. Ning dizayni bilan ushbu sxema bo'yicha mualliflar ochiq muammoni hal qilishdi - bu dumaloq xavfsizlikka erishish gomomorfik shifrlash. Ular, shuningdek, o'zlarining sxemalarining dumaloq xavfsizligini hisoblab chiqdilar
maxfiy kalitni qo'ng'iroq elementi sifatida ifodalashga hurmat, bu erda yuklash kerak maxfiy kalitning bitli ko'rsatilishiga nisbatan dumaloq xavfsizlik (aslida,
siqilgan maxfiy kalitning bitli tasviri). A-ni o'rganadigan oldindan ish bo'lmaganligi sababli dumaloq xavfsizlikning har qanday shakli bilan bir oz gomomorfizm o'rtasida mumkin bo'lgan mavjudlik, ish taxminni olib tashlash uchun muhim birinchi qadamdir (Brakerski & Vaikunta )‐
Natan, 2011). Mualliflar, shuningdek, taklif qilingan sxemani to'liq qanday o'zgartirishni ko'rsatib berishdi
Gentrining siqib chiqarish va yuklashni boshlash rejasidan so'ng gomomorfik shifrlash sxemasi ping. (Brakerski & Vaikuntanathan, 2011a) da keltirilgan texnikani qo'llash, mualliflar RLWE-ning siyrak versiyasiga tayanib, siqib chiqarishni oldini olish mumkin, deb ta'kidlaydilar eng yomon stsenariylarga tushishi ma'lum emas. Bu juda samaradorligini oshiradi
amaliy qo'llanmalarda tavsiya etilgan sxema. Tavsiya etilgan sxema qo'shimcha ravishda keyhomomorphic-kalitlarga bog'liq xavfsizlikka erishish uchun dasturlarni topadigan xususiyatdir. hujumlar (Applebaum va boshq., 2011).
Smart va Vercauteren (Smart & Vercauteren, 2010) to'liq homomorfik shifrlashni taqdim etadi kichikroq kalit va shifrlangan matn o'lchamlariga ega bo'lgan sxema. Mualliflar tomonidan taklif qilingan qurilish
Gentri tomonidan taklif qilingan ideal panjaralarga asoslangan to'liq homomorfik konstruktsiyaga amal qiladi
Gomomorfik shifrlash - nazariyasi va qo'llanilishi
http://dx.doi.org/10.5772/56687
17
(Gentry, 2009). U bir muncha homomorfikadan to'liq homomorfik sxemani ishlab chiqaradi sxema. Biroz homomorfik sxema uchun ochiq va yopiq kalitlar ikkitadan iborat
katta butun sonlar (ulardan bittasi ham ochiq, ham shaxsiy kalit tomonidan foydalaniladi) va shifrlangan matn bitta katta sondan iborat. Sxema (Smart & Vercauteren, 2010) kichikroq shifrlangan ideal panjaralarga asoslangan Gentry sxemasidan ko'ra portlatish va kalit o'lchamini kamaytirish. Bundan tashqari, sxema, shuningdek, ikkita xarakteristikaning har qanday sohasi bo'yicha samarali homomorfik shifrlashga imkon beradi.
Aniqrog'i, siklotomik sonlar maydonlarining arifmetikasidan foydalaniladi. Xususan, mualliflar bor
polinom tomonidan hosil qilingan maydonga yo'naltirilgan: F (X) = X 2 n
+ 1. Biroq, ular ham ta'kidladilar sxema o'zboshimchalik bilan (hatto siklotomik bo'lmagan) raqamlar maydonlarida ham qo'llanilishi mumkin.
Ko'pgina afzalliklarga ega bo'lishiga qaramay, ushbu sxema bo'yicha asosiy muammo bu kalit hosil qilish usuli juda sekin.
Gentri va Halevi Smart va variantlari uchun yangi tatbiq etish uslubini taqdim etdilar Vercauteren taklifi (Smart & Vercauteren, 2010), bu juda yaxshilangan kalitga ega edi avlod bosqichi (Gentry & Halevi, 2011). Xususan, mualliflar buni kalit deb ta'kidladilar avlod (siklotomik maydonlar uchun) asosan Diskret Furye transformatsiyasining qo'llanilishidir
(DFT), so'ngra kichik miqdordagi hisoblash kvantasi va keyin teskari qo'llanilishi
o'zgartirish Keyinchalik mualliflar, hatto buni bajarish talab qilinmasligini ham namoyish qilmoqdalar
DFTlar, agar siklotomik maydonni quyidagi shaklda tanlasa: X
2018-04-01 121 2
n
+ 1. Mualliflar buni tasvirlab berishdi keyinchalik maxfiy kalitdan ikkita doimiyni chiqarib olish uchun rekursiv yondashuv yordamida yaroqli umumiy kalitni yaratish uchun kalitlarni yaratish algoritmini osonlashtiradi. Kalit Gentry va Halevi (Gentry & Halevi, 2011) ishlab chiqarish usuli tezdir. Biroq, sxema birdamlikning ikki quvvatli ildizlari bilan ishlashga ayniqsa moslashtirilgan ko'rinadi.
Tadqiqotchilar shuningdek kalitlarni to'liq homomorf holatida takomillashtirish usullarini ko'rib chiqdilar
shifrlash sxemalari. Masalan, (Ogura va boshq., 2010) da qurilish uchun usul taklif qilingan k ning