ลองนึกภาพว่าคุณมีความรู้ที่เป็นประโยชน์ — อาจเป็นสูตรลับหรือกุญแจสู่รหัส คุณช่วยพิสูจน์ให้เพื่อนรู้ว่าคุณมีความรู้นั้นโดยไม่เปิดเผยอะไรไหม นักวิทยาศาสตร์คอมพิวเตอร์ได้พิสูจน์เมื่อ 30 ปีที่แล้วว่าคุณทำได้ ถ้าคุณใช้สิ่งที่เรียกว่าการพิสูจน์ความรู้เป็นศูนย์
สำหรับวิธีง่ายๆ ในการทำความเข้าใจแนวคิดนี้ สมมติว่าคุณต้องการแสดงให้เพื่อนเห็นว่าคุณรู้วิธีผ่านเขาวงกตโดยไม่เปิดเผยรายละเอียดเกี่ยวกับเส้นทาง คุณสามารถสำรวจเขาวงกตได้ภายในเวลาที่กำหนด ในขณะที่เพื่อนของคุณถูกห้ามไม่ให้ดู (การจำกัดเวลาเป็นสิ่งที่จำเป็น เพราะหากให้เวลาเพียงพอ ทุกคนสามารถหาทางออกผ่านการลองผิดลองถูกได้ในที่สุด) เพื่อนของคุณจะรู้ว่าคุณทำได้ แต่พวกเขาจะไม่รู้ว่าต้องทำอย่างไร
การพิสูจน์ความรู้ที่เป็นศูนย์นั้นมีประโยชน์สำหรับนักเข้ารหัสที่ทำงานด้วยข้อมูลลับ แต่ยังรวมถึงนักวิจัยด้านความซับซ้อนในการคำนวณด้วย ซึ่งเกี่ยวข้องกับการจำแนกความยากของปัญหาต่างๆ “วิทยาการเข้ารหัสลับสมัยใหม่จำนวนมากอาศัยสมมติฐานที่ซับซ้อน — บนสมมติฐานที่ว่าปัญหาบางอย่างแก้ไขได้ยาก ดังนั้นจึงมีความเชื่อมโยงระหว่างสองโลกอยู่เสมอ” กล่าว Claude Crepeauนักวิทยาศาสตร์คอมพิวเตอร์ที่มหาวิทยาลัยแมคกิลล์ “แต่หลักฐาน [เหล่านี้] ได้สร้างโลกแห่งการเชื่อมต่อ”
การพิสูจน์ความรู้ที่เป็นศูนย์อยู่ในหมวดหมู่ที่เรียกว่าการพิสูจน์เชิงโต้ตอบ ดังนั้นเพื่อเรียนรู้วิธีการทำงานแบบเดิม จะช่วยให้เข้าใจอย่างหลัง อันดับแรก อธิบาย ในกระดาษปี 1985 โดยนักวิทยาศาสตร์คอมพิวเตอร์ ชาฟิโกลด์วาสเซอร์Silvio Micali และ Charles Rackoff การพิสูจน์เชิงโต้ตอบทำงานเหมือนการสอบสวน: ในชุดข้อความ ฝ่ายหนึ่ง (ผู้พิสูจน์) พยายามโน้มน้าวให้อีกฝ่ายหนึ่ง (ผู้ตรวจสอบยืนยัน) ว่าข้อความที่ให้มานั้นเป็นความจริง หลักฐานเชิงโต้ตอบต้องเป็นไปตามคุณสมบัติสองประการ ประการแรก ถ้อยแถลงที่แท้จริงจะโน้มน้าวใจผู้ตรวจสอบที่ซื่อสัตย์ในที่สุด ประการที่สอง หากข้อความที่ระบุเป็นเท็จ ไม่มีผู้พิสูจน์ แม้แต่คนที่แสร้งทำเป็นมีความรู้บางอย่าง สามารถโน้มน้าวผู้ตรวจสอบได้ ยกเว้นด้วยความน่าจะเป็นเพียงเล็กน้อย
หลักฐานเชิงโต้ตอบมีความน่าจะเป็นในธรรมชาติ ผู้พิสูจน์สามารถตอบคำถามหนึ่งหรือสองข้อได้อย่างถูกต้องโดยบังเอิญ ดังนั้นจึงต้องใช้ความท้าทายจำนวนมากพอสมควร ซึ่งทั้งหมดนั้นผู้พิสูจน์จะต้องทำให้ถูกต้อง เพื่อให้ผู้ตรวจสอบมั่นใจว่าผู้พิสูจน์ทราบโดยที่จริงแล้วรู้ว่าข้อความนั้นเป็นความจริง
แนวคิดเรื่องการโต้ตอบนี้เกิดขึ้นเมื่อ Micali และ Goldwasser ซึ่งเป็นนักศึกษาระดับบัณฑิตศึกษาที่ University of California, Berkeley งงกับการเล่นโป๊กเกอร์ผ่านเครือข่าย ผู้เล่นทุกคนจะตรวจสอบได้อย่างไรว่าเมื่อหนึ่งในนั้นได้รับการ์ดจากเด็คเสมือนจริง ผลลัพธ์จะเป็นแบบสุ่ม? หลักฐานเชิงโต้ตอบสามารถนำทางได้ แต่แล้วผู้เล่นจะตรวจสอบได้อย่างไรว่าโปรโตคอลทั้งหมด - กฎครบชุด - ปฏิบัติตามอย่างถูกต้องโดยไม่เปิดเผยมือของผู้เล่นทุกคนตลอดทาง?
เพื่อให้บรรลุเป้าหมายนี้ Micali และ Goldwasser ได้เพิ่มคุณสมบัติที่สามให้กับทั้งสองที่จำเป็นสำหรับการพิสูจน์เชิงโต้ตอบ: การพิสูจน์ไม่ควรเปิดเผยสิ่งใดเกี่ยวกับความรู้ของตัวเอง เฉพาะความจริงของข้อความเท่านั้น “มีแนวคิดในการดำเนินการตามขั้นตอน ซึ่งในตอนท้ายคุณเชื่อว่า [ผู้เล่นโป๊กเกอร์] ไม่รู้อะไรมากไปกว่าสิ่งที่พวกเขาควรจะรู้” Goldwasser กล่าว
ลองพิจารณาตัวอย่างคลาสสิก อลิซต้องการพิสูจน์ให้บ๊อบเห็นกราฟบางอย่าง G - คอลเล็กชันจุดยอด (จุด) ที่ไม่ซ้ำกันซึ่งเชื่อมต่อกันด้วยขอบ (เส้น) - มี "วัฏจักรฮามิลโทเนียน" ซึ่งหมายความว่ากราฟมีเส้นทางที่เข้าชมทุกจุดเพียงครั้งเดียวและสิ้นสุดที่จุดเดิม อลิซสามารถทำได้โดยเพียงแค่แสดงให้บ็อบเห็นเส้นทางที่ทำสิ่งนี้ แต่แน่นอนว่าเขาก็ต้องรู้จักเส้นทางนั้นด้วย
อลิซสามารถโน้มน้าวให้ Bob เชื่อว่าเธอรู้ว่าเส้นทางนั้นมีอยู่จริง โดยไม่ต้องแสดงให้เขาเห็น อันดับแรก เธอวาดกราฟใหม่ H, ที่ดูไม่เหมือน G แต่มีความคล้ายคลึงกันอย่างมาก: มีจุดยอดเท่ากัน เชื่อมต่อในลักษณะเดียวกัน (ถ้า G มีวัฏจักรแฮมิลตันจริงๆ ความคล้ายคลึงนี้หมายถึง H ก็เช่นกัน) จากนั้นหลังจากครอบคลุมทุกขอบใน H ด้วยเทปกาวเธอล็อค H ในกล่องและมอบกล่องให้บ๊อบ สิ่งนี้ป้องกันไม่ให้เขาเห็นมันโดยตรง แต่ยังป้องกันไม่ให้เธอแก้ไข จากนั้นบ็อบก็เลือก: ไม่ว่าเขาจะขอให้อลิซแสดงให้เห็นว่า H คล้ายกับ .จริงๆ Gหรือเขาอาจขอให้เธอแสดงวงจรแฮมิลตันให้เขาดูใน H. คำขอทั้งสองน่าจะง่ายสำหรับอลิซ สมมติว่า H คล้ายกันมากพอ Gและเธอรู้เส้นทางจริงๆ
แน่นอน แม้ว่าอลิซจะไม่รู้จักวัฏจักรของแฮมิลตันใน Gเธอสามารถลองหลอกบ๊อบได้ด้วยการวาดกราฟที่ไม่เหมือนกับ Gหรือโดยการส่งกราฟที่เธอไม่ทราบเส้นทาง แต่หลังจากที่พวกเขาเล่นมาหลายรอบแล้ว โอกาสที่อลิซจะหลอกบ๊อบทุกครั้งก็น้อยลงเรื่อยๆ ถ้าเธอทำทุกอย่างถูกต้อง ในที่สุด Bob ก็จะเชื่อว่า Alice รู้วงจร Hamiltonian ในกราฟ Gโดยที่บ๊อบไม่เคยเห็นมัน
หลังจากรายงานฉบับแรกที่อธิบายการพิสูจน์ดังกล่าว มิคาลีและนักคณิตศาสตร์สองคนคือ Oded Goldreich และ Avi Wigderson ได้ค้นพบผลลัพธ์ที่คาดไม่ถึงด้วยผลกระทบในวงกว้าง มันเกี่ยวข้องกับปัญหาหลัก ๆ ที่มีความยากพอ ๆ กันซึ่งเรียกว่า NP ปัญหาเหล่านี้แก้ไขได้ยาก แต่วิธีแก้ปัญหานั้นง่ายต่อการตรวจสอบ นักวิจัยทั้งสาม พบว่า, ถ้าเข้ารหัสได้อย่างปลอดภัยจริง ๆ เป็นไปได้จากนั้นวิธีแก้ไขทุกปัญหาใน NP ก็สามารถพิสูจน์ได้ด้วยหลักฐานที่ไม่มีความรู้ การศึกษานี้ช่วยนักวิจัย คิดของ การพิสูจน์ความรู้ที่เป็นศูนย์รูปแบบต่างๆ ที่ไม่ต้องการการเข้ารหัสที่ปลอดภัยตั้งแต่แรก สิ่งเหล่านี้เรียกว่าการพิสูจน์เชิงโต้ตอบหลายผู้พิสูจน์
และในปี 1988 มิคาลิและคนอื่นๆ แสดงให้เห็นว่า ว่าถ้าผู้พิสูจน์และผู้ตรวจสอบใช้สตริงสั้นๆ ของบิตสุ่ม ไม่จำเป็นต้องมีปฏิสัมพันธ์ ในทางทฤษฎีหมายความว่าการพิสูจน์ความรู้ที่เป็นศูนย์ไม่จำเป็นต้องมีการโต้ตอบ ซึ่งหมายความว่าไม่จำเป็นต้องมีการสื่อสารระหว่างสองฝ่ายอย่างต่อเนื่อง สิ่งนี้จะทำให้พวกเขามีประโยชน์มากขึ้นสำหรับนักวิจัย แต่หลังจากช่วงเปลี่ยนศตวรรษที่ 21 การพิสูจน์ดังกล่าวก็เริ่มขึ้น
“ในช่วงปลายทศวรรษ 2000 เราเริ่มเห็นวิวัฒนาการของเทคนิคที่มีประสิทธิภาพสำหรับการสร้างการพิสูจน์ที่ไม่มีความรู้” กล่าว แมทธิว ดี. กรีน, นักเข้ารหัสที่ John Hopkins University “เรามาถึงจุดที่เราตระหนักว่า 'เดี๋ยวก่อน จริงๆ แล้วอาจมีวิธีใช้สิ่งนี้ในทางปฏิบัติ'”
ตอนนี้ผู้พิสูจน์สามารถส่งข้อความเดียวไปยังผู้ตรวจสอบโดยที่ทั้งคู่ไม่ต้องออนไลน์ และนักวิจัยสามารถสร้างหลักฐานสั้นๆ ที่สามารถตรวจสอบได้อย่างรวดเร็ว แม้กระทั่งสำหรับปัญหาที่ซับซ้อนมาก สิ่งนี้นำไปสู่การใช้งานจริงหลายประการ เช่น ความสามารถในการตรวจสอบบล็อคเชนอย่างรวดเร็วหลังจากธุรกรรมสกุลเงินดิจิทัล ในขณะที่ซ่อนรายละเอียดของธุรกรรม และในปี 2016 กลุ่มนักฟิสิกส์ แสดงให้เห็นว่า การพิสูจน์ความรู้ที่เป็นศูนย์สามารถช่วยในการลดอาวุธนิวเคลียร์ได้อย่างไร: โดยไม่ต้องเปิดเผยความลับใด ๆ เกี่ยวกับการออกแบบหัวรบนิวเคลียร์ ประเทศสามารถพิสูจน์ให้ผู้ตรวจสอบนิวเคลียร์ทราบว่าหัวรบมีการใช้งานหรือไม่ทำงาน
ไม่นานมานี้ ความก้าวหน้าในการคำนวณควอนตัมได้บังคับให้ Crépeau ต้องทำการทดสอบความเครียดในงานวิจัยที่ผ่านมา เพื่อให้แน่ใจว่าโปรโตคอลที่ไม่มีความรู้นั้นยังคงใช้งานได้ ในปี 2021 เขาช่วย สาธิต ว่าการพิสูจน์เชิงโต้ตอบหลายผู้พิสูจน์จะเก็บเป็นความลับแม้ในขณะที่คอมพิวเตอร์ควอนตัมมีส่วนเกี่ยวข้อง แต่การได้รับความปลอดภัยในระดับเดียวกันทำให้โปรโตคอลช้าลงมาก การค้นพบนี้เป็นข่าวดี แต่ความกังวลใหม่จะเกิดขึ้นเมื่อเทคโนโลยีก้าวหน้า
“การคำนวณทุกประเภทที่เราสามารถทำได้ในอนาคตจะเกี่ยวข้องกับคอมพิวเตอร์ควอนตัม” เครโปกล่าว “ดังนั้น ในฐานะนักเข้ารหัสลับที่หวาดระแวง เมื่อใดก็ตามที่เราประเมินความปลอดภัยของระบบ เราต้องการให้แน่ใจว่าระบบของเราปลอดภัย”
หมายเหตุบรรณาธิการ: Shafi Goldwasser ได้รับเงินทุนจากมูลนิธิ Simons ซึ่งให้ทุนนี้ด้วย สิ่งพิมพ์อิสระด้านบรรณาธิการ. การตัดสินใจระดมทุนของมูลนิธิ Simons ไม่มีอิทธิพลต่อการรายงานข่าวของเรา
