จัดเรียงรายการหมายเลขจากสองฝ่ายอย่างปลอดภัย

ฉันกำลังมองหาวิธีจัดเรียงรายการตัวเลขสองรายการอย่างปลอดภัย โจทย์ของเศรษฐีเหยาพิจารณาแต่ละฝ่ายด้วยหมายเลขลับหนึ่งหมายเลขและเปรียบเทียบอย่างปลอดภัย มีเอกสารเพิ่มเติมสำหรับปัญหานี้หรือไม่ที่แต่ละฝ่ายมีรายชื่อหมายเลขเดียวและแต่ละฝ่ายจะเรียนรู้ตำแหน่งของแต่ละองค์ประกอบของรายการที่เกี่ยวข้องกับรายการที่ต่อกันซึ่งรวมจากทั้งสองฝ่าย? ฝ่ายหนึ่งจะไม่รู้จำนวนที่แน่นอนของอีกฝ่ายหนึ่ง

ปัญหามี "วิธีแก้ปัญหาง่ายๆ" โดยใช้เทคนิคทั่วไป

1. มีส่วนขยายของปัญหาเศรษฐีของเหยาเกี่ยวกับวิธีการคำนวณอย่างปลอดภัย วงจรใดๆ $C(x, y)$. นี่คือสาขาวิชาทั้งหมด ซึ่งมักจะใช้ชื่อว่า "Secure Computation" หรือ "Multiparty Computation"

2. มีวงจรที่สามารถจัดเรียงอินพุตที่ไปตามชื่อของ เครือข่ายการเรียงลำดับ. ในขณะที่มีทางเทคนิค $O(n \log n)$ (เครือข่ายการเรียงลำดับ AKS + การเรียงลำดับซิกแซก) มีความซับซ้อนทางเทคนิคโดยมีค่าคงที่ที่ไม่ดี ดังนั้นในทางปฏิบัติแล้วการใช้ $O(n (\log n)^2)$ เครือข่ายการเรียงลำดับซึ่งมีจำนวนมาก (พูดว่า Batcher Odd-Even Mergesort)

นี่คือการบอกว่าปัญหาของคุณได้รับการแก้ไขโดยการคำนวณเครือข่ายการเรียงลำดับ (เช่น Batcher Odd-Even Mergesort) โดยใช้เทคนิคการคำนวณทั่วไปของ 2 ฝ่าย

เมื่อพิจารณาถึงการใช้งานโปรโตคอล MPC ดูเหมือนว่า อันนี้โดยมหาวิทยาลัยบอสตันมีการสาธิตที่เกี่ยวข้อง. โดยเฉพาะอย่างยิ่งพวกเขา

1. รวมสองอาร์เรย์อินพุต จากนั้น
2. จัดเรียงผลลัพธ์โดยใช้ Bubblesort

คุณอาจนำโค้ดบางส่วนกลับมาใช้ใหม่ได้ แต่ต้องระมัดระวังเป็นพิเศษ การรับประกันความปลอดภัยของ MPC นั้น

โปรโตคอล MPC เปิดเผยเท่านั้น $C(x,y)$, เช่น.ดีพอ ๆ กับที่ผู้เข้าร่วมทั้งสองฝ่ายให้ข้อมูล $x, y$ ให้กับบุคคลที่สามที่เชื่อถือได้ $T$ที่คำนวณแล้ว $C(x,y)$และบอกคำตอบแก่พวกเขา

ในทางทฤษฎีคุณสามารถใช้โค้ดตัวอย่างด้านบน สลับส่วนที่รวมสิ่งต่างๆ เป็นการต่อข้อมูล แล้วดำเนินการต่อ สิ่งนี้จะนำไปสู่โครงการที่ไม่ปลอดภัยจริง --- กำหนด $x$ และ $C(x,y)$มันเป็นเรื่องเล็กน้อยที่จะกู้คืน $y$.

