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

3. Gomomorfik shifrlash sxemalari

So'nggi bir necha yil ichida homomorfik shifrlash sxemalari keng o'rganildi chunki ular turli xil kriptografik protokollarda tobora muhimroq bo'lib kelmoqda masalan, ovoz berish protokollari.
Ushbu bo'limda biz homomorfik kriptosistemalarni kiritamiz uchta qadam: nima, qanday va nima uchun bu qiziqarli shifrlashning asosiy jihatlarini aks ettiradi texnika. Biz homomorfik kriptosistemalarni va algebraik ravishda homomorfikani aniqlashdan boshlaymiz kriptotizimlar. Keyin algebraik ravishda homomorfik sxemalar tuzish usulini ishlab chiqamiz maxsus gomomorfik sxemalar berilgan. Va nihoyat, biz homomorfik dasturlarni tavsiflaymiz sxemalar. Ta'rif: Xabar maydoni (M, o) cheklangan (yarim) guruh bo'lsin, σ esa xavfsizlik parametr. M-dagi gomomorfik ochiq kalitli shifrlash sxemasi (yoki homomorfik kriptosistema) to'rtburchak (K, E, D,
A) ehtimollik kutilgan polinom vaqt algoritmlari quyidagi funktsiyalar
Kalit avlod: 1σ kiritishda
kalgoritmi K shifrlash / parol hal qilish tugmachalari juftligini chiqaradi (ke , kd ) = k ∈k, bu erda k asosiy bo'shliqni bildiradi.
Shifrlash: 1σ, ke yozuvlarida , va m ∈M elementi E shifrlash algoritmi A ni chiqaradi shifrlangan matn ∈C, bu erda C shifrlangan matn oralig'ini bildiradi.
Parolni hal qilish: parol hal qilish algoritmi D deterministik. 1σ, k va element kirishlarida c ∈C u M xabar maydonidagi elementni chiqaradi, shunda hamma m ∈M uchun quyidagicha bo'ladi: agar 4 Kriptografiya nazariyasi va amaliyoti va tarmoq xavfsizligi protokollari va texnologiyalari c = E (11σ, ke, m) keyin Prob D (1 σ , k, c) ≠ m ahamiyatsiz, ya'ni uni ushlab turadi Prob D (1 σ, k, c) ≠ m ≤ 2 -σ

• 
  Gomomorfik xususiyat: A - bu 1 kirishlar bo'yicha algoritm σ, ke va elementlar c1, c2 ∈C c3 forC elementini chiqaradi, shunda hamma m1 uchun , m2 ∈M uni ushlab turadi: agar m3 = m1 o m2 va c1 = E (1 σ, ke, m1) va c2= E (1σ, ke, m2), keyin Prob D (A (1)σ, ke, c1, c2)) ≠ m3 ahamiyatsiz Norasmiy ma'noda, gomomorfik kriptosistema qo'shimcha bilan kriptosistemadir summa yoki the ning shifrlanishini hisoblash uchun samarali algoritm mavjud bo'lgan xususiyat ochiq kalit va xabarlarning shifrlanishi berilgan ikkita xabarning mahsuloti, ammo berilmagan xabarlarning o'zi. Agar M qo'shimcha (yarim) guruh bo'lsa, u holda sxema additiv ravishda homomorf va algoritmlari A Aks holda Qo'shish deyiladi, sxemasi ko'paytma sifatida homomorfik va algoritmi A Mult deb nomlanadi. Yuqorida keltirilgan ta'riflarga kelsak, quyidagi fikrlarni e'tiborga olish kerak:
  
• 
  Gomomorfik shifrlash sxemasi samarali bo'lishi uchun uning o'lchamiga ishonch hosil qilishjuda muhimdir shifrlangan matnlar xavfsizlik parametrida polinom bilan chegaralangan bo'lib qoladitakroriy hisoblashlar.
  
• 
  Gomomorfik kriptosistemalarning xavfsizlik jihatlari, ta'riflari va modellari bir xil
  

