สูตรทางคณิตศาสตร์สำหรับระบบเข้ารหัสลับ

ฉันจะพยายามกำหนดง่าย ๆ ว่า ระบบการเข้ารหัสของบทความนี้. ผู้เขียนออกแบบเกมการสื่อสารสำหรับ $N$ ผู้เล่น ข้อมูลส่วนตัวของผู้เล่นทุกคนจะแสดงเป็น $t_i\ใน T_i$ และแสดงถึงประเภทของผู้เล่น $i$. ระบบการเข้ารหัสที่ผู้เล่นใช้ในการสื่อสารขึ้นอยู่กับการรายงานการติดต่อต่อไปนี้

$\textbf{การรายงานการติดต่อ:}$ อนุญาต $\mathcal{R}_i$ เป็นชุดที่ไม่ว่างเปล่า มีขอบเขตจำกัด และกำหนดการโต้ตอบการรายงาน $R_i : T_i\to 2^{\mathcal{R}_i}-\{\emptyset\}$ เพื่อเป็นแผนที่จากผู้เล่น $i$âs พิมพ์ช่องว่างเพื่อรวบรวมชุดย่อยของ $\mathcal{R}_i$. องค์ประกอบ $r\in\mathcal{R}_i$ เรียกว่าข้อความขึ้นกับประเภทและ $R_i(t_i)$ คือชุดของข้อความที่ขึ้นกับประเภทที่สามารถพิมพ์ได้ $t_i$ ของผู้เล่น $i$. ข้อความขึ้นอยู่กับประเภทรับรองคำชี้แจงของผู้เล่นเกี่ยวกับประเภทของเขา ตัวอย่างเช่น ถ้า $S\ใน T_i$ เป็นชุดของประเภทผู้เล่น $i$ ใครสามารถส่งข้อความ $r\ใน R_i$, แล้ว $r$ รับรองข้อความประเภท âmy type is in $S$. ชุด $S$ จึงเรียกว่าเหตุการณ์ที่ได้รับการรับรอง

$\textbf{การกำหนดค่าการรับรอง:}$ อนุญาต $E_i\subseteq 2^{T_i}-\{\emptyset\}$ เป็นเซตย่อยของ $T_i$ ที่ปิดอยู่ใต้ทางแยก. การกำหนดค่าการรับรองคือ $N$-tuple ของการติดต่อรายงานเฉพาะ $C_i:T_i\ถึง E_i$ สำหรับทุกๆ $i = 1, ..., N$, กับ $$C_i(t_i)=\{e_i\in E_i|t_i\in e_i\},\quad\text{$\forall t_i\in T_i$} $$

การติดต่อเพื่อรายงานเหล่านี้มีคุณสมบัติที่มีประโยชน์มากสองประการ ประการแรก แต่ละข้อความจะเหมือนกับเหตุการณ์ที่รับรอง ประการที่สอง เหตุการณ์ใด ๆ ที่ได้รับการรับรองโดยการรวมกันของข้อความใน $C_i(t_i)$ รวมอยู่ในชุดด้วย

อนุญาต $R=(R_i)_{i\in I}$ เป็นโปรไฟล์ตามอำเภอใจในการรายงานการติดต่อ และสำหรับผู้เล่นทุกคน $i\ใน I$, อนุญาต $E_i^R$ หมายถึงชุดที่เล็กที่สุดที่มี $\{R^{-1}(r_i)|r_i\in \mathcal{R}_i\}$ และปิดอยู่ใต้ทางแยก $E_i^R$ เป็นชุดของเหตุการณ์ทั้งหมดที่ผู้เล่น $i$ สามารถรับรองด้วย $R_i$. โปรไฟล์ $R$ สามารถเชื่อมโยงกับการกำหนดค่าการรับรองโดยไม่ซ้ำกัน $C_R=(C_i^R)_{i\in I}$, ที่ไหน $$C_i^R(t_i)=\{e_i\in E_i^R|t_i\in e_i\}$$

การกำหนดค่าการรับรอง $C_i^R$ ของ $R$ แสดงข้อมูลที่รับรองได้อย่างชัดเจนเป็นเหตุการณ์ในพื้นที่ประเภทผู้เล่น

