Білімді ашпай шындықты дәлелдеу

Кіріспе

Басқа деректерді ашпай, жарамдылықты дәлелдеу

Криптографияда нөлдік білімді дәлелдеу немесе нөлдік білімді протокол – бұл бір тараптың (дәлелдеуші) екінші тарапқа (тексерушіге) белгілі бір мәлімдеменің рас екенін дәлелдейтін әдіс, сонымен бірге мәлімдеменің растығынан басқа ешқандай ақпаратты тексерушіге жеткізбеу. Нөлдік білімді дәлелдеудің түйсігі – белгілі бір ақпараттың иесі екенін оны жай ғана ашу арқылы дәлелдеудің оңай екендігінде; қиындық – ақпаратты немесе оның кез келген бөлігін ашпай-ақ осы иелікті дәлелдеу болып табылады. Егер тексеруші мәлімдемеге байланысты белгілі бір құпия ақпаратқа ие болса ғана, сол мәлімдемені дәлелдей алатынын ескере отырып, мәлімдеменің растығына көз жеткізгеннен кейін де, үшінші тараптарға оны дәлелдеу мүмкіндігі болмауы керек. Қарапайым модельде, маңызды емес нөлдік білімді дәлелдеулер (яғни, BPP-ден тыс тілдер үшін) дәлелдеуші мен тексеруші арасындағы өзара әрекеттесуді қажет етеді. Бұл өзара әрекеттесу көбінесе тексерушінің бір немесе бірнеше кездейсоқ сұрақтарды таңдауын қамтиды; осы сұрақтардың кездейсоқ болуы және дәлелдеушінің оларға сәтті жауап беруі тексерушіні дәлелдеушінің мәлімделген білімге ие екеніне бірлесіп сендіреді. Егер өзара әрекеттесу болмаса, тексеруші протоколдың орындалу жазбасын (яғни, дәлелдеушінің жалғыз хабары) алғаннан кейін, оны үшінші тарапқа қайта жіберіп, осылайша үшінші тарапты тексерушінің де құпия ақпаратқа ие екеніне көндіре алады. Ортақ кездейсоқ тізбек және кездейсоқ оракул модельдерінде Fiat–Shamir эвристикасы негізінде өзара әрекеттесусіз нөлдік білімді дәлелдеулер бар. Бұл дәлелдеулер практикада есептеулік болжамдарға (әдетте криптографиялық хэш-функцияның соқтығысу кедергісіне) сүйенеді.

Әли Баба үңгірі

