Có thể xây dựng OT 1 trong số N với độ phức tạp giao tiếp nhỏ hơn toàn bộ đầu vào của người gửi không?

Các công trình xây dựng của 1 trong số$n$ OT cho $l$chuỗi -bit tôi đã thấy có độ phức tạp giao tiếp tỷ lệ thuận với $nl$. Tôi tự hỏi, có thể thực hiện OT với bảo mật tích cực và chuyển ít hơn $O(nl)$ bit (Tôi đang bỏ qua tham số bảo mật trong $O$-ký hiệu ở đây)? Phần quan trọng đối với tôi ở đây là làm cho nó rẻ hơn so với việc chỉ chuyển đầu vào của người gửi sang người nhận.

Có giới hạn cố hữu nào không cho phép loại OT này truyền ít bit hơn đầu vào của người gửi không? Có bất kỳ giới hạn giao tiếp thấp hơn cho điều này?

Giả sử người gửi có chuỗi $x_1, \ldots, x_n$, mỗi chiều dài $\ell$. Người nhận có một sự lựa chọn $y \in \{1, \ldots, n\}$ và muốn học (chỉ) $x_y$. Giao thức có thể tiến hành như sau:

• Người nhận tạo khóa $k$ cho sơ đồ mã hóa đồng cấu hoàn toàn khóa đối xứng.
• Người nhận gửi $c = \textsf{Enc}(k,y)$.
• Người gửi tưởng tượng một mạch boolean $f$ cho chức năng $y \mapsto x_y$ - mạch này có tất cả các $x_i$ các giá trị được xây dựng trong.
• Người gửi sử dụng tính năng đánh giá đồng hình để tính toán cục bộ $c' = \textsf{Enc}(k,f(y))$.
• Người gửi gửi $c'$.
• Người nhận giải mã để có được $f(y) = x_y$.

Chỉ có hai bản mã (mỗi bản mã hóa một $\ell$-bit string) được gửi, vì vậy điều này có thể tốn $O(\kappa)+2\ell$ bit cho sơ đồ FHE phù hợp. Lưu ý: bạn cần một lược đồ mã hóa riêng tư theo mạch -- tức là, $c'$ không nên tiết lộ nhiều hơn $f(y)$, ngay cả với người giữ chìa khóa.

Giao thức này an toàn trước những kẻ thù nửa trung thực, nhưng cũng có nhiều cách để mở rộng nó thành bảo mật độc hại.

Để bổ sung cho câu trả lời của Mikero:

• Nếu bạn muốn 1-trong-$N$ OT trên các bit đầu vào đã chọn, các phương pháp đã biết để nhận $o(N)$ truyền thông được xây dựng dựa trên công việc truy xuất thông tin cá nhân tuyến tính. Hầu hết các giải pháp đều dựa vào mã hóa đồng cấu hoàn toàn, như trong câu trả lời của Mikero. Tuy nhiên, cũng tồn tại nhiều cấu trúc thay thế khác nhau theo các giả định mật mã khác, chẳng hạn như DCR (thông qua hệ thống mật mã DamgÃ¥rd-Jurik), hoặc ĐDDH và QR (sử dụng hàm băm bẫy).
• Nếu bạn muốn 1-trong-$N$ giả ngẫu nhiên OT (tức là $N$ đầu vào của người gửi là đầu ra của một số chức năng giả ngẫu nhiên), thì có các giải pháp thay thế, hiệu quả hơn theo các biến thể của giả định LPN, xem ví dụ: công việc này.
• Tồn tại (nhiều) cấu trúc bằng chứng tri thức không có kiến ​​thức với giao tiếp tuyến tính ở kích thước nhân chứng. Nếu bạn muốn chúng không tương tác, bạn cần có các giả định mạnh (mô hình tiên tri ngẫu nhiên hoặc SNARG) nhưng nếu bạn hài lòng với các tương tác, chúng tồn tại từ các giả định đơn giản như sự tồn tại của các hàm băm chống va chạm (ví dụ: đây). Bạn có thể sử dụng bất kỳ hệ thống bằng chứng nào như vậy theo cách chung để chuyển đổi OT bán trung thực (chẳng hạn như hệ thống trong câu trả lời của Mikero) thành một sơ đồ có bảo mật tích cực.
• Nếu bạn chỉ muốn thực hiện 1 trong số$N$ với giao tiếp nhỏ hơn kích thước cơ sở dữ liệu, điều này được biết là có thể (mặc dù giao tiếp sẽ chỉ khinh bỉ ít hơn) theo các giả định chung: sự tồn tại của hoán vị cửa sập (xem đây). Để bảo mật tích cực, bạn sẽ cần CRHF trên đó.