Криптографияда кездейсоқ оракул моделі

Кіріспе

кездейсоқ сұрақтарға кездейсоқ жауаптар

Криптографияда кездейсоқ оракул – әрбір бірегей сұранысқа өзінің шығыс доменінен тегіс таңдалған (шынайы) кездейсоқ жауап беруге қабілетті оракул (теориялық қара жәшік). Егер сұраныс қайталанса, ол сол сұраныс әр жіберілгенде бірдей жауап береді. Басқаша айтқанда, кездейсоқ оракул – кездейсоқ түрде тегіс таңдалған математикалық функция, яғни әрбір мүмкін сұранысты өзінің шығыс доменінен (белгілі) кездейсоқ жауапқа бейімдейтін функция. Кездейсоқ оракулдар алғаш рет күрделілік теориясы контекстінде пайда болды, онда олар күрделілік кластарының ажыратылуы салыстырмалы тосқауларға тап болуы мүмкін екенін көрсету үшін қолданылды, ең танымал жағдай – 1981 жылы екі кластың кездейсоқ оракулға қатысты дерлік ең болмағанда ерекшеленетіні дәлелденген P vs NP мәселесі. Олар 1993 жылы Михир Белларе мен Филипп Рогавейдің жариялануы арқылы криптографияға енді, олар оларды редукциялық дәлелдерде қолданылатын ресми криптографиялық модель ретінде ұсынды. Олар әдетте криптографиялық хэш-функция туралы нашар болжамдарды қолдана отырып, дәлелдеуді жүзеге асыру мүмкін болмайтын жағдайларда қолданылады. Кездейсоқ оракулмен әрбір хэш-функция ауыстырылғанда қауіпсіздігі дәлелденген жүйе, криптографияның стандартты моделіне қарағанда, кездейсоқ оракул моделінде қауіпсіз деп сипатталады.

Қолданбалар

Кездейсоқ оракулдар криптографиялық хэш-функциялардың идеалды орнын басу үшін жиі қолданылады, әсіресе хэш-функцияның нәтижесінде күшті кездейсоқтық қажет болатын схемаларда. Мұндай дәлелдеме жүйе немесе протоколдың қауіпсіздігін көрсету арқылы жасалады: шабуылшы оракулдан мүмкін емес мінез-құлықты талап етуі керек немесе оны бұзу үшін қиын деп саналатын математикалық есепті шешуі керек. Алайда, бұл тек кездейсоқ оракул моделіндегі қасиеттерді дәлелдейді, яғни жобада елеулі кемшіліктер жоқ екеніне көз жеткізеді. Жалпы, мұндай дәлелдеме стандартты модельде де сол қасиеттерге ие болады деп айту дұрыс емес. Дегенмен, кездейсоқ оракул моделіндегі дәлелдеме, ешқандай формалды қауіпсіздік дәлелдемесінен артық деп есептеледі. Криптографиялық хэш-функциялардың барлық қолданылуы кездейсоқ оракулдарды қажет етпейді: стандартты модельде анықтамасы бар бір немесе бірнеше қасиеттерді (мысалы, соқтығысуға төзімділік, алдын ала кескінді табуға төзімділік, екінші алдын ала кескінді табуға төзімділік және т.б.) қажет ететін схемалар стандартты модельде қауіпсіз екенін дәлелдеуге болады (мысалы, Cramer–Shoup криптожүйесі). Кездейсоқ оракулдар есептеу күрделілігі теориясында ұзақ уақыттан бері қарастырылып келеді, және көптеген схемалар кездейсоқ оракул моделінде қауіпсіз екені дәлелденді, мысалы, Оптималды асимметриялық шифрлау толтыруы, RSA FDH және Ықтималдық қолтаңба схемасы. 1986 жылы Амос Фиат пен Ади Шамир кездейсоқ оракулдардың маңызды қолданылуын көрсетті – қолтаңба құру протоколдарынан өзара әрекеттесуді жою. 1989 жылы Рассел Импаглиаццо мен Стивен Рудич кездейсоқ оракулдардың шектеулерін көрсетті, атап айтқанда, олардың болуы құпия кілт алмасу үшін жеткіліксіз. 1993 жылы Михир Белларе мен Филипп Рогавей осыған қарамастан, кез келген табиғи протокол үшін кездейсоқ оракул моделіндегі қауіпсіздіктің дәлелдемесі, протоколдың практикалық қауіпсіздігіне өте күшті дәлел береді. Жалпы, егер протокол қауіпсіз деп дәлелденсе, оған жасалатын шабуылдар дәлелденгеннен тыс болуы керек немесе дәлелдеудегі болжамдардың біреуін бұзуы керек; мысалы, егер дәлелдеме бүтін сандарды факторлаудың қиындығына сүйенсе, бұл болжамды бұзу үшін жылдам бүтін сандарды факторлау алгоритмін табу қажет. Керісінше, кездейсоқ оракулдың болжамын бұзу үшін, нақты хэш-функцияның белгілі бір белгісіз және жағымсыз қасиеттерін табу керек; мұндай қасиеттердің болуы ықтимал емес деп саналатын жақсы хэш-функциялар үшін қарастырылып отырған протокол қауіпсіз деп есептелуі мүмкін.

