中央研究院 資訊科學研究所

Can we base Private Information Retrieval (PIR) on symmetric-key cryptography? No, because standard PIR implies oblivious transfer (De Crescenzo-Malkin-Ostrovsky, Eurocrypt 2000). How about fine-grained PIR that restricts the adversary's time, similar to the key agreement of Ralph Merkle (CACM 1978)? Unfortunately, Hoover, Persiano, and Yeo (FOCS 2026) recently ruled it out, and their impossibility holds even for PIR that may preprocess the database. The only caveat is that the preprocessing is performed without using cryptographic operations.

Public-key PIR (pk-PIR) is a relaxation of PIR, it is natural yet underexplored. We construct a fine-grained pk-PIR in the random oracle model (ROM), and answered the question positively. Our pk-PIR circumvents the impossibility by using oracle queries during the preprocessing, while otherwise adhering to the Hoover-Persiano-Yeo setting. Our scheme adapts Merkle's key agreement in a non-black-box way. Given the abundant literature on Merkle's protocol, our result is potentially extensible in many directions.

We complement our feasibility by constructing key agreement from pk-PIR. We further construct a more efficient attacker against any pk-PIR in the ROM to clarify the optimality of our fine-grained scheme.