Жан Жак Квискуатер және басқалар 1990 жылы «Балаларға нөлдік білім протоколдарын қалай түсіндіру керек» деген мақаласында алғаш рет жариялаған нөлдік білімді дәлелдеудің негізгі идеяларын көрсететін әйгілі оқия бар. Нөлдік білімді дәлелдеу оқиясындағы екі тарап – Пегги, мәлімдемені растаушы, және Виктор, мәлімдемені тексеруші. Оқия бойынша, Пегги үңгірдегі сиқырлы есікті ашу үшін қолданылатын құпия сөзді тапқан. Үңгір сақина тәрізді, бір жағында кіреберіс, ал қарсы жағында сиқырлы есік орналасқан. Виктор Пеггидің құпия сөзді білетінін білгісі келеді, бірақ Пегги өте жасырын адам болғандықтан, өзінің білімін (құпия сөзді) Викторға немесе жалпы әлемге жария етуді қаламайды. Олар кіреберістен солға және оңға қарай апаратын жолдарды А және В деп белгілейді. Біріншіден, Пегги үңгірге кіргенде, Виктор сыртында күтеді. Пегги А немесе В жолын таңдайды, Виктор қай жолға кіргенін көруге құқығы жоқ. Содан кейін Виктор үңгірге кіреді және Пегги қайту үшін қай жолды таңдауын сұрайды – кездейсоқ таңдалған А немесе В. Егер Пегги шындығында сиқырлы сөзді білсе, бұл оңай: қажет болса, есікті ашып, қалаған жолмен қайта оралады. Бірақ, егер ол сөзді білмейтін болса, онда Виктор кірген жолдың атын атаса ғана сол жолмен қайта оралуы мүмкін. Виктор кездейсоқ түрде А немесе В жолын таңдайтындықтан, Пегги дұрыс болжауға 50% мүмкіндікке ие. Егер олар осы тәжірибені көп рет қайталаса, мысалы, 20 рет қатарынан, Пеггидің Виктордың барлық сұрауларын сәтті орындау мүмкіндігі 1/220-ге дейін төмендейді, яғни 9.56 x 10-7-ге тең. Осылайша, егер Пегги Виктор атаған шығу орындасында қайта-қайта пайда болса, Виктор Пеггидің құпия сөзді білуі мүмкін деген қорытындыға келеді. Үшінші тараптың бақылаушыларына қатысты бір ескерту: егер Виктор бүкіл оқиғаны жазып алатын жасырын камера киіп жүрсе де, камерада тек Виктордың «А!» деп айқайлағаны және Пеггинің А орнында пайда болғаны немесе Виктордың «В!» деп айқайлағаны және Пеггидің В орнында пайда болғаны ғана тіркеледі. Мұндай жазбаны екі адам оңай жасампаздықпен жасауға болады (тек Пегги мен Виктор Виктор айқайлайтын А және В тізбегі туралы алдын ала келісуі керек). Мұндай жазбаға ешкім сенбес, тек оқиғаға қатысқандар ғана сенуі мүмкін. Тіпті алғашқы тәжірибеде болған бақылаушы да сенбеуі мүмкін, өйткені Виктор мен Пегги «тәжірибені» басынан соңына дейін ұйымдастырған болуы мүмкін. Сонымен қатар, егер Виктор камерада монета лақтырып, А және В жолдарын таңдаса, бұл протокол нөлдік білім қасиетін жояды; камерадағы монета лақтыру кейіннен жазбаны көретін кез келген адамды сендіруі мүмкін. Осылайша, бұл Викторға құпия сөзді ашпаса да, Пеггидің білімі бар екеніне әлемді сендіруге мүмкіндік береді, бұл Пеггидің тілегіне қайшы. Дегенмен, цифрлық криптография көбінесе псевдо-кезекті сан генераторына сүйене отырып «монета лақтырады», ол тек монета иесіне ғана белгілі басы мен құйрығының белгілі бір үлгісі бар монетаға ұқсас. Егер Виктордың монетасы осылай жұмыс істесе, онда Виктор мен Пегги тәжірибені жасампаздықпен жасауға болады, сондықтан псевдо-кезекті сан генераторын пайдалану Пеггидің білімін айналдырылған монетаны пайдалану сияқты жарияламайды. Пегги Викторға құпия сөзді ашпастан, оның білуін бір рет тәжірибе жасау арқылы дәлелдей алатынын еске сала кетейік. Егер Виктор мен Пегги үңгірдің аузына бірге барса, Виктор Пеггидің А жолынан кіріп, В жолынан шығып жатқанын көре алады. Бұл Пеггидің сиқырлы сөзді білетінін нақты дәлелдейді, бірақ Викторға оны ашпайды. Бірақ, мұндай дәлелді үшінші тарап байқауы мүмкін немесе Виктор жаздырып алуы мүмкін, және мұндай дәлел кез келген адамды сендіреді. Басқаша айтқанда, Пегги Виктормен сөз байласып жасаған деп жоққа шығара алмайды, сондықтан ол өзінің білімі туралы кім хабардар екенін бақылай алмайды.

