Paper 2024/1307

On Algebraic Homomorphic Encryption and its Applications to Doubly-Efficient PIR

Abstract

The Doubly-Efficient Private Information Retrieval (DEPIR) protocol of Lin, Mook, and Wichs (STOC'23) relies on a Homomorphic Encryption (HE) scheme that is algebraic, i.e., whose ciphertext space has a ring structure that matches the homomorphic operations. While early HE schemes had this property, modern schemes introduced techniques to manage noise growth. This made the resulting schemes much more efficient, but also destroyed the algebraic property. In this work, we study algebraic HE with the goal of improving its performance and thereby also the performance of DEPIR We first prove a lower bound of $2^{\Omega(2^d)}$ for the ciphertext ring size of algebraic HE schemes that can evaluate a circuit of multiplicative depth $d$, thus demonstrating a gap between optimal algebraic HE and the existing schemes, which have a ciphertext ring size of $2^{O(2^{2d})}$. As we are unable to bridge this gap directly, we instead slightly relax the notion of being algebraic. This allows us to construct a practically more efficient relaxed-algebraic HE scheme. We then show that this also leads to a more efficient instantiation and implementation of DEPIR. We experimentally demonstrate run-time improvements of more than 4x and reduce memory queries by more than 8x compared to prior work. Notably, our relaxed-algebraic HE scheme relies on a new variant of the Ring Learning with Errors (RLWE) problem that we call $\{0, 1\}$-CRT RLWE. We give a formal security reduction to standard RLWE, and estimate its concrete security. Both the $\{0, 1\}$-CRT RLWE problem and the techniques used for the reduction may be of independent interest.