ฉันอยากจะแนะนำให้มี $C(x,y)$ คำนวณ (ในการจัดเรียงแทนการต่อข้อมูล $x||ย$) เวกเตอร์บิตบ่งชี้ว่าองค์ประกอบของแต่ละฝ่ายควรจบลงที่ใด สิ่งนี้ยังคงเข้ารหัสข้อมูลการสั่งซื้อที่เกี่ยวข้องทั้งหมด แต่ซ่อนการป้อนข้อมูลของแต่ละฝ่ายจากอีกฝ่ายหนึ่ง (ยกเว้นข้อมูลการสั่งซื้อซึ่ง "ต้องรั่วไหล")

สามารถทำได้โดย

1. การแมปแต่ละองค์ประกอบ $t$ ของ $x$ ถึง $2t$,
2. การแมปแต่ละองค์ประกอบ $t$ ของ $y$ ถึง $2t+1$,
3. เชื่อมโยงองค์ประกอบที่แปลงแล้วเหล่านี้เข้าด้วยกัน
4. การเรียงลำดับการต่อข้อมูล
5. การทำแผนที่ $t\mapsto t\bmod 2$ ในตอนท้าย

วงจรนี้คำนวณฟังก์ชันที่ฉันอธิบายไว้ก่อนหน้านี้ และ "แบ่งความสัมพันธ์" ระหว่าง $x$ และ $y$ โดยใส่องค์ประกอบของ $y$ ต่อมาในเวกเตอร์ ทางเลือกนี้เป็นไปตามอำเภอใจ

แน่นอน นี่คือความคิดของฉันเกี่ยวกับวงจรที่เหมาะสม $C$ เพื่อคำนวณซึ่งอาจบรรลุเป้าหมายของคุณ คุณอาจคิดว่ามันรั่วไหลของข้อมูลมากเกินไป และมีวงจรอื่นที่คุณต้องการคำนวณ คุณยังสามารถใช้เทคนิคทั่วไปของ MPC เพื่อทำสิ่งนี้ได้ --- โดยคุณสามารถระบุการคำนวณที่คุณต้องการทำได้

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

อนุญาต $P_0,\จุด, P_{k-1}$ เป็นฝ่ายป้อนข้อมูล $\vec x_0,\dots, \vec x_{k-1}$. กำหนดวงจร $C(x_0,\dots, x_{k-1})$ นั่น

1. แต่ละ $i$ใช้ฟังก์ชัน $t\mapsto kt + i$ ในแต่ละพิกัดของ $x_i$,
2. เชื่อมโยงผลลัพธ์ทั้งหมดเข้าด้วยกัน
3. เรียงลำดับผลลัพธ์ เช่น ด้วยเครือข่ายการเรียงลำดับ
4. คำนวณฟังก์ชัน $t\mapsto t\bmod k$ ในแต่ละองค์ประกอบของเอาต์พุต

ผลลัพธ์จะเป็นเวกเตอร์ที่มีองค์ประกอบใน $\{0,\dots,k-1\}$. เพื่อความง่าย พูดว่า ผลลัพธ์คือ $[0,3,2,2,1,0,1,3]$. สิ่งนี้จะแสดงให้ทั้ง 4 ฝ่ายทราบว่าลำดับที่สัมพันธ์กันของอินพุตของพวกเขาคือ

1. องค์ประกอบที่เล็กที่สุดของปาร์ตี้ 0
2. องค์ประกอบที่เล็กที่สุดของปาร์ตี้ 3
3. องค์ประกอบที่เล็กที่สุดของปาร์ตี้ 2
4. องค์ประกอบที่ใหญ่ที่สุดของปาร์ตี้ 2
5. องค์ประกอบที่เล็กที่สุดของปาร์ตี้ 1
6. องค์ประกอบที่ใหญ่ที่สุดของปาร์ตี้ 0
7. องค์ประกอบที่ใหญ่ที่สุดของปาร์ตี้ 1
8. องค์ประกอบที่ใหญ่ที่สุดของปาร์ตี้ 3

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

• มีผู้เข้าร่วมไม่มากนักในโปรโตคอล "สมรู้ร่วมคิดเพื่อทำลายโปรโตคอล"
• ฝ่ายตรงข้ามมีประสิทธิภาพในการคำนวณและ
• อาจมีช่วง "การตั้งค่าที่เชื่อถือได้"