There is a well known story presenting the fundamental ideas of zero knowledge proofs, first published in 1990 by Jean Jacques Quisquater and others in their paper "How to Explain Zero Knowledge Protocols to Your Children". The two parties in the zero knowledge proof story are Peggy as the prover of the statement, and Victor, the verifier of the statement. In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general. They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would be reduced to 1 in 220, or 9.5610−7. Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude that it is extremely probable that Peggy does, in fact, know the secret word. One side note with respect to third party observers: even if Victor is wearing a hidden camera that records the whole transaction, the only thing the camera will record is in one case Victor shouting "A!" and Peggy appearing at A or in the other case Victor shouting "B!" and Peggy appearing at B. A recording of this type would be trivial for any two people to fake (requiring only that Peggy and Victor agree beforehand on the sequence of A's and B's that Victor will shout). Such a recording will certainly never be convincing to anyone but the original participants. In fact, even a person who was present as an observer at the original experiment would be unconvinced, since Victor and Peggy might have orchestrated the whole "experiment" from start to finish. Further, if Victor chooses his A's and B's by flipping a coin on camera, this protocol loses its zero knowledge property; the on camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes. However, digital cryptography generally "flips coins" by relying on a pseudo random number generator, which is akin to a coin with a fixed pattern of heads and tails known only to the coin's owner. If Victor's coin behaved this way, then again it would be possible for Victor and Peggy to have faked the experiment, so using a pseudo random number generator would not reveal Peggy's knowledge to the world in the same way that using a flipped coin would. Notice that Peggy could prove to Victor that she knows the magic word, without revealing it to him, in a single trial. If both Victor and Peggy go together to the mouth of the cave, Victor can watch Peggy go in through A and come out through B. This would prove with certainty that Peggy knows the magic word, without revealing the magic word to Victor. However, such a proof could be observed by a third party, or recorded by Victor and such a proof would be convincing to anybody. In other words, Peggy could not refute such proof by claiming she colluded with Victor, and she is therefore no longer in control of who is aware of her knowledge.

Екі шар және түстерге көз жеткізбейтін досы

Досыңыз "Виктор" қызыл-жасыл түстерді ажырата алмайды (ал сіз ажырата аласыз) деп елестетіңіз, және сізде екі шар бар: біреуі қызыл, біреуі жасыл, бірақ қалғандары бірдей. Виктор үшін бұл екі шар толығымен бірдей көрінеді. Виктор шарлардың шын мәнінде әртүрлі екеніне күмәнданады. Сіз Викторға шарлардың түсі әртүрлі екенін дәлелдегіңіз келеді, бірақ басқа ештеңе көрсеткіңіз келмейді. Атап айтқанда, қай шардың қызыл, қай шардың жасыл екенін жасырғыңыз келеді. Міне, дәлелдеу жүйесі. Сіз екі шарды Викторға бересіз, ол оларды өзінен жасырады. Содан кейін ол шарлардың біреуін алып, өзінен жасырған жерден шығарып көрсетеді. Одан кейін ол оны қайтадан жасырады, содан кейін екі шардың біреуін таңдап, екеуінен кездейсоқ, тең мүмкіндікпен біреуін көрсетеді. Ол сізден: "Мен шарды ауыстырдым ба?" деп сұрайды. Бұл процедура қажет болғанша қайталанады. Шарлардың түсіне қарап, сіз оның оларды ауыстырғанын немесе ауыстырмағанын нақты біле аласыз. Екінші жағынан, егер шарлардың түсі бірдей болса және оларды ажырату мүмкін болмаса, сіз 50%-дан жоғары ықтималдықпен дұрыс жауап беруге шамаңыз жетпейді. Әрбір ауыстыруды/ауыстырмауды кездейсоқ дұрыс анықтау мүмкіндігі 50% болғандықтан, барлық ауыстырулар бойынша кездейсоқ сәттілік ықтималдығы нөлге жақындайды ("сенімділік"). Егер сіз бен досыңыз осы "дәлелдеуді" бірнеше рет қайталасаңыз (мысалы, 20 рет), досыңыз шарлардың түсі әртүрлі екеніне ("толықтық") көз жеткізуі керек. Жоғарыдағы дәлелдеу нөлдік білімділікке ие, өйткені досыңыз қай шардың қызыл, қайсысының жасыл екенін ешқашан білмейді; шындығында, ол шарларды қалай ажырату керектігі туралы ешқандай білім алмайды.

Уолдо қайда?

