Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts

Pierrick Méaux 1, 2, 3, 4 Anthony Journault 5 François-Xavier Standaert 6 Claude Carlet 7, 8
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
5 Groupe Crypto
ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
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, 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 smaller 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.
Type de document :
Communication dans un congrès
Advances in Cryptology – EUROCRYPT 2016, May 2016, WIEN, Austria. 9665, pp.311-343, Lecture Notes in Computer Science. 〈〉. 〈10.1007/978-3-662-49890-3_13〉
Liste complète des métadonnées
Contributeur : Pierrick Meaux <>
Soumis le : mercredi 30 novembre 2016 - 15:35:54
Dernière modification le : jeudi 11 janvier 2018 - 06:28:02




Pierrick Méaux, Anthony Journault, François-Xavier Standaert, Claude Carlet. Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts. Advances in Cryptology – EUROCRYPT 2016, May 2016, WIEN, Austria. 9665, pp.311-343, Lecture Notes in Computer Science. 〈〉. 〈10.1007/978-3-662-49890-3_13〉. 〈hal-01405859〉



Consultations de la notice