research-article

GPU Acceleration of High-Precision Homomorphic Computation Utilizing Redundant Representation

Authors:

Shintaro Narisada,

Kazuhide Fukushima,

Shinsaku Kiyomoto,

Takashi NishideAuthors Info & Claims

WAHC '23: Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

Pages 1 - 9

https://doi.org/10.1145/3605759.3625256

Published: 26 November 2023 Publication History

Abstract

Fully homomorphic encryption (FHE) can perform computations on encrypted data, allowing us to analyze sensitive data without losing its security. The main issue for FHE is its lower performance, especially for high-precision computations, compared to calculations on plaintext data. Making FHE viable for practical use requires both algorithmic improvements and hardware acceleration. Recently, Klemsa and Ö nen (CODASPY'22) presented fast homomorphic algorithms for high-precision integers, including addition, multiplication and some fundamental functions, by utilizing a technique called redundant representation. Their algorithms were applied on TFHE, which was proposed by Chillotti et al. (Asiacrypt'16). In this paper, we further accelerate this method by extending their algorithms to multithreaded environments. The experimental results show that our approach performs 128-bit addition in 0.41 seconds, 32-bit multiplication in 4.3 seconds, and 128-bit Max and ReLU functions in 1.4 seconds using a Tesla V100S server.

References

[1]

Martin R Albrecht, Benjamin R Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W Postlethwaite, Fernando Virdia, and Thomas Wunderer. 2018. Estimate all the {LWE, NTRU} schemes!. In International Conference on Security and Cryptography for Networks. Springer, 351--367.

Digital Library

[2]

Algirdas Avizienis. 1961. Signed-digit number representations for fast parallel arithmetic. IRE Transactions on electronic computers 3 (1961), 389--400.

[3]

Loris Bergerat, Anas Boudi, Quentin Bourgerie, Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. 2023. Parameter Optimization and Larger Precision for (T)FHE. J. Cryptol. 36, 3 (2023), 65. https://doi.org/10.1007/s00145- 023-09463--5

Digital Library

[4]

Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. 2019. Simulating Homomorphic Evaluation of Deep Learning Predictions. In Cyber Security Cryptography and Machine Learning. 212--230.

[5]

Florian Bourse, Olivier Sanders, and Jacques Traoré. 2020. Improved Secure Integer Comparison via Homomorphic Encryption. In Topics in Cryptology -- CT-RSA 2020. 391--416.

Digital Library

[6]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS '12). 309--325. https://doi.org/10.1145/2090236.2090262

Digital Library

[7]

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Advances in Cryptology -- ASIACRYPT 2017. 409--437.

[8]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2016. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In Advances in Cryptology -- ASIACRYPT 2016. 3--33.

[9]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: Fast Fully Homomorphic Encryption Over the Torus. Journal of Cryptology 33, 1 (2020), 34--91. https://doi.org/10.1007/s00145-019-09319-x

Digital Library

[10]

Ilaria Chillotti, Marc Joye, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. 2020. CONCRETE: Concrete Operates oN Ciphertexts Rapidly by Extending TFHE. In WAHC 2020--8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Vol. 15.

[11]

Ilaria Chillotti, Marc Joye, and Pascal Paillier. 2021. Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks. In Cyber Security Cryptography and Machine Learning. 1--19.

[12]

Catherine Y. Chow and James E. Robertson. 1978. Logical design of a redundant binary adder. In 1978 IEEE 4th Symposium onomputer Arithmetic (ARITH). 109--115. https://doi.org/10.1109/ARITH.1978.6155767

[13]

Pierre-Emmanuel Clet, Martin Zuber, Aymen Boudguiga, Renaud Sirdey, and Cédric Gouy-Pailler. 2022. Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping. Cryptology ePrint Archive (2022).

[14]

Anamaria Costache, Benjamin R. Curtis, Erin Hales, Sean Murphy, Tabitha Ogilvie, and Rachel Player. 2022. On the precision loss in approximate homomorphic encryption. Cryptology ePrint Archive, Paper 2022/162. (2022). https://eprint.iacr.org/2022/162

