|
Fortuna.
Yaxshiyamki, yuqoridagi xulosa haddan tashqari pessimistik. Haqiqatan ham, yechim g‘oyasi yuqoridagi ikkita mashhur RNG hujjatidan kelib chiqqan bo‘lib, uning dizayni keyingi muammoni muddatidan oldin yengib o‘tish istagi bilan qattiq ta’sirlangan: Yarrow (Schneier, Kelsey va Ferguson [KSF99] tomonidan ishlab chiqilgan va MacOS/iOS/FreeBSF99 tomonidan ishlab chiqilgan va MacOS/iOS/FreeBSFuered(Windows) tomonidan ishlatilgan [va] [FS03] va Windows tomonidan foydalaniladi [Ferguson] ]). Ushbu ishlarning sodda, ammo ajoyib g'oyasi kiruvchi entropiyani bir nechta entropiya "hovuzlariga" bo'lish va keyin kamida bitta hovuz etarli miqdorda to'planishini kafolatlash uchun natijalarni ishlab chiqarishda bu hovuzlardan juda ko'p har xil stavkalarda oqilona foydalanishdir. keyingi qo'ng'iroq bilan "vaqtdan oldin bo'shatilmasdan" xavfsizlikni kafolatlash uchun entropiya. (Batafsil ma'lumot uchun 4-bo'limga qarang.)
Fergyuson va Shnayer o'zlarining Fortuna "hovuz rejalashtiruvchisi" konstruktsiyasi uchun yaxshi xavfsizlik sezgisini ta'minlaydilar, bunda barcha RNGinputsI1, . . . , Iq bir xil(noma'lum)entropiya va hovuzning har biri o'zi olgan barcha entropiyani yo'qotishsiz to'plashi mumkin. (Ular bunga erishish uchun evristik usul sifatida kriptografik xesh funksiyasi bilan takrorlangan xeshlashdan foydalanishni taklif qiladilar.) Xususan, agar q sonining yuqori chegarasi bo'lsa.
kiritishlar, ular hovuzlar sonini P = log2 q qilish va zarur bo'lgan yangi entropiya miqdorida O (log q) omilini yo'qotishda davlat murosasidan (erta keyingi!) tiklanishni taklif qiladi.
Bizning asosiy natijamiz.
Fortuna g'oyasidan ilhomlanib, biz [DPR+13] ning RNG mustahkamligi haqidagi oldingi tushunchasini keyingi erta qarshi mustahkamlikka rasmiy ravishda kengaytiramiz. Fergyuson va Shnayyerdan farqli o'laroq, biz buni hech qanday cheklovchi farazlarsiz, masalan, barcha kirishlar Ij entropiyasi doimiy bo'lishini talab qilmasdan qilamiz. (Haqiqatan ham, bu entropiyalar [DPR+13] modelidagi kabi qarama-qarshilik bilan tanlanishi mumkin va RNG uchun noma'lum bo'lishi mumkin.) Shuningdek, bizning rasmiy va umumiy xavfsizlik modelimizda biz ideal entropiya to'planishini qabul qilmaymiz yoki tabiatan tayanmaymiz. kriptografik xesh-funksiyalar haqida. Aslida, bizning modelimiz sintaktik jihatdan [DPR+13] ning oldingi RNG modeliga juda o'xshaydi, bundan tashqari: (1) muddatidan oldin keyingi qo'ng'iroq tuzatib bo'lmaydigan davlat korruptsiyasi deb hisoblanmaydi, lekin (2) (eski) ga qo'shimcha ravishda " entropiya penalti” parametri g∗ boʻlsa, (yangi) “vaqt jazosi” parametri b ≥ 1 mavjud boʻlib, yangi entropiyaning g∗ bitlarini olish uchun zarur boʻlgan optimal tiklanish vaqtiga nisbatan holat murosasidan tiklanish uchun qancha vaqt ketishini oʻlchaydi. (2 va 3-rasmlarga qarang.)
Xulosa qilib aytadigan bo'lsak, bizning modelimiz davlat murosasidan samarali tiklanish mexanizmini loyihalash muammosini onlayn optimallashtirish muammosi sifatida rasmiylashtiradi. Agar biz oxirgi murosaga kelish vaqtini va o'shandan beri to'plangan entropiya miqdorini bilganimizda, holat yana tasodifiy holga kelguniga qadar har qanday natijalarni ishlab chiqarishni to'xtatishimiz mumkin edi. Biroq, bizning vazifamiz eng qiyin (va eng real) holatda ham ushbu optimal yechimga mutanosib vaqt ichida tiklanishdir, bunda (a) biz oxirgi holatning murosaga kelish vaqti va keyin kiritilgan yangi entropiya miqdori haqida hech narsa bilmaymiz. keyin holatga o'tadi va (b) natijalarni muddatidan oldin ishlab chiqarish RNG tomonidan qo'llaniladigan barcha qo'shilgan entropiyaning to'liq yo'qolishiga olib keladi, chunki tajovuzkor barcha mumkin bo'lgan past entropiya holatlarini sanab o'tish uchun qo'pol kuch ishlatishi mumkin. Boshqacha qilib aytadigan bo'lsak, muammo biz bilmaydigan murosadan keyin kunni imkon qadar tezroq saqlab qolish kafolatlangan tiklanish mexanizmlarini ishlab chiqishdir. Biz duch keladigan dilemma shundaki, muddatidan oldin ishlatilgan har qanday entropiya yo'qoladi va foydalanilmagan holda saqlangan har qanday entropiya tiklanishni kechiktiradi.
Kelgusi erta qo'ng'iroqlarni hal qilish uchun modelimizni kengaytirganimizdan so'ng, biz Fortuna umumlashtirilgan konstruktsiyasini aniqlaymiz, bu esa keyingi erta qo'ng'iroqlarga nisbatan ishonchli. Haqiqiy Fortuna tomonidan ilhomlantirilgan bo'lsa-da, bizning konstruktsiyamiz sintaksisi sezilarli darajada farq qiladi (5-rasmga qarang), chunki biz uni kuchliroq modelda va ideallashtirilgan taxminlarsiz (masalan, mukammal entropiya to'planishi kabi) ishonchli isbotlaymiz.
[DPR+13] dagi hujumlar bilan namoyon bo'ladi, bu gilam ostidan supurish uchun arzimas narsa emas). Darhaqiqat, qurilishimizni olish uchun biz: (a) (hovuz) rejalashtiruvchining qat'iy xavfsizlik tushunchasini mavhumlashtiramiz; (b) keyingi muddatidan oldin xavfsizlikka erishish uchun [DPR+13] ning oldingi modelida xavfsiz rejalashtiruvchi har qanday mustahkam RNG bilan tuzilishi mumkinligini bildiruvchi rasmiy kompozitsiya teoremasini ko'rsating (2-teorema); (c) ishonchli xavfsiz [DPR+13] RNG va Fortuna-ga o'xshash rejalashtiruvchi (bizning sezilarli darajada kuchliroq modelimizda xavfsiz ekanligi isbotlangan) yordamida yakuniy RNG ni oling. Xususan, olingan RNG standart modelda xavfsizdir va faqat standart PRGlar mavjudligidan yagona hisoblash farazi sifatida foydalanadi.
Do'stlaringiz bilan baham: |
