Fast Private Retrieval on Key-Value Store with Multiple Values per Key

Querying desired data from the key-value store on a cloud server is a prevalent scenario. Client queries might include sensitive information that the client prefers to keep confidential from the server. This occasion resembles the Keyword Private Information Retrieval (KPIR). Prior works on keyword PIR consider that there are no duplicated key-value pairs in the store, i.e., each key only occurs once with only a single value attached. This is one of the cases in practical applications. However, there is also a typical case where a key may occur multiple times with different values. Straightly applying the existing keyword PIR to this case doesn't work and may finally obtain a false query result. We are the first to extend the setting that keys in the store may appear with different values multiple times. To solve this problem, we propose FEDPIR, a fast single-server keyword PIR protocol that supports querying a large-scale key-value store with multiple values per key. FEDPIR uses a novel encoding and decoding strategy combined with a high-throughput linear homomorphic encryption to improve performance significantly. Our extensive experiments on different store configurations show that our FEDPIR achieves 1.2-65.6x lower query latency and 1.5-37.9x lower cost monetarily compared with the baseline methods.