ნულოვანი ცოდნის დამადასტურებელი პროტოკოლი. ნულოვანი ცოდნის მტკიცებულება. კარგი, რას ნიშნავს ეს ყველაფერი?

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

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

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

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

1. (სისრულე). ყველასთვის

2. (სისწორე). ნებისმიერი ტურინგის მანქანისთვის ნებისმიერი მრავალწევრისთვის და ყველა საკმარისად დიდი სიგრძისთვის

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

განმარტება 5. ენის ინტერაქტიული მტკიცებულების პროტოკოლს ეწოდება აბსოლუტურად ნულოვანი ცოდნის მტკიცებულება, თუ 1 და 2 პირობების გარდა დაკმაყოფილებულია შემდეგი პირობაც.

3. (ნულოვანი ცოდნის საკუთრება). ნებისმიერი პოლინომიური ალბათური ტურინგის მანქანა V, არის სავარაუდო ტურინგის მანქანა, რომელიც მუშაობს საშუალოდ მრავალწევრულ დროში და ისეთი, რომ ყველასთვის

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

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

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

IG პროტოკოლი

მოდით, იზომორფიზმი შემდეგ ოთხ საფეხურს შორის შესრულდეს ციკლში ერთხელ, ყოველ ჯერზე დამოუკიდებელი შემთხვევითი ცვლადებით.

1. P ირჩევს შემთხვევით პერმუტაციას ნაკრებზე, ითვლის და აგზავნის ამ გრაფიკს

2. V ირჩევს შემთხვევით ბიტს და აგზავნის მას

3. თუ შემდეგ აგზავნის V permutation, წინააღმდეგ შემთხვევაში - permutation o

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

თუ მე-4 საფეხურში შემოწმებებმა მისცა დადებითი შედეგიყველა ციკლში, მაშინ V იღებს მტკიცებულებას.

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

თეორემა 2 (). IG პროტოკოლი არის აბსოლუტურად ნულოვანი ცოდნის მტკიცებულება GRAPH ISOMORPHISM ენისთვის.

IG პროტოკოლის სისრულე აშკარაა.

სისწორის დასამტკიცებლად, საკმარისია აღინიშნოს, რომ ბიტი, რომელსაც V ირჩევს მე-2 საფეხურზე, მიუთითებს, თუ რომელი გრაფიკისთვის არის საჭირო იზომორფიზმის დემონსტრირება, თუ არა იზომორფული, მაშინ ის შეიძლება იყოს იზომორფული საუკეთესო შემთხვევის სცენარი, ერთ-ერთი მათგანი. მაშასადამე, მე-4 ნაბიჯის შემოწმება დადებით შედეგს მოგვცემს 1/2 ალბათობით ერთ ციკლში და ალბათობით ყველა ციკლში.

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

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

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

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

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

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

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

მიეცით ინტერაქტიული მტკიცებულების სისტემა (P,V,S).
ინტერაქტიული მტკიცებულების სისტემის განმარტებისას, ადრე არ იყო ვარაუდი, რომ V შეიძლება იყოს მოწინააღმდეგე (მხოლოდ არაკეთილსინდისიერი მონაწილის არსებობის შესაძლებლობა იყო ვარაუდი, მაგრამ V შეიძლება აღმოჩნდეს მოწინააღმდეგე, რომელსაც სურს გაარკვიოს). რამდენიმე ახალი ინფორმაცია პ. სასარგებლო ინფორმაცია S.-ის განცხადების შესახებ ამ შემთხვევაში P-ს შეიძლება არ სურდეს, რომ ეს მოხდეს სამუშაოს შედეგად
ინტერაქტიული მტკიცებულების სისტემის პროტოკოლი. ასე რომ
28 Zapechnikov S. V. კრიპტოგრაფიული პროტოკოლები და მათი წინამორბედები
ამ გზით მივდივართ ნულოვანი ცოდნის დამადასტურებელი პროტოკოლის იდეამდე. ნულოვანი ცოდნის ცოდნა გულისხმობს, რომ ინტერაქტიული მტკიცებულების სისტემის პროტოკოლის შედეგად V არ გაზრდის თავის ცოდნას S დებულების შესახებ, ან სხვა სიტყვებით რომ ვთქვათ, ვერ შეძლებს რაიმე ინფორმაციის ამოღებას იმის შესახებ, თუ რატომ არის S ჭეშმარიტი.
როგორც ადრე, პროტოკოლი წინასწარ აყალიბებს გარკვეულ განცხადებას S, მაგალითად, რომ ზოგიერთ w ობიექტს აქვს L თვისება: we L. პროტოკოლის დროს P და V ცვლიან შეტყობინებებს. თითოეულ მათგანს შეუძლია შექმნას შემთხვევითი რიცხვებიდა გამოიყენეთ ისინი თქვენს გამოთვლებში. პროტოკოლის ბოლოს, V-მ უნდა მიიღოს თავისი საბოლოო გადაწყვეტილება იმის შესახებ, არის თუ არა S ჭეშმარიტი თუ მცდარი.
P-ის მიზანია ყოველთვის დაარწმუნოს V, რომ S არის ჭეშმარიტი, იმისდა მიუხედავად, არის თუ არა ის სინამდვილეში ჭეშმარიტი, ანუ P შეიძლება იყოს აქტიური ოპონენტი, ხოლო V-ის ამოცანაა P-ის არგუმენტების შემოწმება მართალია თუ მცდარი. როგორც ადრე, V-ს აქვს პოლინომიურად შეზღუდული გამოთვლითი შესაძლებლობები, კერძოდ, მისი მუშაობის დრო შეზღუდულია რამდენიმე პოლინომიით.
დასამტკიცებელი განცხადების სიგრძე: ახლა განვიხილოთ მტკიცებულების პროტოკოლების მაგალითები ნულოვანი ცოდნით.
1. "პრობლემა ალი ბაბას გამოქვაბულთან დაკავშირებით." არის გამოქვაბული, რომლის გეგმა ნაჩვენებია ნახ. 1.2. გამოქვაბულს აქვს კარი საიდუმლოებით C და D წერტილებს შორის. ვინც იცის ჯადოსნური სიტყვები, შეუძლია გააღოს ეს კარი და გადავიდეს C-დან D-მდე ან პირიქით. ყველა დანარჩენისთვის ორივე გამოქვაბულის გადასასვლელი ჩიხში მიდის.
აცნობეთ რ-ს გამოქვაბულის საიდუმლო. მას სურს დაუმტკიცოს V-ს თავისი ცოდნა ამ საიდუმლოს შესახებ ჯადოსნური სიტყვების გამჟღავნების გარეშე. აქ არის მათი კომუნიკაციის პროტოკოლი:
V არის A წერტილში;
P შედის გამოქვაბულში და ხვდება C ან D წერტილამდე.
მას შემდეგ რაც P გამოქვაბულში გაუჩინარდება, V მიდის B წერტილში, არ იცის რა გზით წავიდა P.
V ურეკავს რ-ს და სთხოვს V-ის სურვილისამებრ გამოვიდეს გამოქვაბულის მარცხენა ან მარჯვენა დერეფნიდან;
რ ამას აკეთებს, საჭიროების შემთხვევაში ხსნის კარს, თუ, რა თქმა უნდა, მან იცის ჯადოსნური სიტყვები;
P და V გაიმეორეთ ნაბიჯები (1) - (5) n ჯერ.

პროტოკოლის n რაუნდის შემდეგ, ალბათობა შემცირდება 1/2"-მდე.
2. გრაფიკის იზომორფიზმის დადასტურება. P-ს სურს დაამტკიცოს გრაფიკების V იზომორფიზმი Go და Gb მოდით G, = (p(G0):G0 = G, სადაც φ არის იზომორფიზმის ტრანსფორმაცია; m არის გრაფიკების წვეროების N სიმრავლის კარდინალურობა. ამ განცხადების დამადასტურებელი ოქმი.
მოდით განვმარტოთ ამ პროტოკოლის სტრუქტურა. საფეხურზე (1) მონაწილე P ქმნის შემთხვევით გრაფიკს H, იზომორფულად G\. საფეხურზე (2), მონაწილე V, ირჩევს შემთხვევით ბიტს a = (0D), ამით ითხოვს დაამტკიცოს, რომ
Н ~G0 ან რომ Н « Gj. საფეხურზე (3) მონაწილე P უგზავნის მონაწილე V-ს ტრანსფორმაციას \|/, რომელსაც ის აყალიბებს ისე, რომ a = 1-ისთვის, ამ ტრანსფორმაციის Gu-ზე გამოყენების შედეგად, გრაფიკი F1 = TtG, = H. მიიღება და a = 0-სთვის, ამ ტრანსფორმაციის Ga-ზე გამოყენების შედეგად ვიღებთ გრაფიკს F0 =.
Zo Zapechnikov S.V. კრიპტოგრაფიული პროტოკოლები და მათი გამოყენება
= 7i((p(G0))~7iG] = #, საფეხურზე (4), მონაწილე V, გრაფიკის თანასწორობის შემოწმების შესრულებით, ამით განსაზღვრავს დაკმაყოფილებულია თუ არა პირობა
N = Fa. ნაბიჯები (1) - (4) მეორდება რამდენჯერმე. თუ ამ პროტოკოლის ყველა m რაუნდში ტესტის შედეგი დადებითია, V იღებს მტკიცებულებას.
ცხრილი 1.4. გრაფიკების იზომორფიზმის დამადასტურებელი პროტოკოლი P V 1% - წვეროების შემთხვევითი პერმუტაცია, ითვლის H = nGl 2 f n, თუ (a -1),
V = 1 / h 1 l o f თუ (a = 0) -> m-ჯერ 4 ითვლის გრაფიკს \j/Ga და ადარებს: H =\jfGa 5 იღებს მტკიცებულებას თუ და მხოლოდ თუ Vm-სთვის
ეს პროტოკოლი ნამდვილად ნულოვანი ცოდნის პროტოკოლია, ვინაიდან იზომორფული G0 ~ Gx-ის შემთხვევაში, მონაწილე V არ იღებს არანაირ ინფორმაციას, გარდა G0 და G\ გრაფიკების იზომორფიზმებისა, მათი შემთხვევითი გადანომრებით, რაც მას შეეძლო მიეღო და დამოუკიდებლად. , შემთხვევითი ბიტის არჩევა და გრაფიკის Ga-ს შემთხვევით გადანომრვა.
3. X რიცხვის x დისკრეტული ლოგარითმის ცოდნის დადასტურება. პროტოკოლის დაწყებამდე მითითებულია ღია სიდიდეები: p,
q- მარტივი რიცხვები, ისეთი, რომ q\(p -1), ელემენტი g e Z*, ნომერი X. Do-]. ძირითადი კრიპტოგრაფიული პროტოკოლები 31
პირმა, რომელიც რეკავს P-ს, იცის საიდუმლო მნიშვნელობა x\xცხრილი 1.5. დისკრეტული ლოგარითმის P V I r&RZ ცოდნის დამადასტურებელი პროტოკოლი
M = g (mod p) 2 A. y რიცხვის საფუძველში წარმოდგენის ცოდნის დადასტურება (y წარმოდგენის ცოდნის ნულოვანი ცოდნის დადასტურება). პროტოკოლის დაწყებამდე მითითებულია ღია სიდიდეები, რომლებიც ცნობილია ყველა მონაწილისთვის: მარტივი რიცხვები p, q, ელემენტები y, gvg2,..., gk Є Gq. პროვერმა P-მ იცის საიდუმლო სიდიდეები ara 2,...,ake ZQ: y =
= 8і" " 8г1""> ცოდნა, რომლის ცოდნაც მან უნდა დაუმტკიცოს V-ს თავად ამ რაოდენობების გამჟღავნების გარეშე. პროტოკოლი წარმოდგენილია ცხრილში. 1.6.
ცხრილი 1.6. წარმომადგენლობის ცოდნის დამადასტურებელი პროტოკოლი
რიცხვები საფუძველში P V 1 rl.r2,...,rk. ЄІ( Zq, 2 5. რიცხვთა სიმრავლის შესაბამის ფუძეებში წარმოდგენის ცოდნის დადასტურება (ყველა y(j)-ის ტოლობის ცოდნის ნულოვანი დადასტურება შესაბამის ფუძეებში). ოქმის დაწყებამდე. ღია რაოდენობები მითითებულია, ცნობილია
W I >\
ცნობილია ყველა მონაწილისთვის: მარტივი რიცხვები p, q, ელემენტები y, 82^є ზოგიერთისთვის (/). პროვერტმა P-მა იცის საიდუმლო მნიშვნელობები 0C[,a2,...,a,. є Zq, ისეთი, რომ V/ у^ =
= (і^) " 1 > ცოდნა, რომლის შესახებაც მან უნდა დაამტკიცოს V,
თავად ამ ღირებულებების გამჟღავნების გარეშე. მაგიდაზე 1.7 აჩვენებს პროტოკოლს, რომელიც აგვარებს ამ პრობლემას.
ცხრილი 1.7. რიცხვთა სიმრავლის ცოდნის დამადასტურებელი პროტოკოლი
შესაბამის ფუძეებში P V 1 rvr21...lrkeR U/ 2-ისთვის (AiP«iT-(lt-
6. ჩადენილი ფასეულობების მრავლობითი მიმართების ცოდნის დადასტურება. X ელემენტი = ციკლური ქვეჯგუფის gx მარტივი შეკვეთა, რომელშიც დისკრეტული ლოგარითმის პრობლემა ითვლება გამოთვლით რთულად, ეწოდება დეპონირებული მნიშვნელობა (ჩამოწერილი მნიშვნელობა), რომელიც წარმოადგენს საიდუმლო მნიშვნელობას x. დაე
d არის ისეთი უცნობი ელემენტი, რომ h = gd. პროტოკოლის დაწყებამდე მითითებულია ღია სიდიდეები: მარტივი რიცხვები p, q, ელემენტები A, B, C Є Gq. P-ის პროვერმა იცის საიდუმლო რაოდენობები
a, a, b, b, c, c, ისე, რომ c = ab, A = gah"\ B = gbhb, C = gche. მან უნდა დაამტკიცოს მათი ცოდნა V, თავად მნიშვნელობების გამჟღავნების გარეშე. ცხრილში 1.8 , თან - ასეთი მტკიცებულების ოქმი შენახულია.
ცხრილი 1.8. დეპონირებული სიდიდეების მრავლობითი ურთიერთობის ცოდნის დამადასტურებელი ოქმი P V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
ცოდნის გამჟღავნება
ცხრილი 1.9. მტკიცებულების პროტოკოლების სტრუქტურა ნულოვანი P S: x є L - მტკიცებულება, h - dp, საჯარო პარამეტრები და სიდიდეები, s - პროვერის საიდუმლო მონაცემები იმის შესახებ, თუ რატომ არის S ჭეშმარიტი, r - შემთხვევითი რიცხვი V 1 rp - შემთხვევითი, 2. rv - შემთხვევითი რიცხვი,
c = LM განვაზოგადოთ განხილული მაგალითები და ჩამოვაყალიბოთ რამდენიმე განმარტება. IN ზოგადი ხედიინტერაქტიული მტკიცებულების პროტოკოლი ნულოვანი ცოდნით (ცხრილი 1.9) შედგება ოთხი ეტაპისგან:
მაგიდის დასასრული. 1.9 P S: xe L არის მტკიცებულება, h არის სხვა საჯაროდ ხელმისაწვდომი პარამეტრები და სიდიდეები, s არის პროვერტის საიდუმლო მონაცემები იმის შესახებ, თუ რატომ არის S ჭეშმარიტი, r არის შემთხვევითი რიცხვი V 3 R = f3(C,x) 4
პროვერტი გადამმოწმებელს გადასცემს ეგრეთ წოდებულ მტკიცებულებას (მოწმე -W) - საიდუმლო მნიშვნელობის ცალმხრივი ფუნქციის გამოთვლის შედეგს, რომლის ცოდნასაც ადასტურებს;
რეფერენტი მას უგზავნის შემთხვევით მოთხოვნას;
პროვერტი პასუხობს ამ შეკითხვას და პასუხი დამოკიდებულია როგორც შემთხვევით შეკითხვაზე, ასევე საიდუმლო მნიშვნელობაზე, მაგრამ მისგან ამ საიდუმლო მნიშვნელობის მიღება გამოთვლით შეუძლებელია;
პასუხის მიღებისას V ამოწმებს მის შესაბამისობას პირველ ეტაპზე გადაცემულ „მტკიცებულებებთან“.
მოდით განვიხილოთ მტკიცებულებების აგების ძირითადი პრინციპები ნულოვანი ცოდნის გამოვლენით: რას გულისხმობს ნულოვანი ცოდნის ცოდნის თვისება.
ნულოვანი ცოდნის მტკიცებულების თეორიაში ცოდნა P და V განიხილება როგორც „შავი ყუთები“ (ნახ. 1.3).
დაე, \tr ), \)Py ) იყოს P-დან V-მდე გადაცემული ყველა შეტყობინების სიმრავლე (შესაბამისად V-დან P-მდე), რომელთაგან თითოეული არის შემთხვევითი ცვლადი და, შესაბამისად, (x,h,rv,(mp),( mv)) = = ხედი, ϐϵ)