บทความนี้มาจากบทความนี้มาจากAmbi Laboratory (รหัส: SECBIT)
ผู้เขียน Guo Yu ทำซ้ำโดย Odaily โดยได้รับอนุญาต
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
บทความนี้ได้รับการอัปเดตเป็น Github
"ความท้าทายเป็นเครื่องบ่งชี้ถึงความไว้วางใจของพระเจ้าในตัวคุณ" บางครั้งความท้าทายเป็นเครื่องบ่งชี้ถึงความไว้วางใจของพระเจ้าในตัวคุณ ― ดี. ท็อดด์ คริสทอฟเฟอร์สัน
ชุดที่ 1 ทำความรู้จัก "Zero Knowledge" และ "Proof"
ชุดที่ 2 ทำความเข้าใจ "สถานการณ์จำลอง"
ชุดที่ 3 การค้นหา "ความรู้"
ปฏิสัมพันธ์และความท้าทาย
ระบบพิสูจน์ความรู้ที่ไม่มีความรู้ที่เราแนะนำก่อนหน้านี้ทั้งหมดเป็นแบบ "โต้ตอบ" ซึ่งกำหนดให้ผู้ตรวจสอบ Bob ระบุ "ตัวเลขสุ่ม" หนึ่งหรือหลายตัวเพื่อท้าทายระหว่างการโต้ตอบ เช่น "ปัญหาแผนที่สามสี" (ดู "ชุดที่ 2" ) ผู้ตรวจสอบ Bob จำเป็นต้อง "สุ่ม" สุ่มเลือกข้างเพื่อท้าทายคำตอบของ Alice จนกว่า Bob จะพอใจ และความน่าจะเป็นในการโกงของ Alice จะลดลง "อย่างทวีคูณ" และ "พื้นฐาน" ที่ Bob เชื่อในการพิสูจน์นั้นขึ้นอยู่กับว่าหมายเลขสุ่มที่ Bob เลือกนั้นสุ่มเพียงพอหรือไม่ หากอลิซสามารถทำนายจำนวนสุ่มของบ็อบได้ล่วงหน้า หายนะจะเกิดขึ้น โลกแห่งความเป็นจริงจะเสื่อมโทรมลงเป็น "โลกในอุดมคติ" และอลิซสามารถอัปเกรดเป็น "เครื่องจำลอง" ได้ทันทีเพื่อหลอกบ็อบผ่านพลังวิเศษ
ใน "ซีรีส์ 3" เราได้วิเคราะห์โปรโตคอล Schnorr ในโปรโตคอล แม้ว่า Bob ผู้ตรวจสอบจะต้องเลือกหมายเลขสุ่ม c เพื่อท้าทายอลิซและขอให้เธอคำนวณค่า z แต่ Bob จะต้องไม่ให้อลิซมีความสามารถในการทำนาย ค่าของ c ความรู้ใด ๆ มิฉะนั้นอลิซจะเปลี่ยนเป็นตัวจำลอง
ความสำคัญของตัวเลขสุ่มนั้นชัดเจนในตัวเอง:
การสุ่มตัวเลขเป็น "รากฐานของความไว้วางใจ" สำหรับการพิสูจน์แบบโต้ตอบที่ไม่มีความรู้
อย่างไรก็ตาม "กระบวนการโต้ตอบ" จะจำกัดสถานการณ์ของแอปพลิเคชัน จะเกิดอะไรขึ้นหากการพิสูจน์ความรู้ที่ไม่มีความรู้เชิงโต้ตอบสามารถเปลี่ยนเป็น "ไม่โต้ตอบ" ได้ มันจะน่าตื่นเต้นมาก สิ่งที่เรียกว่าการไม่โต้ตอบสามารถถือเป็นกระบวนการพิสูจน์แบบ "รอบเดียว" นั่นคืออลิซส่งหลักฐานให้บ็อบตรวจสอบโดยตรง
Non-interactive zero-knowledge Proof ภาษาอังกฤษคือ Non-Interactive Zero Knowledge หรือเรียกสั้นๆ ว่า NIZK หมายความว่าหลักฐานทั้งหมดจะถูกเข้ารหัสเป็น "สตริง" ซึ่งสามารถเขียนลงบนกระดาษและส่งไปยังผู้ตรวจสอบตามต้องการด้วยวิธีการต่างๆ เช่น อีเมลและเครื่องมือแชท สตริงสามารถวางบน Github ได้สำหรับทุกคน เพื่อดาวน์โหลดได้ตลอดเวลาตรวจสอบ
ในโลกของบล็อกเชน "NIZK" สามารถใช้เป็นส่วนหนึ่งของระเบียบการฉันทามติได้ เนื่องจากธุรกรรมต้องใช้ผู้ขุดหลายคนในการตรวจสอบ ลองนึกภาพ หากผู้ส่งธุรกรรมและนักขุดแต่ละคนต้องโต้ตอบและปล่อยให้นักขุดท้าทาย กระบวนการที่เป็นเอกฉันท์จะช้ามาก การพิสูจน์ความรู้เป็นศูนย์แบบไม่โต้ตอบสามารถถ่ายทอดโดยตรงไปยังโหนดขุดทั้งหมด ทำให้สามารถตรวจสอบตัวเองได้
เพื่อนบางคนอาจถามว่า: ท้าทายนักขุดเพียงคนเดียวไม่พอหรือ? เข้ารหัสสคริปต์การโต้ตอบระหว่างนักขุดและผู้ส่งธุรกรรมเป็นหลักฐาน จากนั้นเผยแพร่ไปยังนักขุดรายอื่น จากนั้นนักขุดรายอื่นจะเชื่อโดยตรงว่ากระบวนการท้าทายนั้นน่าเชื่อถือ เป็นไปได้ไหม อย่างไรก็ตาม เป็นที่ชัดเจนว่าเครื่องขุดแบบโต้ตอบเครื่องแรกจำเป็นต้องได้รับความไว้วางใจในฐานะบุคคลที่สามที่เชื่อถือได้ บุคคลที่สาม? ดูไม่เป็นความคิดที่ดี...
เราจะพูดว่า "NIZK" ด้านล่างโดยตรง แทนที่จะเป็นการพิสูจน์แบบโต้ตอบที่ไม่มีความรู้เป็นศูนย์ ซึ่งดูเหมาะสมที่สุด และไม่มีบุคคลที่สามที่จะสร้างความแตกต่าง
ความสับสนที่เกิดจากการ "ไม่โต้ตอบ"
การพิสูจน์ความรู้เป็นศูนย์แบบไม่โต้ตอบ NIZK หากมีอยู่ มีประสิทธิภาพมากกว่าการพิสูจน์แบบโต้ตอบ
การพิสูจน์เชิงโต้ตอบสามารถเชื่อถือได้โดยผู้ตรวจสอบเพียงคนเดียว ในขณะที่ NIZK สามารถเชื่อถือได้โดยผู้ตรวจสอบหลายคน แม้แต่ทุกคน
หลักฐานเชิงโต้ตอบสามารถใช้ได้ในขณะที่โต้ตอบเท่านั้น ในขณะที่ NIZK จะใช้ได้ตลอด
NIZK ไม่เพียงขยายพื้นที่ แต่ยังขยายเวลาได้อีกด้วย
ฟังดูสวยงามใช่ไหม แต่,……
ทำซ้ำข้อสรุปจากส่วนก่อนหน้า:
การสุ่มตัวเลขเป็น "รากฐานของความไว้วางใจ" สำหรับการพิสูจน์แบบโต้ตอบที่ไม่มีความรู้
แต่ถ้า NIZK แพ้กระบวนการท้าทาย ผลที่ตามมาคืออะไร?
เราได้เรียกคืนการพิสูจน์แบบ "zero-knowledge" แล้ว (อ้างอิงจาก "ชุดที่ 2") กระบวนการพิสูจน์จำเป็นต้องสร้างเครื่องจำลอง (อัลกอริทึม) ซึ่งโต้ตอบกับผู้ตรวจสอบ (Bob) ในโลกอุดมคติด้วย และ Bob ผู้ตรวจสอบ ไม่มีความสามารถในการแยกแยะว่าอีกฝ่ายเป็นอลิซตัวจริงหรือตัวจำลอง
หากตอนนี้คุณพิจารณาถึงการไม่โต้ตอบใน NIZK ถ้า "ฉัน" แสดงให้คุณเห็นแผ่นกระดาษที่มีหลักฐาน X เขียนอยู่ "จริง" และถ้า "คุณ" เชื่อฉันจริงๆ หลังจากอ่านบทความนี้ และเนื่องจาก โปรโตคอลคือ "ความรู้เป็นศูนย์" ดังนั้นหาก "ฉัน" ถูกแทนที่ด้วยเครื่องมือจำลอง เครื่องมือจำลองยังสามารถ "ปลอมแปลง" หลักฐานเท็จ Y ซึ่งสามารถโน้มน้าวใจ "คุณ" ได้เช่นกัน
ตกลง นี่คือปัญหา:
คุณจะแยกความแตกต่างระหว่าง X และ Y ว่าอะไรจริงและเท็จได้อย่างไร แน่นอนว่าคุณไม่สามารถบอกความแตกต่างได้ เนื่องจากโปรโตคอลไม่มีความรู้ คุณจึงต้องไม่สามารถบอกความแตกต่างได้
ฉันสามารถแสดง Y ให้คุณเห็นได้ หมายความว่า "ฉัน" หลอกคุณไม่ได้เหรอ?
ไม่ปรองดองกัน? โปรดคิดสองนาทีที่นี่
(สองนาทีต่อมา...)
เนื่องจาก NIZK ไม่มีการโต้ตอบ ไม่มีกระบวนการท้าทาย กระบวนการพิสูจน์ทั้งหมดให้อลิซคำนวณและเขียน ตามทฤษฎีแล้ว อลิซสามารถเขียนอะไรก็ได้ที่เธอต้องการ และไม่มีใครหยุดเธอได้ ตัวอย่างเช่น อลิซเขียนว่า "โลกในอุดมคติ" เป็นเท็จ หลักฐานของวาย
สันนิษฐานว่า เพื่อนๆ ที่มีความเข้าใจอย่างลึกซึ้งเกี่ยวกับตัวจำลองจะพบประเด็นสำคัญที่นี่: ตัวจำลองจะต้องสร้าง Y ใน "โลกแห่งอุดมคติ" เท่านั้น กล่าวคือ สิ่งที่ชั่วร้ายอย่าง Y สามารถดำรงอยู่ได้ใน "โลกแห่งอุดมคติ" เท่านั้น และไปไม่ถึง "โลกแห่งความจริง" คือหายนะของโลก
คิดต่อไป...
นอกจากนี้ยังมีปัญหาที่ลึกกว่านั้น โปรดนึกถึง "ปัญหาแผนที่สามสี" สาเหตุหลักที่ตัวจำลองไม่สามารถทำสิ่งชั่วร้ายใน "โลกแห่งความจริง" ได้เพราะเขามีพลังวิเศษในการ "ย้อนเวลา" ในโลกอุดมคติ และ ใน "โลกแห่งความจริง" ไม่มีมนต์ดำเช่นนั้น "ความไม่มีอยู่จริง" ของโลกแห่งความจริงคือกุญแจสำคัญ
ยิ่งกว่านั้น NIZK ไม่มีการโต้ตอบซึ่งนำไปสู่ผลลัพธ์ที่ร้ายแรง Simulator ไม่มีทางที่จะใช้มหาอำนาจของ "rewinding time" และแน่นอนว่ามันไม่สามารถแยกแยะพฤติกรรมของผู้พิสูจน์ในสองโลกได้
กล่าวอีกนัยหนึ่งหากเราเผชิญกับระบบ NIZK ใด ๆ ดูเหมือนว่า "ตัวจำลอง" นั้นยากที่จะยืนเหนือพื้นดูเหมือนว่ามันจะตกลงสู่โลกและกลายเป็นมนุษย์ธรรมดาเท่านั้น ถ้าฉันบอกว่า ถ้าตามการอนุมานนี้ สมมติว่าตัวจำลองไม่มีพลังพิเศษอีกต่อไป หมายความว่าอลิซกับตัวจำลองไม่ต่างกัน อลิซสามารถกลายเป็นตัวจำลองได้ แล้วอนุมานต่อไป อลิซสามารถอยู่ใน " ในโลกแห่งความจริง" หากบ็อบถูกหลอกโดยพลการในกระบวนการนี้ ระบบพิสูจน์หลักฐานนี้ก็ไม่มีประโยชน์อีกต่อไป เพราะระบบจะสูญเสีย "ความน่าเชื่อถือ" ไป สรุป: NIZK ใด ๆ ไม่น่าเชื่อถือ
ต้องมีบางอย่างผิดปกติที่นี่ ...
ในกระบวนการวิเคราะห์ข้างต้น เราได้กล่าวถึงการขาดความท้าทายเชิงโต้ตอบ แท้จริงแล้ว หากบ็อบไม่มีส่วนร่วมในกระบวนการสร้างหลักฐานของอลิซ ทุกส่วนในหลักฐานนั้นมาจากอลิซเอง และดูเหมือนว่า "หลักฐาน" เองนั้นไม่มี "ต้นตอ" ใดๆ ให้บ็อบเชื่อถือ สิ่งนี้ดูเหมือนจะไม่สมเหตุสมผล "โดยสัญชาตญาณ"
หมายความว่าหากปราศจากการมีส่วนร่วมของบ็อบ ก็ไม่มีทาง "สมบูรณ์" ที่จะสร้าง "รากเหง้าแห่งความไว้วางใจ" ได้ใช่หรือไม่ รากฐานของความไว้วางใจสามารถมาจากไหนได้อีก?
คำตอบคือ "มือที่สาม"!
เดี๋ยวก่อน... มีเพียงสองฝ่ายในการโต้ตอบของโปรโตคอลไม่ใช่หรือ อลิซกับบ็อบ มือที่สามอยู่ที่ไหน?
ต้องแนะนำบุคคลภายนอกด้วยวิธีพิเศษและมีมากกว่า 1 วิธี ลองศึกษาวิธีแรกก่อน
(น้ำตา: พูดไม่ดี เราไม่แนะนำมือที่สาม?)
การทบทวนโปรโตคอล Schnorr
มาดูเพื่อนเก่าของเรากัน—โปรโตคอล Schnorr ซึ่งเป็นโปรโตคอลสามขั้นตอน: ในขั้นตอนแรก อลิซส่งคำสัญญา จากนั้นในขั้นตอนที่สอง บ็อบส่งคำท้าเป็นตัวเลขสุ่ม และในขั้นตอนที่สาม อลิซ ตอบสนองต่อความท้าทาย
มาดูวิธีเปลี่ยนโปรโตคอล Schnorr สามขั้นตอนเป็นขั้นตอนเดียว
c = Hash(PK, R)
ดูขั้นตอนที่สองของโปรโตคอล Schnorr Bob ต้องให้หมายเลขการท้าทายแบบสุ่ม c ที่นี่เราสามารถให้อลิซใช้สูตรต่อไปนี้เพื่อคำนวณหมายเลขการท้าทายเพื่อให้บรรลุวัตถุประสงค์ในการกำจัดขั้นตอนที่สองของโปรโตคอล
โดยที่ R คือจุดโค้งวงรีที่อลิซส่งให้บ็อบ และ PK คือคีย์สาธารณะ คุณสามารถดูสูตรนี้สำหรับการคำนวณ c โดยใช้อัลกอริทึมแฮช สูตรนี้มีจุดประสงค์สองประการ:
ก่อนที่อลิซจะสร้างความมุ่งมั่น R ไม่มีทางที่จะทำนาย c ได้ แม้ว่าในที่สุดอลิซจะปลอมตัวมาเลือก c ก็ตาม
c คำนวณโดยฟังก์ชันแฮช มันจะถูกกระจายอย่างเท่าๆ กันในฟิลด์จำนวนเต็ม และสามารถใช้เป็นตัวเลขสุ่มได้ (หมายเหตุ: โปรดเข้าใจสิ่งนี้ในตอนนี้ เราจะพูดถึงในเชิงลึกในภายหลัง)
โปรดทราบ: อลิซไม่สามารถทำนาย c ได้ก่อนที่จะสร้าง R มิฉะนั้น อลิซจะมีพลังพิเศษในการ "ย้อนเวลา" เพื่อที่เธอจะได้หลอกบ็อบโดยพลการ
และฟังก์ชันแฮชที่ปลอดภัยในการเข้ารหัสคือ "ทางเดียว" เช่น SHA256, SHA3, blake2 เป็นต้น ด้วยวิธีนี้ แม้ว่า c จะถูกคำนวณโดย Alice แต่ Alice ไม่มีความสามารถในการโกงโดยการเลือก c เพราะทันทีที่อลิซสร้าง R ค่า c ก็เท่ากับได้รับการแก้ไข เราคิดว่าอลิซซึ่งเป็นมนุษย์ไม่มีความสามารถในการย้อนกลับการคำนวณแฮชใน "โลกแห่งความจริง"
เมื่อดูรูปด้านบน เราใช้ฟังก์ชันแฮชเพื่อรวมโปรโตคอล Schnorr สามขั้นตอนเป็นขั้นตอนเดียว อลิซสามารถส่งโดยตรง: (R, c, z) และเนื่องจาก Bob มี PK Bob สามารถคำนวณ c ได้ด้วยตัวเอง ดังนั้น Alice จึงสามารถส่ง (R, z) ได้
เราเปลี่ยนรูปแบบด้านบนเล็กน้อยและได้รับรูปแบบ "ลายเซ็นดิจิทัล" ลายเซ็นดิจิทัลที่เรียกว่าหมายความว่า "ฉัน" นำเสนอสตริงถึง "คุณ" เช่น "ดวงอาทิตย์อยู่ที่ปลายภูเขาแม่น้ำเหลืองไหลลงสู่ทะเล" และเพื่อพิสูจน์ว่าบทกวีนี้ ถูกนำเสนอโดยฉัน ฉันต้องลงนามบางอย่าง สิ่งนี้สามารถพิสูจน์ได้ว่าตัวตนของฉันเชื่อมโยงกับบทกวีนี้
ลายเซ็นดิจิทัลจากมุมมองของ NIZK
แบบแผนลายเซ็นดิจิทัลเทียบเท่ากับการพิสูจน์ (1) ว่าฉันมีคีย์ส่วนตัว และ (2) ว่าคีย์ส่วนตัวและข้อความนั้นเชื่อมโยงกับการคำนวณ
ฉันต้องพิสูจน์ตัวตนของฉันก่อน ดังนั้นมันจึงง่าย นี่คือหน้าที่ของโปรโตคอล Schnorr ซึ่งสามารถพิสูจน์ข้อความว่า "ฉันมีรหัสส่วนตัว" ให้กับบุคคลอื่นได้ และกระบวนการพิสูจน์นี้ไม่มีความรู้: จะไม่มีการเปิดเผยความรู้เกี่ยวกับ "คีย์ส่วนตัว"
m = "แล้วมันเกี่ยวข้องกับบทกวี Tang นี้อย่างไร? เราแก้ไขกระบวนการคำนวณ c:"
c = Hash(m, R)
ตะวันลับขอบเขา แม่น้ำฮวงโห ไหลลงทะเล
ที่นี่ เพื่อให้แน่ใจว่าผู้โจมตีไม่สามารถปลอมแปลงลายเซ็นได้ตามต้องการ มีข้อสันนิษฐานว่าปัญหาลอการิทึมไม่ต่อเนื่อง (DLP) และฟังก์ชันแฮชเป็นไปตามค่าความต้านทานพรีอิมเมจรอง (Secondary Preimage Resistance)
หมายเหตุ: พูดอย่างเคร่งครัด เพื่อให้แน่ใจว่าลายเซ็นดิจิทัลไม่สามารถปลอมแปลงได้ จำเป็นต้องพิสูจน์ว่าโปรโตคอล Schnorr เป็นไปตามคุณสมบัติที่แข็งแกร่งกว่าของ "Simulation Soundness" สำหรับสิ่งนี้ โปรดดูที่ [2]
รูปภาพด้านบนคือรูปแบบลายเซ็นดิจิทัลที่รู้จักกันดี - รูปแบบลายเซ็นของ Schnorr [1] มีการเพิ่มประสิทธิภาพอื่นที่นี่ สิ่งที่ Alice ส่งให้ Bob ไม่ใช่ (R, z) แต่เป็น (c, z) เนื่องจาก R สามารถคำนวณผ่าน c, z
หมายเหตุ: เหตุใดจึงเป็น "การเพิ่มประสิทธิภาพ" ปัจจุบันมีอัลกอริทึมของแชงค์ส อัลกอริทึมแลมบ์ดา และอัลกอริทึม rho ของพอลลาร์ดสำหรับโจมตีเส้นโค้งวงรี โปรดจำไว้ว่าความซับซ้อนของอัลกอริทึมนั้นประมาณ [3] และ n คือจำนวนหลักในขนาดของฟิลด์จำกัด สมมติว่าเราใช้เขตข้อมูลจำกัดที่ใกล้เคียงกับ 2^256 มาก กล่าวคือ z คือ 256 บิต ดังนั้นขนาดของกลุ่มเส้นโค้งวงรีจึงเกือบจะใกล้เคียงกับ 256 บิต ดังนั้นรากที่สองของ 2^256 จึงเท่ากับ 2^ 128 ดังนั้นความปลอดภัยของกลุ่มเส้นโค้งวงรี 256 บิตจึงมีเพียง 128 บิต จากนั้นเพียง 128 บิตก็เพียงพอสำหรับความท้าทายหมายเลข c ด้วยวิธีนี้ Alice จึงประหยัดพื้นที่ในการส่ง c มากกว่าการส่ง R และอย่างหลังต้องใช้อย่างน้อย 256 บิต ค่าสองค่าของ c และ z รวมกันได้ทั้งหมด 384 บิต เมื่อเทียบกับรูปแบบลายเซ็น ECDSA ยอดนิยม สามารถช่วยประหยัดพื้นที่อันมีค่าได้ถึง 1/4 ตอนนี้ทีมพัฒนา Bitcoin พร้อมที่จะเปลี่ยนรูปแบบลายเซ็น ECDSA เป็นแบบแผนลายเซ็นที่คล้าย Schnorr—muSig[4] ซึ่งสามารถรองรับหลายลายเซ็นและการรวมที่ยืดหยุ่นมากขึ้น
วิธีการใช้ฟังก์ชันแฮชเพื่อเปลี่ยนระบบการพิสูจน์แบบโต้ตอบเป็นวิธีการแบบไม่โต้ตอบเรียกว่าการแปลง Fiat-Shamir [5] ซึ่งเสนอในปี 1986 โดย Amos Fiat และ Adi Shamir ผู้คร่ำหวอดในการเข้ารหัส
สร้างความน่าเชื่อถือใหม่ - ตัวช่วยสร้างคำทำนายแบบสุ่ม
ดังที่ได้กล่าวไว้ก่อนหน้านี้ หากไม่มีความท้าทาย ดูเหมือนว่า "รากฐานความน่าเชื่อถือ" ของการพิสูจน์จะสูญหายไป ในรูปแบบลายเซ็นของ Schnorr ฟังก์ชันแฮชจะรับบทบาทเป็น "ผู้ท้าชิง" บทบาทนี้มีชื่อทางวิชาการว่า "Random Oracle" (Random Oracle) [6]
แต่ทำไมต้องใช้แฮชที่นี่? ในความเป็นจริง เมื่ออลิซต้องการสร้างตัวเลขสุ่มสาธารณะ เธอต้องการสิ่งที่เรียกว่า "คำพยากรณ์แบบสุ่ม" มันคืออะไร?
ได้เวลาระดมความคิดแล้ว!
เราจินตนาการว่าใน "โลกแห่งความจริง" มี "เอลฟ์" อยู่บนท้องฟ้า เขาถือแบบฟอร์มสองคอลัมน์ คอลัมน์ซ้ายเป็นสตริง และคอลัมน์ขวาเป็นตัวเลข ใครก็ตาม รวมทั้งคุณและฉัน รวมถึงอลิซและบ็อบ สามารถส่งสตริงไปยัง "เอลฟ์" ได้
หลังจากที่เอลฟ์ได้รับ string แล้ว มันจะตรวจสอบคอลัมน์ด้านซ้ายของตารางเพื่อดูว่ามี string ดังกล่าวในตารางหรือไม่ มีสองกรณี ดังนี้
สถานการณ์ที่ 1: ถ้าไม่พบสตริงในคอลัมน์ด้านซ้าย เอลฟ์จะสร้าง "หมายเลขสุ่มจริง" จากนั้นเขียนสตริงและหมายเลขสุ่มลงในตาราง จากนั้นส่งคืนหมายเลขสุ่มให้กับมนุษย์ที่อยู่บนพื้น
กรณีที่ 2: ถ้ามีระเบียนสตริงนี้ในคอลัมน์ด้านซ้าย เอลฟ์จะคืนค่าตัวเลขในคอลัมน์ด้านขวาลงกราวด์โดยตรง
คุณจะพบว่าสไปรท์นี้ทำหน้าที่เหมือนตัวสร้างตัวเลขแบบสุ่มแต่แตกต่างกันมาก ความแตกต่าง คือ เมื่อเราส่งสตริงเดียวกันก็จะส่งกลับเป็นตัวเลขเดียวกัน เอลฟ์นี้เป็นตำนาน "สุ่มออราเคิล"
ในกระบวนการผสานโปรโตคอล Schnorr นั้น สิ่งที่เราต้องการจริง ๆ ก็คือตัวช่วยสร้าง oracle แบบสุ่ม ไม่ใช่ฟังก์ชันแฮช ความแตกต่างระหว่างทั้งสองคืออะไร? ความแตกต่างคือ:
ออราเคิลแบบสุ่มส่งคืนตัวเลขสุ่ม "จริง" พร้อมการแจกแจงที่สอดคล้องกันทุกครั้งสำหรับสตริงใหม่
ผลลัพธ์ที่คำนวณโดยฟังก์ชันแฮชไม่ใช่ตัวเลขสุ่มอย่างแท้จริงที่มีการแจกแจงที่สอดคล้องกัน
เหตุใดจึงใช้ฟังก์ชันแฮชก่อนหน้านี้ นี่เป็นเพราะในโลกแห่งความเป็นจริงไม่มี oracles สุ่มที่แท้จริง! ทำไม ในความเป็นจริง เป็นไปไม่ได้ที่ฟังก์ชันแฮชจะสร้างตัวเลขสุ่มอย่างแท้จริง เนื่องจากฟังก์ชันแฮชเป็นอัลกอริทึม "เชิงกำหนด" และไม่มีการแนะนำปริมาณสุ่มอื่นใดนอกจากพารามิเตอร์
และฟังก์ชันแฮชที่มีความปลอดภัยในการเข้ารหัส "ดูเหมือน" สามารถทำหน้าที่เป็นออราเคิลสุ่ม "หลอก" ได้ จากนั้นโปรโตคอลความปลอดภัยแบบรวมจำเป็นต้องเพิ่มข้อสันนิษฐานด้านความปลอดภัยเพิ่มเติม ซึ่งก็คือ:
สมมติฐาน: ฟังก์ชันแฮชที่มีความปลอดภัยในการเข้ารหัสสามารถประมาณ "สุ่มออราเคิล" ในตำนานได้
เนื่องจากข้อสันนิษฐานนี้ไม่สามารถพิสูจน์ได้ เราจึงทำได้เพียงเชื่อถือข้อสันนิษฐานนี้ หรือใช้เป็นสัจพจน์ นอกจากนี้ คุณสมบัติป้องกันการชนกันโดยทั่วไปของฟังก์ชันแฮชระบุว่าเอาต์พุตสามารถจำลองตัวเลขสุ่มได้ ขณะเดียวกัน ในหลายกรณี (ไม่ใช่ทั้งหมด) เป็นเรื่องยากมากที่จะโจมตีฟังก์ชันแฮช ใช้มันอย่างกล้าหาญ
โมเดลความปลอดภัยที่ไม่ใช้สมมติฐานนี้เรียกว่า "โมเดลมาตรฐาน" และโมเดลความปลอดภัยที่ใช้สมมติฐานนี้ไม่สามารถเรียกว่า "โมเดลที่ไม่ได้มาตรฐาน" ได้อย่างแน่นอน มีคำเรียกสั้นๆ ว่า "โมเดลสุ่มของออราเคิล"
มีคนอยู่สองประเภทในโลก คนที่ชอบเต้าหู้หวานและคนที่ไม่ชอบ ในทำนองเดียวกัน มีนักเข้ารหัสลับอยู่สองประเภทในโลก คนที่ชอบแบบจำลอง oracle แบบสุ่ม และผู้ที่ไม่ชอบแบบจำลอง oracle แบบสุ่ม [6]
โครงสร้างรากฐาน - ลักพาตัวเอลฟ์
หลังจากโปรโตคอล Schnorr ผ่านการแปลง Fiat-Shamir ก็จะมีคุณสมบัติ NIZK สิ่งนี้แตกต่างจาก SHVZK ที่เราพิสูจน์แล้ว SHVZK กำหนดให้ผู้ตรวจสอบต้องซื่อสัตย์ ในขณะที่ NIZK ไม่มีข้อกำหนดที่ไม่เป็นจริงอีกต่อไปเกี่ยวกับผู้ตรวจสอบเนื่องจากผู้ตรวจสอบไม่ได้มีส่วนร่วมในการโต้ตอบและปัญหาที่เรียกว่าการเรียกร้องผู้ซื่อสัตย์ ไม่มีตัวตรวจสอบอีกต่อไป
หมายเหตุ: จะเกิดอะไรขึ้นหากผู้ตรวจสอบ Bob ไม่ซื่อสัตย์ จากนั้นจึงเป็นไปได้ที่บ็อบจะดึงความรู้ของอลิซออกมา แต่สำหรับโปรโตคอล Schnorr สามขั้นตอนนั้นยังไม่ทราบว่าเป็นไปตาม "ความรู้เป็นศูนย์" หรือไม่ เราพิสูจน์ให้เห็นแล้วว่ามันตอบสนองคุณสมบัติที่ค่อนข้างอ่อนแอใน Series 3: SHVZK
อย่างไรก็ตาม เมื่อโปรโตคอล Schnorr ถูกเปลี่ยนให้เป็นระบบพิสูจน์ความรู้เป็นศูนย์ที่ไม่มีการโต้ตอบ มันจะกลายเป็น "ความรู้ที่ไม่มีศูนย์" อย่างแท้จริง
อย่างไรก็ตาม คำถามของคุณอาจตามมาด้วย คำยืนยันนี้ฟังดูสมเหตุสมผล คุณพิสูจน์ได้ไหม
หมดเวลาแล้ว "Cuihua ขึ้นเครื่องจำลอง"
จะใช้วิธีการจำลองเพื่อสร้าง "โลกในอุดมคติ" ได้อย่างไร? ลองคิดดูสิ เราเคยใช้ "ย้อนเวลา" มาก่อน และดัดแปลงพลังพิเศษของ "สายพานลำเลียงตัวเลขสุ่ม" เพื่อให้ "เครื่องจำลอง" โกงได้ แต่ไม่มีการโต้ตอบซึ่งหมายความว่า: ไม่สามารถใช้พลังพิเศษของ "ย้อนเวลากลับไป" สายพานลำเลียงหมายเลขสุ่มของ Bob ไม่มีอยู่และไม่สามารถใช้พลังพิเศษของ "การดัดแปลงสายพานลำเลียง" ได้!
แต่เครื่องจำลองจะต้องมี "พลังพิเศษ" บางอย่างอยู่เสมอเพื่อที่จะสามารถสร้าง "ราก" ของความไว้วางใจได้
(หากเครื่องจำลองมีความสามารถในการโกงโดยปราศจากพลังวิเศษ ก็เท่ากับเป็นการพิสูจน์ว่าโปรโตคอลไม่น่าเชื่อถือ)
ตอนนี้ทุกคนคงเดาได้แล้ว เครื่องจำลองต้องทำอะไรสักอย่างกับ "สุ่มออราเคิล"ก่อนอื่นให้พิจารณาสร้าง "โลกในอุดมคติ" เพื่อพิสูจน์ว่า "ความรู้เป็นศูนย์" ในโลกอุดมคติ ตัวจำลองได้ "ลักพาตัว" "เอลฟ์" ซึ่งเป็นผู้รับผิดชอบในการทำนาย เมื่อบ็อบขอตัวเลขสุ่มเอลฟ์ เอลฟ์ไม่ได้ให้ตัวเลขสุ่มจริง แต่มอบให้ Zlice (ตัวจำลอง แสร้งทำเป็นอลิซ) ตัวเลขที่เตรียมไว้ล่วงหน้า (ซึ่งสอดคล้องกับการแจกแจงที่สอดคล้องกันและรับประกันว่าแยกไม่ออก) "มาร" ไม่มีทางเลือกอื่นนอกจากส่งคืนตัวเลขที่ดูสุ่มให้บ็อบ แต่จริงๆ แล้วมีประตูหลัง
ประตูหลังที่เรียกว่าหมายความว่า Zlice เลือกหมายเลขนี้ล่วงหน้า
ขั้นตอนที่ 1: Zlice สุ่มเลือก z สุ่มเลือก c และคำนวณ R'=z*G - c*PK
ขั้นตอนที่ 2: Zlice เขียน c และ (m, R') ลงในตารางของ sprite
ขั้นตอนที่ 3: Zlice ส่งลายเซ็น (c, z) ให้ Bob
ขั้นตอนที่ 4: Bob คำนวณ R=z*G - c*PK และส่ง (m, R) ไปยังเอลฟ์ และเอลฟ์ส่งกลับ c' โปรดทราบว่าที่นี่ R' ที่คำนวณได้ของ Bob และ R' ที่คำนวณได้ของ Zlice มีค่าเท่ากัน
ขั้นตอนที่ 5: Bob ตรวจสอบว่า c ?= c' เพื่อดูว่าตัวเลขสุ่มที่เอลฟ์ส่งคืนนั้นเท่ากับตัวเลขสุ่มที่อีกฝ่ายส่งมาหรือไม่ หากเท่ากันแสดงว่าลายเซ็นการตรวจสอบผ่าน มิฉะนั้น การตรวจสอบจะล้มเหลว
ด้วยการลักพาตัว "เอลฟ์" Zlice ยังสามารถทำนายจำนวนสุ่มล่วงหน้า ซึ่งสามารถบรรลุผลเช่นเดียวกับการย้อนเวลากลับไป
เราได้พิสูจน์ "การมีอยู่" ของเครื่องจำลอง Zlice แล้ว ดังนั้นเราจึงได้พิสูจน์ NIZK ข้างต้น
sk = (z1 - z2)/(c1 - c2)
ต่อไป เราจะพิสูจน์ "ความน่าเชื่อถือ" ของโปรโตคอลนี้ ลองนึกภาพว่าในอีก "โลกในอุดมคติ" สิ่งที่เรียกว่า "ผู้สกัด" ก็ลักพาตัวเอลฟ์ไปด้วย เมื่ออลิซผู้ไร้เดียงสาขอตัวเลขสุ่มจาก "เอลฟ์" "เอลฟ์" กลับเป็น c1 และ "ตัวแยก" มองที่ c1 จากตารางเอลฟ์ หลังจากที่อลิซคำนวณ z1 แล้ว "ตัวแยก" ก็ยังสามารถเปิดใช้งาน super ได้ พลังของ "การย้อนเวลา" ให้อลิซกลับไปที่ขั้นตอนที่สองแล้วขอตัวเลขสุ่มจาก "เอลฟ์" อีกครั้ง สตริงที่อลิซส่งมานั้นเห็นได้ชัดว่าเหมือนกับสตริงที่ส่งไปครั้งแรก (R, m ) . ตามเหตุผลแล้ว เนื่องจาก (R, m) ถูกเขียนไว้แล้วใน "คอลัมน์ด้านซ้าย" ของสไปรต์ชีต ดังนั้น "สไปรต์" ที่ซื่อสัตย์ควรส่งคืน c1 อย่างไรก็ตาม "ผู้แยก" ได้ลักพาตัวสไปรต์ไป และเขาเปลี่ยน "คอลัมน์ขวา" ที่ตรงกับแถว (R, m) ในตารางเป็นเลขอื่น c2 หลังจากที่ Alice คำนวณ z2 อื่นแล้ว ตัวแยกข้อมูลจะทำงานให้เสร็จสิ้นและคำนวณ sk คีย์ส่วนตัวของ Alice ผ่านสมการต่อไปนี้:
การแปลง Fiat-Shamir - จาก Public-Coin เป็น NIZK
ไม่เพียงแต่สำหรับโปรโตคอล Schnorr แต่สำหรับ "โปรโตคอล Public-Coin" ใดๆ ก็ตาม การแปลง Fiat-Shamir สามารถใช้เพื่อ "บีบอัด" โปรโตคอลทั้งหมดให้เป็นการโต้ตอบแบบขั้นตอนเดียว นั่นคือ ระบบพิสูจน์แบบไม่โต้ตอบ เทคนิคการแปลงร่างเริ่มมาจากเอกสาร "How to Prove Yourself: Practical Solutions to Identification and Signature Problems." โดย Amos Fiat และ Adi Shamir เผยแพร่ในการประชุม Crypto ในปี 1986 [5] ว่ากันว่าเทคนิคนี้มาจาก Manuel Blum[6]
ขอย้ำอีกครั้งว่าในโปรโตคอล Public-coin ผู้ตรวจสอบความถูกต้อง Bob ทำเพียงประเภทเดียวเท่านั้น ซึ่งก็คือการสร้างตัวเลขสุ่มและท้าทายอลิซ ด้วยการเปลี่ยนแปลงของ Fiat-Shamir แต่ละ "พฤติกรรมที่ท้าทาย" ของ Bob สามารถถูกแทนที่ด้วย "คำทำนายแบบสุ่ม"
ในการใช้งานที่เฉพาะเจาะจง Oracle แบบสุ่มจำเป็นต้องใช้ฟังก์ชันแฮชที่มีความปลอดภัยสูงในการเข้ารหัส (คุณไม่สามารถเลือกแบบสุ่มได้ คุณต้องใช้แฮชที่ปลอดภัยในการเข้ารหัส) และพารามิเตอร์ของฟังก์ชันแฮชควรเป็นอินพุตบริบทก่อนหน้าทั้งหมด ต่อไปนี้คือแผนภาพตัวอย่าง คุณสามารถเข้าใจแนวทางปฏิบัติของการแปลง Fiat-Shamir นี้ได้อย่างรวดเร็ว
ดังที่ได้กล่าวไว้ก่อนหน้านี้ ในระบบการพิสูจน์แบบไม่โต้ตอบ จำเป็นต้องมีการแนะนำบุคคลที่สามเพื่อสร้าง "รากเหง้า" ของความไว้วางใจ เพื่อให้ Bob สามารถไว้วางใจการพิสูจน์ที่ Alice สร้างขึ้นได้อย่างเต็มที่ ในที่นี้ บุคคลที่สามคือ "เอลฟ์" ซึ่งในภาษาสแลงทางวิชาการคือ "Random Oracle" เอลฟ์ตนนี้ไม่ใช่บุคคลที่สามที่แท้จริง แต่เป็นบุคคลที่สามเสมือนซึ่งมีอยู่ทั้งใน "โลกแห่งความจริง" และ "โลกแห่งอุดมคติ" ใน "โลกแห่งความจริง" เอลฟ์เป็นผู้ชายที่หล่อเหลาและมีความรับผิดชอบ แต่ใน "โลกแห่งอุดมคติ" มันจะถูก "จำลอง" ลักพาตัวไป
โปรโตคอล Public-Coin ยังมีชื่อที่ดีว่า "Arthur-Merlin Game"...
ดูภาพด้านบน "เสื้อคลุมสีขาว" ทางซ้ายคือ Merlin (ผู้วิเศษ Merlin) และหนุ่มหล่อถือดาบตรงกลางคือ King Arthur (คิงอาเธอร์) ตัวละครทั้งสองมาจากตำนานยุคกลางของยุโรป - อัศวินโต๊ะกลมของกษัตริย์อาเธอร์
อาเธอร์เป็นกษัตริย์ใจร้อนที่พกเหรียญติดตัว ส่วนเมอร์ลิน คือจอมเวทย์มนตร์ที่มีพลังการคำนวณไม่จำกัด ในบทสนทนา แต่เนื่องจากราชาขี้เกียจ เขาจะโยนเหรียญเพียงครั้งเดียวเท่านั้น แล้ว "ท้าทาย" นักมายากลและนักมายากลจำเป็นต้องตอบสนองให้ทันเวลาและจำเป็นต้องทำให้กษัตริย์เชื่อในการตัดสินของเขาเองหลังจากรอบ k เนื่องจากเมอร์ลินมีเวทมนตร์ เหรียญทุกเหรียญที่กษัตริย์อาเธอร์ขว้างจึงสามารถมองเห็นได้โดยเมอร์ลิน[7]นี้อยู่กับเราใน"ชุดที่หนึ่ง"
Interactive Proof System (เรียกสั้นๆ ว่า IP) ที่กล่าวถึงนั้นค่อนข้างคล้ายกัน แต่แตกต่างกัน IP ถูกเสนออย่างเป็นทางการโดย Goldwasser, Micali และ Rackoff (เรียกสั้นๆ ว่า GMR) ในปี 1985 และความสามารถในการพิสูจน์ของมันครอบคลุมปัญหาความซับซ้อนทางการคำนวณในระดับมาก ข้อแตกต่างคือในนิยามของ IP ทั้ง Prover และ Verifier เป็นเครื่อง Turing ที่สามารถโยนเหรียญได้ และ Verifier สามารถแอบโยนเหรียญและซ่อนเหรียญจาก Prover ในขณะที่ในเกม Arthur-Merlin กษัตริย์ทำได้เพียงการโยนเหรียญ ไม่เพียงเท่านั้น Merlin ยังรู้ผลของการโยนเหรียญเสมอ
อย่างไรก็ตาม การแปลง Fiat-Shamir สามารถพิสูจน์ความปลอดภัยภายใต้ "แบบจำลอง oracle แบบสุ่ม" เท่านั้น และกระบวนการใช้ฟังก์ชันแฮชเพื่อให้ทราบว่า oracle แบบสุ่มนั้นปลอดภัยหรือไม่นั้นขาดการพิสูจน์ความปลอดภัย ไม่เพียงเท่านั้น โปรโตคอลที่ปลอดภัยภายใต้ "แบบจำลอง oracle แบบสุ่ม" อาจไม่ปลอดภัย และพบตัวอย่างที่ขัดแย้งกัน [8] โชคไม่ดีที่ S. Goldwasser และ Y. Tauman พิสูจน์ในปี 2546 ว่าการเปลี่ยนแปลงของ Fiat-Shamir มีความปลอดภัย ตัวอย่างย้อนแย้งในตัวเอง [9] แต่นี่ไม่ได้หมายความว่าจะใช้การแปลง Fiat-Shamir ไม่ได้ แต่ต้องใช้ความระมัดระวังอย่างมากระหว่างการใช้งานและไม่สามารถใช้แบบสุ่มสี่สุ่มห้าได้
ถึงกระนั้นก็ไม่มีใครต้านทานการล่อลวงของการเปลี่ยนแปลงของ Fiat-Shamir ซึ่งใช้กันอย่างแพร่หลายอย่างมาก เป็นมูลค่าการกล่าวขวัญว่าการแปลง Fiat-Shamir มีอยู่มากมายในแผนการต่างๆ ของ zkSNARK ที่ไม่ต้องมีการโต้ตอบเพื่อวัตถุประสงค์ทั่วไปที่ร้อนแรงที่สุด ตัวอย่างเช่น คุณอาจคุ้นเคยกับ Bulletproofs (การพิสูจน์กระสุน) และมีแผนการพิสูจน์ความรู้ที่ไม่มีจุดประสงค์ทั่วไปบางอย่างที่ยังไม่เป็นที่รู้จักกันดีในขณะนี้ เช่น Hyrax, Ligero, Supersonic, Libra เป็นต้น (เราจะติดตามและอธิบายทีละรายการ)
ข้อควรระวัง: ผลกระทบด้านความปลอดภัยในการแปลง Fiat-Shamir
ในการแปลง Fiat-Shamir ให้ความสนใจเป็นพิเศษกับพารามิเตอร์ที่ส่งไปยังฟังก์ชัน Hash ในการใช้งานโค้ดจริงมีกรณีที่พารามิเตอร์บางตัวของฟังก์ชัน Hash ถูกละเว้น:
ตัวอย่างเช่น ใน A, Hash(A), B, Hash(B) ฟังก์ชัน Hash ที่สองไม่มีพารามิเตอร์ A และวิธีที่ถูกต้องควรเป็น A, Hash(A), B, Hash(A,B) แนวทางประเภทนี้จะทำให้เกิดช่องโหว่ด้านความปลอดภัยที่ร้ายแรง ตัวอย่างเช่น ในระบบการลงคะแนนอิเล็กทรอนิกส์ของสวิส SwissPost-Scytl โค้ดการดำเนินการของการแปลง Fiat-Shamir ได้พลาดพารามิเตอร์ที่ควรมีอยู่ซ้ำแล้วซ้ำอีก ตามความประสงค์ และบัตรลงคะแนนสามารถปลอมแปลงได้ตามความประสงค์เพื่อให้บรรลุวัตถุประสงค์ในการฉ้อโกง [10] ดังนั้นในการใช้งานด้านวิศวกรรม โปรดใส่ใจ
ผู้อ่านที่ระมัดระวังอาจมองย้อนกลับไปที่ลายเซ็น Schnorr และคุณจะพบว่าอัลกอริทึมแฮชในลายเซ็น Schnorr ดูเหมือนจะพลาดพารามิเตอร์ PK ซึ่งไม่ใช่การแปลง Fiat-Shamir ที่เคร่งครัด ซึ่งเรียกว่าการแปลง Fiat-Shamir แบบอ่อนแอ [11 ] อย่างไรก็ตาม ไม่มีปัญหาด้านความปลอดภัยในกรณีพิเศษนี้ [3] โปรดอย่าเลียนแบบผู้เยาว์ตามความประสงค์
เมื่อเร็ว ๆ นี้ นักวิชาการบางคนได้เริ่มศึกษาวิธีการพิสูจน์ความปลอดภัยของ Fiat-Shamir อย่างเคร่งครัดภายใต้โมเดลมาตรฐาน ในปัจจุบัน พวกเขาเสนอสมมติฐานด้านความปลอดภัยที่แข็งแกร่งเพิ่มเติมหรือพิสูจน์ด้วยโปรโตคอลเฉพาะแต่ดูเหมือนว่าจะมีไม่มากนัก ความคืบหน้า.
พลังของการโต้ตอบ
ว่ากันว่าในปี 1985 เมื่อวิทยานิพนธ์ของ GMR ทั้งสามคนได้รับการยอมรับจาก STOC'85 หลังจากการปฏิเสธหลายครั้ง STOC'85 ก็ยอมรับงานอื่นที่คล้ายกันเช่นกัน นี่คือ László Babai จาก University of Roland ประเทศฮังการี และบทความ "Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes" เขียนโดย Shlomo Moran จาก Israel Institute of Technology [7] แนะนำ Public-coin interactive protocol (ตามชื่อที่แนะนำคือ Verifier เท่านั้น พลิกเหรียญต่อสาธารณะ) .
วิธีการของ King Arthur นั้นง่ายมาก การยืนยันของ Merlin ได้รับการทดสอบโดยการท้าทาย "สุ่ม" ซ้ำๆ ซึ่งสอดคล้องกับสัญชาตญาณที่เราอธิบายไว้ก่อนหน้านี้: ใช้การท้าทายแบบสุ่มเพื่อสร้าง "ราก" ของความไว้วางใจ Babai พิสูจน์ข้อสรุปที่น่าสนใจในบทความ: AM[k]=AM[2] โดยที่ k แทนจำนวนของการโต้ตอบ และผลของการโต้ตอบหลายครั้งเทียบเท่ากับสองการโต้ตอบ การโต้ตอบสองครั้งหมายถึง: อาเธอร์ส่งหมายเลขท้าทาย แล้วเมอร์ลินก็ตอบกลับ
หมายเหตุ: มีปัญหาอีกประเภทหนึ่งที่เป็นของ MA ลำดับการโต้ตอบของปัญหาประเภทนี้แตกต่างจากปัญหาของ AM ใน MA เมอร์ลินจะทำการพิสูจน์ก่อน จากนั้น Arthur จะพลิกเหรียญเพื่อตรวจสอบ ได้รับการพิสูจน์แล้วว่าปัญหาที่ MA สามารถจัดการได้นั้นเป็นส่วนย่อยของ AM
ไม่เพียงเท่านั้น Babai ยังคาดเดาอย่างกล้าหาญว่า AM[poly] เทียบเท่ากับ IP นี่เป็นคำยืนยันที่มีมนต์ขลัง: ราชาขี้เกียจ เขาเพียงต้องพลิกเหรียญพหุนามเพื่อท้าทายนักมายากลให้สำเร็จ และพลังการแสดงออกของวิธีนี้เทียบเท่ากับระบบพิสูจน์ IP แบบโต้ตอบที่อธิบายโดย GMR แน่นอนว่าในการประชุม STOC'86 บทความจาก S. Goldwasser และ M. Sipser ได้พิสูจน์เรื่องนี้ว่า AM[poly] == IP[12]
ซึ่งหมายความว่า: "การท้าทายแบบสุ่ม" สาธารณะซ้ำ ๆ นั้นทรงพลังอย่างไร้ขีด จำกัด และเทียบเท่ากับระบบพิสูจน์แบบโต้ตอบใด ๆ อย่างไรก็ตาม ความสัมพันธ์ระหว่าง AM[poly] กับคลาสความซับซ้อนทางการคำนวณอื่นๆ คือฮอตสปอตการวิจัยถัดไป
AM[poly] == IP == PSPACE
สามปีต่อมา ณ สิ้นเดือนพฤศจิกายน พ.ศ. 2532 เมื่อ 30 ปีที่แล้ว โนม นิสัน นักเข้ารหัสอายุน้อยได้ส่งอีเมลส่งข้อสรุปเชิงวิชาการชั่วคราวของเขาไปยังนักเข้ารหัสหลายคน จากนั้นเขาก็วิ่งไปที่อเมริกาใต้ซึ่งกำลังอยู่ในช่วงพักร้อน แต่เขาไม่เคยคิดว่าอีเมลฉบับนี้จะก่อให้เกิดการแข่งขันทางวิชาการที่ดุเดือดในประวัติศาสตร์ โดยมีกลุ่มใหญ่อย่าง M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund ฯลฯ บรรดาชนชั้นสูงเริ่มเข้าร่วมการต่อสู้พวกเขาหารือกันทั้งวันทั้งคืนและแข่งขันกันเผยแพร่ผลการวิจัย ในที่สุด วันที่ 26 ธันวาคม ตรงกับหนึ่งเดือน Adi Shamir ได้พิสูจน์ข้อสรุปดังต่อไปนี้:
โดยจะอธิบายลักษณะทางทฤษฎีการคำนวณของแนวคิดของ "การพิสูจน์ที่มีประสิทธิภาพ" และอธิบายถึงพลังการประมวลผลที่ครอบคลุมโดยแนวคิดของ "ระบบพิสูจน์แบบโต้ตอบ"
หมายเหตุ: คลาส NP เป็นส่วนย่อยของคลาส PSPACE ทุกคนคุ้นเคยมากกว่าคลาสแรกและคลาสหลังเกี่ยวข้องกับกลยุทธ์การชนะในเกมหรือหมากรุก [13]
จากนั้น L. Babai ได้เขียนบทความชื่อ "อีเมลและพลังแห่งการโต้ตอบที่คาดไม่ถึง" (อีเมลและพลังแห่งการโต้ตอบที่คาดไม่ถึง) [14] ซึ่งอธิบายรายละเอียดตลอดทั้งเดือนนี้ใน "การโต้ตอบทางอีเมล" "และรายละเอียดเกี่ยวกับ "หลักฐานเชิงโต้ตอบ".
สตริงอ้างอิงสาธารณะ - อีก "รากของความไว้วางใจ"
ใช่ คุณอ่านถูกแล้ว ที่นี่มี "บุคคลที่สาม" อีกแล้ว! แม้ว่าบุคคลที่สามจะไม่ได้มีส่วนร่วมในการพิสูจน์โดยตรง แต่เขาต้องรับประกันความน่าเชื่อถือของกระบวนการสร้างสตริงแบบสุ่ม กระบวนการสร้าง CRS เรียกอีกอย่างว่า "การตั้งค่าที่เชื่อถือได้" ซึ่งเป็นสิ่งที่ทุกคนรักและเกลียด แน่นอนว่าการนำบุคคลที่สามเข้ามาในสถานการณ์จริงอาจทำให้คุณปวดหัวได้ CRS ใช้สำหรับอะไรกันแน่? ความเชื่อถือของ Trusted Setup มาจากไหน ส่วนนี้จะสงวนไว้สำหรับบทความถัดไปในชุดนี้
ยังมีต่อ
ยังมีต่อ
ความรู้ที่เป็นศูนย์แบบไม่โต้ตอบได้พิสูจน์ว่า "รากฐานของความไว้วางใจ" ของ NIZK ยังต้องการ "ความท้าทาย" แบบสุ่มบางรูปแบบ "ความท้าทาย" รูปแบบหนึ่งถูกส่งมอบให้กับ "เอลฟ์พยากรณ์แบบสุ่ม" สตริงสุ่มที่ใช้ร่วมกันเพื่อให้บรรลุ ความท้าทายทั้งสองรูปแบบเป็นการแนะนำบุคคลที่สามโดยพื้นฐานแล้ว และทั้งสองต้องมี "ประตูหลัง" ที่ "เครื่องจำลอง" สามารถใช้ประโยชน์ได้ เพื่อให้เครื่องจำลองมี "ข้อได้เปรียบ" บางอย่างใน "โลกแห่งอุดมคติ" และข้อได้เปรียบนี้จะต้อง ล้มเหลวใน "โลกแห่งความเป็นจริง"
NIZK แสดงออกถึงเสน่ห์ที่ไม่สิ้นสุดซึ่งทำให้ฉันประหลาดใจเป็นครั้งคราว ในช่วง 30 ปีที่ผ่านมา ผู้บุกเบิกได้สำรวจข้อสรุปที่ลึกซึ้งและในขณะเดียวกันก็มีมุมที่ไม่รู้จักมากมายรอแสงแห่งแรงบันดาลใจบทความชุดนี้อยู่บน Githubที่เก็บโครงการ
ได้รับคำขอดึงครั้งแรกจาก Jingyu Hu (colortigerhu) เปลี่ยนเพียงไม่กี่คำ แต่ในขณะนั้นฉันรู้สึกถึงพลัง การแลกเปลี่ยนความรู้ การปะทะกันทางความคิด
"ทุกคนที่เรามีปฏิสัมพันธ์ด้วยจะกลายเป็นส่วนหนึ่งของเรา" ทุกคนที่เราโต้ตอบด้วยจะกลายเป็นส่วนหนึ่งของเรา ―โจดี อามาน
ข้อความ
อ้างอิง
[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.
[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.
[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.
[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.
[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols." Proc. of the 1st CCS (1995): 62-73.
[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m
[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.
[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
[10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).
[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.
[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.
[13] Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.
[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.
[15] Yi Deng. "อ้างอิง" https://zhuanlan.zhihu.com/p/29491567
IOS
Android