International Association
for Cryptologic Research

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^Ω(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 4x for benchmarked parameters and reduce memory queries by 23x 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.

BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes. Both schemes have a common plaintext space, with a rich algebraic structure. Our main contribution is to show how this structure can be exploited to more efficiently homomorphically evaluate polynomials. Namely, using Galois automorphisms, we present an algorithm to homomorphically evaluate a polynomial of degree d in only 3 log(d) (in some cases only 2 log(d)) many ciphertext-ciphertext multiplications and automorphism evaluations, where d is bounded by the ring degree. In other words, as long as the degree of the polynomial is bounded, we achieve an exponential speedup compared to the state of the art. In particular, the approach also improves on the theoretical lower bound of 2 sqrt(d) many ciphertext-ciphertext multiplications, which would apply if automorphisms were not available. We investigate how to apply our improved polynomial evaluation to the bootstrapping procedure for BFV, and show that we are able to significantly improve its performance. We demonstrate this by providing an implementation of our improved BFV bootstrapping using the Microsoft SEAL library. More concretely, we obtain a 1.6× speed up compared to the prior implementation given by Chen and Han (Eurocrypt 2018). The techniques are independent of, and can be combined with, the more recent optimisations presented by Geelen et al. (Eurocrypt 2023). As an additional contribution, we show how the bootstrapping approach used in schemes such as FHEW and TFHE can be applied in the BFV context. In particular, we demonstrate that programmable bootstrapping can be achieved for BFV. Moreover, we show how this bootstrapping approach can be improved in the BFV context to make better use of the Galois structure. However, we estimate that its complexity is around three orders of magnitude slower than the classical approach to BFV bootstrapping.