Cryptology ePrint Archive: Report 2021/1081

OnionPIR: Response Efficient Single-Server PIR

Muhammad Haris Mughees and Hao Chen and Ling Ren

Abstract: This paper presents OnionPIR and stateful OnionPIR two single-server PIR schemes that significantly improve the response size and computation cost over state-of-the-art schemes. OnionPIR scheme utilizes recent advances in somewhat homomorphic encryption (SHE) and carefully composes two lattice-based SHE schemes and homomorphic operations to control the noise growth and response size. Stateful OnionPIR uses a technique based on the homomorphic evaluation of copy networks. OnionPIR achieves a response overhead of just $4.2$x over the insecure baseline, in contrast to the $100$x response overhead of state-of-the-art schemes. Our stateful OnionPIR scheme improves upon the recent stateful PIR framework of Patel et al. and drastically reduces its response overhead by avoiding downloading the entire database in the offline stage. Compared to stateless OnionPIR, Stateful OnionPIR reduces the computation cost by $1.8-22$x for different database sizes.

Category / Keywords: cryptographic protocols / PIR, quantum cryptography, homomorphic encryption

Original Publication (with minor differences): The ACM Conference on Computer and Communications Security (CCS) 2021

Date: received 23 Aug 2021, last revised 20 Sep 2021

Contact author: mughees2 at illinois edu, sxxach at gmail com, renling at illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20210920:132310 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]