Кіріспе

Криптографиялық схема, таңдалған мәнге міндеттеме беруге мүмкіндік береді.

Міндеттеме схемасы – бұл таңдалған мәнді (немесе таңдалған мәлімдемені) жасырып, кейіннен міндеттелген мәнді ашу мүмкіндігімен байланыстыруға мүмкіндік беретін криптографиялық құрал. Міндеттеме схемалары осылай жасалған, оларға міндеттелгеннен кейін мән немесе мәлімдемені өзгертуге ешкімнің мүмкіндігі болмайды: яғни, міндеттеме схемалары міндетті. Міндеттеме схемалары қауіпсіз монета лақтыру, нөлдік білімді дәлелдеу және қауіпсіз есептеу сияқты бірқатар криптографиялық протоколдарда маңызды қолданысқа ие. Міндеттеме схемасын елестетудің бір жолы – жіберушінің хабарламаны құлыпталған қорапқа салып, қорапты алушыға беруі. Қораптың ішіндегі хабар алушыдан жасырылады, ол кілтін өзі аша алмайды. Алушы қорапты иеленгендіктен, хабарламаны өзгерте алмайды – тек жіберуші кейінірек кілтті берсе ғана ашуға болады. Міндеттеме схемасындағы өзара әрекеттесу екі кезеңде жүзеге асырылады:

міндеттеме кезеңі, онда мән таңдалып, міндеттеледі;
ашу кезеңі, онда жіберуші мәнді ашады, содан кейін алушы оның дұрыстығын тексереді.

Жоғарыдағы мысалда, міндеттеме кезеңі – жіберушінің хабарламаны қорапқа салып, құлыптап қоюы. Ашу кезеңі – жіберушінің кілтті алушыға беруі, ол оны қорапты ашып, мазмұнын тексеру үшін пайдаланады. Құлыпталған қорап – бұл міндеттеме, ал кілт – дәлел. Қарапайым протоколдарда міндеттеме кезеңі жіберушіден алушыға бір хабарламадан тұрады. Бұл хабарлама "міндеттеме" деп аталады. Мүмкін емес, алушы сол кезде хабарламадан таңдалған нақты мәнді анықтай алуы керек (бұл жасыру қасиеті деп аталады). Қарапайым ашу кезеңі бір хабарламадан тұрады, жіберушіден алушыға, содан кейін алушы оны тексереді. Міндеттеме кезеңінде таңдалған мән жіберуші есептей алатын және ашу кезеңінде расталатын жалғыз мән болуы керек (бұл байланыс қасиеті деп аталады). Міндеттеме схемаларының тұжырымдамасын алғаш рет 1988 жылы Жиль Брассар, Дэвид Шоум және Клод Крепо НП үшін әртүрлі міндеттеме схемаларына негізделген әртүрлі нөлдік білім протоколдарының бөлігі ретінде ресмилендірген болуы мүмкін. Бірақ бұл ұғым бұрын ресми түрде қарастырылмастан қолданылған. Міндеттемелер туралы түсінік алғаш рет Мануэль Блум, Шимон Эвен және Ади Шамир және т.б. еңбектерінде пайда болды. Терминологияны Блум жасаған сияқты. Екіншіден, міндеттемелер нөлдік білімді дәлелдеуде тексеруші тарапынан да қолданылады, олар көбінесе өз таңдауларын міндеттемеде алдын ала көрсетеді. Бұл нөлдік білімді дәлелдеулерді қосымша ақпаратты дәлелдеушіге көрсетпей қатар құрастыруға мүмкіндік береді.

Қолтаңбалау жүйелері

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

Тексерілетін құпияны ортаға салу

Міндеттемелердің тағы бір маңызды қолданылуы – расталатын құпия бөлісу, көп тарапты қауіпсіз есептеудің өте маңызды құралы. Құпия бөлісу схемасында, бірнеше тараптың әрқайсысына құпия сақталуы тиіс мәннің "үлестері" беріледі. Егер жеткілікті тараптар біріксе, олардың үлестерін пайдаланып құпияны қайта құруға болады, бірақ тіпті жеткіліксіз көлемдегі қастандық жасаушылардың тобы да ештеңе білмеуі керек. Құпия бөлісу – қауіпсіз есептеуге арналған көптеген протоколдардың негізі: ортақ кіріс функциясын қауіпсіз есептеу үшін, құпия үлестерді манипуляциялау арқылы жұмыс істейді. Дегенмен, егер үлестер қастандық жасаушы тараптармен жасалса, олардың дұрыстығын тексеру маңызды болуы мүмкін. Расталатын құпия бөлісу схемасында, құпияны тарату жеке үлестерге міндеттемелермен бірге жүреді. Міндеттемелер қастандық жасаушы топқа көмектесетін ештеңе ашпайды, бірақ үлестер әр тарапқа өз үлестерінің дұрыс екенін тексеруге мүмкіндік береді.

Қамқорлықты анықтау