"Where's Waldo" мысалы нөлдік білімді дәлелдеудің бір танымал мысалы болып табылады. Бұл мысалда, дәлелдеуші верификаторға Уолдоның қайда екенін білетінін дәлелдегісі келеді, бірақ оның орналасқан жерін верификаторға көрсетпейді. Дәлелдеуші алдымен Уолдоның мөлшеріндегі кішкентай тесігі бар үлкен қара тақтаны алады. Тақта кітаптан әр жағынан екі есе үлкен болғандықтан, верификатор дәлелдеушінің оны кітаптың қай бетіне орналастырғанын көре алмайды. Содан кейін дәлелдеуші тақтаны кітап бетіне орналастырады, сонда Уолдо тесікке түседі. Нөлдік білімді дәлелдеулер терминнің математикалық мағынасындағы дәлелдеу емес, себебі шағын ғана ықтималдық бар, яғни дұрыс емес жағдай, онда алдаушы дәлелдеуші верификаторды жалған мәлімдемеге көндіре алады. Басқаша айтқанда, нөлдік білімді дәлелдеулер детерминистік дәлелдеулердің орнына ықтималдық "дәлелдер" болып табылады. Дегенмен, дұрыс емес жағдайды елеусіз шамаға дейін азайтуға болатын әдістер бар (мысалы, жүз немесе мың бинарлық шешімді дұрыс болжау тиісінше 1 / 2^{100} немесе 1/ 2^{1000} дұрыс емес жағдайға ие. Биттер саны артқан сайын, дұрыс емес жағдай нөлге қарай төмендейді). Нөлдік білімнің формальды анықтамасы белгілі бір есептеу моделін пайдалануы керек, ең көп таралғаны – Тьюринг машинасы. P, V және S – Тьюринг машиналары болсын. L тілі үшін интерактивті дәлелдеу жүйесі, егер кез келген ықтималдық полиномиалдық уақыт (PPT) верификаторы үшін PPT симуляторы S болса, онда нөлдік білімді болып табылады: мұнда – P және V арасындағы өзара әрекеттесудің жазбасы, ал дәлелдеушінің шексіз есептеу қуаты бар (практикада P көбінесе ықтималдық Тьюринг машинасы болады). Интуитивті түрде, анықтамада интерактивті дәлелдеу жүйесі нөлдік білімді болып табылады, егер кез келген верификатор үшін тиімді симулятор S (негізгіге байланысты) P пен верификатор арасындағы кез келген берілген кіріс бойынша әңгімені қайта жасай алатын болса. Анықтамадағы z көмекші тізбегі "алдын ала білім" рөлін атқарады (соның ішінде кездейсоқ сандар). Анықтамаға сәйкес, верификатор P-мен әңгімелесуден ақпаратты алу үшін z алдын ала білімін пайдалана алмайды, себебі егер S-ге осы алдын ала білім берілсе, ол P пен верификатор арасындағы әңгімені бұрынғыдай қайта жасай алады. Берілген анықтама – толыққанды нөлдік білім. Есептеулік нөлдік білім, верификатор мен симулятордың көзқарастары көмекші тізбекті ескере отырып, тек есептеулік тұрғыдан ажыратылмауын талап ету арқылы қол жеткізіледі.

One well known example of a zero knowledge proof is the "Where's Waldo" example. In this example, the prover wants to prove to the verifier that they know where Waldo is on a page in a Where's Waldo? book, without revealing his location to the verifier. The prover starts by taking a large black board with a small hole in it, the size of Waldo. The board is twice the size of the book in both directions, so the verifier cannot see where on the page the prover is placing it. The prover then places the board over the page so that Waldo is in the hole. Zero knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values (e. g. guessing correctly on a hundred or thousand binary decisions has a 1 / 2^{100} or 1/ 2^{1000} soundness error, respectively. As the number of bits increases, soundness error decreases toward zero). A formal definition of zero knowledge has to use some computational model, the most common one being that of a Turing machine. Let P, V, and S be Turing machines. An interactive proof system with for a language L is zero knowledge if for any probabilistic polynomial time (PPT) verifier there exists a PPT simulator S such that:

where is a record of the interactions between and The prover P is modeled as having unlimited computation power (in practice, P usually is a probabilistic Turing machine). Intuitively, the definition states that an interactive proof system is zero knowledge if for any verifier there exists an efficient simulator S (depending on ) that can reproduce the conversation between P and on any given input. The auxiliary string z in the definition plays the role of "prior knowledge" (including the random coins of ). The definition implies that cannot use any prior knowledge string z to mine information out of its conversation with P, because if S is also given this prior knowledge then it can reproduce the conversation between and P just as before. The definition given is that of perfect zero knowledge. Computational zero knowledge is obtained by requiring that the views of the verifier and the simulator are only computationally indistinguishable, given the auxiliary string.

