[2025.12.15] PIANO: Extremely Simple, Single-Server PIR with Sublinear Server Computation

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

메인세미나 발표 자료 업로드 합니다.

Abstract:
We construct a sublinear-time single-server preprocessing Private Information Retrieval (PIR) scheme with an optimal tradeoff between client storage and server computation (up to poly-logarithmic factors). Our scheme achieves amortized ~O(√n) server and client computation and O(√n) online communication per query, and requires ~Oλ(√n) client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme relies only on Pseudo-Random Functions (PRF). To the best of our knowledge, Piano is the first practical single-server sublinear-time PIR scheme, and we outperform the state-of-the-art single-server PIR by 10×-300×. In comparison with the best known two-server PIR scheme, Piano enjoys comparable performance but our construction is considerably simpler. Experimental results show that for a 100GB database and with 60ms round-trip latency, Piano achieves 93ms response time, while the best known prior scheme requires 11s or more.