International Association
for Cryptologic Research

In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob\'s public key pk and to send the ciphertext c = HE_pk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c′ = (HE_pk(k), E_k(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit.

In this paper, we revisit that paradigm in light of its concrete implementation constraints; in particular E is chosen to be an additive IV-based stream cipher. We propose 2 new designs such that the decryption circuit has very small multiplicative depth, typically between 8 and 12 for 128-bit security. Our first construction of depth 12 is inspired by Trivium and reportedly the current fastest option. Our second construction, based on exponentiation in binary fields, is impractical but sets the lowest depth record to 8 for 128-bit security.