Random oracles are typically used as an idealised replacement for cryptographic hash functions in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof often shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some mathematical problem believed hard in order to break it. However, it only proves such properties in the random oracle model, making sure no major design flaws are present. It is in general not true that such a proof implies the same properties in the standard model. Still, a proof in the random oracle model is considered better than no formal security proof at all. Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the standard model (such as collision resistance, preimage resistance, second preimage resistance, etc.) can often be proven secure in the standard model (e. g., the Cramer–Shoup cryptosystem). Random oracles have long been considered in computational complexity theory, and many schemes have been proven secure in the random oracle model, for example Optimal Asymmetric Encryption Padding, RSA FDH and Probabilistic Signature Scheme. In 1986, Amos Fiat and Adi Shamir showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures. In 1989, Russell Impagliazzo and Steven Rudich showed the limitation of random oracles – namely that their existence alone is not sufficient for secret key exchange. In 1993, Mihir Bellare and Phillip Rogaway Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the practical security of the protocol. In general, if a protocol is proven secure, attacks to that protocol must either be outside what was proven, or break one of the assumptions in the proof; for instance if the proof relies on the hardness of integer factorization, to break this assumption one must discover a fast integer factorization algorithm. Instead, to break the random oracle assumption, one must discover some unknown and undesirable property of the actual hash function; for good hash functions where such properties are believed unlikely, the considered protocol can be considered secure.

Кездейсоқ оракулдық гипотеза

Бейкер-Гилл-Соловей теоремасы PA = NPA болатын А оракулының бар екенін көрсеткенімен, Беннетт пен Гиллдің кейінгі жұмыстары кездейсоқ B оракулы үшін (әрбір кіріс элементінің 0 немесе 1-ге 1/2 ықтималдығымен бейнеленетін {0,1}n-ден {0,1}-ге дейінгі функция, барлық басқа кірістердің бейнеленуіне тәуелсіз), PB ⊊ NPB ықтималдығы 1-ге тең екенін көрсетті. Осындай айырмашылықтар, сондай-ақ кездейсоқ оракулдардың сыныптарды 0 немесе 1 ықтималдығымен бөліп тұратындығы (Колмогоровтың нөл-бір заңының салдарынан) кездейсоқ оракул гипотезасын құруға алып келді: егер және тек егер екі "қабылданатын" күрделілік сыныбы C1 және C2 кездейсоқ оракул астында тең болса (1-ге тең ықтималдықпен), онда олар тең болады (кеңдеулік сыныптың қабылданатындығы BG81-де анықталған, IPA ⊊ PSPACEA кездейсоқ оракул A үшін 1 ықтималдығымен орын алады).

Идеал шифр

Идеал шифр – идеалданған блок шифрды модельдеу үшін қолданылатын кездейсоқ пермутация оракулы. Кездейсоқ пермутация әрбір шифрланған мәтін блогын бір және тек бір ғана ашық мәтін блогына, ал керісінше – ашық мәтін блогын бір және тек бір ғана шифрланған мәтін блогына түрлендіреді, яғни бір-бірге сәйкестік бар. Кейбір криптографиялық дәлелдемелерде барлық қатысушыларға тек "алға" пермутация ғана емес, сонымен қатар "кері" пермутация да қолжетімді болады. Жақындағы зерттеулер 10 кезеңдік немесе тіпті 8 кезеңдік Фейстель желілерін қолдана отырып, кездейсоқ оракулдан идеал шифр құрастыру мүмкін екенін көрсетті.

Идеалдық пермутация

Идеалдық пермутация – криптографияда пермутацияның қызметін модельдеу үшін кейде қолданылатын, шығыстары кездейсоқ пермутациядан ажыратылмайтын идеалданған объект. Идеалдық пермутация моделінде идеалдық пермутацияға және оның кері функциясына қосымша оракул арқылы қолжетімділік беріледі. Идеалдық пермутация моделі, идеалдық шифрлау моделінің ерекше жағдайы ретінде қарастырылуы мүмкін, онда идеалдық шифрлау моделіндегі пермутациялар отбасының орнына, тек бір пермутацияға ғана рұқсат беріледі.

Кванттық қолжетімді кездейсоқ оракулдар

Кванттық криптографиядан кейінгі зерттеулер классикалық криптографиялық схемаларға қатысты кванттық шабуылдарды қарастырады. Кездейсоқ оракул – хэш-функцияның абстракциясы болғандықтан, кванттық шабуылшының кездейсоқ оракулға кванттық суперпозиция күйінде қол жеткізе алатынын ескеру логикалық. Көптеген классикалық қауіпсіздік дәлелдемелері осы кванттық кездейсоқ оракул моделінде күшін жояды және қайта қарауды қажет етеді.