$\textbf{การเข้ารหัส:}$ อนุญาต $C=(C_i)_{i\in I}$ เป็นการกำหนดค่าการรับรอง หากมีการเข้ารหัสข้อมูลที่ตรวจสอบได้สำหรับทุกๆ $i\ใน I$, รับรองทุกงาน $e_i\ใน E_i$ ถูกเข้ารหัสโดยใช้อัลกอริธึมการเข้ารหัสที่เรียกว่ารหัส ตัวเลขคือแผนที่ $Ï_i: E_i à Y_i â X_i$ ที่มีการป้อนข้อมูลส่วนตัว $e_i$ และข้อมูลเพิ่มเติม $y_i\ ใน Y_i$เรียกว่าคีย์และสร้างเป็นเอาต์พุตรหัส $x_i\ใน X_i$. สันนิษฐานว่าชุดของคีย์ $Y_i$ มีขนาดใหญ่เพียงพอเช่น $|Y_i| ⥠|E_i|$และนั่นสำหรับแต่ละคน $y_i\ ใน Y_i$ การทำแผนที่ $Ï(\cdot, y_i)$ เป็น bijective เพื่อให้ทุกคู่ $(x_i, y_i)$ มีความเกี่ยวข้องกับเหตุการณ์ที่ได้รับการรับรองเพียงเหตุการณ์เดียว $e_i$. เมื่อข้อมูลของผู้เล่นถูกเข้ารหัส ข้อความที่ขึ้นกับประเภทจะเป็นคู่ที่ประกอบด้วยโค้ดและคีย์ ในเวลาที่ผู้เล่นเรียนรู้ประเภทของพวกเขา ธรรมชาติจะเลือกรหัสลับต่อสาธารณะ $Ï_i$ สำหรับผู้เล่น $i\ใน I$ และรหัสส่วนตัว $y_i$ สม่ำเสมอจากชุด $Y_i$. ผู้เล่น $i$จดหมายโต้ตอบรายงานนั้นมอบให้โดย

$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=Ï_i(e_i, y_i), e_i\in C_i(t_i)\}$$

การตีความตามธรรมชาติของข้อความใน $R_i$ เป็นชิ้นส่วนของหลักฐานเข้ารหัสเกี่ยวกับผู้เล่น $i$ประเภท ซึ่งจัดทำโดยบุคคลที่สามที่เชื่อถือได้ซึ่งใช้รหัสลับที่เปิดเผยต่อสาธารณะและคีย์ส่วนตัวเพื่อเข้ารหัสข้อมูล โปรดทราบว่าหาก $C=C^R$จากนั้นโปรไฟล์ $R(\cdot)=(R_i(\cdot))_{i\in I}$ และ $\hat{R}(\cdot,y)=(\hat{R}_i(\cdot,y_i))_{i\in I}$ มีการกำหนดค่าการรับรองร่วมกันสำหรับทุกคีย์รวมกัน $y\in(Y_i)_{i\in I}$

อนุญาต $E^R=(E_i^R)_{i\in I}$ เป็นรายละเอียดของชุดเหตุการณ์ที่ได้รับการรับรองจาก $R$. ชุด $E_i^R$ มีขอบเขตจำกัด ดังนั้นองค์ประกอบทั้งหมดอาจถูกระบุตามลำดับโดยพลการโดยมีดัชนีจาก $1$ เป็นจำนวนเต็มบวก $n_i$. เหตุการณ์ที่ได้รับการรับรองแต่ละรายการสามารถเชื่อมโยงกับดัชนีได้ เช่น ตัวเลขในชุด $\{1,...,n_i\}$. ฉันจะเขียน $z_i(อี_ไอ)$ เพื่ออ้างถึงหมายเลขที่แสดงถึงเหตุการณ์ $e_i$ และฉันจะเขียนโดยใช้สัญกรณ์ในทางที่ผิดเล็กน้อย $e_i(z_i)$ เพื่ออ้างถึงเหตุการณ์ที่มีดัชนีเท่ากับ $z_i$.

จำเป็นต้องมีบทแทรกต่อไปนี้

$\textbf{บทแทรก:}$ ถ้า $z_i$ เป็นตัวแปรสุ่มที่มีการสนับสนุน $\{1,...,n_i\}$ และ $y_i$ มีการกระจายอย่างสม่ำเสมอ $\{1,...,n_i\}$ เป็นอิสระจาก $z_i$แล้วตัวแปรสุ่ม $x_i$ ที่กำหนดโดย $x_i=z_iây_i(mod{n}_i)$ ยังกระจายตัวอย่างสม่ำเสมอ $\{1,...,n_i\}$.

ที่นี่, $z_i$ แสดงถึงเหตุการณ์ที่ได้รับการรับรอง $y_i$ แสดงถึงคีย์และ $x_i$ เป็นรหัสที่สร้างขึ้นโดยรหัส $Ï_i(e_i,y_i)=z_i(e_i)ây_i(mod{n}_i)$. ตอนนี้สมมติว่าผู้เล่น $i$ข้อมูลส่วนตัวของเขาถูกเข้ารหัสและการติดต่อรายงานของเขาถูกเข้ารหัส

