Các cuộc tấn công cụ thể vào Truy xuất thông tin cá nhân (PIR)

Các giao thức Truy xuất Thông tin Cá nhân (PIR) đã được nghiên cứu trong nhiều năm. Câu hỏi sau đây chỉ liên quan đến kịch bản máy chủ duy nhất.

Giả sử có $N$ tổng số mục ở phía máy chủ, theo định nghĩa bảo mật, có vẻ như tất cả $N$ các mục nên được "chạm" (về mặt giao tiếp hoặc tính toán) vì lý do bảo mật. Nhưng kể từ khi $N$ thường lớn, ai đó có thể hỏi những loại TẤN CÔNG BÊ TÔNG tồn tại khi chỉ "chạm" vào một cái nhỏ hơn $n\ll N$.

Ví dụ: để máy chủ sử dụng hàm băm $h$ trên mỗi mục $x$, và chỉ sử dụng cái đầu tiên $\alpha$ bit của $h(x)$ để xác định $n$ các mặt hàng giống nhau $\alpha$tiền tố -bit để lọc $n$ mục dữ liệu ra. Sau đó, thực hiện PIR trên những $n$ mục thay vì tất cả $N$ các mục trên máy chủ.

Tái bút: Tôi biết phương pháp trên là không chính xác về mặt lý thuyết (gian lận), nhưng tôi không thể đưa ra lời giải thích hay hoặc ví dụ phản bác mạnh mẽ để minh họa rằng sẽ tồn tại các lỗi bảo mật nghiêm trọng đối với những người không phải là chuyên gia về bảo mật và mật mã.