დამტკიცება ნულოვანი ინფორმაციით

კრიფტოგრაფიაში დამტკიცება ნულოვანი ინფორმაციით არის პროტოკოლი, რომელიც საშუალებას აძლევს ერთ მხარეს (შემმოწმებელს, verifier) შეამოწმოს და დარწმუნდეს გარკვეული ამოცანის დამტკიცების სისწორეში, ისე რომ, არ მიიღოს არანაირი დამატებით ინფორმაციას მეორე მხარისგან (დამტკიცებლისგან, prover). მოცემული პრინციპი მუშაობს მხოლოდ მაშინ, როდესაც დამტკიცებელს გააჩნია ფარული ინფორმაცია, რომელიც არ არის ცნობილი შემმოწმებლისთვის, სხვა შემთხვევაში მოცემული დამტკიცების ფორმას არ შეიძლება ეწოდოს დამტკიცება ნულოვანი ინფორმაციით. ეს არის ინტერაცტიული დამტკიცების კონკრეტული შემთხვევა რომელსაც უწოდებენ ნულოვანი ინფორმაციით დამტკიცებას(zero-knowledge proof). სახელწოდება კარგად ასახავს ამ მეთოდიკის არსს. მთავარი აზრი იმაში მდგომარეობს, რომ მოცემული მეთოდი უზრუნველყოფს ინფორმაციის დაცულობას და აძლევს საშუალებას ორ მხარეს იქონიონ ურთეირთობა ისე რომ არ მოხდეს დაცული ინფორმაციის გამჟღავნება.

დამტკიცების პროტოკოლი

ნულოვანი ინფორმაციით დამტკცება მოითხოვს მხარეთა შორის ინტერაქტიულ კავშირს. თავიდან შემმოწმებელი აწვდის გარკვეულ მონაცემებს დამტკიცებელს, რათა მან მოახდინოს ამ მონაცემების საკუთარი საიდუმლო ინფორმაციის(ალგორითმის) მიხედვით გადამუშავება და რეზულტატის შემმოწმებლისთვის დაბრუნება. როგორც წელსი მონაცემების მხოლოდ ერთხელ გაცვლა-გამოცვლა არ არის საკმარისი. ეს პროცესი გრძელდება, მანამ სანამ შემმოწმებელი არ დარწმუნდება, რომ დამტკიცება ყოველთვის სწორად ხდება.

• $A\Rightarrow B$ : მტკიცებულება (witness)
• $A\Leftarrow B$ : გამოწვევა (challenge)
• $A\Rightarrow B$ : პასუხი (response)

თავიდან A ირჩევს მტკიცებულებას, საიდუმლო გასაღებს, რომლის მიხედვითაც მან წარმატებით უნდა გადაჭრას B- ს მიერ დასმული ამოცანა. შემდეგ A ამ გასაღების მეშვეობით(რაიმე ალგორითმით) გამოითვის ღია პასუხს, მტკიცებულებას იმისა რომ ამოცანა გადაჭრილია და გაუგზავნის B - ს. პასუხად B ირჩევს ყველა შესაძლო არსებული კითხვიდან ერთ-ერთს და უბრუნებს A-ს პასუხის მისაღებად. A იღებს კითხვას და საკუთარი საიდუმლო ალგორითმის მეშვეობით აბრუნებს სწორ პასუხს. მოცემული ციკლი შეიძლება განმეორდეს ბევრჯერ, სანამ მინიმუმამდე არ დავა იმის ალბათობა, რომ A პასუხებს იცნობს.

განსაზღვრება

ფორმალური განსაზღვრება

