Cryptology ePrint Archive: Report 2015/113

How to Compress Homomorphic Ciphertexts

Anne Canteaut and Sergiu Carpov and Caroline Fontaine and Tancrède Lepoint and María Naya-Plasencia and Pascal Paillier and Renaud Sirdey

Abstract: 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.

Category / Keywords: Homomorphic cryptography, Ciphertext compression, Trivium, LowMC

Date: received 13 Feb 2015, last revised 24 Feb 2015

Contact author: tancrede lepoint at cryptoexperts com

Available format(s): PDF | BibTeX Citation

Version: 20150224:095450 (All versions of this report)

Short URL: ia.cr/2015/113

Discussion forum: Show discussion | Start new discussion