Paper 2021/731

Pasta: A Case for Hybrid Homomorphic Encryption

Christoph Dobraunig, Lamarr Security Research, Graz, Austria
Lorenzo Grassi, Digital Security Group, Radboud University, Nijmegen
Lukas Helminger, Graz University of Technology / Know-Center GmbH, Graz, Austria
Christian Rechberger, Graz University of Technology, Graz, Austria
Markus Schofnegger, Graz University of Technology, Graz, Austria
Roman Walch, Graz University of Technology / Know-Center GmbH, Graz, Austria
Abstract

The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However, it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We address this situation in several ways. We build an open-source benchmarking framework involving several use cases covering three popular libraries. Using this framework, we explore properties of the respective HHE proposals. It turns out that even medium-sized use cases are infeasible, especially when involving integer arithmetic. Next, we propose Pasta, a cipher thoroughly optimized for integer HHE use cases. Pasta is designed to minimize the multiplicative depth, while also leveraging the structure of two state-of-the-art integer HE schemes (BFV and BGV) to minimize the homomorphic evaluation latency. Using our new benchmarking environment, we extensively evaluate Pasta in SEAL and HElib and compare its properties to 8 existing ciphers in two use cases. Our evaluations show that Pasta outperforms its competitors for HHE both in terms of homomorphic evaluation time and noise consumption, showing its efficiency for applications in real-world HE use cases. Concretely, Pasta outperforms Agrasta by a factor of up to 82, Masta by a factor of up to 6 and Hera up to a factor of 11 when applied to the two use cases.

Note: The accompanying open-source benchmarking framework can be found at https://github.com/IAIK/hybrid-HE-framework.git

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in TCHES 2023
Keywords
homomorphic encryptionhybrid homomorphic encryptionPastaSEALHElibTFHE
Contact author(s)
roman walch @ iaik tugraz at
History
2023-04-06: revised
2021-06-03: received
See all versions
Short URL
https://ia.cr/2021/731
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/731,
      author = {Christoph Dobraunig and Lorenzo Grassi and Lukas Helminger and Christian Rechberger and Markus Schofnegger and Roman Walch},
      title = {Pasta: A Case for Hybrid Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/731},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/731}},
      url = {https://eprint.iacr.org/2021/731}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.