Берілген мәннің дискретті журналы

Осы идеяларды криптографияның нақты қолданысына қолдануға болады. Пегги Викторға белгілі бір топтағы берілген мәннің дискретті логарифмін білетінін дәлелдегісі келеді. Мысалы, берілген мән *x*, үлкен жай сан *p* және генератор *g*, ол өзінің *y* мәнін білетінін дәлелдегісі келеді, мұндай, *gy = x*, ашпай. Шын мәнінде, *y*-дың білімін сәйкестікті дәлелдеу ретінде пайдалануға болады, Пеггиде мұндай білім болуы мүмкін, өйткені ол кездейсоқ мән *k*-ні таңдады, оны ешкімге көрсетпеді, *gk*-ні есептеп, барлық ықтимал тексерушілерге *gk* мәнін бөліп берді, сондықтан кейіннен *y*-дың білімін дәлелдеу Пегги ретінде сәйкестікті дәлелдеуге тең. Протокол келесідей жүреді: әр раундта Пегги кездейсоқ санды *r* шығарады, *gr*-ді есептеп, Викторға хабарлайды. Виктор *gr*-ді алғаннан кейін, кездейсоқ түрде төмендегі екі сұраудың бірін қояды: ол Пеггиден *r* мәнін ашуын немесе *y* мәнін ашуын сұрайды.

We can apply these ideas to a more realistic cryptography application. Peggy wants to prove to Victor that she knows the discrete log of a given value in a given group. For example, given a value , a large prime and a generator , she wants to prove that she knows a value such that , without revealing Indeed, knowledge of could be used as a proof of identity, in that Peggy could have such knowledge because she chose a random value that she didn't reveal to anyone, computed and distributed the value of to all potential verifiers, such that at a later time, proving knowledge of is equivalent to proving identity as Peggy. The protocol proceeds as follows: in each round, Peggy generates a random number , computes and discloses this to Victor. After receiving , Victor randomly issues one of the following two requests: he either requests that Peggy discloses the value of , or the value of

Victor can verify either answer; if he requested , he can then compute and verify that it matches If he requested , he can verify that is consistent with this, by computing and verifying that it matches If Peggy indeed knows the value of , she can respond to either one of Victor's possible challenges. If Peggy knew or could guess which challenge Victor is going to issue, then she could easily cheat and convince Victor that she knows when she does not: if she knows that Victor is going to request , then she proceeds normally: she picks , computes and discloses to Victor; she will be able to respond to Victor's challenge. On the other hand, if she knows that Victor will request , then she picks a random value , computes , and discloses to Victor as the value of that he is expecting. When Victor challenges her to reveal , she reveals , for which Victor will verify consistency, since he will in turn compute , which matches , since Peggy multiplied by the modular multiplicative inverse of
However, if in either one of the above scenarios Victor issues a challenge other than the one she was expecting and for which she manufactured the result, then she will be unable to respond to the challenge under the assumption of infeasibility of solving the discrete log for this group. If she picked and disclosed , then she will be unable to produce a valid that would pass Victor's verification, given that she does not know And if she picked a value that poses as , then she would have to respond with the discrete log of the value that she disclosed but Peggy does not know this discrete log, since the value C she disclosed was obtained through arithmetic with known values, and not by computing a power with a known exponent. Thus, a cheating prover has a 0.5 probability of successfully cheating in one round. By executing a large enough number of rounds, the probability of a cheating prover succeeding can be made arbitrarily low. To show that the above interactive proof gives zero knowledge other than the fact that Peggy knows the value, one can use similar arguments as used in the above proof of completeness and soundness. Specifically, a simulator, say Simon, who does not know the value, can simulate the exchange between Peggy and Victor by the following procedure. Firstly, Simon randomly flips a fair coin. If the result is "head", he picks a random value , computes , and discloses as if it is a message from Peggy to Victor. Then Simon also outputs a message "request the value of " as if it is sent from Victor to Peggy, and immediately outputs the value of as if it is sent from Peggy to Victor. A single round is complete. On the other hand, if the coin flipping result is "tail", Simon picks a random number , computes , and discloses as if it is a message from Peggy to Victor. Then Simon outputs "request the value of " as if it is a message from Victor to Peggy. Finally, Simon outputs the value of as if it is the response from Peggy back to Victor. A single round is complete. By the previous arguments when proving the completeness and soundness, the interactive communication simulated by Simon is indistinguishable from the true correspondence between Peggy and Victor. The zero knowledge property is thus guaranteed.