ნულოვანი ცოდნის ფორმალურ განსაზღვრებას იყენებს ზოგიერთი თეორიული კომპიუტერული მოდელი, მაგალითად ტურინგის მანქანა. ინტერაქტიული დამტკიცების სისტემა განსაზღვრული როგორც (P, V), სადაც $P$ არის დამმტკიცებელი ტურინგის მანქანა (prover), ხოლო $V$ შემმოწმებელი ტურინგის მანქანა (verifier), $L$ ენისთვის არის ნულოვანი ინფორმაციით დამტკიცების ფორმა, თუ ნებისმიერ ალბათურ პოლინომიალურ დროში (PPT)შემმოწმებლისთივს _${\hat {V}}$ (verifier) არსებობს ისეთი (PPT) სიმულატორი $S$, რომ
$\forall x\in L,z\in \{0,1\}^{*},{\text{View}}_{\hat {V}}[P(x)\leftrightarrow {\hat {V}}(x,z)]=S(x,z)$
ტურინგის მანქანა $P$ არის შეუზღუდავი შესაძლებლობების მქონე მანქანა, როგორც წესი პრაქტიკაში მხედველობაში მიიღება, როგორც ალბათური ტურინგის მანქანა. განსაზღვრების მიხედვით ინტერაცტიული დამტკიცების სისტემა არის ნულოვანი ინფორმაციის ტიპის თუ ნებისმიერი $V$-სთვის არსებობს ისეთი ეფექტიანი სიმულატორი $S$ რომელიც ნებისმიერი შემომავალი ინფორმაციისთვის მოახერხებს კავშირის სწორად დამყარებას ორ მხარეს შორის. ფორმალურ განსაზღვრებაში მითითებული Z არის საწყისი ცოდნა, რომელსაც ${\hat {V}}$ ვერ გამოიყენებს $P$-სთან კავშირის გარეშე, რადგან წინააღმდეგ შემთხვევაში $S$-საც ექნება მოცემული საწყისი ინფორმაცია z, მაშინ მას ექნება საშუალება მოახდინოს დამტკიცების ფორმის კოპირება $V$-სა და $P$-ს შორის და თავად შეეძლება მოცემული დებულების დამტკიცება.

თვისებები

დამტკიცებას ნულოვანი ინფორმაციით ხასიათდება სამი თვისებით

1. სისრულე (Completeness): როდესაც მხარეს, რომელიც ახდენს დამტკიცებას, აქვს დამატებით საჭირო ინფორმაცია, იგი აუცილებლად მოახერხებს დაუმტკიცოს შემმოწმებელს სასურველი ამოცანა(ჰიპოთეზა).
2. სტაბილურობა (Soundness): როდესაც საჭირო ინფრმაციის არ მქონე დამმტკიცებელს თითქმის არ აქვს შანსი სწორად დაამტკიცოს მოცემული ამოცანა ისე რომ შეემმოწმებელმა დაიჯეროს დმტკიცების სისწორე.
3. ნულოვანი-ინფორმაცია (Zero-knowledge): გულისხმობს, რომ შემმოწმებელს არ გააჩნია არავითარი დამატებითი ინფორმაცია დასამტკიცებელი ჰიპოთეზის(ამოცანის) შესახებ, მას, მხოლოდ, აქვს საშუალება შეამოწმოს მეორე მხარის მიერ მიღებული პასუხების (დამტკიცების) სისწორე, სხვადასხვა ტესტით. ამიტომ, თვითონ შემმოწმებელი ვერ შეძლებს იგივე ამოცანა სხვას დაუმტკიცოს, რადგან მას არ გააჩნია საჭირო ინფორმაცია ამისათვის.

პირველი ორი თვისება ახასიათებს ზოგადად ინტერაქტიულ დამტკიცებებს, ხოლო, ბოლო არის სწორედ ნულოანი ინფორმაციით დამტკიცების, მთავარი დამახასიათებელი ნიშან-თვისება, რომელიც განაპირობებს მის არსს.

დამტკიცების სისრულე

ნულოვანი ცოდნით დამტკიცებას უწოდებენ სრულს თუ, დამმტკიცებელს, რომელსაც აქვს საიდუმლო ინფორმაცია, ყოველთვის შეუძლია ამოცანის წარმატებით დამტკიცება, ანუ ალბათობა იმისა რომ მოახერხებს დამტკიცებას ნებისმიერ ცდაზე 1-ის ტოლი უნდა იყოს, წინააღმდეგ შემთხვევაში მოცემული პროტოკოლი არ არის სრული.

დამტკიცების სტაბილურობა

ნულოვანი ინფორმაციით მტკიცების მეთოდს ეწოდება სტაბილური, თუ მხარეს, რომელიც ცდილობს დამტკიცებას, არ გააჩნია საჭირო საიდუმლო ინფორმაციალ, მაშინ დამტკიცების სწორი ალგორითმის მოფიქრების შანსი ნულთან ძალიან ახლოს უნდა იყოს, ანუ სხვა სიტყვებით რომ ვთქვათ ალბათობა იმისა რომ, ინფორმაციის არმქონე დამმტკიცებელი მოახერხებს დამტკიცებას თითქმის ნულის ტოლი უნდა იყოს.