Міндеттемелік схемалардың ресми анықтамалары нотация және мазмұны жағынан күрт өзгеше. Мұндай мазмұнның біріншісі – міндеттемелік схема жасыру немесе байланыстыру қасиеттеріне қатысты толық немесе есептеулік қауіпсіздік қамтамасыз ете ме. Тағы бір мазмұны – міндеттеме интерактивті ме, яғни міндеттеме және ашу кезеңдері криптографиялық протокол арқылы орындала ма, әлде олар Commit және CheckReveal есімді екі алгоритмнен тұратын интерактивті емес пе. Соңғы жағдайда CheckReveal схемасын Commit схемасының кездейсоқтандырылмаған түрі деп қарастыруға болады, ал Commit схемасында қолданылған кездейсоқтық ашу ақпаратын құрайды. Егер C міндеттемесі x мәніне C:=Commit(x,open) арқылы есептелсе, онда open міндеттеме есептеу үшін қолданылған кездейсоқтық болып табылады, сонда CheckReveal(C,x,open) теңдеуін C=Commit(x,open) тексеруге дейін тоғытылады. Осы нотацияны және математикалық функциялар мен ықтималдықтар теориясы туралы білімді пайдаланып, біз міндеттемелердің байланыстыру және жасыру қасиеттерінің әртүрлі нұсқаларын ресми түрде жасаймыз. Бұл қасиеттердің ең маңызды екі комбинациясы – толық байланыстырғыш және есептеулік жасырындыратын міндеттеме схемалары, сондай-ақ есептеулік байланыстырғыш және толық жасырындыратын міндеттеме схемалары. Ешбір міндеттеме схемасы бір уақытта толық байланыстырғыш және толық жасырындыратын бола алмайды – есептеулік шексіз қарсылас x-тің әрбір мәні үшін Commit(x,open) құра алады және C нәтижесін беретін жұпты тапқанға дейін іздейді, ал толық байланыстырғыш схемада бұл x-ті бірегей анықтайды.

Есептеулік байлау

open өлшемдер жиынтығынан таңдалсын, яғни оны k биттік тізбек ретінде көрсетуге болады, ал – сәйкес міндеттеме схемасы. k-ның мөлшері міндеттеме схемасының қауіпсіздігін анықтайтындықтан, ол қауіпсіздік параметрі деп аталады. Содан кейін, ұзындығы k-ға дейін өсетін және шығыс беретін барлық біркелкі емес ықтималдық полиномиалдық уақыт алгоритмдері үшін, және болатын ықтималдық k-ға қатысты мардымсыз функция болып табылады. Бұл асимптотикалық талдаудың бір түрі. Сондай-ақ, нақты қауіпсіздікті қолдану арқылы да осы талапты көрсетуге болады: Commit міндеттеме схемасы, егер t уақытында жұмыс істейтін және шығыс беретін барлық алгоритмдер үшін, және болатын ықтималдық -тан аспаса, қауіпсіз болып есептеледі.

Кемел, статистикалық және есептеу жасыру

Кез келген қауіпсіздік параметрі k үшін ашылу мәндері бойынша біркелкі үлестірілім болсын. Егер барлық ықтималдық жиынтықтары үшін, міндеттеме схемасы тиісінше толық, статистикалық немесе есептеулік жасыруға ие болса, онда олар тең, статистикалық жақын немесе есептеу арқылы ажыратылмайды.

Құрылыс

Міндеттеме схемасы толыққанды міндетті болуы мүмкін (Алиса жасағаннан кейін міндеттемесін өзгерте алмайды, тіпті шексіз есептеу ресурстары болған жағдайда да); немесе толыққанды жасырын болуы мүмкін (Боб Алиса ашпастан міндеттемені анықтай алмайды, тіпті шексіз есептеу ресурстары болған жағдайда да); немесе басқа мәселенің шешіміне байланысты жасырын немесе міндетті болатын, инстанцияға тәуелді міндеттеме схемасы түрінде құрылуы мүмкін. Міндеттеме схемасы бір уақытта толыққанды жасырын және толыққанды міндетті бола алмайды.

Кездейсоқ оракул үлгісіндегі бит-келісу

Біттік міндеттеме схемаларын кездейсоқ оракул модельде құру оңай. 3k биттік шығысы бар H хэш-функциясы берілгенде, k биттік хабарлама m жіберу үшін Алиса кездейсоқ k биттік тізбек R-ді жасайды және Бобқа H(R||m) жібереді. Кез келген R′, m′ бар болу ықтималдығы, мұнда m′ ≠ m, сондықтан H(R′||m′) = H(R||m) шамамен 2−k-ға тең, бірақ Бобтың хабарлама m туралы кез келген болжамды тексеруі үшін кездейсоқ оракулға 2k (бұрыс болжам үшін) немесе 2k+1 (орташа есеп бойынша, дұрыс болжам үшін) сұрау салу қажет болады. Хэш-функцияларға негізделген бұрынғы схемалардың, негізінен, осы хэш-функцияларды кездейсоқ оракул ретінде идеалдауға негізделген схемалар екенін атап өтейік.

Бір бағыттағы кез келген пермутациядан біттік жүктеме

Біт-келісім схемасын инъективті кез келген бір бағытты функциядан жасауға болады. Схеманың негізі – әрбір бір бағытты функцияны (Голдрейх-Левин теоремасы арқылы) есептеу қиын өзекті предикатқа ие болу үшін өзгертуге болады (инъективті қасиетті сақтап). f инъективті бір бағытты функция болсын, ал h – қатты өзекті предикат. Онда b битіне келісім беру үшін Алиса кездейсоқ x енгізуін таңдайды және Бобқа үштік жібереді, мұнда ⊕ – XOR операциясын, яғни 2 модулі бойынша биттік қосуды білдіреді. Келісімнен бас тарту үшін Алиса Бобқа тек x жібереді. Боб f(x) есептеу арқылы және келісімге берілген мәнмен салыстырып тексеріп шығады. Бұл схема жасырады, себебі Бобтың b-ні қалпына келтіруі үшін ол h(x)-ті қалпына келтіруі керек. h есептеу бойынша қатты өзекті предикат болғандықтан, f(x) бойынша h(x)-ті жартысынан артық ықтималдықпен қалпына келтіру, f-ді кері айналдырумен бірдей қиын. Керемет байланыс f инъективті болғандықтан және осылайша f(x)-тің дәл бір кері бейнесі болғандықтан туындайды.

Физикалық клонды емес функцияларға негізделген міндеттемелер

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