Виктор кез келген жауапты тексеруі мүмкін; егер ол *r*-ді сұраса, онда ол *gy = x* екенін есептеп, нәтижесі *x*-ке сәйкес келе ме екенін тексеруі мүмкін. Егер ол *y*-ді сұраса, онда ол *gr*-дің осыған сәйкес келе ме екенін тексеруі мүмкін, *gr*-ді есептеп, нәтижесі *gr*-ге сәйкес келе ме екенін тексеруі мүмкін. Егер Пегги шын мәнінде *y*-дың мәнін білсе, онда ол Виктордың кез келген сұрауына жауап бере алады. Егер Пегги Виктордың қандай сұрақ қоятынын білсе немесе болжаса, онда ол Викторды оңай алдап, өзінің *y*-ды білмейтініне сендіре алады: егер ол Виктордың *r*-ді сұрамақшы екенін білсе, онда ол әдеттегідей әрекет етеді: ол *r*-ді таңдайды, *gr*-ді есептейді және оны Викторға ашады; ол Виктордың сұрауына жауап бере алады. Екінші жағынан, егер ол Виктордың *y*-ді сұрауының мәнін білсе, ол кездейсоқ мән *r*-ді таңдайды, *gr*-ді есептейді және оны Викторға *gr* ретінде ашады, оны Виктор күтеді. Виктор оны *y*-ды анықтауға шақырғанда, ол *y*-ды ашады, онда Виктор сәйкестігін тексереді, өйткені ол өз кезегінде *gy*-ді есептейді, бұл *x*-ке сәйкес келеді, өйткені Пегги оны *g*-ның модулдік көбейту керісімен көбейтті.

Алайда, егер жоғарыда көрсетілген сценарийлердің бірінде Виктор күткеннен басқа және ол нәтижесін жасаған сұрақ қойса, онда ол осы топ үшін дискретті логарифмді шешу мүмкін емес деп есептегенде, осы сұраққа жауап бере алмайды. Егер ол *r*-ді таңдап, *gr*-ді ашып көрсеткен болса, онда ол Виктордың тексеруінен өтетін жарамды *y*-ды шығара алмайды, өйткені ол *y*-ды білмейді. Ал егер ол *y* ретінде көрінетін мәнді таңдаса, онда ол ашып көрсеткен мәннің дискретті логарифмімен жауап беруге тиіс, бірақ Пегги бұл дискретті логарифмді білмейді, өйткені ол ашып көрсеткен *C* мәні белгілі мәндермен арифметика арқылы алынған, ал белгілі бір көрсеткіші бар қуатты есептеу арқылы емес. Осылайша, алдаушы сынақшы бір раундта ойдағыдай алдаудың 0.5 ықтималдығына ие. Орындау арқылы жеткілікті көп раундтар, алдаушы пробкердің сәтті болу ықтималдығын кездейсоқ түрде төмендетуге болады. Жоғарыда көрсетілген интерактивті дәлелдеу Пегги *y* мәнін білетіндігінен басқа нөлдік білім беретінін көрсету үшін, жоғарыда көрсетілген толық және дұрыс дәлелдеуде қолданылғанға ұқсас аргументтерді қолдануға болады. Нақтырақ айтқанда, *y* мәнін білмейтін, мысалы, Саймон секілді симулятор Пегги мен Виктор арасындағы алмасуды келесі әдіспен симуляциялай алады. Біріншіден, Саймон кездейсоқ әділ монетаны лақтырады. Егер нәтиже "басты" болса, ол кездейсоқ мәнді *r*-ді таңдайды, *gr*-ді есептейді және оны Пеггиден Викторға жіберілген хабарлама ретінде жариялайды. Содан кейін Саймон "Victor-дан Peggy-ге жіберілгендей" "*y*-дың мәнін сұрау" деген хабарламаны шығарады, және дереу Пеггиден Викторға жіберілгендей *y*-дың мәнін шығарады. Бір раунд аяқталды. Екінші жағынан, егер монетаны лақтырып тастау нәтижесі "құйрық" болса, Саймон кездейсоқ санды *r*-ді таңдайды, *gr*-ді есептейді және оны Пеггиден Викторға жіберілген хабар сияқты жариялайды. Содан кейін Саймон "Victor to Peggy" деген хабарды жібергендей "*r*-дың мәнін сұрау" дегенді шығарады. Ақырында, Саймон *r*-дың мәнін Пеггидің Викторға берген жауабы сияқты шығарады. Бір раунд аяқталды. Бұрынғы дәлелдерге сүйенсек, Саймонның симуляциялаған интерактивті қарым-қатынасы Пегги мен Виктордың арасындағы шынайы хат алмасудан ажыратылмайды. Сонымен, нөлдік білім қасиетінің кепілдігі беріледі.

