Fani bo’yicha mustaqil ish mavzu

Rivojlanish tarixi
Shafi Goldvasser 1986 yilda Silvio Micali, Oded Goldreich[en] va Avi Vigderson maxfiylikni saqlagan holda tomonlarning "adolatli xulq-atvorini" ta'minlashi kerak bo'lgan kriptografik protokollarni yaratish uchun nol bilim dalillaridan foydalanishni tasvirlab berdilar.
Nolinchi bilim isboti quyidagi olimlar tomonidan ishlab chiqilgan va ishlab chiqilgan: Shafi Goldwasser, Silvio Micali va Charlz Reckoff va ular tomonidan 1989 yilda "Isbotli interaktiv tizimning bilimi va murakkabligi" maqolasida nashr etilgan. Bu ish Proverdan Verifierga uzatilishi kerak bo'lgan isbot ma'lumotlari miqdoriga asoslangan interaktiv isbot tizimlari ierarxiyasini taqdim etdi. Ular, shuningdek, maxsus qo'yilgan nol bilim dalilining birinchi isbotini taklif qildilar, kvadratik qoldiq moduli m. Keyinchalik, o'z ishlarini to'ldirib, ular 1993 yilda birinchi Gödel mukofotiga sazovor bo'lishdi.
Bundan tashqari, 1982 yilda Shafi Goldwasser va Silvio Micali tomonidan ishlab chiqilgan ochiq kalitli kriptografik tizim bo'lgan ko'rib chiqilgan interaktiv protokolga asoslangan Goldwasser-Micali kriptotizimi standart kriptografik taxminlar ostida ishonchli xavfsiz bo'lgan birinchi ochiq kalit ehtimoliy shifrlash sxemasi hisoblanadi. Taklif etilgan tizim hakamlar hay'ati tomonidan yuqori baholandi: Goldowasser va Mikali 2012 yil uchun Tyuring mukofoti laureatlari bo'lishdi, ehtimollik shifrlash bilan kriptotizimni yaratish, nominatsiyada zamonaviy texnologiyalarga sezilarli ta'sir ko'rsatgan innovatsion ish sifatida qayd etilgan. kriptografiya. Biroq, kriptotizim samarasiz, chunki u tomonidan yaratilgan shifrlangan matn shifrlangan xabardan yuzlab marta uzunroq bo'lishi mumkin.
Kriptotizimning xavfsizlik xususiyatlarini isbotlash uchun Goldwasser va Micali semantik xavfsizlik tushunchasini kiritdilar. 2021 yilda Laslo Lovas va Avi Vigderson nazariy informatika sohasidagi ishlari uchun Abel mukofoti bilan taqdirlandilar, bu esa hisoblash murakkabligi nazariyasi, grafiklar nazariyasi, taqsimlangan hisoblash usullari va nol bilim isbotlari kontseptsiyasining rivojlanishiga katta hissa qo'shgan.

Nolinchi ma'lumotni isbotlash - kriptografik protokol bo'lib, tomonlardan biriga (tasdiqlovchi, B tomon) ikkinchi tomon (tasdiqlovchi, A tomon) bayonotni bilishini tekshirishga imkon beradi, tekshiruvchi esa bayonot haqida boshqa ma'lumot olmaydi o'zi. Boshqacha qilib aytganda, A sirning o'zini oshkor qilmasdan, sirni bilishni isbotlaydi.

Shaxsni tasdiqlash uchun nol bilim dalillaridan foydalanish birinchi marta Uriel Feig, Amos Fiat va Adi Shamir tomonidan taklif qilingan. Bunday holda, foydalanuvchi o'zining shaxsiy kaliti haqidagi bilimini isbotlaydi, bu holda uni oshkor qilmasdan, bu sir bo'lib xizmat qiladi. Shunday qilib, u o'z shaxsini isbotlaydi.
Isbot interaktiv protokol shaklini oladi. Bu shuni anglatadiki, B partiya proverga bir qator savollar beradi, agar u sirni bilsa, barcha savollarga to'g'ri javob beradi. Agar A tomon sirni bilmasa, lekin tekshiruvchini aksiga ishontirmoqchi bo'lsa, u savolga to'g'ri javob berish ehtimoli bor (ehtimol, bu mavzudagi misollarda bo'lgani kabi 50%). Biroq, ma'lum miqdordagi savollardan so'ng (10 - 20), tekshiruvchi prover sirni bilmasligiga juda katta ehtimollik bilan ishonch hosil qiladi. Shu bilan birga, javoblarning hech biri sirning o'zi haqida hech qanday ma'lumot bermaydi.