จะแปลงโมดูลัสการแบ่งปันความลับได้อย่างไร?

สมมติ $ค$ เป็นเบอร์ลับใน $Z_p$ และ $c = a + b$. อลิซมี $a$ และบ๊อบมี $ข$. มีวิธีใดในการแปลงโมดูโล $p$ เพื่อบางคน $คิว$, ($c<q$, $ค<p$)? กล่าวคือ, $c = a' + b'$ ใน $Z_q$ และ $a'$, $ข'$ เป็นที่รู้จักโดยอลิซและบ็อบตามลำดับ

สมมติว่า $p$ และ $คิว$ เป็นจำนวนเฉพาะที่แตกต่างกัน (ถ้า $คิว$ แบ่ง $p$เช่น ปัญหาเป็นเรื่องเล็กน้อย) โดยปกติการแปลงโมดูลัสจะไม่ใช่งานที่ง่ายในบริบทของการแบ่งปันความลับกรณีการใช้งานที่พบบ่อยที่สุดสำหรับประเภทดั้งเดิมนี้คือ ใช้เวลาสักหน่อย $b\in\{0,1\}$ ที่เป็นความลับร่วมกับนายกขนาดใหญ่ $p$ เช่น $b = a+b\bmod p$และเปลี่ยนเป็นหุ้นบวกเลขฐานสอง $b = a'+b'\b mod 2$ (ซึ่งในที่สุด $b = a'\oบวก b'$. มีแอปพลิเคชันมากมาย เช่น เมื่อคุณต้องการจัดการกับการดำเนินการที่ไม่ใช่เลขคณิตใน Secure Multiparty Computation (เช่น การเปรียบเทียบที่ปลอดภัย การตัดทอน ฟังก์ชันทางคณิตศาสตร์ เป็นต้น)

แนวทางส่วนใหญ่ในการทำงานของการแปลงอย่างปลอดภัยเป็นไปตามเทคนิคนี้ ให้เราแสดงว่า $[x]_p$ เมื่อมีค่า $x$ เป็นโมดูโลที่ใช้ร่วมกันอย่างลับๆ $p$. เป้าหมายของเราคือการได้รับ $[x\bmod q]_q$. สมมติว่าฝ่ายต่างๆ มีหุ้นที่มีมูลค่าสุ่มอยู่แล้ว $r$ไม่รู้จักฝ่ายใดฝ่ายหนึ่ง โดยใช้โมดูลทั้งสอง $p$ และ $คิว$. กล่าวอีกนัยหนึ่งถือว่าคู่กรณีมี $[r]_p$ และ $[r]_q$. จากนั้นคู่สัญญาสามารถดำเนินการได้ดังนี้

1. คำนวณหุ้นในเครื่องของ $x-r$ โมดูโล $p$ โดยการลบหุ้นของพวกเขาในเครื่อง $x$ ด้วยหุ้นของพวกเขา $r$.
2. ส่งหุ้นของพวกเขาจาก $x-r$ ซึ่งกันและกันเพื่อให้แต่ละฝ่ายได้เรียนรู้ $x-r$. สิ่งนี้ทำให้ $x$ ซ่อนไว้เพราะถูกสวมหน้ากาก $r$ซึ่งเป็นการสุ่มอย่างสม่ำเสมอและไม่รู้จักฝ่ายใดฝ่ายหนึ่ง
3. หนึ่งในฝ่ายเสริม $(x-r\bmod q)$ ให้กับส่วนแบ่งของเขา/เธอ $r$ โมดูโล $คิว$, ซึ่งนำไปสู่ $[r]_q + (x-r) = [x\bmod q]_q$.

สิ่งนี้ถือว่าฝ่ายต่างๆสามารถเข้าถึงทั้งคู่ได้ $([r]_p, [r]_q)$แต่ในหลายกรณีนี้ไม่ใช่เรื่องง่ายที่จะได้รับ ตัวอย่างเช่น ถ้า $q=2$คุณจะพบเทคนิคบางอย่างที่อาจเป็นประโยชน์ ที่นี่. ทั้งหมดนี้ยิ่งซับซ้อนมากขึ้นเมื่อการรักษาความปลอดภัยที่ใช้งานอยู่ในภาพ