ติดตั้ง
เมื่อเร็ว ๆ นี้ฉันเริ่มสนใจ การพิสูจน์ตามการจำลองในบริบทของการคำนวณที่ปลอดภัยของสองฝ่าย. ฉันอ่านหนังสือบางบท (จาก รักษาความปลอดภัย MPC และการแบ่งปันความลับ และ พื้นฐานการเข้ารหัส เล่มที่ 2), กระดาษ (ที่สำคัญที่สุด วิธีการจำลองมัน) และโพสต์จากการแลกเปลี่ยนการเข้ารหัสลับ แต่ฉันยังไม่มั่นใจในการประยุกต์ใช้เทคนิคการพิสูจน์การจำลอง ในขั้นแรก ผมพิจารณาแบบง่ายๆ โปรโตคอลการแบ่งปันความลับเพิ่มเติมกับฝ่ายกึ่งซื่อสัตย์. ที่นั่น ทุกฝ่ายต้องการทวีคูณความลับของพวกเขาและใช้บีเวอร์สามเท่าสำหรับสิ่งนั้น เพื่อให้โปรโตคอลเกี่ยวข้องกับการโต้ตอบบางอย่าง ฉันแบ่งปันที่นี่เพราะอาจเป็นประโยชน์สำหรับผู้เริ่มต้นคนอื่น ๆ และฉันจะขอบคุณมากสำหรับการแก้ไข คำติชม และความคิดเห็น
โปรโตคอลการคูณ
สมมติสองฝ่ายที่ไม่สมรู้ร่วมคิดกันและสมมติข้อมูลเข้า $x,y$ เป็นของคู่กรณี $P_1,P_2$ตามลำดับ แล้ว, $P_1$ คำนวณหุ้น $x_1\leftarrow \mathbb{Z}_q$, $x_2 = x-x_1\,\mathrm{mod}\,q$, ที่ไหน $\leftarrow \mathbb{Z}_q$ หมายถึงการสุ่มตัวอย่างอย่างสม่ำเสมอจาก $\mathbb{Z}_q$และส่ง $x_2$ ถึง $P_2$. สิ่งเดียวกันนี้เกิดขึ้นแบบเดียวกันกับ $y_1,y_2$ ที่ $P_2$ ดังนั้น $P_1$ สามารถเข้าถึง $x_1,y_1$ และ $P_2$ สามารถเข้าถึง $x_2,y_2$ หลังจากขั้นตอนนี้ เพื่อที่จะคำนวณ $xy$, ฝ่ายใช้บีเวอร์สามเท่าดังนี้. ก่อนการดำเนินการของโปรโตคอล เราสุ่มตัวอย่าง $(\alpha,\beta)\leftarrow \mathbb{Z}_q^2$,คำนวณ $\alpha \beta \,\mathrm{mod}\,q = \gamma$ เช่นเดียวกับหุ้น $\alpha_i,\beta_i,\gamma_i$ กับ $i\in\{1,2\}$และแจกจ่ายให้กับพรรคที่เกี่ยวข้อง จากนั้น $i$-th ปาร์ตี้คอมพิวเตอร์
\begin{align*}
\delta_i=x_i-\alpha_i\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon_i=y_i-\beta_i\,\mathrm{mod}\,q
\end{จัดตำแหน่ง*}
และส่ง $\delta_i$ เช่นเดียวกับ $\epsilon_i$ ให้กับอีกฝ่ายหนึ่ง เป็นผลให้ทั้งสองฝ่ายสามารถคำนวณได้
$$
\delta=\delta_1+\delta_2\,\mathrm{mod}\,q=x-\alpha\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon=\epsilon_1+\epsilon_2\, \mathrm{mod}\,q=y-\beta\,\mathrm{mod}\,q
$$
ด้วยสิ่งเหล่านี้ ในที่สุดเราก็ได้รับหุ้นของ $z:=z_1+z_2\,\mathrm{mod}\,q$ ด้วยวิธีการ
\begin{align*}
z_1=\gamma_1+\delta \beta_1 +\epsilon \alpha_1+\delta\epsilon\,\mathrm{mod}\,q \quad \text{and} \quad
z_2=\gamma_2+\delta \beta_2+\epsilon \alpha_2\,\mathrm{mod}\,q.
\end{จัดตำแหน่ง*}
เราไม่เปิดเผย $z_1$ หรือ $z_2$ (แม้ว่าโปรโตคอลจะดูไร้ประโยชน์ด้วยวิธีนี้)
โปรดทราบว่า $x_2,y_1,\delta_1,\delta_2,\epsilon_1,\epsilon_2$ ถูกแลกเปลี่ยนและปริมาณเหล่านี้เป็นตัวเลขสุ่มแบบเดียวกันใน $\mathbb{Z}_q$. การคำนวณอื่น ๆ ทั้งหมดเป็นแบบโลคัล จากนี้ ฉันสรุปได้ว่าโปรโตคอลควรมีความปลอดภัยอย่างสมบูรณ์
การพิสูจน์จากการจำลอง (พยายาม)
เท่าที่ฉันเข้าใจ การพิสูจน์จากการจำลองเป็นสิ่งที่น่าสนใจเป็นพิเศษสำหรับโปรโตคอล ซึ่งนอกเหนือจากการเข้ารหัสแล้ว การคำนวณและการแลกเปลี่ยนข้อมูลอาจเปิดเผยบางสิ่ง จึงควรเหมาะสมกับโปรโตคอลที่ระบุไว้ข้างต้น
มาลองพิสูจน์สัญชาตญาณดังกล่าวข้างต้น (ว่าโปรโตคอลมีความปลอดภัยอย่างสมบูรณ์) อย่างเป็นทางการมากขึ้นโดยใช้สิ่งที่พบได้ใน วิธีการจำลองมัน และ รักษาความปลอดภัย MPC และการแบ่งปันความลับ. ขั้นแรก เราสังเกตว่าโปรโตคอลนั้น (เกือบ) สมมาตรดังนั้นหากพิจารณาเพียงอย่างเดียวก็น่าจะเพียงพอแล้ว $P_1$ จะกึ่งซื่อสัตย์ ถัดไป ฟังก์ชันการทำงาน $f(x,y):=z$ ของโปรโตคอล $\pi$ เป็นตัวกำหนดและตอบสนองความถูกต้อง (ประเมิน $z_1+z_2\,\mathrm{mod}\,q$ สำหรับการตรวจสอบยืนยัน). นอกจากนี้ องค์ประกอบแรกของ $f(x,y)$ เป็น $f_1(x,y):=z_1$ และเราแนะนำมุมมองของ $P_1$ โดย
\begin{align*}
\mathrm{view}_1^{\pi}(x,y):=\left(x,r_1,m_1,m_2,\dots,m_t\right)\in \mathbb{Z}_q^{1\times p },
\end{จัดตำแหน่ง*}
ที่ไหน $r_1$ เป็นเนื้อหาของ $P_1$เทปสุ่มภายในและ $m_1,m_2,\จุด,m_t$ หมายถึงข้อความที่ได้รับ
จากนั้น การพิสูจน์ตามการจำลองเพื่อความปลอดภัยที่สมบูรณ์แบบจำเป็นต้องมีเครื่องจำลองเวลาความน่าจะเป็น-โพลิโนเมียล $S_1$ ดังนั้น
\begin{align*}
\{S_1\left(x,f_1(x,y)\right)\}_{x,y\in\{0,1\}^*} \stackrel{\mathrm{perf}}{\equiv} \ {\mathrm{view}_1^{\pi}\left(x,y\right)\}_{x,y\in\{0,1\}^*}
\end{จัดตำแหน่ง*}
การแยกไม่ออกที่สมบูรณ์แบบระหว่างกลุ่มความน่าจะเป็นเหล่านี้ควรเข้าถึงได้หากเป็นไปได้ทั้งหมด $x,y\in\{0,1\}^*$ สถิติระยะทาง
\begin{สมการ}
\label{eq:dist}
\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y)):=\frac{1}{2} \sum_{\bold symbol{w}\in\ mathbb{Z}_q^{1\times p}} |\mathrm{Pr}(\mathrm{view}_1^{\pi}(x,y)=\bold symbol{w})-\mathrm{Pr}( S_1(x,f_1(x,y)=\bold symbol{w})|
\end{สมการ}
หายไป เราเริ่มต้นด้วยการวิ่ง $\pi$ และตามคำจำกัดความจากก่อนหน้านี้ ค้นหา
$$
\mathrm{view}_1^{\pi}\left(x,y\right)=\left(x,x_1,y_1,\alpha_1,\beta_1,\gamma_1,\delta_2,\epsilon_2\right),
$$
ที่ไหน $x_1$ เกิดจาก $P_1$แหล่งที่มาของการสุ่มภายใน (เทปสุ่ม) $\alpha_1,\beta_1,\gamma_1$ เกิดจากแหล่งที่มาเสริมออฟไลน์ของการสุ่ม (แต่อาจถือเป็นข้อความด้วย?) และ $y_1,\delta_2,\epsilon_2$ เป็นข้อความที่ได้รับจาก $P_2$. โปรดทราบว่านอกเหนือจาก $x$ ปริมาณทั้งหมดเหล่านี้สุ่มอย่างเท่าเทียมกัน $\mathbb{Z}_q$. นอกจากนี้ จาก $\mathrm{view}_1^{\pi}(x,y)$ ปริมาณอื่น ๆ ทั้งหมดนั้น $P_1$ สามารถเข้าถึงได้สามารถคำนวณได้ เพราะฉะนั้น, $\mathrm{view}_1^{\pi}(x,y)$ มีทั้งหมด $P_1$ข้อมูลของ.
มันยังคงค้นหาที่เหมาะสม $S_1$. ด้วยเหตุนี้เราเลือก
$$
S_1(x,f_1(x,y))=\left(x,\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\ gamma}_1,\tilde{\delta}_2,\tilde{\epsilon}_2\right)
$$
เพื่อให้แต่ละส่วนประกอบใน $(\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{ \epsilon}_2)$ เป็นแบบสุ่มอย่างสม่ำเสมอ $\mathbb{Z}_q$ (ดูเหมือนว่าเราไม่ต้องการเอาต์พุต $f_1(x,y)$). ในที่สุดตั้งแต่ $S_1$ สามารถเลียนแบบการแจกแจงของแต่ละองค์ประกอบได้อย่างแน่นอน $\mathrm{ดู}_1^\pi$มันง่ายที่จะเห็นว่า $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))=0$ สำหรับทุกอย่าง $x,y$. กล่าวอีกนัยหนึ่งทุกอย่างนอกเหนือจาก $x$ (ซึ่งมอบให้ $P_1$) แยกไม่ออกจากขยะแบบสุ่ม ดังนั้นเราจึงสรุปได้ว่าโปรโตคอลมีความปลอดภัยอย่างสมบูรณ์
ข้อสังเกต/คำถามบางประการ
- ในบริบทของการคำนวณสองฝ่ายที่ปลอดภัย ดูเหมือนว่าเมื่อใดก็ตามที่ $\mathrm{ดู}_1^\pi$ มีเฉพาะตัวแปรสุ่ม (ยกเว้น $x$) เราสามารถสร้างโปรแกรมจำลองได้โดยเลือกตัวแปรที่มีการแจกแจงแบบเดียวกับตัวแปรสุ่ม สิ่งนี้ทำให้การสร้างเครื่องจำลองเป็นเรื่องเล็กน้อย
- ในกรณีที่หนึ่งตัวแปรใน $\mathrm{ดู}_1^\pi$ ทำหน้าที่ไม่สุ่ม เราต้องสร้างจาก $x,f_1(x,y)$ เพื่อให้ได้เครื่องจำลองที่ถูกต้อง เพื่อจุดประสงค์นี้สมมติว่า $y_1=y$ เพราะ $P_2$ ทำผิดพลาด เห็นได้ชัดว่าสิ่งนี้ไม่ปลอดภัยตั้งแต่นั้นมา $P_1$ ได้เข้าถึงแล้ว $x,y$. อย่างไรก็ตามเฉพาะจาก $x,f_1(x,y)$ เราไม่สามารถสร้างได้ $y$ เพราะ $x$ ไม่มีอะไรเกี่ยวข้องกับ $y$ และ $f_1(x,y)$ เป็นแบบสุ่มอย่างสม่ำเสมอ $\mathbb{Z}_q$ โดยการก่อสร้าง. ดังนั้นโปรโตคอลนี้จึงไม่ปลอดภัยเนื่องจาก $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.
- อะไรคือเหตุผลที่เครื่องจำลองต้องการ $f_1(x,y)$?