เป็นไปได้ไหมที่จะสร้าง OT แบบ 1 ออกจาก N ที่มีความซับซ้อนในการสื่อสารน้อยกว่าอินพุตทั้งหมดของผู้ส่ง

โครงสร้างของ 1-out-of-$n$ โอทีสำหรับ $l$สตริงบิตที่ฉันเคยเห็นมีความซับซ้อนในการสื่อสารตามสัดส่วน $nl$. ฉันสงสัยว่าเป็นไปได้ไหมที่จะทำ OT ด้วยความปลอดภัยที่ใช้งานอยู่และถ่ายโอนน้อยกว่า $O(nl)$ บิต (ฉันไม่สนใจพารามิเตอร์ความปลอดภัยใน $O$-สัญกรณ์ที่นี่)? ส่วนที่สำคัญสำหรับฉันในที่นี้คือการทำให้ราคาถูกกว่าการถ่ายโอนข้อมูลของผู้ส่งไปยังผู้รับ

มีข้อจำกัดโดยธรรมชาติบางประการที่ไม่อนุญาตให้ OT ประเภทนี้ถ่ายโอนบิตน้อยกว่าอินพุตของผู้ส่งหรือไม่ มีขอบเขตล่างของการสื่อสารสำหรับเรื่องนี้หรือไม่?

เพื่อเสริมคำตอบของ Mikero:

• หากคุณต้องการ 1-out-of-$N$ OT บนบิตอินพุตที่เลือก วิธีที่ได้รับ $o(น)$ การสื่อสารสร้างขึ้นจากการทำงานในการดึงข้อมูลส่วนตัวแบบซับลิเนียร์ การแก้ปัญหาส่วนใหญ่ขึ้นอยู่กับ การเข้ารหัสแบบโฮโมมอร์ฟิกอย่างเต็มที่เช่นเดียวกับคำตอบของ Mikero อย่างไรก็ตาม ยังมีการสร้างทางเลือกที่หลากหลายภายใต้สมมติฐานการเข้ารหัสอื่น ๆ เช่น ดีซีอาร์ (ผ่านระบบเข้ารหัส DamgÃ¥rd-Jurik) หรือ DDH และ QR (ใช้ฟังก์ชันแฮชประตูกล)
• หากคุณต้องการ 1-out-of-$N$ หลอก OT (เช่น $N$ อินพุตของผู้ส่งเป็นเอาต์พุตของฟังก์ชันสุ่มเทียมบางตัว) จากนั้นมีโซลูชันทางเลือกอื่นที่มีประสิทธิภาพมากกว่าภายใต้ตัวแปรของสมมติฐาน LPN ดูเช่น งานนี้.
• มีการสร้าง (จำนวนมาก) ของการพิสูจน์ความรู้ที่ไม่มีความรู้พร้อมการสื่อสารแบบซับลิเนียร์ในขนาดของพยาน หากคุณต้องการให้ไม่มีการโต้ตอบ คุณต้องมีสมมติฐานที่ชัดเจน (แบบจำลองสุ่มของ oracle หรือ SNARGs) แต่ถ้าคุณพอใจกับการโต้ตอบ สิ่งเหล่านี้จะเกิดขึ้นจากสมมติฐานง่ายๆ เช่น การมีอยู่ของฟังก์ชันแฮชที่ป้องกันการชนกัน (เช่น ที่นี่). คุณสามารถใช้ระบบพิสูจน์ใดก็ได้ในลักษณะทั่วไปเพื่อเปลี่ยน OT กึ่งซื่อสัตย์ (เช่นระบบในคำตอบของ Mikero) ให้เป็นโครงร่างที่มีการรักษาความปลอดภัยที่ใช้งานอยู่
• หากคุณต้องการทำ 1-out-of-$N$ ด้วยการสื่อสาร น้อยกว่าขนาดฐานข้อมูลเป็นที่ทราบกันดีว่าเป็นไปได้ (แม้ว่าการสื่อสารจะเป็นเพียง เล็กน้อย น้อยกว่า) ภายใต้สมมติฐานทั่วไป: การมีอยู่ของการเรียงสับเปลี่ยนประตูกล (ดู ที่นี่). เพื่อความปลอดภัยที่ใช้งานอยู่ คุณจะต้องมี CRHF เหนือสิ่งอื่นใด

สมมติว่าผู้ส่งมีสตริง $x_1, \ldots, x_n$, แต่ละความยาว $\ell$. ผู้รับมีทางเลือก $y \in \{1, \ldots, n\}$ และต้องการเรียนรู้ (เท่านั้น) $x_y$. โปรโตคอลสามารถดำเนินการได้ดังนี้:

• ตัวรับสัญญาณสร้างคีย์ $k$ สำหรับโครงร่างการเข้ารหัสแบบโฮโมมอร์ฟิกแบบคีย์สมมาตร
• รับ ส่ง $c = \textsf{Enc}(k,y)$.
• ผู้ส่งจินตนาการถึงวงจรบูลีน $f$ สำหรับฟังก์ชั่น $y \mapsto x_y$ -- วงจรนี้มีทั้งหมดของ $x_i$ คุณค่าในตัว
• ผู้ส่งใช้คุณลักษณะการประเมินแบบโฮโมมอร์ฟิคเพื่อคำนวณในเครื่อง $c' = \textsf{Enc}(k,f(y))$.
• ผู้ส่งส่ง $c'$.
• ตัวรับถอดรหัสเพื่อรับ $f(y) = x_y$.

ข้อความเข้ารหัสเพียงสองรายการ (แต่ละรายการเข้ารหัสไฟล์ $\ell$-บิตสตริง) ถูกส่ง ดังนั้นสิ่งนี้อาจมีค่าใช้จ่าย $O(\kappa)+2\ell$ บิตสำหรับโครงร่าง FHE ที่เหมาะสม หมายเหตุ: คุณต้องมีรูปแบบการเข้ารหัสที่เป็นวงจรส่วนตัว เช่น $c'$ ควรเปิดเผยไม่เกิน $ฉ(ย)$แม้กระทั่งกับผู้ถือกุญแจ

โปรโตคอลนี้ปลอดภัยต่อศัตรูกึ่งไม่จริงใจ แต่ก็มีวิธีที่จะขยายไปสู่ความปลอดภัยที่เป็นอันตรายได้เช่นกัน