Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space

Pierrick Méaux; Jeongeun Park; Hilder V. L. Pereira

doi:10.62056/anxrxrxqi

Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space

Authors

Pierrick Méaux, Jeongeun Park, Hilder V. L. Pereira

Pierrick Méaux

University of Luxembourg, Esch sur Alzette, Luxembourg
pierrick dot meaux at uni dot lu

Jeongeun Park

Norwegian University of Science and Technology (NTNU), Trondheim, Norway
jeongeun dot park at ntnu dot no

Hilder V. L. Pereira

University of Campinas (UNICAMP), Campinas, Brazil
hilder at unicamp dot br

Abstract

Fully Homomorphic Encryption (FHE) is a powerful tool to achieve non-interactive privacy preserving protocols with optimal computation/communication complexity. However, the main disadvantage is that the actual communication cost (bandwidth) is high due to the large size of FHE ciphertexts. As a solution, a technique called transciphering (also known as Hybrid Homomorphic Encryption) was introduced to achieve almost optimal bandwidth for such protocols. However, all existing works require clients to fix a precision for the messages or a mathematical structure for the message space beforehand. It results in unwanted constraints on the plaintext size or underlying structure of FHE based applications.

In this article, we introduce a new approach for transciphering which does not require fixed message precision decided by the client, for the first time. In more detail, a client uses any kind of FHE-friendly symmetric cipher for $\{0,1\}$ to send its input data encrypted bit-by-bit, then the server can choose a precision $p$ depending on the application and homomorphically transforms the encrypted bits into FHE ciphertexts encrypting integers in $\mathbb{Z}_p$. To illustrate our new technique, we evaluate a transciphering using FiLIP cipher and adapt the most practical homomorphic evaluation technique [CCS'22] to keep the practical latency. As a result, our proof-of-concept implementation for $p$ from $2^2$ to $2^8$ takes only from $13$ ms to $137$ ms.

References

[AMT22]

Tomer Ashur, Mohammad Mahzoun, and Dilara Toprakhisar. Chaghri - a fhe-friendly block cipher. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS '22, 139–150. New York, NY, USA, 2022. Association for Computing Machinery. https://doi.org/10.1145/3548606.3559364.

Google Scholar ePrint

[AOSV23]

Adi Akavia, Neta Oren, Boaz Sapir, and Margarita Vald. CSHER: a system for compact storage with HE-Retrieval. In 32nd USENIX Security Symposium (USENIX Security 23), 4751–4768. Anaheim, CA, 2023. USENIX Association. https://doi.org/10.5555/3620237.3620503.

Google Scholar ePrint

[APS15]

Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. https://doi.org/doi:10.1515/jmc-2015-0016.

Google Scholar ePrint

[ARS⁺15]

Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, 430–454. Sofia, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-662-46800-5_17.

Google Scholar ePrint

[BDGM19]

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019: 17th Theory of Cryptography Conference, Part II, volume 11892 of Lecture Notes in Computer Science, 407–437. Nuremberg, Germany, December 1–5, 2019. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-36033-7_16.

Google Scholar ePrint

[BGV12]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science, 309–325. Cambridge, MA, USA, January 8–10, 2012. Association for Computing Machinery. https://doi.org/10.1145/2090236.2090262.

Google Scholar ePrint

[BIP⁺22]

Charlotte Bonte, Ilia Iliashenko, Jeongeun Park, Hilder V. L. Pereira, and Nigel P. Smart. FINAL: faster FHE instantiated with NTRU and LWE. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part II, volume 13792 of Lecture Notes in Computer Science, 188–215. Taipei, Taiwan, December 5–9, 2022. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-031-22966-4_7.

Google Scholar ePrint

[BOS23]

Thibault Balenbois, Jean-Baptiste Orfila, and Nigel P. Smart. Trivial transciphering with trivium and TFHE. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, 69–78. ACM, 2023. https://doi.org/10.1145/3605759.3625255.

Google Scholar ePrint

[BPM22]

Matthieu Brabant, Olivier Pereira, and Pierrick Méaux. Homomorphic encryption for privacy-friendly augmented democracy. In 2022 IEEE 21st Mediterranean Electrotechnical Conference (MELECON), volume, 18–23. 2022. https://doi.org/10.1109/MELECON53508.2022.9843009.

Google Scholar ePrint

[CCF⁺16]

Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrède Lepoint, María Naya-Plasencia, Pascal Paillier, and Renaud Sirdey. Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression. In Thomas Peyrin, editor, Fast Software Encryption – FSE 2016, volume 9783 of Lecture Notes in Computer Science, 313–333. Bochum, Germany, March 20–23, 2016. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-662-52993-5_16.

Google Scholar ePrint

[CCR19]

Hao Chen, Ilaria Chillotti, and Ling Ren. Onion ring ORAM: efficient constant bandwidth oblivious RAM from (leveled) TFHE. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019: 26th Conference on Computer and Communications Security, 345–360. London, UK, November 11–15, 2019. ACM Press. https://doi.org/10.1145/3319535.3354226.

Google Scholar ePrint

[CDNP23]

Kelong Cong, Debajyoti Das, Georgio Nicolas, and Jeongeun Park. Panacea: non-interactive and stateless oblivious ram. 2023.

Google Scholar ePrint

[CDPP22]

Kelong Cong, Debajyoti Das, Jeongeun Park, and Hilder V.L. Pereira. Sortinghat: efficient private decision tree evaluation via homomorphic encryption and transciphering. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS '22, 563–577. New York, NY, USA, 2022. Association for Computing Machinery. https://doi.org/10.1145/3548606.3560702.

Google Scholar ePrint

[CGGI16]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, Part I, volume 10031 of Lecture Notes in Computer Science, 3–33. Hanoi, Vietnam, December 4–8, 2016. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-662-53887-6_1.

Google Scholar ePrint

[CGGI20]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91, January 2020. https://doi.org/10.1007/s00145-019-09319-x.

Google Scholar ePrint

[CHK⁺21]

Jihoon Cho, Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Joohee Lee, Jooyoung Lee, Dukjae Moon, and Hyojin Yoon. Transciphering framework for approximate homomorphic encryption. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part III, volume 13092 of Lecture Notes in Computer Science, 640–669. Singapore, December 6–10, 2021. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-92078-4_22.

Google Scholar ePrint

[CHMS22]

Orel Cosseron, Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. Towards case-optimized hybrid homomorphic encryption - featuring the elisabeth stream cipher. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part III, volume 13793 of Lecture Notes in Computer Science, 32–67. Taipei, Taiwan, December 5–9, 2022. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-031-22969-5_2.

Google Scholar ePrint

[CJP21]

Ilaria Chillotti, Marc Joye, and Pascal Paillier. Programmable bootstrapping enables efficient homomorphic inference of deep neural networks. In Shlomi Dolev, Oded Margalit, Benny Pinkas, and Alexander Schwarzmann, editors, Cyber Security Cryptography and Machine Learning, 1–19. Cham, 2021. Springer International Publishing. https://doi.org/10.1007/978-3-030-78086-9_1.

Google Scholar ePrint

[CKKS17]

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, 409–437. Hong Kong, China, December 3–7, 2017. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-319-70694-8_15.

Google Scholar ePrint

[CM22]

Claude Carlet and Pierrick Méaux. A complete study of two classes of boolean functions: direct sums of monomials and threshold functions. IEEE Trans. Inf. Theory, 68(5):3404–3425, 2022. https://doi.org/10.1109/TIT.2021.3139804.

Google Scholar ePrint

[DEG⁺18]

Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel, and Christian Rechberger. Rasta: A cipher with low ANDdepth and few ANDs per bit. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part I, volume 10991 of Lecture Notes in Computer Science, 662–692. Santa Barbara, CA, USA, August 19–23, 2018. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-319-96884-1_22.

Google Scholar ePrint

[DGH⁺23]

Christoph Dobraunig, Lorenzo Grassi, Lukas Helminger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Pasta: a case for hybrid homomorphic encryption. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(3):30–73, Jun. 2023. https://doi.org/10.46586/tches.v2023.i3.30-73.

Google Scholar ePrint

[DM15]

Léo Ducas and Daniele Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, 617–640. Sofia, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-662-46800-5_24.

Google Scholar ePrint

[DvW21]

Léo Ducas and Wessel P. J. van Woerden. NTRU fatigue: how stretched is overstretched? In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part IV, volume 13093 of Lecture Notes in Computer Science, 3–32. Singapore, December 6–10, 2021. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-92068-5_1.

Google Scholar ePrint

[FV12]

Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012.

Google Scholar ePrint

[GH19]

Craig Gentry and Shai Halevi. Compressible FHE with applications to PIR. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019: 17th Theory of Cryptography Conference, Part II, volume 11892 of Lecture Notes in Computer Science, 438–464. Nuremberg, Germany, December 1–5, 2019. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-36033-7_17.

Google Scholar ePrint

[GHBJR23]

Henri Gilbert, Rachelle Heim Boissier, Jérémy Jean, and Jean-René Reinhard. Cryptanalysis of elisabeth-4. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, 256–284. Singapore, 2023. Springer Nature Singapore. https://doi.org/10.1007/978-981-99-8727-6_9.

Google Scholar ePrint

[HKC⁺20]

Jincheol Ha, Seongkwang Kim, Wonseok Choi, Jooyoung Lee, Dukjae Moon, Hyojin Yoon, and Jihoon Cho. Masta: an he-friendly cipher using modular arithmetic. IEEE Access, 8():194741–194751, 2020. https://doi.org/10.1109/ACCESS.2020.3033564.

Google Scholar ePrint

[HKL⁺22]

Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Jooyoung Lee, and Mincheol Son. Rubato: noisy ciphers for approximate homomorphic encryption. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part I, volume 13275 of Lecture Notes in Computer Science, 581–610. Trondheim, Norway, May 30 – June 3, 2022. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-031-06944-4_20.

Google Scholar ePrint

[HL20]

Phil Hebborn and Gregor Leander. Dasta – alternative linear layer for rasta. IACR Transactions on Symmetric Cryptology, 2020(3):46–86, Sep. 2020. https://doi.org/10.13154/tosc.v2020.i3.46-86.

Google Scholar ePrint

[HMR20]

Clément Hoffmann, Pierrick Méaux, and Thomas Ricosset. Transciphering, using FiLIP and TFHE for an efficient delegation of computation. In Karthikeyan Bhargavan, Elisabeth Oswald, and Manoj Prabhakaran, editors, Progress in Cryptology - INDOCRYPT 2020: 21st International Conference in Cryptology in India, volume 12578 of Lecture Notes in Computer Science, 39–61. Bangalore, India, December 13–16, 2020. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-65277-7_3.

Google Scholar ePrint

[HMS24]

Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. The patching landscape of elisabeth-4 and the mixed filter permutator paradigm. In Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, and Chester Rebeiro, editors, Progress in Cryptology – INDOCRYPT 2023, 134–156. Cham, 2024. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-56232-7_7.

Google Scholar ePrint

[HS21]

Shai Halevi and Victor Shoup. Bootstrapping for HElib. Journal of Cryptology, 34(1):7, January 2021. https://doi.org/10.1007/s00145-020-09368-7.

Google Scholar ePrint

[JLP23]

Sohyun Jeon, Hyang-Sook Lee, and Jeongeun Park. Practical randomized lattice gadget decomposition with application to fhe. 2023.

Google Scholar ePrint

[KJL⁺22]

Miran Kim, Xiaoqian Jiang, Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Secure human action recognition by encrypted neural network inference. Nature Communications, 13:, 08 2022. https://doi.org/10.1038/s41467-022-32168-5.

Google Scholar ePrint

[MCJS19]

Pierrick Méaux, Claude Carlet, Anthony Journault, and François-Xavier Standaert. Improved filter permutators for efficient FHE: better instances and implementations. In Feng Hao, Sushmita Ruj, and Sourav Sen Gupta, editors, Progress in Cryptology - INDOCRYPT 2019: 20th International Conference in Cryptology in India, volume 11898 of Lecture Notes in Computer Science, 68–91. Hyderabad, India, December 15–18, 2019. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-35423-7_4.

Google Scholar ePrint

[MJSC16]

Pierrick Méaux, Anthony Journault, François-Xavier Standaert, and Claude Carlet. Towards stream ciphers for efficient FHE with low-noise ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, 311–343. Vienna, Austria, May 8–12, 2016. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-662-49890-3_13.

Google Scholar ePrint

[MW22]

Samir Jordan Menon and David J. Wu. SPIRAL: fast, high-rate single-server PIR via FHE composition. In 2022 IEEE Symposium on Security and Privacy, 930–947. San Francisco, CA, USA, May 22–26, 2022. IEEE Computer Society Press. https://doi.org/10.1109/SP46214.2022.9833700.

Google Scholar ePrint

[NLV11]

Michael Naehrig, Kristin E. Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In Christian Cachin and Thomas Ristenpart, editors, Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, October 21, 2011, 113–124. ACM, 2011. https://doi.org/10.1145/2046660.2046682.

Google Scholar ePrint

[Per21]

Hilder Vitor Lima Pereira. Bootstrapping fully homomorphic encryption over the integers in less than one second. In Juan Garay, editor, PKC 2021: 24th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 12710 of Lecture Notes in Computer Science, 331–359. Virtual Event, May 10–13, 2021. Springer, Heidelberg, Germany. https://doi.org/10.1007/978-3-030-75245-3_13.

Google Scholar ePrint

[SFB⁺23]

Andrei Stoian, Jordan Frery, Roman Bredehoft, Luis Montero, Celia Kherfallah, and Benoit Chevallier-Mames. Deep neural networks for encrypted inference with tfhe. 2023.

Google Scholar ePrint

[TBK20]

Anselme Tueno, Yordan Boev, and Florian Kerschbaum. Non-interactive private decision tree evaluation. In IFIP Annual Conference on Data and Applications Security and Privacy, 174–194. Springer, 2020. https://doi.org/10.1007/978-3-030-49669-2_10.

Google Scholar ePrint

[TCBS23]

Daphné Trama, Pierre-Emmanuel Clet, Aymen Boudguiga, and Renaud Sirdey. A homomorphic AES evaluation in less than 30 seconds by means of TFHE. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, 79–90. ACM, 2023. https://doi.org/10.1145/3605759.3625260.

Google Scholar ePrint

[ZS21]

Martin Zuber and Renaud Sirdey. Efficient homomorphic evaluation of k-NN classifiers. Proceedings on Privacy Enhancing Technologies, 2021:111 – 129, 2021. https://doi.org/10.2478/popets-2021-0020.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/anxrxrxqi

History

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Pierrick Méaux, Jeongeun Park, and Hilder V. L. Pereira, "Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/anxrxrxqi.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-20,
    author = "Méaux, Pierrick and Park, Jeongeun and Pereira, Hilder V. L.",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Towards Practical Transciphering for {FHE} with Setup Independent of the Plaintext Space",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/anxrxrxqi"
}