მაგალითები

ალიბაბას გამოქვაბული

ანი რამნდომით ირჩევს გზას A-სა და B-ს შეორის,დათო გარეთ ელოდება

დათო ირჩევს მხარეს რომლიდანაც უნდა გამოვიდეს ანი

ანი გამოდის იმ გზიტ რომელიც უკარნახა დათომ

ყველაზე მარტივ მაგალითად ნულოვანი ინფორმაციით დამტკიცების ფორმის ასახსნელად, შეგვიძლია მოვიყვანოთ სახალისო ამოცანა ალიბაბას გამოქვბულის შესახებ, რომელშიც არის ჯადოსნური კედელი, რომელიც იხსნება საიდუმლო სიტყვის წარმოთქმისას. ვთქვათ ანიმ იცსი "პაროლი" და სურს დაუმტკიცოს საკუთარ მეგობარ დათოს, რომ მას შეუძლია ჯადოსნური კედლის გახსნა, ისე რომ არ გაანდოს საიდუმლო სიტყვა და ამასთან დათომ ვერ შეძლოს ვინმე სხვის დარწმუნება იმაში, რომ ანის კედლის გახსნა შეუძლია(ან უბრალოდ თავად დათომ ვერ შეძლოს დამუუკიდებლად კედლის გახსნა). ამისთვის ისინი იფიქრებენ შემდეგ ალგორითმს:

• ანი შედის გამოქვაბულში და მიდის არსებული ორი გზიდან ერთ-ერთით(რანდომით ირჩევს) დათო მას გარეთ ელოდებ და არ იცის რომელი გზით შევიდა ანი.
• შემდეგ დათო ირჩევს იმ მხარეს რომლიდანაც უნდა გამოვიდეს ანი. დათო ეძახის ანის და ეუბნება იმ გზას რომლითაც უნდა დაბუნდეს უკან.
• ანი ისმენს მითითებას და გამოდის საჭირო მხრიდან.

ამ პროცედურას იმერორებენ რამდენიმეჯერ(რაც უფრო მეტია ცდათა რაოდენობა, მით უფრო სანდოა დამტკიცება). საბოლოოდ, რადგან ანი არ იტყუება და მან ნამდვილად იცის საიდუმლა, ამიტომ ყოველ ჯერზე მოახერხებს საჭირო მხრიდან გამოსვლას, ამიტომ დამტკიცების თვისებებიდა შეგვიძლია ვთქვათ, რომ დამტკიცება სრულია. თუ ანი იტყუება და მან არ იცის საიდუმლო სიტყვა, მან ყოველ ჯერზე უნდა გამოიცნოს ის მიმართულება, რომლიდანაც მოიხოვს მის გამოსვლას დათო. ამიტომ მოტყუებით გამოცნობის ალბათობა ყოველ ჯერზე 1/2-ის ტოლია, ხოლო n ცდის შემდეგ 1/2ⁿ-ის.

ჰამილტონის ციკლი დიდი გრაფებისთვის

მეორე მაგალიშიც სიმარტივისთვის მხარეებად განვიხილოთ, დამმტკიცებელი მარი და შემმოწმებელი სალომე. დავუშვათ მარიმ იცის სადაა ჰამილტონის ციკლი დიდ გრაფ G-ში. სალომემ იცის გრაფ G-ს აღწერილობა, მაგრამ მან არ იცის მასში ჰამილტონის ციკლის არსებობის შესახებ. მარის უნდა დაუმტკიცოს სალომეს, რომ მან იცის სადაა ჰამილტონის ციკლი გრაფში და თან არ გათქვას ციკლის შესახება რაიმე ინფორმაცია.(შესაძლებენია საქმიან გარიგებებში, როდესაც ხდება რაიმე ინფორმაციის შეძენა მეორე პირისგან ჯერ აუცილებელია იმაში დარწმუნება, რომ ეს ინფორმაცია ნამდვილად არსებობს, მაგრამ გამყიდველი არ გათქვამს ინფორმაციას სანამ არ მიიღებს სარგოს. იგი ინფორმაციის არსებობას სწორედ ნულოვანი ინფორმაციით დამტკიცების მეთოდით დაამტკიცებს).

