Tôi sẽ tập trung vào bảo mật bán trung thực trong phản hồi này. Bạn có thể chia các giao thức PSI có liên quan thành hai loại:
Trong dựa trên Diffie-Hellman giao thức (bắt nguồn từ Huberman-Franklin-Hogg), các bên phải tính toán một vài số mũ cho mỗi mục trong bộ của họ.
Trong Oblivious-chuyển dựa trên các giao thức (những giao thức hàng đầu trong trường hợp này sẽ là KKRT và Chase-Miao), trước tiên các bên thực hiện vài trăm OT cơ bản (mỗi OT yêu cầu một vài phép lũy thừa), bất kể quy mô của bộ PSI của họ. Mọi thứ xuất hiện sau trong giao thức chỉ sử dụng các thao tác khóa đối xứng hiệu quả hơn nhiều, chẳng hạn như lệnh gọi tới AES/SHA.
Phương pháp Diffie-Hellman luôn có chi phí liên lạc thấp hơn, bất kể bộ PSI lớn đến đâu. Và khi các bộ PSI nhỏ, thời gian để thực hiện một vài phép lũy thừa cho mỗi mục sẽ ít hơn thời gian để thực hiện "OT cơ sở" của các giao thức khác. Nói chung, Diffie-Hellman PSI cho các bộ nhỏ là một quy tắc tuyệt vời của ngón tay cái.
Nhưng nhỏ như thế nào là nhỏ? Bạn đề cập đến các bộ chứa ~ 1000 mặt hàng. Với các bộ có kích thước này, không còn hoàn toàn rõ ràng giao thức nào là tốt nhất. Trong các thử nghiệm mà chúng tôi đã thực hiện trong nhóm nghiên cứu của mình, ngưỡng giới hạn (trong đó các giao thức dựa trên OT trở nên nhanh hơn) chỉ dưới 500 mục trên các mạng rất nhanh và trên 1000 mục trên các mạng rất chậm.Nhưng ngay cả trên các mạng nhanh, sự khác biệt về hiệu suất không có gì đáng lo ngại đối với ứng dụng này: chúng ta đang nói về 0,35 so với 0,25 giây để thực hiện PSI.
Tóm tắt, Tôi khuyên bạn nên triển khai giao thức Diffie-Hellman PSI của Huberman-Franklin-Hogg, vì (1) thời gian chạy đủ gần mức thấp nhất; (2) giao tiếp là thấp nhất; (3) tính đơn giản của giao thức giúp dễ thực hiện hơn.
Chỉnh sửa tháng 12 năm 2021: Gần đây chúng tôi đã xuất bản một cải tiến giao thức Huberman-Franklin-Hogg cho PSI trên các bộ nhỏ. Nó nhanh hơn, sử dụng ít giao tiếp hơn và có bảo mật (độc hại) mạnh hơn. Đây sẽ là khuyến nghị mới nhất của tôi.
Để trả lời câu hỏi của bạn về PSI đa bên: Hiện tại khá dễ dàng để chuyển đổi hầu hết các giao thức PSI 2 bên thành đa bên.
Hầu hết các giao thức PSI được xây dựng từ một PRF ẩn bên dưới (trong Diffie-Hellman PSI, PRF ẩn là $x \mapsto H(x)^k$ ở đâu $H$ là một tiên tri ngẫu nhiên). Trong KMPRT chúng tôi đã chỉ ra cách xây dựng PSI đa bên từ OPRF 2 bên. Một trong những cấu trúc được bảo mật trước những kẻ thù bán trung thực và cấu trúc còn lại có thuộc tính bảo mật với bản in đẹp hơn. trong một giấy sẽ xuất hiện tại Crypto 2021, chúng tôi cho thấy rằng cấu trúc thứ hai này trên thực tế an toàn trước các đối thủ độc hại.
Nhìn chung, PSI nhiều bên về cơ bản liên quan đến việc mỗi bên thực hiện PSI 2 bên đã sửa đổi với một bên trung tâm (bên nhận đầu ra).