TY - JOUR
AU - Méaux, Pierrick
AU - Park, Jeongeun
AU - Pereira, Hilder
PY  - 2024
TI  - Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/anxrxrxqi
UR  - https://doi.org/10.62056/anxrxrxqi
AB  - <p>        Fully Homomorphic Encryption (FHE) is a powerful tool to achieve non-interactive privacy preserving protocols with optimal computation/communication complexity.         However, the main disadvantage is that the actual communication cost (bandwidth) is high due to the large size of FHE ciphertexts.         As a solution,         a technique called transciphering (also known as Hybrid Homomorphic Encryption) was introduced to achieve almost optimal bandwidth for such protocols.          However, all existing works require clients to fix a  precision for the messages or a mathematical structure for the message space beforehand. It results in unwanted constraints          on the plaintext size or underlying structure of FHE based applications.</p><p> In this article, we introduce a new approach for transciphering which does not require fixed message precision decided by the client, for the first time. In more detail, a client uses any kind of FHE-friendly symmetric cipher for $\{0,1\}$ to send its input data encrypted bit-by-bit, then the server can choose a precision $p$ depending on the application and homomorphically transforms the encrypted bits into FHE ciphertexts encrypting integers in $\mathbb{Z}_p$. To illustrate our new technique, we evaluate a transciphering using FiLIP cipher and adapt the most practical homomorphic evaluation technique [CCS'22] to keep the practical latency. As a result, our proof-of-concept implementation for $p$ from $2^2$ to $2^8$ takes only from $13$ ms to $137$ ms. </p>
ER  -

Pierrick Méaux, Jeongeun Park, and Hilder V. L. Pereira, "Towards Practical Transciphering for FHE with Setup Independent of the Plaintext Space," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/anxrxrxqi.