คนที่ไม่น่าไว้ใจสองคนต้องการสุ่มตัวเลขขึ้นมา

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

ฉันเป็นนักเรียนวิทยาการเข้ารหัสลับควอนตัมและกำลังทำงานสร้างตัวเลขสุ่มควอนตัมยินดีต้อนรับวิธีแก้ปัญหาใด ๆ ไม่ว่าจะเป็นแบบคลาสสิกหรือแบบควอนตัม

แก้ไข

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

https://arxiv.org/pdf/1911.13283.pdf

จำนวนสุ่มที่ต้องการคือจำนวนเต็มระหว่าง 0 ถึง $\ell$. แต่ละคนเลือกหมายเลขสุ่ม $x_i$ ระหว่าง 0 ถึง $\ell$, และแต่ละคนเลือก $n$- ปัจจัยที่ทำให้ไม่เห็นแบบสุ่มบิต $b_i$ ที่ไหน $n\geq 128$ และ $n$ จะต้องตกลงกันล่วงหน้า แต่ละประกาศความมุ่งมั่นแฮชที่คำนวณเป็น $H(b \mathbin\|x)$. จากนั้นพวกเขาแต่ละคนก็เปิดข้อผูกพันโดยประกาศคุณค่าของ $ข$ และ $x$และคำนวณจำนวนสุ่มเป็น $$x_1 + x_2\ \pmod \ell.$$ นี่เป็นความปลอดภัยเชิงควอนตัมหากแฮชและทางเลือกของ $n$ อยู่ด้วยกันอย่างปลอดภัยควอนตัม

ตามที่ @poncho ชี้ให้เห็น บุคคลที่เปิดข้อผูกมัดของตนเป็นคนสุดท้ายสามารถจำลองความล้มเหลวในการดำเนินโปรโตคอลให้เสร็จสมบูรณ์ได้ หากพวกเขาไม่พอใจกับค่าสุ่มที่ใช้ร่วมกันซึ่งจะถูกสร้างขึ้นระหว่างการเรียกใช้โปรโตคอลนั้นนี่อาจเป็นปัญหาโดยเฉพาะอย่างยิ่งหาก $\ell$ เล็ก.

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

Manuel Blaum มองปัญหานี้ในปี 1981 ใน การพลิกเหรียญทางโทรศัพท์ โปรโตคอลสำหรับการแก้ปัญหาที่เป็นไปไม่ได้

รายละเอียดทางเทคนิคอยู่บนกระดาษ โปรโตคอลนี้รับประกันสิ่งเหล่านั้น (จากกระดาษ ตัวหนาคือใจ);

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

ฉันคิดว่า กระดาษแผ่นนี้ แก้ปัญหาของคุณอย่างน้อยบางส่วน