Қысқаша қорытынды

Пегги x-тің мәнін білетінін дәлелдейді (мысалы, оның паролі). Пегги мен Виктор бір-бір жай сан және өрістің мультипликативтік тобының генераторы туралы келіседі. Пегги мәнді есептеп, осы мәнді Викторға жібереді. Келесі екі қадам (көп) рет қайталанады. Пегги қайта-қайта кездейсоқ мәнді таңдап, оны есептейді және Викторға жібереді. Виктор Пеггиден есептеп, мәннің немесе мәнін жіберуді сұрайды. Бірінші жағдайда Виктор тексереді, екінші жағдайда ол тексереді. мәнін, егер шын мәнінде кездейсоқ болса және нөл мен арасында тең үлестірілген болса, -тің шифрланған мәні ретінде қарастыруға болады, бұл туралы ешқандай ақпарат ағып кетпейді (бір реттік блокқа қараңыз).

Толықтығы

Егер Пегги графтағы Гамильтон циклін білсе, Виктордың талабын оңай орындай алады: яғни, граф изоморфизмін беру арқылы графты графқа түрлендіру (ол алғашқы қадамда осыны міндеттенген болатын) немесе графтың өзінде Гамильтон циклын табу (оның орнына изоморфизмді қолданып циклді түрлендіру арқылы құра алады).

Білімі жоқ

Пеггидің жауаптары бастапқы Гамильтон циклін ашпайды. Әр раундта Виктор тек 's' изоморфизмін немесе 's' Гамильтон циклін ғана біледі. Бір 's' үшін циклді анықтау үшін оған екі жауап қажет, сондықтан Пегги әр раундта ерекше 's' жасай берсе, ақпарат құпия болып қалады. Егер Пегги 's' Гамильтон циклінің бар екенін білмесе, бірақ Виктордың әр раундта нені көруді сұрайтынын алдын ала білсе, ол алдауы мүмкін. Мысалы, егер Пегги Виктордың 's' Гамильтон циклін көруді сұрайтынын алдын ала білсе, ол байланыссыз график үшін Гамильтон циклін жасауы мүмкін. Сол сияқты, егер Пегги Виктордың изоморфизмді көруді сұрайтынын алдын ала білсе, ол жай ғана изоморфты график 's' жасауы мүмкін (онда ол Гамильтон циклін де білмейді). Виктор протоколды өзі (Пеггисіз) симуляциялай алады, өйткені ол нені көруді сұрайтынын біледі. Сондықтан Виктор әр раундта ашылған ақпараттан 's' Гамильтон циклі туралы ешқандай жаңа ақпарат алмайды.

Саулық

Егер Пегги ақпаратты білмесе, ол Виктордың қандай сұрақ қоятынын болжап, оған изоморфты графты немесе байланыссыз граф үшін Гамильтон циклын құра алады, бірақ ол Гамильтон циклын білмейтіндіктен, екеуін де бірдей жасай алмайды. Осы болжау арқылы, Викторды жаңылыстыру мүмкіндігі – раундтардың саны (n) болады. Нақты жағдайларда, ақылға қонымды раундтар санымен нөлдік білімді дәлелдеуді осылай жеңу мүмкін емес.

