Paper 2016/254

Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts

Pierrick Méaux, Anthony Journault, François-Xavier Standaert, and Claude Carlet

Abstract

Symmetric ciphers purposed for Fully Homomorphic Encryption (FHE) have recently been proposed for two main reasons. First, minimizing the implementation (time and memory) overheads that are inherent to current FHE schemes. Second, improving the homomorphic capacity, \textit{i.e.} the amount of operations that one can perform on homomorphic ciphertexts before bootstrapping, which amounts to limit their level of noise. Existing solutions for this purpose suggest a gap between block ciphers and stream ciphers. The first ones typically allow a constant but small homomorphic capacity, due to the iteration of rounds eventually leading to complex Boolean functions (hence large noise). The second ones typically allow a larger homomorphic capacity for the first ciphertext blocks, that decreases with the number of ciphertext blocks (due to the increasing Boolean complexity of the stream ciphers' output). In this paper, we aim to combine the best of these two worlds, and propose a new stream cipher construction that allows constant and small(er) noise. Its main idea is to apply a Boolean (filter) function to a public bit permutation of a constant key register, so that the Boolean complexity of the stream cipher outputs is constant. We also propose an instantiation of the filter function designed to exploit recent (3rd-generation) FHE schemes, where the error growth is quasi-additive when adequately multiplying ciphertexts with the same amount of noise. In order to stimulate further investigation, we then specify a few instances of this stream cipher, for which we provide a preliminary security analysis. We finally highlight the good properties of our stream cipher regarding the other goal of minimizing the time and memory complexity of calculus delegation (for 2nd-generation FHE~schemes). We conclude the paper with open problems related to the large design space opened by these new constructions.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
Stream CiphersHomomorphic cryptography
Contact author(s)
meaux @ di ens fr
History
2016-03-08: received
Short URL
https://ia.cr/2016/254
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/254,
      author = {Pierrick Méaux and Anthony Journault and François-Xavier Standaert and Claude Carlet},
      title = {Towards Stream Ciphers for Efficient FHE  with Low-Noise Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2016/254},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/254}},
      url = {https://eprint.iacr.org/2016/254}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.