• თავიდან მარი ქმნის G გრაფის იზომორფულ გრაფ H-ს. ჰამილტონის ციკლის გარდაქმნა იზომორფულ გრაფში უკვე ტრივიალურია. ამიტომ თუ მარიმ იცის ჰამილტონის ციკლი G-ში მანი იცის ჰამილტონის ციკლი H-შიც.
• მარი გადასცემს ახალ H გრაფს სალომეს.
• სალომე პასუხად უბრუნებს ან 0-ს ან 1-ს. 0 ნიშნავს, რომ იგი ითხოვს გრაფების იზომორფულობის დამტკიცებას, ხოლო 1 ნიშნავს, რომ ითხოვს ჰამილტონის ციკლს H-ში.
  • თუ სალომემ დააბრუნა 0, მაშინ მარი ამტკიცებს იზომორფულობას G და H გრაფების წვეროებს შორის შესაბამისობით.
  • თუ სალომემ დააბრუნა 1, მაშინ მარი ამჟღავნებს ჰამილტონის ციკლს H-ში. (რადგან ჯერჯერობით შეუძლებლად ითვლება ერთი იზომორფული გრაფის ჰამილტონის ციკლით მეორე იზომორფულ გრაფში ჰამილტონის ციკლის მიგნება).

ყოველ რაუნდში, სალომე ირჩევს შემთხვევით 0-სა და ერთს შორის და რათა მარი შეძლოს ორივე კითხვაზე პასუხის სწორად გაცემა საჭიროა, რომ მოცემული H გრაფები ნამდვილად G-ს იზომორფული იყოს და მარიმ უნდა იცოდეს ჰამილტონის ციკლი H-ში (შესაბამისად G-შიც). ამიტომ ცდათა საკმარისი რაოდენობის შემდეგ, სალომე შეიძლება დარწმუნებული იყოს იმაში რომ მარიმ იცის ჰამილტონის ციკლი G გრაფში. ამასთან აღსანიშნავია, რომ მარის არ გაუთქვია არანაირი ინფორმაცია ციკლის შესახებ და თან თუ სალომე მოინდომებს ვინმე სხვას დაუმტკიცოს ჰამიტონის ციკლის არსებობა G-ში ის ამას ვერ მოახერხებს, რადგან არ აქვს საჭირო ინფორმაცია. დავუშვათ მარიმ არ იცის სადაა ჰამილტონის ციკლი G-ში და სურს მოატყუას სალომე, მაშინ მარის ესაჭიროება G' გრაფი, რომელიც არ არის G-ს იზომორფული, მაგრამ ამ გრაფში მარიმ იცის ჰამილტონის ციკლი. ყოველ რაუნდში მარიმ შეუძლია გადასცეს ან H' იზომორფული G'-ს, ან H იზომორფული G-ს. თუ სალომე მოითხოვს იზომორფულობის დამტკიცებას და გადაცემული H, მაშინ ტყუილი არ გამოაშკარავდება. ანალოგიურად თუ მოთხოვნილია ჰამილტონის ციკლი იზომორფულ გრაფში და გადაცემულია H', არც მაშინ გაირკვევა, რომ მარი იტუება. ალბათობა იმისა რომ n ცდის მერე მარი მოახერხებს სალომეს მოტყუებას 1/2ⁿ-ის ტოლია, რაც ძალიან მცირეა ცდათა დიდი რაოდენობის შემთხვევაში. თუ სალომე შეეცდება სხვას დაუტკიცოს, რომ მარიმ იცის ჰამილტონის ციკლი G გრაფში, და ამის დასამტკიცებლად პროცესსგადაიღებს კამერით. მესამე პირი მას მაინც არ დაუჯერებს, რადგან შესაძლებელია რომ მარი და სალომე სვლათა თანმიმდევრობაზე წინასწარ ყოფილიყვნენ შეთანხმებული, ეს კი სრულიად უარყოფს დამტკიცებას, რადგან იგი ემყარება სწორედ სალომეს მიერ სვლათა შემთხვევით შერჩევის აუცილებლობას.