Тақырыбы жоқ білім түрлері

Білімді дәлелдеу: білім жоғарыда көрсетілген мысалдағыдай экспонентада жасырылған. Жұптастыруға негізделген криптография: егер және берілсе, оларды білмей, куәгерді ажыратуға болмайтын дәлелді есептеуге болады. Куәгерді ажыратуға болмайтын дәлел: тексерушілер дәлелді жасау үшін қандай куәгер қолданылғанын біле алмайды. Көп тарапты есептеу: әр тарап өзінің құпиясын сақтай отырып, бірлесіп нәтиже шығарады. Сақиналық қолтаңба: сырттан қараған адамдар қол қою үшін қандай кілт қолданылғанын біле алмайды.

Аутентификация жүйелері

Нөлдік білімді дәлелдеу саласындағы зерттеулер, бір тараптың екінші тарапқа қандай да бір құпия ақпарат (мысалы, пароль) арқылы өзін таныстыруға, бірақ екінші тараптың осы құпия туралы ештеңе білмеуіне мүдделі аутентификация жүйелерімен шақырылды. Бұл "білімнің нөлдік дәлелі" деп аталады. Дегенмен, парольдер көбінесе нөлдік білімді дәлелдеу схемаларында қолдануға тым кішкентай немесе жеткіліксіз кездейсоқ болып келеді. Парольдің нөлдік білімді дәлелі – бұл парольдердің шектеулі өлшемдерін ескеретін білімнің арнайы түрі. 2015 жылдың сәуір айында көптеген нұсқалардың бірінен дәлелдеу протоколы (Сигма протоколы) ұсынылды.

Этикалық мінез-құлық

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

Ядролық қарусыздану

2016 жылы Принстон плазма физикасы зертханасы мен Принстон университеті болашақ ядролық қарусыздану келіссөздерінде пайдаланылуы мүмкін бір әдіс көрсетті. Бұл инспекторларға құпиялы ақпаратты жазбастан, бөліспестен немесе ашпастан, бір заттың ядролық қару екенін не емесін анықтауға мүмкіндік береді.

Блокчейндер

Нөлдік білімді дәлелдемелер Zerocoin және Zerocash протоколдарында қолданылды, бұл 2016 жылы Zcoin және Zcash криптовалюталарының дүниеге келуіне әкелді. Zerocoin құрамында анонимділікті қамтамасыз ету үшін ешқандай пірлерге немесе орталықтандырылған араластыру провайдерлеріне сенбеуді қамтитын араластыру моделі бар. Zerocash протоколы ұқсас модельді қолданады (интерактивті емес нөлдік білімді дәлелдеу деп белгілі бір түрі), бірақ ол транзакция сомасын жасыра алады, ал Zerocoin мұны істей алмайды. Zerocash желісінде транзакциялық деректерге қатысты маңызды шектеулер болғандықтан, Zerocash, Zerocoin-мен салыстырғанда, құпиялылыққа қатысты уақыт шабуылдарына аз бейім. Дегенмен, құпиялылықтың бұл қосымша деңгейі, жалған монеталарды қадағалау мүмкін болмағандықтан, Zerocash ұсынысының байқалмайтын гиперинфляциясына әкелуі мүмкін. 2018 жылы Bulletproofs енгізілді. Bulletproofs – бұл сенімді орнатуды қажет етпейтін, интерактивті емес нөлдік білімді дәлелдеуден жасалған жақсарту. Кейіннен ол Mimblewimble протоколына (Grin және Beam криптовалюталары негізделген) және Monero криптовалютасына енгізілді. 2019 жылы Firo, Zerocoin протоколының жақсаруы болып табылатын Sigma протоколын іске қосты, оған сенімді орнату қажет емес. Сол жылы Firo Lelantus протоколын енгізді, ол Sigma протоколының жақсартуы болып табылады, онда бұл протокол транзакцияның бастауын және сомасын жасырады.

Орталықтандырылған идентификаторлар

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