[15]

Léo Ducas and Daniele Micciancio. 2015. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Advances in Cryptology -- EUROCRYPT 2015. 617--640

[16]

Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptol. ePrint Arch. 2012 (2012), 144.

[17]

Craig Gentry. 2009. Fully Homomorphic Encryption Using Ideal Lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (STOC '09). Association for Computing Machinery, New York, NY, USA, 169--178. https://doi.org/10.1145/1536414.1536440

Digital Library

[18]

Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Advances in Cryptology -- CRYPTO 2013. 75--92.

[19]

Antonio Guimaraes, Edson Borin, and Diego F Aranha. 2021. Revisiting the functional bootstrap in TFHE. IACR Transactions on Cryptographic Hardware and Embedded Systems (2021), 229--253.

[20]

Jakub Klemsa and Melek Önen. 2022. Parallel Operations over TFHE-Encrypted Multi-Digit Integers. In Proceedings of the Twelveth ACM Conference on Data and Application Security and Privacy. 288--299.

Digital Library

[21]

Jakub Klemsa and Melek Önen. 2022. Parmesan: Parallel ARithMEticS on TFHE ENcrypted data. (2022). https://github.com/fakub/parmesan/.

[22]

Jakub Klemsa and Melek Önen. 2023. PARMESAN: Parallel ARithMEticS over ENcrypted data. Cryptology ePrint Archive, Paper 2023/544. (2023). https: //eprint.iacr.org/2023/544

[23]

Kenji Koyama and Yukio Tsuruoka. 1993. Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method. In Advances in Cryptology - CRYPTO' 92, Ernest F. Brickell (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 345--357.

[24]

Daisuke Maeda, Koki Morimura, and Takashi Nishide. 2022. Efficient Homomorphic Evaluation of Arbitrary Bivariate Integer Functions. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC'22). Association for Computing Machinery, New York, NY, USA, 13--22. https://doi.org/10.1145/3560827.3563378

Digital Library

[25]

Zama Team. 2022. Announcing Concrete-core v1.0.0-gamma with GPU acceleration. (2022). https://www.zama.ai/post/concrete-core-v1-0-gamma-with-gpuacceleration.

[26]

Zama. 2022. TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics Over Encrypted Data. (2022). https://github. com/zama-ai/tfhe-rs.

Cited By

Prasetiyo Putra AKim J(2024)Morphling: A Throughput-Maximized TFHE-based Accelerator using Transform-domain Reuse2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00028(249-262)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00028

Index Terms

GPU Acceleration of High-Precision Homomorphic Computation Utilizing Redundant Representation
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multicore architectures
2. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Efficient fully homomorphic encryption with circularly secure key switching process

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper,...
A Survey on Homomorphic Encryption Schemes: Theory and Implementation

Legacy encryption systems depend on sharing a key (public or private) among the peers involved in exchanging an encrypted message. However, this approach poses privacy concerns. The users or service providers with the key have exclusive rights on the ...
Efficient batch identity‐based fully homomorphic encryption scheme in the standard model

Identity‐based fully homomorphic encryption (IBFHE) provided a fundamental solution to the problem of huge public key size that exposed in fully homomorphic encryption (FHE) schemes, thus it is significant to make FHE become more practical. In recent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WAHC '23: Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography

November 2023

111 pages

ISBN:9798400702556

DOI:10.1145/3605759

Program Chairs:
Michael Brenner
Leibniz Universität Hannover, Germany
,
Anamaria Costache
NTNU: Norwegian University of Science and Technology, Norway
,
Kurt Rohloff
NJIT and Duality Technologies, USA

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 November 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '23

Sponsor:

SIGSAC

CCS '23: ACM SIGSAC Conference on Computer and Communications Security

November 26, 2023

Copenhagen, Denmark

Acceptance Rates

Overall Acceptance Rate 6 of 17 submissions, 35%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
98
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prasetiyo Putra AKim J(2024)Morphling: A Throughput-Maximized TFHE-based Accelerator using Transform-domain Reuse2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00028(249-262)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00028

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents