แผนการผูกมัด (Commitment scheme ) เป็นกลไกการเข้ารหัสลับพื้นฐานที่ช่วยให้สามารถผูกมัดค่าที่เลือก (หรือข้อความที่เลือก) ไว้ได้ในขณะที่ยังคงซ่อนค่าดังกล่าวจากผู้อื่น โดยสามารถเปิดเผยค่าที่ผูกมัดไว้ได้ในภายหลัง^{[ 1 ]}แผนการผูกมัดถูกออกแบบมาเพื่อให้ฝ่ายใดฝ่ายหนึ่งไม่สามารถเปลี่ยนแปลงค่าหรือข้อความหลังจากที่ได้ผูกมัดไว้แล้ว กล่าวคือ แผนการผูกมัดมีผลผูกพัน แผนการผูกมัดมีการใช้งานที่สำคัญใน โปรโตคอลการเข้ารหัสลับหลายอย่างรวมถึงการโยนเหรียญอย่างปลอดภัยการพิสูจน์ความรู้เป็นศูนย์และ การ คำนวณ อย่างปลอดภัย

วิธีหนึ่งที่จะทำให้เห็นภาพโครงสร้างการผูกมัดได้ชัดเจนขึ้นคือ ลองนึกภาพผู้ส่งสารใส่ข้อความไว้ในกล่องที่ล็อกได้ แล้วส่งกล่องนั้นให้ผู้รับสาร ข้อความในกล่องนั้นถูกซ่อนไว้จากผู้รับสาร เพราะผู้รับสารไม่สามารถเปิดล็อกได้ด้วยตนเอง เนื่องจากผู้รับสารมีกล่องอยู่แล้ว ข้อความภายในจึงไม่สามารถเปลี่ยนแปลงได้ เพียงแต่จะถูกเปิดเผยก็ต่อเมื่อผู้ส่งสารเลือกที่จะมอบกุญแจให้ในภายหลังเท่านั้น

ปฏิสัมพันธ์ในโครงการสร้างความผูกพันเกิดขึ้นในสองขั้นตอน:

1. ขั้นตอนการยืนยันค่า ซึ่งเป็นขั้นตอนที่เลือกและยืนยันค่าลงไป
2. ขั้นตอน การเปิดเผยข้อมูลซึ่งผู้ส่งจะเปิดเผยค่าของข้อมูล จากนั้นผู้รับจะตรวจสอบความถูกต้องของข้อมูลนั้น

ในอุปมาข้างต้น ขั้นตอนการยืนยัน (Commit) คือผู้ส่งนำข้อความใส่กล่องและล็อกกล่องไว้ ขั้นตอนการเปิดเผย (Reveal) คือผู้ส่งมอบกุญแจให้ผู้รับ ซึ่งใช้กุญแจนั้นเปิดกล่องและตรวจสอบเนื้อหาภายใน กล่องที่ล็อกไว้คือการยืนยัน และกุญแจคือหลักฐาน

ในโปรโตคอลแบบง่ายๆ ขั้นตอนการยืนยัน (commit phase) ประกอบด้วยข้อความเดียวจากผู้ส่งไปยังผู้รับ ข้อความนี้เรียกว่า การยืนยัน ( commitment ) สิ่งสำคัญคือค่าที่เลือกนั้นจะต้องไม่สามารถดึงออกมาจากข้อความโดยผู้รับได้ในขณะนั้น (คุณสมบัตินี้เรียกว่า การซ่อน (hiding property)) ขั้นตอนการเปิดเผย (reveal phase) แบบง่ายๆ จะประกอบด้วยข้อความเดียวการเปิด (opening ) จากผู้ส่งไปยังผู้รับ ตามด้วยการตรวจสอบโดยผู้รับ ค่าที่เลือกในระหว่างขั้นตอนการยืนยันจะต้องเป็นค่าเดียวที่ผู้ส่งสามารถคำนวณได้และตรวจสอบความถูกต้องได้ในระหว่างขั้นตอนการเปิดเผย (คุณสมบัตินี้เรียกว่า การ ผูกมัด ( binding property))

แนวคิดของแผนการผูกมัดอาจได้รับการกำหนดเป็นทางการครั้งแรกโดยGilles Brassard , David ChaumและClaude Crépeauในปี 1988 ^{[ 2 ]}ซึ่งเป็นส่วนหนึ่งของโปรโตคอลความรู้เป็นศูนย์ต่างๆ สำหรับNPโดยอิงจากแผนการผูกมัดประเภทต่างๆ^{[ 3 ] [ 4 ]}แต่แนวคิดนี้ถูกนำมาใช้ก่อนหน้านั้นโดยไม่ได้ถูกกำหนดเป็นทางการ^{[ 5 ] [ 6 ]}แนวคิดเรื่องการผูกมัดปรากฏขึ้นครั้งแรกในงานของManuel Blum [ ^{7 ]} Shimon Even [ ^{8 ] และ} Adi Shamirและคณะ^{[ 9 ]}ดูเหมือนว่าคำศัพท์นี้จะมีต้นกำเนิดมาจาก Blum ^{[ 6 ]}แม้ว่าแผนการผูกมัดสามารถเรียกแทนกันได้ว่าแผนการผูกมัดบิต ซึ่งบาง ^{ครั้ง}สงวนไว้สำหรับกรณีพิเศษที่ค่าที่ผูกมัดเป็นบิตก่อนหน้านั้น การผูกมัดผ่านฟังก์ชันแฮชแบบทางเดียวได้รับการพิจารณา เช่น เป็นส่วนหนึ่งของลายเซ็น Lamportซึ่งเป็นแผนการลายเซ็นแบบใช้ครั้งเดียวหนึ่งบิตดั้งเดิม

สมมติว่าอลิซและบ็อบต้องการยุติข้อพิพาทบางอย่างด้วยการโยนเหรียญหากพวกเขาทั้งสองอยู่สถานที่เดียวกัน ขั้นตอนทั่วไปอาจเป็นดังนี้:

1. อลิซ "ทาย" การโยนเหรียญ
2. บ็อบโยนเหรียญ
3. ถ้าอลิซทายถูก เธอจะชนะ แต่ถ้าทายผิด บ็อบจะชนะ

หากอลิซและบ็อบไม่ได้อยู่สถานที่เดียวกัน ปัญหาจะเกิดขึ้น เมื่ออลิซ "ประกาศ" ผลลัพธ์ของการโยนเหรียญแล้ว บ็อบสามารถกำหนด "ผลลัพธ์" ของการโยนเหรียญให้เป็นอะไรก็ได้ที่เขาต้องการมากที่สุด ในทำนองเดียวกัน หากอลิซไม่ประกาศ "การประกาศ" ของเธอให้บ็อบทราบ หลังจากที่บ็อบโยนเหรียญและประกาศผลลัพธ์แล้ว อลิซก็สามารถรายงานว่าเธอประกาศผลลัพธ์อะไรก็ได้ที่เธอต้องการมากที่สุด อลิซและบ็อบสามารถใช้ข้อผูกมัดในกระบวนการที่จะทำให้ทั้งสองฝ่ายไว้วางใจในผลลัพธ์ได้

1. อลิซ "ทายผล" การโยนเหรียญ แต่บอกแค่กับบ็อบว่าเธอต้องทำตามที่ ทายไว้เท่านั้น
2. บ็อบโยนเหรียญและรายงานผลลัพธ์
3. อลิซเปิดเผยสิ่งที่เธอให้คำมั่นสัญญาไว้
4. บ็อบตรวจสอบว่าการโทรของอลิซตรงกับคำมั่นสัญญาของเธอหรือไม่
5. ถ้าคำทำนายของอลิซตรงกับผลการโยนเหรียญที่บ็อบรายงาน อลิซก็จะเป็นผู้ชนะ

เพื่อให้บ็อบสามารถบิดเบือนผลลัพธ์ให้เป็นไปในทางที่ตนเองได้เปรียบ เขาต้องเข้าใจเงื่อนไขที่ซ่อนอยู่ในการให้คำมั่นสัญญาของอลิซ หากแผนการให้คำมั่นสัญญานั้นดี บ็อบก็ไม่สามารถบิดเบือนผลลัพธ์ได้ ในทำนองเดียวกัน อลิซก็ไม่สามารถเปลี่ยนแปลงผลลัพธ์ได้หากเธอไม่สามารถเปลี่ยนแปลงมูลค่าที่เธอให้คำมั่นสัญญาไว้ได้

ปัญหาดังกล่าวพบได้ในชีวิตจริง เมื่อผู้คน (โดยเฉพาะในสื่อ) ตัดสินใจหรือให้คำตอบใน "ซองปิดผนึก" ซึ่งจะถูกเปิดออกในภายหลัง ตัวอย่างเช่น ในรายการเกมโชว์ ประโยคที่ว่า "มาดูกันว่าผู้สมัครตอบแบบนั้นจริงหรือไม่" สามารถใช้เป็นแบบจำลองของระบบนี้ได้

ตัวอย่างหนึ่งที่กระตุ้นให้เกิดการใช้ระบบข้อผูกมัดในการพิสูจน์ความรู้เป็นศูนย์ คือ การใช้ข้อผูกมัดในการพิสูจน์ความรู้เป็นศูนย์มีวัตถุประสงค์หลักสองประการ ประการแรก เพื่อให้ผู้พิสูจน์สามารถมีส่วนร่วมในการพิสูจน์แบบ "ตัดและเลือก" โดยที่ผู้ตรวจสอบจะได้รับตัวเลือกในการเรียนรู้ และผู้พิสูจน์จะเปิดเผยเฉพาะสิ่งที่สอดคล้องกับตัวเลือกของผู้ตรวจสอบเท่านั้น ระบบข้อผูกมัดช่วยให้ผู้พิสูจน์สามารถระบุข้อมูลทั้งหมดล่วงหน้า และเปิดเผยเฉพาะสิ่งที่ควรเปิดเผยในภายหลังในการพิสูจน์^{[ 10 ]} ประการที่สอง ข้อผูกมัดยังถูกใช้ในการพิสูจน์ความรู้เป็นศูนย์โดยผู้ตรวจสอบ ซึ่งมักจะระบุตัวเลือกของตนล่วงหน้าในข้อผูกมัด สิ่งนี้ช่วยให้สามารถประกอบการพิสูจน์ความรู้เป็นศูนย์แบบขนานได้โดยไม่ต้องเปิดเผยข้อมูลเพิ่มเติมแก่ผู้พิสูจน์^{[ 11 ]}

ระบบ ลาย เซ็นดิจิทัลLamportเป็นระบบที่อาศัยการเก็บรักษาชุดข้อมูล ลับสองชุด เผยแพร่ค่าแฮชที่ตรวจสอบได้ของชุดข้อมูลเหล่านั้น และจากนั้นจึงเปิดเผยชุดข้อมูลลับบางส่วนอย่างเลือกสรรในลักษณะที่สอดคล้องกับข้อมูลที่จะลงนามโดยเฉพาะ ด้วยวิธีนี้ การยืนยันต่อสาธารณะล่วงหน้าเกี่ยวกับค่าลับจึงกลายเป็นส่วนสำคัญของการทำงานของระบบ

เนื่องจากระบบลายเซ็น Lamport ไม่สามารถใช้งานได้มากกว่าหนึ่งครั้ง จึงได้มีการพัฒนาระบบเพื่อรวมชุดคีย์ Lamport หลายชุดเข้าไว้ในค่าสาธารณะเดียวที่สามารถเชื่อมโยงกับบุคคลและตรวจสอบโดยผู้อื่นได้ ระบบนี้ใช้โครงสร้างแฮชแบบต้นไม้เพื่อบีบอัดชุดคีย์ Lamport ที่เผยแพร่แล้วหลายชุดให้เป็นค่าแฮชเดียวที่สามารถเชื่อมโยงกับผู้เขียนข้อมูลที่ได้รับการตรวจสอบในภายหลังได้

การประยุกต์ใช้ที่สำคัญอีกประการหนึ่งของข้อผูกพันคือการแบ่งปันความลับที่ตรวจสอบได้ซึ่งเป็นองค์ประกอบสำคัญของการคำนวณแบบหลายฝ่ายที่ปลอดภัยใน แผนการ แบ่งปันความลับแต่ละฝ่ายจะได้รับ "ส่วนแบ่ง" ของค่าที่ตั้งใจจะซ่อนจากทุกคน หากมีฝ่ายต่างๆ รวมตัวกันมากพอ ส่วนแบ่งของพวกเขาจะสามารถใช้ในการสร้างความลับขึ้นมาใหม่ได้ แต่แม้แต่กลุ่มผู้ไม่ประสงค์ดีที่มีขนาดไม่เพียงพอก็ไม่ควรเรียนรู้อะไรเลย การแบ่งปันความลับเป็นรากฐานของโปรโตคอลจำนวนมากสำหรับการคำนวณที่ปลอดภัย : เพื่อคำนวณฟังก์ชันของอินพุตที่ใช้ร่วมกันอย่างปลอดภัย จะมีการจัดการส่วนแบ่งความลับแทน อย่างไรก็ตาม หากส่วนแบ่งจะถูกสร้างขึ้นโดยฝ่ายที่ไม่ประสงค์ดี อาจเป็นสิ่งสำคัญที่ส่วนแบ่งเหล่านั้นสามารถตรวจสอบความถูกต้องได้ ในแผนการแบ่งปันความลับที่ตรวจสอบได้ การแจกจ่ายความลับจะมาพร้อมกับข้อผูกพันต่อส่วนแบ่งแต่ละส่วน ข้อผูกพันไม่ได้เปิดเผยสิ่งใดที่สามารถช่วยกลุ่มผู้ไม่ประสงค์ดีได้ แต่ส่วนแบ่งช่วยให้แต่ละฝ่ายสามารถตรวจสอบได้ว่าส่วนแบ่งของตนถูกต้องหรือไม่^{[ 12 ]}

คำจำกัดความอย่างเป็นทางการของแผนการยืนยันตัวตนมีความแตกต่างกันอย่างมากทั้งในด้านสัญลักษณ์และลักษณะเฉพาะ ลักษณะเฉพาะประการแรกคือ แผนการยืนยันตัวตนนั้นให้ความปลอดภัยที่สมบูรณ์แบบหรือความปลอดภัยเชิงคำนวณหรือไม่ เมื่อเทียบกับคุณสมบัติการซ่อนหรือการผูกมัด ลักษณะเฉพาะอีกประการหนึ่งคือ การยืนยันตัวตนนั้นเป็นแบบโต้ตอบหรือไม่ กล่าวคือ ทั้งขั้นตอนการยืนยันและขั้นตอนการเปิดเผยสามารถมองได้ว่าดำเนินการโดยโปรโตคอลการเข้ารหัสลับหรือไม่ หรือเป็นแบบไม่โต้ตอบ ซึ่งประกอบด้วยสองอัลกอริธึม คือCommitและCheckRevealในกรณีหลังCheckRevealมักถูกมองว่าเป็นเวอร์ชันที่ลดความสุ่มของCommitโดยความสุ่มที่ใช้โดยCommit นั้น เป็นข้อมูลเริ่มต้น

หากค่าผูกมัดCต่อค่าxถูกคำนวณเป็นC:=Commit(x,open)โดยที่openคือค่าสุ่มที่ใช้ในการคำนวณค่าผูกมัดแล้วCheckReveal (C,x,open)จะลดลงเหลือเพียงการตรวจสอบสมการC=Commit (x,open)เท่านั้น

โดยใช้สัญลักษณ์นี้และความรู้เกี่ยวกับฟังก์ชันทางคณิตศาสตร์และทฤษฎีความน่าจะเป็นเราจะกำหนดรูปแบบที่เป็นทางการของคุณสมบัติการผูกมัดและการซ่อนเร้นของข้อผูกมัดในรูปแบบต่างๆ การผสมผสานคุณสมบัติที่สำคัญที่สุดสองแบบคือ แผนการผูกมัดที่ผูกมัดอย่างสมบูรณ์และซ่อนเร้นเชิงคำนวณ และแผนการผูกมัดที่ผูกมัดเชิงคำนวณและซ่อนเร้นอย่างสมบูรณ์ โปรดทราบว่าไม่มีแผนการผูกมัดใดที่สามารถผูกมัดอย่างสมบูรณ์และซ่อนเร้นอย่างสมบูรณ์ได้ในเวลาเดียวกัน – ฝ่ายตรงข้ามที่ไม่มีขีดจำกัดเชิงคำนวณสามารถสร้างCommit(x,open)สำหรับทุกค่าของxและopen ไป เรื่อยๆ จนกว่าจะพบคู่ที่ให้ผลลัพธ์เป็นCและในแผนการผูกมัดอย่างสมบูรณ์ สิ่งนี้จะระบุx ได้อย่างเฉพาะ เจาะจง

ให้ เลือก ตัวแปรเปิดจากเซตที่มีขนาดk กล่าวคือ สามารถแสดงเป็น สตริง kบิตได้ และให้ เป็นแผนการผูกมัดที่สอดคล้องกัน เนื่องจากขนาดของkเป็นตัวกำหนดความปลอดภัยของแผนการผูกมัด จึงเรียกว่าพารามิเตอร์ความปลอดภัย ${\displaystyle 2^{k}}$${\displaystyle {\text{Commit}}_{k}}$

จากนั้นสำหรับ อัลกอริธึมเวลาพหุนามเชิงความน่าจะเป็นที่ไม่สม่ำเสมอ ทั้งหมดที่ส่งออกและมีความยาว k เพิ่มขึ้นความ น่าจะเป็นที่และเป็นฟังก์ชันที่ไม่สำคัญในk${\displaystyle x,x'}$${\displaystyle open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$

นี่เป็นรูปแบบหนึ่งของการวิเคราะห์เชิงอะซิมโทติกนอกจากนี้ยังสามารถระบุข้อกำหนดเดียวกันโดยใช้ความปลอดภัยที่เป็นรูปธรรมได้ : โครงการผูกพันCommitมีความปลอดภัย หากสำหรับอัลกอริธึมทั้งหมดที่ทำงานในเวลาtและส่งออกความน่าจะเป็นที่และ มีค่า ไม่ เกิน${\displaystyle (t,\epsilon )}$${\displaystyle x,x',open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$${\displaystyle \epsilon }$

ให้เป็นการแจกแจงแบบเอกรูปเหนือค่าเริ่มต้นสำหรับพารามิเตอร์ความปลอดภัยkแผนการผูกมัดจะถือว่าเป็นการซ่อนข้อมูลที่สมบูรณ์แบบ การซ่อนข้อมูลเชิงสถิติ หรือการซ่อนข้อมูลเชิงคำนวณ ตามลำดับ หากสำหรับกลุ่มความน่าจะเป็นทั้งหมดและมีค่าเท่ากันใกล้เคียงกันทางสถิติหรือไม่สามารถแยกแยะได้ทางคำนวณ ${\displaystyle U_{k}}$${\displaystyle 2^{k}}$${\displaystyle x\neq x'}$${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$${\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}$

เป็นไปไม่ได้ที่จะทำให้แผนการผูกพันเกิดขึ้นใน กรอบงาน การประกอบสากล (UC) เหตุผลก็คือการผูกพัน UC จะต้องสามารถแยกออกมาได้ดังที่ Canetti และ Fischlin ^{[ 13 ]} ได้แสดงไว้ และอธิบายไว้ด้านล่าง

ฟังก์ชันการยืนยันในอุดมคติ ซึ่งในที่นี้แทนด้วยFนั้น ทำงานโดยคร่าว ๆ ดังนี้ ผู้ยืนยันCส่งค่าmไปยังFซึ่งจะจัดเก็บค่าดังกล่าวและส่ง "ใบเสร็จรับเงิน" ไปยังผู้รับRต่อมาCส่ง "การเปิด" ไปยัง Fซึ่งจะส่งค่า mไปยัง R

ทีนี้ สมมติว่าเรามีโปรโตคอลπที่ทำงานตามฟังก์ชันนี้ สมมติว่าตัวยืนยัน (committer) Cเสียหาย ในกรอบงาน UC นั้น หมายความว่าCถูกควบคุมโดยสภาพแวดล้อม ซึ่งพยายามแยกแยะการทำงานของโปรโตคอลออกจากกระบวนการในอุดมคติ ลองพิจารณาสภาพแวดล้อมที่เลือกข้อความmแล้วบอกให้Cทำงานตามที่กำหนดโดยπราวกับว่าได้ยืนยัน ข้อความ m แล้ว โปรดสังเกตว่า เพื่อให้F ทำงานได้อย่างถูกต้อง ผู้รับจะต้องส่งข้อความ "receipt" ออกมาหลังจากได้รับคำยืนยันแล้ว หลังจากที่สภาพแวดล้อมเห็นข้อความนี้แล้ว ก็จะบอกให้Cเปิดคำยืนยันนั้น

โปรโตคอลจะปลอดภัยก็ต่อเมื่อสถานการณ์นี้ไม่แตกต่างจากกรณีในอุดมคติ ซึ่งฟังก์ชันการทำงานจะโต้ตอบกับโปรแกรมจำลองSในที่นี้SควบคุมCโดยเฉพาะอย่างยิ่ง เมื่อใดก็ตามที่Rส่งออก "ใบเสร็จรับเงิน" Fก็ต้องทำเช่นเดียวกัน วิธีเดียวที่จะทำได้คือSต้องบอกให้Cส่งค่าไปยังFอย่างไรก็ตาม โปรดทราบว่า ณ จุดนี้Sยังไม่ทราบค่าmดังนั้น เมื่อมีการเปิดข้อผูกมัดระหว่างการดำเนินการโปรโตคอล จึงไม่น่าเป็นไปได้ที่Fจะเปิดรับค่าmเว้นแต่Sจะสามารถดึงค่าm ออกมา จากข้อความที่ได้รับจากสภาพแวดล้อมก่อนที่Rจะส่งออกใบเสร็จรับเงิน

อย่างไรก็ตาม โปรโตคอลที่สามารถดึงออกมาได้ในแง่นี้ไม่สามารถซ่อนข้อมูลทางสถิติได้ สมมติว่ามีโปรแกรมจำลองSอยู่จริง ทีนี้ลองพิจารณาสภาพแวดล้อมที่แทนที่จะทำให้C เสียหาย กลับทำให้ Rเสียหายแทน นอกจากนี้ยังรันสำเนาของSด้วย ข้อความที่ได้รับจากCจะถูกป้อนเข้าไปในSและการตอบกลับจากSจะถูกส่งต่อไปยัง C

ในขั้นต้น สภาพแวดล้อมจะบอกให้Cยืนยันข้อความmณ จุดใดจุดหนึ่งของการปฏิสัมพันธ์Sจะยืนยันค่าm′ข้อความนี้จะถูกส่งต่อให้Rซึ่งจะแสดง ค่า m′ ออกมา โปรดสังเกตว่าตามสมมติฐาน เรามีm' = m ด้วยความน่าจะเป็นสูงในกระบวนการในอุดมคติ ตัวจำลองจะต้องสร้างค่าm ขึ้นมา แต่สิ่งนี้เป็นไปไม่ได้ เพราะ ณ จุดนี้ การยืนยันยังไม่ได้ถูกเปิดออก ดังนั้นข้อความเดียวที่Rจะได้รับในกระบวนการในอุดมคติคือข้อความ "รับ" ดังนั้นเราจึงพบข้อขัดแย้ง

แผนการผูกมัดสามารถผูกมัดได้อย่างสมบูรณ์แบบ (เป็นไปไม่ได้ที่อลิซจะเปลี่ยนแปลงการผูกมัดของเธอหลังจากที่เธอได้ผูกมัดไปแล้ว แม้ว่าเธอจะมีทรัพยากรการคำนวณที่ไม่จำกัดก็ตาม) หรือปกปิดได้อย่างสมบูรณ์แบบ (เป็นไปไม่ได้ที่บ็อบจะค้นพบการผูกมัดโดยที่อลิซไม่เปิดเผย แม้ว่าเขาจะมีทรัพยากรการคำนวณที่ไม่จำกัดก็ตาม) หรือกำหนดเป็นแผนการผูกมัดที่ขึ้นอยู่กับอินสแตนซ์ ซึ่งอาจเป็นการซ่อนหรือผูกมัดขึ้นอยู่กับวิธีแก้ปัญหาอื่น^{[ 14 ] [ 15 ]}แผนการผูกมัดไม่สามารถซ่อนได้อย่างสมบูรณ์แบบและผูกมัดได้อย่างสมบูรณ์แบบในเวลาเดียวกัน

แผนการยืนยันบิตนั้นสร้างได้ง่ายใน แบบ จำลองออราเคิลแบบสุ่มเมื่อกำหนดฟังก์ชันแฮช H ที่มีเอาต์พุต 3k บิตเพื่อยืนยันข้อความm k บิต อลิซจะสร้าง สตริง R kบิต แบบสุ่ม และส่ง H( R || m ) ไปให้บ็อบ ความน่าจะเป็นที่R′ , m′ ใดๆ จะมีอยู่โดยที่m′ ≠ mซึ่งทำให้ H( R′ || m′ ) = H( R || m ) คือ ≈ 2 ^{− k}แต่ในการทดสอบการเดาข้อความm ใดๆ บ็อบจะต้องทำการสอบถามออราเคิลแบบสุ่ม 2k ครั้ง (สำหรับการเดาที่ไม่ถูกต้อง) หรือ 2k-1 ครั้ง (โดยเฉลี่ยสำหรับการเดาที่ถูกต้อง) ^[ 16 ^{]เราสังเกตว่าแผนการ}ก่อนหน้านี้ที่อิงตามฟังก์ชันแฮช โดยพื้นฐานแล้วสามารถคิดได้ว่าเป็นแผนการที่อิงตามการทำให้เป็นอุดมคติของฟังก์ชันแฮชเหล่านี้ในฐานะออราเคิลแบบสุ่ม

เราสามารถสร้างรูปแบบการผูกมัดบิตได้จากฟังก์ชันทางเดียว ใดๆ ที่เป็นฟังก์ชัน หนึ่งต่อ หนึ่ง รูปแบบนี้อาศัยข้อเท็จจริงที่ว่า ฟังก์ชันทางเดียวทุกฟังก์ชันสามารถปรับเปลี่ยนได้ (ผ่านทฤษฎีบทโกลด์ไรช์-เลวิน ) เพื่อให้มี ตัวบ่งชี้หลักที่ยากต่อการคำนวณ(ในขณะที่ยังคงรักษาคุณสมบัติหนึ่งต่อหนึ่งไว้)

ให้fเป็นฟังก์ชันหนึ่งทางเดียวแบบหนึ่งต่อหนึ่ง และhเป็น述语แบบฮาร์ดคอร์ จากนั้น เพื่อให้ยืนยันบิตb ได้ อลิซจะเลือกอินพุตx แบบสุ่ม และส่งสามค่า

${\displaystyle (h,f(x),b\oplus h(x))}$

สำหรับ Bob นั้นหมายถึงการดำเนินการ XOR หรือก็คือการบวกแบบบิตต่อบิตโมดูล 2 ในการยกเลิกข้อผูกมัด Alice เพียงแค่ส่งxไปให้ Bob Bob ตรวจสอบโดยการคำนวณf ( x ) และเปรียบเทียบกับค่าที่ผูกมัดไว้ วิธีการนี้เป็นการปกปิด เพราะเพื่อให้ Bob สามารถกู้คืนb ได้ เขาต้องกู้คืนh ( x ) ก่อน เนื่องจากhเป็น述语ที่ยากต่อการคำนวณ การกู้คืนh ( x ) จาก f ( x ) ด้วยความน่าจะเป็นมากกว่าครึ่งนั้นยากพอๆ กับการหาค่าผกผันของfการผูกมัดที่สมบูรณ์แบบเป็นผลมาจากข้อเท็จจริงที่ว่าfเป็นฟังก์ชันหนึ่งต่อหนึ่ง ดังนั้นf ( x ) จึงมีภาพผกผันเพียงภาพเดียว ${\displaystyle \oplus }$

โปรดทราบว่า เนื่องจากเราไม่ทราบวิธีการสร้างการเรียงสับเปลี่ยนแบบทางเดียวจากฟังก์ชันแบบทางเดียวใดๆ ส่วนนี้จึงลดความแข็งแกร่งของสมมติฐานทางด้านการเข้ารหัสที่จำเป็นต่อการสร้างโปรโตคอลการยืนยันบิตลง

ในปี พ.ศ. 2534 Moni Naorได้แสดงวิธีการสร้างแผนการผูกมัดบิตจากตัวสร้างเลขสุ่มเทียมที่มีความปลอดภัยทางการเข้ารหัส [ ^{17 ] โครงสร้าง}มีดังนี้ หากGเป็นตัวสร้างเลขสุ่มเทียมที่Gใช้บิตn ถึง 3nบิต หาก Alice ต้องการผูกมัดกับบิตb :

• บ็อบเลือกเวกเตอร์ 3n บิตแบบสุ่มRและส่ง R ไปให้อลิซ
• อลิซเลือกเวกเตอร์Y ขนาด n บิตแบบสุ่ม และคำนวณเวกเตอร์G ( Y ) ขนาด n บิต
• ถ้าb = 1 อลิซจะส่งG ( Y ) ไปให้บ็อบ มิฉะนั้นเธอจะส่งผลการดำเนินการเอกซ์คลูซีฟออร์แบบบิตของG ( Y ) และRไปให้บ็อบ

เพื่อยกเลิกข้อผูกมัด อลิซส่งYไปให้บ็อบ ซึ่งบ็อบสามารถตรวจสอบได้ว่าในตอนแรกเขาได้รับG ( Y )หรือG ( Y ) R${\displaystyle \oplus }$

แผนการนี้มีผลผูกพันทางสถิติ หมายความว่าแม้ว่าอลิซจะมีขีดจำกัดในการคำนวณ เธอก็ไม่สามารถโกงได้ด้วยความน่าจะเป็นที่มากกว่า 2 ^{− n}หากอลิซต้องการโกง เธอจะต้องหาค่าY'ที่ทำให้G ( Y' ) = G ( Y ) Rถ้าเธอหาค่าดังกล่าวได้ เธอก็สามารถยกเลิกข้อผูกมัดได้โดยการส่งคำตอบที่ถูกต้องและYหรือส่งคำตอบที่ตรงกันข้ามและY'อย่างไรก็ตามG ( Y ) และG ( Y' ⁾สามารถสร้างค่าที่เป็นไปได้เพียง 2n ^ค่า เท่านั้น (นั่นคือ^2²n ) ในขณะที่Rถูกเลือกจาก^{2³n ค่า}เธอไม่ได้เลือกRดังนั้นจึงมีความน่าจะ เป็น ^2²n / ^2³n = 2 ^{− n ที่ค่า}Y'ที่ตรงตามสมการที่จำเป็นสำหรับการโกงจะมีอยู่ ${\displaystyle \oplus }$

คุณสมบัติการปกปิดเป็นผลมาจากการลดทอนมาตรฐาน หากบ็อบสามารถบอกได้ว่าอลิซเลือกเลขศูนย์หรือเลขหนึ่ง เขาก็สามารถแยกแยะผลลัพธ์ของตัวสร้างเลขสุ่มเทียมG ออกจากเลขสุ่มแท้ได้เช่นกัน ซึ่งขัดแย้งกับ ความ ปลอดภัยทางด้านการเข้ารหัสของG

อลิ ซ เลือกกลุ่มจำนวนเฉพาะที่มีอันดับpโดยมีตัวสร้างg

อลิซสุ่มเลือกค่าลับxจาก0ถึงp  − 1 เพื่อยืนยัน และคำนวณc = g ^xแล้วเผยแพร่c ปัญหาลอการิทึมแบบไม่ต่อเนื่องระบุว่า จากcนั้น การคำนวณx เป็นไปไม่ได้ในทางปฏิบัติ ดังนั้นภายใต้สมมติฐานนี้ บ็อบจึงไม่สามารถคำนวณx ได้ ในทางกลับกัน อลิซไม่สามารถคำนวณx ′ <> x ได้ โดยที่g ^{x ′} = cดังนั้นแผนการนี้จึงมีผลผูกพัน

แผนการนี้ไม่ได้ปกปิดอย่างสมบูรณ์แบบ เพราะใครก็ตามสามารถหาข้อผูกมัดได้หากเขาสามารถแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่องได้อันที่จริง แผนการนี้ไม่ได้ซ่อนเร้นเลยเมื่อเทียบกับเกมการซ่อนเร้นแบบมาตรฐาน ซึ่งฝ่ายตรงข้ามไม่ควรจะเดาได้ว่าข้อความใดในสองข้อความที่เขาเลือกนั้นมีข้อผูกมัดอยู่ – คล้ายกับ เกม IND-CPAผลที่ตามมาอย่างหนึ่งก็คือ หากพื้นที่ของค่าที่เป็นไปได้ของxมีขนาดเล็ก ผู้โจมตีก็สามารถลองใช้ค่าทั้งหมดได้ และข้อผูกมัดนั้นก็จะไม่ถูกซ่อนเร้นอีกต่อไป

ตัวอย่างที่ดีกว่าของแผนการผูกมัดที่สมบูรณ์แบบคือแผนการที่การผูกมัดคือการเข้ารหัสxภายใต้แผนการเข้ารหัสแบบกุญแจสาธารณะที่มีความปลอดภัยทางความหมาย และมีความสมบูรณ์อย่างสมบูรณ์แบบ และการยกเลิกผูกมัดคือสตริงของบิตสุ่มที่ใช้ในการเข้ารหัส xตัวอย่างของแผนการผูกมัดที่ซ่อนข้อมูลตามทฤษฎีคือแผนการผูกมัดของ Pedersen ^{[ 18 ]}ซึ่งผูกมัดการคำนวณภายใต้สมมติฐานลอการิทึมแบบไม่ต่อเนื่อง ^{[ 19 ]} นอกจากแผนการข้างต้นแล้ว ยังใช้ตัวสร้างh อีกตัวหนึ่ง ของกลุ่มจำนวนเฉพาะและหมายเลขสุ่มrการผูกมัดถูกตั้งค่าไว้^{[ 20 ]}${\displaystyle c=g^{x}h^{r}}$

โครงสร้างเหล่านี้มีความเกี่ยวข้องอย่างใกล้ชิดและอิงตามคุณสมบัติทางพีชคณิตของกลุ่มพื้นฐาน และแนวคิดเดิมดูเหมือนจะเกี่ยวข้องกับพีชคณิตมาก อย่างไรก็ตาม ได้มีการแสดงให้เห็นว่าการวางกรอบการผูกมัดทางสถิติบนสมมติฐานทั่วไปที่ไม่มีโครงสร้างนั้นเป็นไปได้ ผ่านแนวคิดของการแฮชแบบโต้ตอบสำหรับการผูกมัดจากสมมติฐานความซับซ้อนทั่วไป (โดยเฉพาะและเดิมที อิงตามการเรียงสับเปลี่ยนทางเดียวใดๆ) ดังใน^{[ 21 ]}

อลิซเลือกโดยที่และเป็นจำนวนเฉพาะลับขนาดใหญ่ นอกจากนี้ เธอยังเลือกจำนวนเฉพาะโดยที่และอลิซจึงคำนวณจำนวนสาธารณะเป็นองค์ประกอบที่มีอันดับสูงสุดในกลุ่ม^{[ 22 ]}สุดท้าย อลิซยืนยันความลับของเธอโดยการสร้างตัวเลขสุ่มจาก ก่อน แล้วจึงคำนวณ ${\displaystyle N}$${\displaystyle N=p\cdot q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle e}$${\displaystyle e>N^{2}}$${\displaystyle gcd(e,\phi (N^{2}))=1}$${\displaystyle g_{m}}$${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$${\displaystyle m}$${\displaystyle r}$${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$${\displaystyle c=m^{e}g_{m}^{r}}$

ความปลอดภัยของคำมั่นสัญญาข้างต้นขึ้นอยู่กับความยากของปัญหา RSA และมีการซ่อนและการผูกมัดการคำนวณที่สมบูรณ์แบบ^{[ 23 ]}

แผนการผูกมัดของ Pedersen นำเสนอคุณสมบัติโฮโมมอร์ฟิกที่น่าสนใจ ซึ่งช่วยให้สามารถทำการบวกระหว่างการผูกมัดสองรายการได้ โดยเฉพาะอย่างยิ่ง เมื่อกำหนดข้อความสองข้อความและและค่าสุ่มและตามลำดับ สามารถสร้างการผูกมัดใหม่ได้ดังนี้: กล่าวอย่างเป็นทางการคือ: ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}$

${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}$

เพื่อเปิดข้อความใหม่ตามคำมั่นสัญญาของ Pedersen ข้างต้นจะต้องเพิ่ม ความสุ่ม เข้าไปด้วย${\displaystyle m_{1}+m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$

ในทำนองเดียวกัน การยืนยันแบบ RSA ที่กล่าวถึงข้างต้นมีคุณสมบัติแบบโฮโมมอร์ฟิกเมื่อเทียบกับการดำเนินการคูณ เมื่อมีข้อความสองข้อความและที่มีค่าสุ่มและตามลำดับ เราสามารถคำนวณได้ดังนี้: อย่างเป็นทางการคือ : ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$

ในการเปิดข้อผูกพันข้างต้นไปยังข้อความใหม่จะต้องเพิ่มความสุ่ม เข้าไปด้วย ข้อผูกพันที่สร้างขึ้นใหม่นี้จะถูกกระจายในลักษณะเดียวกับข้อผูกพันใหม่ไป ยัง ${\displaystyle m_{1}\cdot m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle m_{1}\cdot m_{2}}$

รูปแบบการรักษาความลับบางรูปแบบอนุญาตให้พิสูจน์ได้เพียงบางส่วนของค่าที่รักษาความลับไว้เท่านั้น ในรูปแบบเหล่านี้ ค่าลับจะเป็นเวกเตอร์ของค่าย่อยจำนวนมากที่สามารถแยกออกจากกันได้ ${\displaystyle X}$

${\displaystyle X=(x_{1},x_{2},...,x_{n})}$

การยืนยันจะถูกคำนวณจากในขั้นตอนการยืนยืนยัน โดยปกติแล้ว ในขั้นตอนการเปิดเผย ผู้พิสูจน์จะเปิดเผยข้อมูลทั้งหมดและข้อมูลการพิสูจน์เพิ่มเติมบางส่วน (เช่นในการยืนยืนยันแบบบิตอย่างง่าย ) แต่ผู้พิสูจน์สามารถเปิดเผยค่าใดค่าหนึ่งจากเวกเตอร์ และสร้างการพิสูจน์ที่มีประสิทธิภาพว่าองค์ประกอบที่ th ที่แท้จริงของเวกเตอร์ดั้งเดิมที่สร้างการยืนยันนั้นการพิสูจน์ไม่จำเป็นต้องเปิดเผยค่าอื่นใดของและเป็นไปไม่ได้ที่จะสร้างการพิสูจน์ที่ถูกต้องซึ่งเปิดเผยค่าที่แตกต่างกันสำหรับค่าใด ๆ ของนอกเหนือจากค่าที่แท้จริง^{[ 24 ]}${\displaystyle C}$${\displaystyle X}$${\displaystyle X}$${\displaystyle R}$${\displaystyle X}$${\displaystyle i}$${\displaystyle C}$${\displaystyle X}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$

การแฮชเวกเตอร์เป็นวิธีการเปิดเผยข้อมูลบางส่วนแบบง่ายๆ สำหรับการยืนยันเวกเตอร์ โดยอาศัยการยืนยันบิต ค่าต่างๆจะถูกเลือกแบบสุ่ม การยืนยันแต่ละรายการจะถูกสร้างขึ้นโดยการแฮชการยืนยันโดยรวมจะถูกคำนวณดังนี้ ${\displaystyle m_{1},m_{2},...m_{n}}$${\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}$

${\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}$

เพื่อพิสูจน์องค์ประกอบหนึ่งของเวกเตอร์ผู้พิสูจน์จะเปิดเผยค่าขององค์ประกอบนั้น ${\displaystyle X}$

${\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}$

ผู้ตรวจสอบสามารถคำนวณจากและจากนั้นจึงสามารถตรวจสอบได้ว่าแฮชของค่าทั้งหมดคือข้อผูกมัดน่าเสียดายที่การพิสูจน์นั้นมีขนาดและเวลาในการตรวจสอบมาก ในทางกลับกัน ถ้าคือเซตของค่าทั้งหมด ข้อผูกมัดจะมีขนาด และการพิสูจน์จะมีขนาดและเวลาในการตรวจสอบมาก ไม่ว่าในกรณีใด ข้อผูกมัดหรือการพิสูจน์จะแปรผันตามซึ่งไม่เหมาะสม ${\displaystyle y_{i}}$${\displaystyle x_{i}}$${\displaystyle m_{i}}$${\displaystyle y}$${\displaystyle C}$${\displaystyle O(n)}$${\displaystyle C}$${\displaystyle y}$${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

ตัวอย่างทั่วไปของแผนการเปิดเผยบางส่วนที่ใช้งานได้จริงคือMerkle treeซึ่งสร้างต้นไม้แฮชไบนารีขององค์ประกอบต่างๆแผนการนี้สร้างคำมั่นสัญญาที่มีขนาด และหลักฐานที่มีขนาดและเวลาในการตรวจสอบ แฮชรากของต้นไม้คือคำมั่นสัญญาเพื่อพิสูจน์ว่าสิ่งที่เปิดเผยเป็นส่วนหนึ่งของต้นไม้ดั้งเดิมจะต้องเปิดเผยเฉพาะค่าแฮชจากต้นไม้ หนึ่งค่าจากแต่ละระดับ เป็นหลักฐาน ผู้ตรวจสอบสามารถติดตามเส้นทางจากโหนดใบที่อ้างสิทธิ์ขึ้นไปจนถึงราก โดยแฮชโหนดพี่น้องในแต่ละระดับ และในที่สุดก็จะมาถึงค่าโหนดรากที่ต้องเท่ากับ^{[ 25 ]}${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(\log _{2}{n})}$${\displaystyle C}$${\displaystyle x_{i}}$${\displaystyle \log _{2}{n}}$${\displaystyle C}$

การยืนยันแบบ Kate–Zaverucha–Goldberg (KZG) ใช้การเข้ารหัสแบบจับคู่เพื่อสร้างแผนการเปิดเผยบางส่วนโดยมีขนาดการยืนยัน ขนาดการพิสูจน์ และเวลาในการตรวจสอบการพิสูจน์ กล่าวอีกนัยหนึ่งคือ เมื่อจำนวนค่าในเพิ่มขึ้น การยืนยันและการพิสูจน์จะไม่ใหญ่ขึ้น และการตรวจสอบการพิสูจน์จะไม่ใช้ความพยายามมากขึ้น ${\displaystyle O(1)}$${\displaystyle n}$${\displaystyle X}$

ข้อตกลง KZG ต้องการชุดพารามิเตอร์ที่กำหนดไว้ล่วงหน้าเพื่อสร้างการจับคู่และองค์ประกอบกับดักที่เชื่อถือได้ ตัวอย่างเช่นสามารถใช้การจับคู่แบบ Tate ได้ สมมติว่า เป็นกลุ่มบวก และเป็นกลุ่มคูณของการจับคู่ กล่าวอีกนัยหนึ่ง การจับคู่คือแผนที่ให้เป็นองค์ประกอบกับดัก (ถ้าเป็นอันดับเฉพาะของและ) และให้และเป็นตัวสร้างของและตามลำดับ ในส่วนของการตั้งค่าพารามิเตอร์ เราสมมติว่าและเป็นค่าที่ทราบและใช้ร่วมกันสำหรับค่าจำนวนเต็มบวกจำนวนมากของในขณะที่ค่ากับดักนั้นถูกละทิ้งและไม่มีใครทราบ ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}$${\displaystyle \mathbb {G} _{T}}$${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$${\displaystyle t\in \mathbb {F} _{p}}$${\displaystyle p}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G\cdot t^{i}}$${\displaystyle H\cdot t^{i}}$${\displaystyle i}$${\displaystyle t}$

การให้คำมั่นสัญญาแบบ KZG จะแปลงเวกเตอร์ของค่าที่จะให้คำมั่นสัญญาให้เป็นพหุนาม ขั้นแรก เราจะคำนวณพหุนาม เช่นนั้นสำหรับทุกค่าของในเวกเตอร์ของเราการประมาณค่าแบบลากรางจ์ช่วยให้เราสามารถคำนวณพหุนามนั้นได้ ${\displaystyle p(i)=x_{i}}$${\displaystyle x_{i}}$

${\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}$

ภายใต้สูตรนี้ พหุนามจะเข้ารหัสเวกเตอร์ โดยที่. ให้เป็นสัมประสิทธิ์ของโดยที่. การคำนวณความมุ่งมั่นทำได้ดังนี้ ${\displaystyle p(0)=x_{0},p(1)=x_{1},...}$${\displaystyle p_{0},p_{1},...,p_{n-1}}$${\displaystyle p}$${\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}$

${\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}$

การคำนวณนี้ทำได้ง่ายๆ โดยใช้ผลคูณดอทระหว่างค่าที่กำหนดไว้ล่วงหน้ากับสัมประสิทธิ์ของพหุนามเนื่องจากเป็นกลุ่มการบวกที่มีคุณสมบัติการสลับที่และการเชื่อมโยง ดังนั้นจึงเท่ากับเพราะการบวกและการคูณทั้งหมดกับสามารถกระจายออกไปจากการประเมินได้ เนื่องจากค่าของกับดักไม่เป็นที่รู้จัก การตัดสินใจจึงเป็นพหุนามที่ประเมินค่าที่จำนวนที่ไม่มีใครทราบ โดยผลลัพธ์ถูกซ่อนไว้ในองค์ประกอบที่ไม่โปร่งใสของ ${\displaystyle G\cdot t^{i}}$${\displaystyle p_{i}}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle C}$${\displaystyle G\cdot p(t)}$${\displaystyle G}$${\displaystyle t}$${\displaystyle C}$${\displaystyle \mathbb {G} _{1}}$

การพิสูจน์แบบ KZG ต้องแสดงให้เห็นว่าข้อมูลที่เปิดเผยนั้นเป็นค่าที่แท้จริงของเมื่อคำนวณค่า ให้ เป็นค่าที่เปิดเผยที่เราต้องพิสูจน์ เนื่องจากเวกเตอร์ของถูกแปลงเป็นพหุนาม เราจึงจำเป็นต้องพิสูจน์ว่าพหุนามเมื่อประเมินค่าที่ จะมีค่าเป็น กล่าวคือ เราเพียงแค่ต้องพิสูจน์ว่าเราจะทำเช่นนี้โดยการแสดงให้เห็นว่าการลบจากจะได้รากที่ กำหนดพหุนามเป็น ${\displaystyle x_{i}}$${\displaystyle C}$${\displaystyle y=x_{i}}$${\displaystyle x_{i}}$${\displaystyle p}$${\displaystyle i}$${\displaystyle y}$${\displaystyle p(i)=y}$${\displaystyle y}$${\displaystyle p}$${\displaystyle i}$${\displaystyle q}$

${\displaystyle q(x)={\frac {p(x)-y}{x-i}}}$

พหุนามนี้เป็นเครื่องพิสูจน์ว่าเพราะถ้ามีอยู่จริง ก็จะหารด้วยลงตัว ซึ่งหมายความว่ามีรากที่ดังนั้น(หรือกล่าวอีกนัยหนึ่งคือ) การพิสูจน์แบบ KZG จะแสดงให้เห็นว่ามีอยู่จริงและมีคุณสมบัตินี้ ${\displaystyle p(i)=y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$${\displaystyle i}$${\displaystyle p(i)-y=0}$${\displaystyle p(i)=y}$${\displaystyle q}$

ผู้พิสูจน์คำนวณโดยใช้การหารพหุนามข้างต้น จากนั้นจึงคำนวณค่าพิสูจน์ KZG${\displaystyle q}$${\displaystyle \pi }$

${\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}$

สิ่งนี้เท่ากับดังที่กล่าวมาข้างต้น กล่าวอีกนัยหนึ่ง ค่าพิสูจน์คือพหุนาม ที่ประเมิน ค่า อีกครั้งที่ค่าประตูที่ซ่อนอยู่ในตัวสร้างของ${\displaystyle G\cdot q(t)}$${\displaystyle q}$${\displaystyle t}$${\displaystyle G}$${\displaystyle \mathbb {G} _{1}}$

การคำนวณนี้จะเป็นไปได้ก็ต่อเมื่อพหุนามข้างต้นหารลงตัวเท่านั้น เพราะในกรณีนั้น ผลหารจะเป็นพหุนาม ไม่ใช่ฟังก์ชันตรรกยะเนื่องจากโครงสร้างของกับดัก ทำให้ไม่สามารถประเมินค่าฟังก์ชันตรรกยะที่ค่ากับดักได้ แต่สามารถประเมินค่าพหุนามโดยใช้การรวมเชิงเส้นของค่าคงที่ที่ทราบค่าที่คำนวณไว้ล่วงหน้าได้เท่านั้นนี่คือเหตุผลที่ทำให้ไม่สามารถสร้างบทพิสูจน์สำหรับค่าที่ไม่ถูกต้องของได้ ${\displaystyle q}$${\displaystyle G\cdot t^{i}}$${\displaystyle x_{i}}$

เพื่อตรวจสอบความถูกต้องของการพิสูจน์ จะใช้แผนที่เชิงเส้นคู่ของการจับคู่ เพื่อแสดงว่าค่าการพิสูจน์ สรุปเป็นพหุนามจริงที่แสดงคุณสมบัติที่ต้องการ ซึ่งก็คือหารลงตัวด้วยการคำนวณเพื่อตรวจสอบความถูกต้องจะตรวจสอบความเท่าเทียมกัน ${\displaystyle \pi }$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}$

โดยที่ฟังก์ชันแผนที่เชิงเส้นคู่ดังที่กล่าวมาข้างต้นเป็นค่าคงที่ที่คำนวณไว้ล่วงหน้า และคำนวณจาก ${\displaystyle e}$${\displaystyle H\cdot t}$${\displaystyle H\cdot i}$${\displaystyle i}$

โดยการเขียนการคำนวณใหม่ในกลุ่มการจับคู่แทนที่ด้วยและและให้เป็นฟังก์ชันช่วยในการยกขึ้นสู่กลุ่มการจับคู่ การตรวจสอบการพิสูจน์จึงชัดเจนยิ่งขึ้น ${\displaystyle \mathbb {G} _{T}}$${\displaystyle \pi =q(t)\cdot G}$${\displaystyle C=p(t)\cdot G}$${\displaystyle \tau (x)=e(G,H)^{x}}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}$

${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$

${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$

สมมติว่าแผนที่เชิงเส้นคู่ถูกสร้างขึ้นอย่างถูกต้อง สิ่งนี้แสดงให้เห็นว่าโดยที่ผู้ตรวจสอบไม่ทราบว่าหรือคืออะไร ผู้ตรวจสอบสามารถมั่นใจได้ในเรื่องนี้เพราะถ้าแล้วพหุนามจะประเมินค่าได้ผลลัพธ์เดียวกันที่ค่ากับดักสิ่งนี้แสดงให้เห็นว่าพหุนามนั้นเหมือนกัน เพราะถ้าพารามิเตอร์ถูกสร้างขึ้นอย่างถูกต้อง ค่ากับดักจะไม่เป็นที่รู้จักของใครเลย ซึ่งหมายความว่าการออกแบบพหุนามให้มีค่าเฉพาะที่กับดักนั้นเป็นไปไม่ได้ (ตามทฤษฎีบทของ Schwartz–Zippel ) ถ้าตอนนี้ได้รับการยืนยันว่าเป็นจริงแล้วก็ได้รับการยืนยันว่ามีอยู่จริง ดังนั้นจะต้องหารลงตัวด้วยพหุนามดังนั้นเนื่องจากทฤษฎีบทตัวประกอบสิ่งนี้พิสูจน์ได้ว่าค่าที่ ของเวกเตอร์ที่ผูกพันจะต้องเท่ากับเนื่องจากนั่นคือผลลัพธ์ของการประเมินพหุนามที่ผูกพันที่ ${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$${\displaystyle x=t}$${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle (x-i)}$${\displaystyle p(i)-y=0}$${\displaystyle i}$${\displaystyle y}$${\displaystyle i}$

นอกจากนี้ ความมุ่งมั่นของ KZG สามารถขยายเพื่อพิสูจน์ค่าของค่า ใดๆ ก็ได้ (ไม่ใช่แค่ค่าเดียว) โดยที่ขนาดของการพิสูจน์ยังคงอยู่แต่เวลาในการตรวจสอบการพิสูจน์จะแปรผันตามการพิสูจน์จะเหมือนกัน แต่แทนที่จะลบค่าคงที่เราจะลบพหุนามที่ทำให้เกิดรากหลายราก ในทุกตำแหน่งที่เราต้องการพิสูจน์ และแทนที่จะหารด้วยเราจะหารด้วยสำหรับตำแหน่งเดียวกันเหล่านั้น^{[ 26 ]}${\displaystyle k}$${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(k)}$${\displaystyle y}$${\displaystyle x-i}$${\textstyle \prod _{i}x-i}$

ในด้าน การเข้ารหัสควอนตัมคำถามที่น่าสนใจคือมี โปรโตคอลการยืนยันบิต ที่ปลอดภัยอย่างไม่มีเงื่อนไขในระดับควอนตัมหรือไม่ กล่าวคือ โปรโตคอลที่ (อย่างน้อยในเชิงอะซิมโทติก) สามารถผูกมัดและปกปิดข้อมูลได้ แม้ว่าจะไม่มีข้อจำกัดด้านทรัพยากรการคำนวณก็ตาม เราอาจหวังว่าจะมีวิธีที่จะใช้ประโยชน์จากคุณสมบัติที่แท้จริงของกลศาสตร์ควอนตัมเช่นเดียวกับในโปรโตคอลสำหรับการแจกจ่ายกุญแจที่ปลอดภัยอย่างไม่มีเงื่อนไข

อย่างไรก็ตาม สิ่งนี้เป็นไปไม่ได้ ดังที่โดมินิก เมเยอร์สได้แสดงให้เห็นในปี 1996 โปรโตคอลใดๆ ก็ตามสามารถลดทอนลงเหลือโปรโตคอลที่ระบบอยู่ในสถานะบริสุทธิ์ 1 ใน 2 สถานะหลังจากขั้นตอนการยืนยัน ขึ้นอยู่กับบิตที่อลิซต้องการยืนยัน หากโปรโตคอลนั้นปกปิดอย่างไม่มีเงื่อนไข อลิซสามารถแปลงสถานะเหล่านี้ไปเป็นอีกสถานะหนึ่งได้โดยใช้คุณสมบัติของการแยกส่วนของชมิดท์ซึ่งเป็นการทำลายคุณสมบัติการผูกมัดอย่างมีประสิทธิภาพ

ข้อสมมติฐานที่แฝงนัยประการหนึ่งของการพิสูจน์คือ ขั้นตอนการคอมมิตจะต้องเสร็จสิ้น ณ จุดใดจุดหนึ่งในเวลา ซึ่งเปิดโอกาสให้โปรโตคอลที่ต้องการการไหลของข้อมูลอย่างต่อเนื่องจนกว่าบิตจะถูกเปิดเผยหรือโปรโตคอลถูกยกเลิก ซึ่งในกรณีนี้จะไม่มีผลผูกพันอีกต่อไป^{[ 28 ]}โดยทั่วไปแล้ว การพิสูจน์ของ Mayers ใช้ได้เฉพาะกับโปรโตคอลที่ใช้ประโยชน์จากฟิสิกส์ควอนตัมแต่ไม่ใช่ทฤษฎีสัมพัทธภาพพิเศษ Kent ได้แสดงให้เห็นว่ามีโปรโตคอลที่ปลอดภัยอย่างไม่มีเงื่อนไขสำหรับการคอมมิตบิตที่ใช้ประโยชน์จากหลักการของทฤษฎีสัมพัทธภาพพิเศษที่ระบุว่าข้อมูลไม่สามารถเดินทางได้เร็วกว่าแสง^{[ 29 ]}

ฟังก์ชันที่ไม่สามารถลอกเลียนแบบได้ทางกายภาพ (PUF) อาศัยการใช้คีย์ทางกายภาพที่มีความสุ่มภายใน ซึ่งยากต่อการลอกเลียนแบบหรือจำลอง ฟังก์ชัน PUF ประเภทอิเล็กทรอนิกส์ ออปติคอล และประเภทอื่นๆ^{[ 30 ]}ได้รับการกล่าวถึงอย่างกว้างขวางในเอกสารทางวิชาการ โดยเชื่อมโยงกับแอปพลิเคชันการเข้ารหัสที่มีศักยภาพ รวมถึงแผนการผูกมัด^{[ 31 ] [ 32 ]}

• การโอนที่ไม่รู้ตัว
• ตัวสะสม (การเข้ารหัส)
• งานลงนามกุญแจ
• เครือข่ายแห่งความไว้วางใจ
• ซีโร่คอยน์
• อนาแกรม — คำที่นักปรัชญาธรรมชาติในศตวรรษที่ 17 ใช้เพื่อพิสูจน์ความเป็นเจ้าของผลงานค้นพบโดยไม่ต้องเปิดเผยให้ผู้อื่นทราบ

• ความมุ่งมั่นเกี่ยวกับบิตควอนตัมบน arxiv.org
• Kate-Zaverucha-Goldberg (KZG) ข้อผูกมัดพหุนามขนาดคงที่ - Alin Tomescu
• ข้อผูกพันพหุนามเคท