โครงการแบ่งปันความลับรวมกับผลลัพธ์ของทฤษฎีความน่าจะเป็น ?

เป็นผลสืบเนื่องจากก่อนหน้านี้ของฉัน โพสต์ ฉันกำลังเขียนใหม่เกี่ยวกับแผนการแบ่งปันความลับ ฉันจะอ้างถึงคำตอบที่นี่เท่านั้นเพราะฉันต้องการตั้งคำถาม

$\textbf{คำตอบ:}$ พูดตามตรง ฉันไม่คุ้นเคยกับการนำเสนอต้นฉบับใน RB89 100% แต่พวกเขาได้แนะนำเทคนิคหลายอย่างที่ใช้ในบทความต่อๆ มา และวันนี้มีเวอร์ชันที่เรียบง่าย (ในรูปแบบสมัยใหม่) ของความลับที่แข็งแกร่ง รูปแบบการแบ่งปันที่นั่น ตัวอย่างเช่น คำอธิบายระดับสูงสามารถพบได้ในหน้า 3 ที่นี่.

สรุปเป้าหมายคือการเป็นความลับ $s\in\mathbb{F}$ และแจกจ่ายให้แก่กัน $n$ ปาร์ตี้ $P_1,\ldots,P_n$ เพื่อที่ในเวลาต่อมาคู่สัญญาจะสามารถสร้างความลับนี้ต่อกันได้ ในขณะที่รับประกันว่าแม้บางคน $t$ ฝ่ายทุจริตด้วย $t<n/2$ ส่งค่าที่ไม่ถูกต้อง ฝ่ายที่ซื่อสัตย์ (เช่น ไม่ทุจริต) ยังสามารถรับความลับที่ซ่อนอยู่ได้ สิ่งนี้สำเร็จได้ดังนี้:

• เจ้ามือใช้การแบ่งปันความลับของ Shamir แบบดั้งเดิมเพื่อรับส่วนแบ่งของความลับ $(s_1,\ldots,s_n)$. ถ้า $t<n/2$แล้วหุ้นเหล่านี้ให้ การตรวจจับข้อผิดพลาดหมายความว่าฝ่ายใดฝ่ายหนึ่งได้หุ้นเหล่านี้ไปโดยที่ $t$ พวกเขาอาจถูกแก้ไขเนื่องจากพฤติกรรมที่เป็นปฏิปักษ์ สามารถค้นหาได้ว่าความลับถูกแก้ไขหรือไม่ แต่ในกรณีที่มีข้อผิดพลาด ฝ่ายที่กำหนดไม่สามารถ "แก้ไข" เพื่อสร้างความลับที่ถูกต้องขึ้นใหม่ได้ สิ่งนี้ไม่เพียงพอสำหรับการแบ่งปันความลับที่มีประสิทธิภาพ

• เจ้ามือสุ่มตัวอย่างคู่สุ่มอย่างสม่ำเสมอ $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ และคอมพิวเตอร์ $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$ สำหรับทุกคู่ $i,j\in[n]$ (ที่นี่ $[n] = \{1,\ldots,n\}$). ดังที่เราจะเห็น เป้าหมายของข้อมูลเพิ่มเติมนี้คือเพื่อให้แน่ใจว่าฝ่ายรับข้อมูลไม่เพียงตรวจจับได้ว่ามีการดัดแปลงหุ้นหรือไม่ แต่ที่จริงแล้ว แยกแยะ สิ่งที่ไม่ถูกต้อง ด้วยเหตุนี้จึงกรองสิ่งที่ถูกต้องออก ซึ่งนำไปสู่การสร้างความลับที่ถูกต้องขึ้นใหม่

• แม่ค้าส่ง $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n ]})$ ให้กับแต่ละฝ่าย $P_i$. ในคำ: ทุก $P_i$ ได้รับส่วนแบ่ง $s_i$ แถมกุญแจอีกคู่ $(\alpha_{ij},\beta_{ij})$ สำหรับแต่ละฝ่าย นอกจากนี้, $P_i$ ได้รับ "รุ่นตรวจสอบความถูกต้องของ $s_i$"โดยใช้กุญแจของกันและกัน

สมมติว่าเป็นปาร์ตี้ $P_j$ ควรจะเรียนรู้ความลับ ด้วยเหตุนี้ฝ่ายต่างๆ $P_i$ สำหรับ $i\in[n]\setminus\{j\}$ ส่ง $P_j$ ค่าของพวกเขา $(s_i',\tau_{ij}')$ (ถ้า $P_i$ เป็นความจริงแล้ว $s_i' = s_i$ และ $\tau_{ij}' = \tau_{ij}$แต่ฝ่ายเสียหายอาจส่งค่าที่ไม่ถูกต้อง) และ $P_j$ ตรวจสอบโดยใช้กุญแจของตัวเอง $(\alpha_{ji},\beta_{ji})$, นั่น $\tau_{ij}' = \alpha_{ji}\cdot s_i' + \beta_{ji}$.

ในแบบฝึกหัด เราสามารถตรวจสอบได้ว่าถ้า $s_i'\neq s_i$แล้วความน่าจะเป็นที่สมการนี้มีมากที่สุด $1/|\mathbb{F}|$ (สิ่งนี้ใช้ประโยชน์จากข้อเท็จจริงที่ว่า $P_i$ ไม่รู้จักกุญแจ $(\alpha_{ji}, \beta_{ji})$ซึ่งเป็นแบบสุ่ม) ดังนั้น ตราบใดที่ฟิลด์มีขนาดใหญ่พอ $P_j$ จะสามารถกรองหุ้นที่ไม่ถูกต้องออกได้ และสร้างความลับขึ้นมาใหม่จากหุ้นที่ถูกต้องที่เหลืออยู่

สิ่งนี้ช่วยคุณในคำถามที่เป็นรูปธรรมหรือไม่? อย่าลังเลที่จะแสดงความคิดเห็นใด ๆ หากคุณต้องการคำชี้แจงในทิศทางที่แน่นอน

$\textbf{คำถาม:}$ โดยปกติแล้วปัญหามากมายจะกำหนด $s$ เป็นตัวแปรสุ่มที่กระจายอย่างสม่ำเสมอบนฟิลด์ $\mathbb{F}$. ตัวแทนจำหน่ายตามคำตอบที่แจกจ่ายนี้ $s$ ท่ามกลาง $n$ ปาร์ตี้และทุกปาร์ตี้ $i$ เรียนรู้ $s_i$. ผู้เล่น $i$ เรียนรู้ $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n ]})$, ที่ไหน $(\alpha_{ij},\beta_{ij})$ หมายถึงกุญแจคู่หนึ่งสำหรับแต่ละฝ่าย $j\neq ฉัน$. นอกจากนี้, $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ เป็นคู่สุ่มและคำนวณอย่างสม่ำเสมอ $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$. คำถามของฉันคือเราจะมั่นใจได้อย่างไรว่าสำหรับตัวแปรสุ่มทุกชุด $s_i$ เกิน $\mathbb{F}$เราสามารถหาคู่ของตัวแปรสุ่มอื่นๆ $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ ดังนั้น $s_j=(\tau_{ij}-\beta_{ij})\cdot\alpha_{ij}^{-1}$? กล่าวคือ มีผลบางอย่างจากทฤษฎีความน่าจะเป็นที่ทำให้เราสามารถเขียนตัวแปรสุ่มทุกตัวได้ $s_i$ ให้เป็นสูตรที่เทียบเท่ากับการรวมกันของตัวแปรสุ่มอื่น ๆ ถ้า $+$ และ $\cdot$ ถูกกำหนดมากกว่า $\mathbb{F}$?