boshqa kriptosistemalardagidek. Agar E shifrlash algoritmi qo'shimcha kirish sifatida z to'plamining bir xil tasodifiy sonini oladigan bo'lsa,shifrlash sxemasi ehtimollik, aks holda deterministik deb nomlanadi. Demak, agar a kriptotizim ehtimoliy, bitta xabarga bir nechta turli xil shifrlangan matnlar kiradi r ∈ number tasodifiy soniga qarab. Shunga qaramay, parol hal qilish algoritmida bo'lgani kabi deterministik bo'lib qoladi, ya'ni ma'lum bir shifrlangan matnga tegishli bitta xabar bor. Keyingi ko'proq, ehtimollik, homomorfik kriptosistemada A algoritmi ehtimoliy bo'lishi kerak kirish kodini yashirish uchun ham. Masalan, buni ko'r-ko'rona qo'llash orqali amalga oshirish mumkin mahsulotni yig'indisini va yig'indisini shifrlashni (deterministik) hisoblash algoritmi navbati bilan. Izohlar: Quyida biz xavfsizlik parametri σ va ochiq kalitni qoldiramiz algoritmlarning tavsifi. Biz Eke yozamiz (m) yoki E (m) uchun E (1 σ , ke , m) va Dk (c) yoki D (c) D uchun (1 σ , k, c) har qanday noaniqlik ehtimoli bo'lmaganida. Agar sxema ehtimoliy bo'lsa, biz ham Eke yozamiz (m) yoki E (m), shuningdek Eke (m, r) yoki E (m, r) uchun E (1 σ , ke , Janob). Keyingi ko'proq, biz A (E (m), E (m) yozamiz ')) = E (m o m') algoritm A (yoki Add yoki Mult) m, m '∈ (M, o) xabarlarning ikkita shifrlashida qo'llaniladi va shifrlashni chiqaradi‐ m o m ' ya'ni, ahamiyatsiz ehtimoli bundan mustasno:
D(A(1 σ , ke , Eke (m), Eke (m '))) =m o m '
Misol: Quyida biz deterministik multiplikativ homomorga misol keltiramiz phic sxema va ehtimollik, qo'shimchali homomorfik sxema misoli
RSA sxemasi: Klassik RSA sxemasi (Rivest va boshq., 1987b) bu to'xtatishning misoli.
vazirlik multiplikativ ravishda homomorfik kriptotizim M = (g / N ℤ,.) bo'yicha, bu erda N ikkita katta sonli mahsulot. Shifrlangan matnli bo'shliq sifatida bizda C = (ℤ / N ℤ,.) Va biz bo'shliq sifatida k= {(ke, kd) = ((N, e), d) | N = pq, ed -1 mod φ (N)}. M ∈M xabarni shifrlash Eke deb ta'riflanadi (m) = men Eke kodli shifrini ochish uchun mod N (m) = c ∈C ni hisoblaymiz Dke,kd (c) = c d mod N = m mod N. Shubhasiz, ikkita xabar mahsulotining shifrlanishi mumkin tegishli shifrlangan matnlarni ko'paytirish orqali samarali hisoblash, ya'ni. Eke(m1.m2) = (m1.m2)emod N = (m1e mod n) (m2e mod N) = Eke(m1). Eke(m2) qaerda m1, m2∈M. Shuning uchun Mult uchun algoritmni quyidagicha amalga oshirish mumkin: Mult (Eke.)(m1), Eke(m2)) = Eke(m1). Eke(m2) Odatda RSA sxemasida, shuningdek kriptosistemalarning ko'pchiligida paramet xavfsizlik parametrini faktoring qilish qiyinligi N ning bit uzunligini tashkil etadi, masalan, σ = 1024 umumiy xavfsizlik parametric
Algebraically Homomorfik Kriptosistemalar: samarali va xavfsiz mavjudligi algebraik homomorfik kriptosistema uzoq vaqtdan beri ochiq savol bo'lib kelgan. Bunda Bo'lim, biz ushbu muammoni hisobga olgan holda dastlab ba'zi tegishli ishlarni taqdim etamiz.
Keyinchalik, biz tasvirlab beramiz
algebraik homomorfik sxemalar va homomorfik sxemalar orasidagi bog'liqlik
abelian bo'lmagan maxsus guruhlar. Aniqrog'i, biz homomorfik shifrlash sxemasi ekanligini isbotlaymiz
qobiliyatsiz guruh bo'yicha (S7
,.), ettita element bo'yicha simmetrik guruh, qurishga imkon beradi
(F2, + ,.) bo'yicha algebraik homomorfik shifrlash sxemasi. Algebraik homomorfik
(F2, + ,.) bo'yicha shifrlash sxemasini gomomorfik shifrlash sxemasidan ham olish mumkin F2 ustidagi maxsus chiziqli guruhda (SL (3, 2),)
. Bundan tashqari, kodlash nazariyasidan foydalanib, algebra‐
Gomomorfik shifrlash - nazariyasi va qo'llanilishi
http://dx.doi.org/10.5772/56687
7
a ixtiyoriy sonli halqa yoki maydonda gomomorfik shifrlash mumkin
ushbu abeliya bo'lmagan guruhlardan birida homomorfik shifrlash sxemasi. Ushbu kuzatishlar samarali va xavfsiz algebraik homo bo'lsin muammoni hal qilish uchun birinchi qadam bo'lishi mumkin‐
morfik sxemalar mavjud. Kriptografiya tadqiqotlari jamoasi katta kuch sarfladilar
ushbu muammo bo'yicha. 1996 yilda Boneh va Lipton buni har bir asosli taxmin asosida isbotladilar deterministik, algebraik homomorfik kriptosistemani sub-eksponentlikda sindirish mumkin vaqt (Boneh & Lipton, 1996). Bu bilan bog'liq salbiy natija sifatida qabul qilinishi mumkin
mavjud bo'lsa ham, algebraik homomorfik shifrlash sxemasining mavjudligi kriptotizimlar, masalan, RSA sxemasi yoki ElGamal sxemasi ham subekspentsial vaqt ichida buzilishi mumkin. Bundan tashqari, agar biz algebraik ravishda homomorfik ochiq kalit sxemalarini qidirsak
M = F2 kabi kichik maydonlarda yoki halqalarda , shubhasiz, bunday sxema tartibda bo'lishi mumkin xavfsiz bo'lish.
Ba'zi tadqiqotchilar algebraik homomorfik sxemalar uchun nomzodlarni topishga harakat qilishdi. 1993 yilda,
Fellows va Koblitz Polly Cracker deb nomlangan algebraik ochiq kalit kriptotizimini taqdim etdilar
(Fellows & Koblitz, 1993). U algebraik jihatdan homomorfik va ishonchli. Afsuski, sxema bir qator qiyinchiliklarga ega va shifrlangan matn uzunligiga nisbatan samarali emas. Birinchidan, Polly Cracker - bu polinomga asoslangan tizim. Shuning uchun, ning shifrlashini hisoblash mahsulot E (m1
.m2
) m1 ikkita xabaridan va m2
tegishli shifrlangan matnni ko'paytirish orqali
polinomlar E (m1
) va E (m2
), monomiallar sonining eksponensial puflanishiga olib keladi.
Demak, takroriy hisob-kitoblar paytida shifrlangan matn uzunligida eksponensial zarba bo'ladi. Ikkinchidan, Polly Cracker-ning mavjud bo'lgan barcha ko'rsatmalari keyingi kamchiliklardan aziyat chekmoqda (Koblitz,
1998). Ular o'zlariga ishonchsiz, chunki ular ba'zi hujumlarga duchor bo'lishadi, ular juda samarasiz amaliy bo'lishi yoki ular algebraik homomorf xususiyatini yo'qotishi. Demak, bu aniq emas bunday sxemalarni qanday qilib samarali va xavfsiz algebraik homomorfga aylantirish mumkin edi shifrlash sxemalari. Ushbu sxemalarning batafsil tahlilini va tavsifini (Ly, 2002).
2002 yilda J. Domingo-Ferrer ehtimollik, algebraik ravishda homomorfik maxfiy kalitni ishlab chiqdi
kriptotizim (Domingo-Ferrer, 2002). Biroq, ushbu sxema mavjud bo'lganidan beri samarali emas edi takrorlangan ko'paytirish paytida shifrlangan matn uzunligiga eksponensial zarba bajarilishi talab qilinadi. Bundan tashqari, uni Vagner va Bao ham buzgan (Bao, 2003; Vagner, 2003).
Shunday qilib, uzuklar o'rniga guruhlarda gomomorfik shifrlash sxemalarini ko'rib chiqish ko'proq ko'rinadi
mumkin bo'lgan algebraik homomorfik shifrlash sxemasini ishlab chiqishni va'da qilmoqda. Bu bizni olib keladi
kriptografiyada muvaffaqiyatli ishlatilgan tuzilmalarga yaqinroq. Quyidagi teorema haqiqatan ham algebraik ravishda homomorfik sxemalarni qidirishni gabel bo'lmagan maxsus guruhlarda homomorfik sxemalarni izlash (Rappe, 2004). I teorema: Quyidagi ikkita bayon tengdir: (1) algebraik mavjud gomomorfik shifrlash sxemasi (F2 , + ,.). (2) Gomomorfik shifrlash mavjud nosimmetrik guruh bo'yicha sxema (S7
,.).
Isbot: 1 → 2: Ushbu isbot yo'nalishi darhol amal qiladi va u o'zboshimchalik bilan cheklangan uchun amal qiladi
guruh, chunki cheklangan guruhlarning operatsiyalari doimo mantiqiy davrlar tomonidan amalga oshirilishi mumkin. S7 ga ruxsat bering
8 Kriptografiya nazariyasi va amaliyoti va tarmoq xavfsizligi protokollari va texnologiyalari
{0, 1} l kichik to'plam sifatida ifodalanadi
, bu erda masalan. l = 21 ni tanlash mumkin, va C ning zanjiri bo'lsin
elementlarning ikkilik ko'rinishini kirishga qabul qiladigan qo'shish va ko'paytirish eshiklari m1
, m2∈S7
va m1m2 ning ikkilik ko'rinishini chiqaradi
. Agar bizda algebraik bo'lsa
homomorfik shifrlash sxemasi (K, E, D, Add, Mult) bo'yicha (F2
, + ,.) keyin biz homo aniqlay olamiz morfik shifrlash sxemasi (K
˜
, E˜
, D˜
, Mult7) S7 da
E ˜ (m) = (E (s0) ni belgilash orqali
),… .E (sl-1))
bu erda (s0,…… ..sl-1) m ning ikkilik ko'rinishini bildiradi. Mult ˜ almashtirish yordamida tuziladi qo'shimcha.