อะไรคือเหตุผลที่โครงการ Shamir ใช้ modulo prime?

ในแผนการแบ่งปันความลับของ Shamir นั้น Dealer ดำเนินการตามขั้นตอนต่อไปนี้

1. เลือกหมายเลขเฉพาะ $คิว$ ดังนั้น $q > n$

2. เลือกความลับ $s$ จากเขตข้อมูลจำกัด $\mathbb{Z}_q$

3. เลือก $t-1$ พหุนามดีกรี

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

4. คำนวณหุ้น $s_i = g(id_i) \mod q \text{ สำหรับ } i=1,2, \cdots,n$ และส่งไปยังผู้เข้าร่วมอย่างลับๆ

5. จำนวนผู้เข้าร่วมขั้นต่ำตามเกณฑ์สามารถสร้างความลับใหม่ได้โดยใช้สูตรการแก้ไข Lagranges

ข้อสงสัยของฉันคือ:

แทนที่จะเป็นขั้นตอนที่ 4 ที่กล่าวถึงข้างต้น ถ้าเราเขียนโดยไม่ $\mod q$ ดังภาพด้านล่างแล้วจะเกิดอะไรขึ้น?

4. คำนวณหุ้น $s_i = g(id_i) , i=1,2, \cdots,n$.

มีประโยชน์อะไรที่จะใช้ $\mod q$ มากกว่าวิธีการไร้เดียงสา (โดยไม่ใช้โมดูโล)? ถ้าใช่ เป็นเรื่องความปลอดภัยหรือความซับซ้อนในการคำนวณหรืออื่นๆ หรือไม่

มีประโยชน์อะไรที่จะใช้ $\bmod q$ มากกว่าวิธีไร้เดียงสา (โดยไม่ใช้โมดูโล)? ถ้าใช่ เป็นเรื่องความปลอดภัยหรือความซับซ้อนในการคำนวณหรืออื่นๆ หรือไม่

ใช่; ทำสิ่งต่างๆ $\bmod q$ มีข้อได้เปรียบในทางปฏิบัติที่หุ้นมีความยาวขอบเขต คำนวณหุ้นใน $\mathbb{Z}$ อาจให้เราส่งค่าที่ค่อนข้างยาว (เนื่องจากค่านั้นไม่มีขอบเขตบน)

อย่างไรก็ตาม ยังมีข้อกังวลด้านความปลอดภัย:

• เผยยอดหุ้นใน $\mathbb{Z}$ ข้อมูลรั่วไหล; เช่น สมมติว่ามีคนรู้ส่วนแบ่ง $(x, y)$ สำหรับ $x=2$ ที่สอดคล้องกับความลับ $z$. นั่นคือเขาได้รับค่า $y = a_n2^n + a_{n-1} 2^{n-1} + ... + a_12^1 + z$. ตอนนี้ เงื่อนไขที่ไม่คงที่ทั้งหมดเป็นเลขคู่ ดังนั้นหากพวกเขาเห็นเช่นนั้น $y$ เป็นเรื่องแปลก นั่นหมายความว่า $z$ ต้องเป็นเลขคี่ด้วย นั่นคือเราเพิ่งรั่วไหลออกมา การขยายข้อสังเกตนี้แสดงให้เห็นว่าการแบ่งปัน $(x, y)$ เผยคุณค่าของ $z \bmod x$. ข้อสังเกตที่คล้ายกันแสดงให้เห็นว่าหุ้นสองตัว $(x_0, y_0)$, $(x_1, y_1)$ ยังเผยให้เห็น $z \bmod x_0 - x_1$. สิ่งนี้ตรงกันข้ามกับ Shamir Secret Sharing มาตรฐานซึ่งไม่มีการรั่วไหลดังกล่าว

• Shamir สันนิษฐานว่าค่าสัมประสิทธิ์ลับ $a_n, a_{n-1}, ..., a_1$ ได้รับเลือกอย่างเท่าเทียมกัน อย่างไรก็ตาม ปรากฎว่าเป็นไปไม่ได้ที่จะเลือกแบบสุ่มอย่างสม่ำเสมอจากชุดขนาด $\aleph_0$ (ซึ่งเป็นชุดของจำนวนเต็ม) นั่นคือ วิธีการเลือกใดๆ จะต้องมีความลำเอียง และขึ้นอยู่กับว่าการกระจายคืออะไร อคตินี้จะรั่วไหลของข้อมูลเพิ่มเติมด้วย

BTW: Shamir Secret Sharing ไม่จำเป็นต้องทำโมดูโลเป็นไพรม์ขนาดใหญ่ สามารถนำไปใช้กับเขตข้อมูล จำกัด ใด ๆ ในทางปฏิบัติ เรามักจะใช้ฟิลด์ลักษณะเฉพาะ เช่น $GF(2^8)$ หรือ $GF(2^{128})$; ความปลอดภัยเหมือนกัน แต่มีข้อได้เปรียบในทางปฏิบัติของทุกสิ่งที่เหมาะสมในจำนวนรวมของไบต์