Improved Filter Permutators: Combining Symmetric Encryption Design, Boolean Functions, Low Complexity Cryptography, and Homomorphic Encryption, for Private Delegation of Computations

Méaux, Pierrick;Carlet, Claude;Journault, Anthony;Standaert, François-Xavier
(2019) Progress in Cryptology - 20th International Conference on Cryptology in India (INDOCRYPT 2019) — Location: Hyderabad (India) (15.December.2019)

Files

ImprovedFilterPermutators-CombiningSymmetricEncryptionDesignBooleanFunctionsLowComplexityCryptographyandHomomor.pdf
  • Open Access
  • Adobe PDF
  • 629.43 KB
Download

Details

Authors
  • Méaux, PierrickUCLouvain
    Author
  • Carlet, ClaudeLAGA, University of Paris 8, France and Department of Informatics, University of Bergen, Norway
    Author
  • Journault, AnthonyUCLouvain
    Author
  • Standaert, François-Xavierorcid-logoUCLouvain
    Author
Abstract
Motivated by the application of delegating computation, we revisit the design of filter permutators as a general approach to build stream ciphers that can be efficiently evaluated in a fully homomorphic manner. We first introduce improved filter permutators that allow better security analyses, instances and implementations than the previously proposed FLIP family of stream ciphers. We also put forward the similarities between these improved constructions and a popular PRG design by Goldreich. Then, we exhibit the relevant cryptographic parameters of two families of Boolean functions, direct sums of monomials and XOR-MAJ functions, which give candidates to instantiate the improved filter permutator paradigm. We develop new Boolean functions techniques to study them, and refine Goldreich’s PRG locality bound for this purpose. We give an asymptotic analysis of the noise level of improved filter permutators instances using both kind of functions, and recommend them as good candidates for evaluation with a third-generation FHE scheme. Finally, we propose a methodology to evaluate the performance of such symmetric cipher designs in a FHE setting, which primarily focuses on the noise level of the symmetric ciphertexts (hence on the amount of operations on these ciphertexts that can be homomorphically evaluated). Evaluations performed with HElib show that instances of improved filter permutators using direct sums of monomials as filter outperform all existing ciphers in the literature based on this criteria. We also discuss the (limited) overheads of these instances in terms of latency and throughput.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Méaux, P., Carlet, C., Journault, A., & Standaert, F.-X. (2019). Improved Filter Permutators: Combining Symmetric Encryption Design, Boolean Functions, Low Complexity Cryptography, and Homomorphic Encryption, for Private Delegation of Computations. Proceedings of INDOCRYPT 2019. Progress in Cryptology - 20th International Conference on Cryptology in India (INDOCRYPT 2019), Hyderabad (India). https://hdl.handle.net/2078.5/120513 (Original work published 2019)