Pseudorandom tasodifiy almashtirish - Pseudorandom permutation

Yilda kriptografiya, a yolg'on tasodifiy almashtirish (PRP) dan ajratib bo'lmaydigan funktsiya tasodifiy almashtirish (ya'ni, funktsiya sohasidagi barcha almashtirishlar oilasidan bir xil ehtimollik bilan tasodifiy tanlangan almashtirish) amaliy harakat bilan. An oldindan aytib bo'lmaydigan almashtirish (YUQARILADI) Fk a almashtirish uning qiymatlarini ro'za bashorat qila olmaydi tasodifiy algoritm. A sifatida oldindan aytib bo'lmaydigan almashtirishlardan foydalanish mumkin kriptografik ibtidoiy, yanada murakkab xususiyatlarga ega kriptografik tizimlar uchun qurilish bloklari.

Ta'rif

Pseudorandom tasodifiy almashtirish

Ruxsat bering F xaritalash bo'ling {0,1}n × {0,1}s →{0,1}n. F agar bu PRP bo'lsa

  • Har qanday kishi uchun K ∈ {0,1}s, F a bijection {0,1} dann {0,1} gachan.
  • Har qanday kishi uchun K ∈ {0,1}s, baholash uchun "samarali" algoritm mavjud FK(x).
  • Barcha ehtimoliy polinom-vaqt uchun farqlovchi vositalar D: ∣Pr (D.FK(1n) = 1) - Pr (D.fn(1n) = 1)∣ < ε(s), qaerda K ← {0,1}n tasodifiy ravishda bir xil tanlanadi va fn permutasiyalar to'plamidan tasodifiy ravishda bir tekis tanlanadi n-bit qatorlari.[1]

A pseudorandom permutation oilasi - bu soxta tasodifiy almashtirishlar to'plami, bu erda ma'lum bir almashtirishni kalit yordamida tanlash mumkin.

Oldindan aytib bo'lmaydigan almashtirish

An dushman oldindan aytib bo'lmaydigan almashtirish uchun oldinga va teskari almashtirish operatsiyalari uchun oracle-ga kirish huquqi berilgan algoritm aniqlanadi. Raqibga qiyinchilik tug'diradi k va qiymatini taxmin qilishni so'raydi Fk. Oracle-ga ushbu bashoratni amalga oshirishda unga yordam berish uchun bir qator so'rovlar yuborishga ruxsat beriladi, ammo qiymatini so'rashga yo'l qo'yilmaydi. k o'zi.[2]

O'zgarishlar yaratish uchun tasodifiy algoritm an hosil qiladi oldindan aytib bo'lmaydigan almashtirish agar uning natijalari buyumlar to'plamidagi almashtirishlar bo'lsa (uzunlik bilan tavsiflanadi -n aniqlik bilan oldindan aytib bo'lmaydigan ikkilik satrlar) polinom ( n) sinov davri oldidan oracle-ga so'rovlar soni, ularning ishlash vaqti polinom yilda n, va uning xato ehtimoli barcha misollar uchun 1/2 dan kam. Ya'ni, buni oldindan aytib bo'lmaydi murakkablik sinfi PP, relyativlashtirilgan almashtirish uchun oracle tomonidan.[2]

Blok shifrlarining modeli

A (kalitli) ning idealizatsiya qilingan abstraktsiyasi blok shifr haqiqatan ham tasodifiy almashtirish oddiy va shifrlangan matnlar orasidagi xaritalarda. Agar farq qiladigan algoritm mavjud bo'lsa, unda muhim natijalarga erishiladi afzallik blok shifrida ko'rsatilganidan kam harakat bilan xavfsizlik parametri (bu odatda talab qilinadigan kuch, shifrning asosiy maydoni orqali qo'pol kuch qidirish bilan bir xil bo'lishi kerakligini anglatadi), u holda shifr hech bo'lmaganda sertifikatlash ma'nosida buzilgan deb hisoblanadi, hatto bunday tanaffus darhol amaliy natijalarga olib kelmasa ham xavfsizlik muvaffaqiyatsizlik.[3]

Zamonaviy shifrlarning super pseudorandomness bo'lishi kutilmoqda, ya'ni shifr bo'lishi kerak tasodifiy tanlangan almashtirishdan farq qilmaydi dushman shifrning oldinga va teskari yo'nalishlariga qora quti orqali kirish huquqiga ega bo'lsa ham, xuddi shu xabar maydonida.[4]

Bashorat qilinmaydigan almashtirishlarning xususiyatlari

Bu funktsiya ekanligini ko'rsatish mumkin Fk xavfsiz emas xabarni tasdiqlash kodi (MAC), agar u faqat oldindan aytib bo'lmaydigan talabni qondirsa. Bundan tashqari, UP sifatida modellashtirilgan blokli shifrdan samarali o'zgaruvchan kirish uzunligini MAC ni qurish mumkin emasligini ko'rsatish mumkin. n bitlar. A ning chiqishi ko'rsatilgan k = n/ω(logλ) oldindan taxmin qilinmaydigan yumaloq funktsiyalarga ega Feistel konstruktsiyasi barcha oraliq dumaloq qiymatlarni chiqarib yuborishi mumkin.[2] Haqiqiy oldindan aytib bo'lmaydigan funktsiyalar (UF) uchun ham oraliq dumaloq qiymatlar haqida ba'zi qisman ma'lumotlar chiqishi orqali chiqib ketishi mumkin. Keyinchalik, agar Feistel konstruktsiyasida o'ta logaritmik ko'p sonli tur ishlatilsa, u holda raqib barcha oraliq dumaloq qiymatlarni permütasyon chiqishi bilan birga olgan taqdirda ham, UP qurilishi xavfsiz bo'ladi.[5]

Bu borada isbotlangan teorema ham mavjud, agar u erda UPning samarali raqibi bo'lsa Aπ bu beparvo bo'lmagan afzalliklarga ega επ UP qurilishiga qarshi oldindan aytib bo'lmaydigan o'yinda ψU, k va raqibga polinom sonli savollar beradigan, UF raqibi ham mavjud Af UF oilasidan olingan UFga qarshi oldindan aytib bo'lmaydigan o'yinda beparvo bo'lmagan ustunlikka egaF . Bundan ko'rinib turibdiki, UP raqibining maksimal ustunligi Aπ bu επ = O (εf. (qk)6). Bu yerda εf U vaqtida ishlaydigan UF dushmanining maksimal ustunligini bildiradi (t + (qk)5) dan olingan UFga qarshi F, qayerda t PRP dushmanining ishlash vaqti Aψ va q u tomonidan qilingan so'rovlar soni.[5][6]

Bundan tashqari, oldindan aytib bo'lmaydigan xususiyatni qondiradigan va psevdo-tasodifiy emas, balki imzolash sxemasi aslida tasdiqlanadigan oldindan aytib bo'lmaydigan funktsiya (VUF) hisoblanadi. Tasdiqlanadigan oldindan aytib bo'lmaydigan funktsiya Verifiedable Pseudorandom Function (VRF) ga o'xshash tarzda aniqlanadi, ammo psevdo-tasodifiylik uchun kuchsizroq oldindan aytib bo'lmaydiganlik bilan almashtiriladi. Tasdiqlanadigan oldindan aytib bo'lmaydigan almashtirishlar - VUFlarning permutatsion analoglari yoki VRPlarning oldindan aytib bo'lmaydigan analoglari. VRP ham VUP va VUP aslida VRFga tatbiq etilgan Feistel konstruktsiyasi orqali VRP qurish orqali qurilishi mumkin. Ammo bu foydali deb hisoblanmaydi, chunki VUFlarni qurish VRFlarga qaraganda ancha osonroq ko'rinadi.[7]

Pseudorandom funktsiyasi bilan ulanishlar

Maykl Lubi va Charlz Rakoff[8] a dan "kuchli" psevdordan tasodifiy almashtirishni qurish mumkinligini ko'rsatdi pseudorandom funktsiyasi yordamida Luby-Rackoff qurilishi yordamida qurilgan Feystel shifri.

Ilovalar

K x X → X ∀ X = {0,1}64, K = {0,1}56
K x X → X ∀ k = X = {0,1}128

Shuningdek qarang

  • Shifrni bloklash (sobit o'lchovli bit bloklarida ishlaydigan pseudorandom tasodifiy almashtirish oilalari)
  • Formatni saqlaydigan shifrlash (o'zboshimchalik bilan cheklangan to'plamlarda ishlaydigan yolg'on tasodifiy almashtirish oilalari)

Adabiyotlar

  1. ^ Kats, Jonatan; Lindell, Yuda (2007). Zamonaviy kriptografiyaga kirish: tamoyillar va protokollar. Chapman va Hall / CRC. ISBN  978-1584885511.
  2. ^ a b v Puniya, Prashant (2007), Hash funktsiyalari va blokirovka shifrlari uchun yangi dizayn mezonlari (PDF), T.f.n. tezis, Nyu-York universiteti kompyuter fanlari bo'limi.
  3. ^ Mixir Bellare, Fillip Rogavey (2005-05-11). "4-bob: Pseudorandom funktsiyalari" (PDF). Zamonaviy kriptografiyaga kirish. Olingan 2020-05-18.
  4. ^ Kreyg Gentri va Zulfikar Ramzan. "Hatto Mansur shifridagi tasodifiy permautatsiya mo''jizalarini yo'q qilish".
  5. ^ a b Kriptologiya sohasidagi yutuqlar - EUROCRYPT 2007: Xalqaro Kriptologik tadqiqotlar assotsiatsiyasi Moni Naor tomonidan 26-yillik Xalqaro konferentsiya - Kriptografik texnika nazariyasi va qo'llanilishi.
  6. ^ http://cs.nyu.edu/~puniya/papers/public_feistel.pdf
  7. ^ Mikali, Silvio; Rabin, Maykl; Vadhan, Salil (1999), "Tasdiqlanadigan tasodifiy funktsiyalar", Kompyuter fanlari asoslari bo'yicha 40-yillik simpozium (Nyu-York, 1999), IEEE Computer Soc., Los Alamitos, CA, 120-130 betlar, CiteSeerX  10.1.1.207.6638, doi:10.1109 / SFFCS.1999.814584, ISBN  978-0-7695-0409-4, JANOB  1917552, S2CID  221565852.
  8. ^ Lyui, Maykl; Rackoff, Charlz (1988). "Pseudorandom funktsiyalardan psevdandom tasodifiy permutatsiyalarni qanday tuzish kerak". SIAM J. Comput. 17 (2): 373–386. doi:10.1137/0217022.