[2025.04.30] Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries

안녕하세요, 석사과정생 박홍근입니다.

4월 30일에 발표할 논문인 "Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries"의 초록 올려드립니다.

해당 논문은 서버에게 자신이 무엇을 query하는지를 숨길 수 있는 기법인 Private Information Retrieval (PIR)에서 Keyword Query를 Probabilistic Filter인 Binary Fuse Filter (BFF)를 사용하여 경량화기킨 ChalametPIR을 제시하고 있습니다.

감사합니다.

박홍근 드림

Abstract

We introduce ChalametPIR: a single-server Private Information Retrieval (PIR) scheme supporting fast, low-bandwidth keyword
queries, with a conceptually very simple design. In particular, we develop a generic framework for converting PIR schemes for index
queries over flat arrays (based on Learning With Errors) into keyword PIR. This involves representing a key-value map using any
probabilistic filter that permits reconstruction of elements from inclusion queries (e.g. Cuckoo filters). In particular, we make use of
recently developed Binary Fuse filters to construct ChalametPIR, with minimal efficiency blow-up compared with state-of-the-art
index-based schemes (all costs bounded by a factor of ≤ 1.08). Furthermore, we show that ChalametPIR achieves runtimes and
financial costs that are factors of between 6×-11× and 3.75×-11.4× more efficient, respectively, than state-of-the-art keyword PIR approaches,
for varying database configurations. Bandwidth costs are reduced or remain competitive, depending on the configuration. 
Finally, we believe that our application of Binary Fuse filters can have independent value towards developing efficient variants of
related cryptographic primitives (e.g. private set intersection), that already benefit from using less efficient filter constructions.