Entropiyangizni qanday iste'mol qilish va unga EGA bo'lish va buzilgan rng uchun optimal tiklash strategiyalari

Boshqa tegishli ishlar.
Yuqorida aytib o'tganimizdek, standart modeldagi kirishlar bilan RNG-larni loyihalash va tahlil qilishga qaratilgan adabiyotlar juda kam. [BH05, DPR+13] ga qo'shimcha ravishda, Linux RNG ning ba'zi tahlillari Lacharme, Röck, Strubel va Videau [LRSV12] tomonidan amalga oshirildi. Boshqa tomondan, ko'plab ishlar zaif tasodifiylikdan foydalanganda turli kriptografik sxemalarga halokatli hujumlarni ko'rsatdi; ba'zi muhim misollar orasida [GPR06, KSWH98, NS02, CVE08, DGP07, LHA + 12, HDWH12] mavjud.
2. Dastlabki o'yinlar
Entropiya. Diskret X taqsimot uchun uning minimal entropiyasini H∞(X) = minx{− log Pr[X = x]} bilan belgilaymiz.
Shuningdek, X ning boshqa tasodifiy o‘zgaruvchisi Z tufayli eng yomon minimal entropiyasini quyidagicha aniqlaymiz: konservativ tarzda: H∞(X|Z) = − log([maxx,z Pr[X = x|Z = z]]). Biz bu ta'rifni odatdagi o'rniga ishlatamiz, shuning uchun u "zanjir qoidasi" deb ataladigan quyidagi munosabatni qondiradi: H∞(X, Z) − H∞(Z) ≥ H∞(X|Z).
Pseudortasodifiy funktsiyalar va generatorlar. Biz aytamizki, F : {0, 1}ℓ × {0, 1}m → {0, 1}m, agar vaqtda bo'lsa, (deterministik) (t, qF, e)-psevdo-tasodifiy funktsiya (PRF) bo'ladi. t va F(kalit, ·) da qF oracle so‘rovlarini ishga tushirish F(kalit, ·) va tasodifiy funksiyani ←$ {0, 1}ℓ kaliti bo‘lganda, ehtimolligi e dan katta bo‘lgan tasodifiy funksiyani ajrata oladi. Biz aytamizki, G : {0, 1}m → {0, 1}n funksiyasi (deterministik) (t, e)-psevdo-tasodifiy generator (PRG) boʻlsa, t vaqtida ishlayotgan hech qanday raqib G (urugʻ) ni ajrata olmasa. ) va urug' ←$ {0, 1}m bo'lganda ehtimollik e dan katta bo'lgan bir xil tasodifiy bitlar.
O'yin tuzilishi. Xavfsizlik ta'riflari va dalillarimiz uchun biz kodga asoslangan o'yin tizimidan foydalanamiz [BR06]. O'YINda ishga tushirish protsedurasi, dushman oracle so'rovlariga javob berish tartiblari va tugatish protsedurasi mavjud. GAME o'yini raqib A bilan quyidagicha amalga oshiriladi: birinchidan, ishga tushirish amalga oshiriladi va uning natijalari A ga kiritiladi. Keyin A bajariladi va uning oracle so'rovlariga tegishli GAME protseduralari orqali javob beriladi. A tugagach, uning chiqishi yakuniy protseduraga kirishga aylanadi. Ikkinchisining chiqishi o'yindan chiqish deb ataladi va GAMEA ⇒ y bu o'yindan chiqish y qiymatini olgan voqeani bildirsin. AGAME raqibning natijasini bildiradi va AdvAGAME = 2 × Pr[GAMEA ⇒ 1] − 1. Bizning konventsiyamiz shundan iboratki, mantiqiy bayroqlar noto'g'ri ishga tushirilgan deb taxmin qilinadi va raqib A ning ish vaqti jami sifatida aniqlanadi. raqib kutayotgan o'yin vaqti, shu jumladan o'yin tartibi.
3. Kirish bilan RNG: modellashtirish va xavfsizlik
Ushbu bo'limda biz kirishlari bilan RNG uchun rasmiy modellashtirish va xavfsizlik ta'riflarini taqdim etamiz, asosan [DPR+13] dan keyin.