$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=z_i(e_i)ây_i(mod{n}_i), e_i\in C_i(t_i)\}$ $

เพื่อให้ผู้เล่น $i$ สามารถส่งคู่ $(x_i,y_i)$ ถ้าเหตุการณ์ $e_i$ แสดงโดย $z_i=x_i+y_i(mod{n}i)$ อยู่ใน $C_i^R(t_i)$. การกำหนดค่าการรับรองที่สร้างขึ้นด้วยวิธีนี้ เหมือนกับการกำหนดค่าการรับรองของ $R$: ถ้าเฉพาะประเภทของผู้เล่น $i$ ใครรับรองได้ $e_i$ กับ $R_i$ สามารถส่งคู่ $(x_i, y_i)$ ที่ตอบสนอง $z_i=x_i+y_i(mod{n}_i)$แล้วส่งคู่ดังกล่าวเท่ากับรับรอง $e_i$. โดยเล็มมา $1$, ทั้งสอง $x_i$ และ $y_i$ มีการกระจายอย่างสม่ำเสมอทั่ว $\{1,...,n_i\}$, และด้วยเหตุนี้, โดยส่วนตัว, $x_i$ และ $y_i$ ไม่มีข้อมูลเกี่ยวกับ $e_i$.

$\textbf{คำถาม:}$ หากเราถือว่าในกรณีของโครงสร้างทางคณิตศาสตร์ข้างต้น ตัวเลขที่กำหนดเป็น bijective โดยที่ทุกคู่ $(x_i,y_i)$ อ้างถึงสมการเชิงเส้นเช่นนั้น $h(x)=ขวาน+b$, $b=e_i$. ถ้าผู้เล่นสองคนรู้ $(x_i,y_i)$ สามารถรวมพวกเขาและนำสิ่งที่พลาดไปให้กับพวกเขาได้ $x_i+y_i(พยักหน้า{n}_i)=z_i(e_i)\quad\text{หรือ $e_i(z_i)$}$. ดังนั้นในกรณีที่เราใช้เวลา $h$ พหุนามของดีกรี $t<2N$ ดังนั้น

$$h(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0,\quad\text{โดยที่ $a_0=e_i(z_i)$}$$

สิ่งที่เป็นตัวแทนเทียบเท่าของ $\rho_i$ซึ่งรู้ว่าจำเป็น $t+1$ คู่ที่จะคำนวณ $h(x)$ โดยมีระยะเวลาคงที่ $e_i(z_i)$ (ซึ่งโดยเนื้อแท้แล้วหมายความว่า $t+1$ คู่ $(x_i,y_i)$ มีความเกี่ยวข้องเพียงหนึ่งเดียว $e_i$ (ทรรศนะ))?

กล่าวอีกนัยหนึ่งคำถามจะเปลี่ยนไปในคำถามที่เทียบเท่ากันซึ่งระบุว่า: "ใครสามารถช่วยในการแสดงพหุนามอย่างง่ายของรหัส $\rho_i$"?

$\textbf{คำใบ้:}$ ด้วยสัญกรณ์ในทางที่ผิดเล็กน้อยฉันคิดว่าผู้เขียนใช้ $\{1,...,n_i\}$ แทน $\{0,1,...,n_i-1\}$.

แค่คิด...ในกรณีที่รหัสใช้ค่ามากกว่าเป็นคีย์หรือรหัส นี่ไม่ได้หมายความว่าคุณกำลังทำงานในโครงการที่ใช้โปรโตคอล BGW หรือไม่ กล่าวคือด้วยคีย์เดียวและรหัสเดียวหมายความว่าคุณมีการทำแผนที่แบบลีนาร์สำหรับรหัส $\rho_i$ อย่างไรก็ตาม เมื่อคุณมีคะแนนมากขึ้น คุณจะทำงานกับพหุนาม หากเป็นกรณีนี้ คุณสามารถสรุปโครงร่างการทำงานสำหรับรหัสพหุนามได้ และสิ่งนี้อาจคงคุณสมบัติที่คุณต้องการไว้ และนี่คือกลไกใหม่

ปล. ลักษณะทั่วไปของการพิสูจน์โปรโตคอล BGW ถ้ามีใครสามารถช่วยคุณด้วยคณิตศาสตร์และคำจำกัดความ ...

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