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

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

연구 분야: Cryptography

학회: Annual International Conference on the Theory and Applications of Cryptographic Techniques

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. Since modern, well-studied HE schemes are not algebraic, an important prerequisite for practical DEPIR is to find an efficient algebraic HE scheme. In this work, we study the properties of algebraic HE and try to make progress in solving this problem. We first prove a lower bound of \(2^{\varOmega (2^d)}\) for the ciphertext ring size of post-quantum algebraic HE schemes (in terms of the depth d of the evaluated circuit), which demonstrates 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, which indeed leads to a more efficient instantiation and implementation of DEPIR. We experimentally demonstrate run-time improvements of more than \(4\times \) for benchmarked parameters and reduce memory queries by \(23\times \) for larger parameters 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 from 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.