research-article

Open access

Accelerating N-Bit Operations over TFHE on Commodity CPU-FPGA

Authors:

Yunheung PaekAuthors Info & Claims

ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design

Article No.: 98, Pages 1 - 9

https://doi.org/10.1145/3508352.3549413

Published: 22 December 2022 Publication History

Abstract

TFHE is a fully homomorphic encryption (FHE) scheme that evaluates Boolean gates, which we will hereafter call Tgates, over encrypted data. TFHE is considered to have higher expressive power than many existing schemes in that it is able to compute not only N-bit Arithmetic operations but also Logical/Relational ones as arbitrary ALR operations can be represented by Tgate circuits. Despite such strength, TFHE has a weakness that like all other schemes, it suffers from colossal computational overhead. Incessant efforts to reduce the overhead have been made by exploiting the inherent parallelism of FHE operations on ciphertexts. Unlike other FHE schemes, the parallelism of TFHE can be decomposed into multilayers: one inside each FHE operation (equivalent to a single Tgate) and the other between Tgates. Unfortunately, previous works focused only on exploiting the parallelism inside Tgate. However, as each N-bit operation over TFHE corresponds to a Tgate circuit constructed from multiple Tgates, it is also necessary to utilize the parallelism between Tgates for optimizing an entire operation. This paper proposes an acceleration technique to maximize performance of a TFHE N-bit operation by simultaneously utilizing both parallelism comprising the operation. To fully profit from both layers of parallelism, we have implemented our technique on a commodity CPU-FPGA hybrid machine with parallel execution capabilities in hardware. Our implementation outperforms prior ones by 2.43× in throughput and 12.19× in throughput per watt when performing N-bit operations under the 128-bit quantum security parameters.

References

[1]

C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 2009.

Digital Library

[2]

Q. Lou and L. Jiang. She: A fast and accurate deep neural network for encrypted data. In Annual Conference on Neural Information Processing Systems, 2019.

[3]

I. Chillotti et al. Tfhe: Fast fully homomorphic encryption over the torus. Cryptology ePrint Archive, Report 2018/421, 2018. https://ia.cr/2018/421.

[4]

J. Cheon et al. Homomorphic encryption for arithmetic of approximate numbers. Cryptology ePrint Archive, Report 2016/421, 2016. https://ia.cr/2016/421.

[5]

S. S. Roy et al. Fpga-based high-performance parallel architecture for homomorphic computing on encrypted data. In IEEE International Symposium on High Performance Computer Architecture, 2019.

[6]

A. C. Mert et al. Design and implementation of encryption/decryption architectures for bfv homomorphic encryption scheme. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 28(2):353--362, 2019.

[7]

F. Turan et al. Heaws: an accelerator for homomorphic encryption on the amazon aws fpga. IEEE Transactions on Computers, 69(8):1185--1196, 2020.

[8]

S. Gener et al. An fpga-based programmable vector engine for fast fully homomorphic encryption over the torus. In SPSL: Secure and Private Systems for Machine Learning (ISCA Workshop), 2021.

[9]

L. Jiang et al. Matcha: A fast and energy-efficient accelerator for fully homomorphic encryption over the torus. arXiv preprint arXiv:2202.08814, 2022.

[10]

M. Riazi et al. Heax: An architecture for computing on encrypted data. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, 2020.

Digital Library

[11]

Y. Choi et al. A quantitative analysis on microarchitectures of modern cpu-fpga platforms. In Proceedings of the 53rd Annual Design Automation Conference, pages 1--6, 2016.

Digital Library

[12]

J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144, 2012. https://ia.cr/2012/144.

[13]

V. Lyubashevsky et al. On ideal lattices and learning with errors over rings. In Annual international conference on the theory and applications of cryptographic techniques, pages 1--23. Springer, 2010.

Digital Library

[14]

I. Chillotti et al. TFHE: Fast fully homomorphic encryption library, August 2016. https://tfhe.github.io/tfhe.

[15]

A gpu implementation of fully homomorphic encryption on torus. https://github.com/nucypher/nufhe.

[16]

M. Albrecht et al. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018.

[17]

S. Gupta et al. Memfhe: End-to-end computing with fully homomorphic encryption in memory. arXiv preprint arXiv:2204.12557, 2022.

[18]

K. Matsuoka. Tfhepp: pure c++ implementation of tfhe cryptosystem. https://github.com/virtualsecureplatform/TFHEpp, 2020.

[19]

K. Baker. Introduction to sequencing and scheduling. John Wiley & Sons, 1974.

[20]

Xilinx Inc. Alveo u280 data center accelerator card. https://www.xilinx.com/products/boards-and-kits/alveo/u280.html.

[21]

W. Dai. CUDA-accelerated fully homomorphic encryption library. https://github.com/vernamlab/cuFHE, 2018.

[22]

R. P. Brent and H. T. Kung. A regular layout for parallel adders. IEEE transactions on Computers, 31(03):260--264, 1982.

Digital Library

[23]

L. Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141--142, 2012.

[24]

Nvidia Corporation. Nvidia system management interface. https://developer.nvidia.com/nvidia-system-management-interfac.

[25]

Xilinx Inc. Xilinx board utility. https://xilinx.github.io/XRT/master/html/xbutil.html.

[26]

Xilinx Inc. Xilinx power estimator. https://www.xilinx.com/products/technology/power/xpe.html.

[27]

The Free Software Foundation. Powertop. https://github.com/fenrus75/powertop.

[28]

C. I. King. powerstat. https://github.com/ColinIanKing/powerstat.

[29]

T. Morshed et al. Cpu and gpu accelerated fully homomorphic encryption. In 2020 IEEE International Symposium on Hardware Oriented Security and Trust.

[30]

M. Chase et al. Security of homomorphic encryption. HomomorphicEncryption.org, Redmond WA, Tech. Rep, 2017.

[31]

N. Samardzic et al. F1: A fast and programmable accelerator for fully homomorphic encryption. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, pages 238--252, 2021.

Digital Library

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
Wang RWei BLi ZLu XWang K(2024)TFHE Bootstrapping: Faster, Smaller and Time-Space Trade-OffsInformation Security and Privacy10.1007/978-981-97-5025-2_11(196-216)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_11
Putra APrasetiyo Chen YKim JKim J(2023)Strix: An End-to-End Streaming Architecture with Two-Level Ciphertext Batching for Fully Homomorphic Encryption with Programmable BootstrappingProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614264(1319-1331)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614264
Show More Cited By

Index Terms

Accelerating N-Bit Operations over TFHE on Commodity CPU-FPGA

Index terms have been assigned to the content through auto-classification.

Recommendations

Accelerating relational database operations using both CPU and GPU co-processor

Data is evolving and the number of existing data sources is vastly growing. Therefore, there is a compelling need for effective techniques to store, retrieve and process such massive data. Significant speed-ups at a small cost can be achieved by ...
Accelerating Kirchhoff Migration by CPU and GPU Cooperation
SBAC-PAD '09: Proceedings of the 2009 21st International Symposium on Computer Architecture and High Performance Computing

We discuss the performance of Petrobras production Kirchhoff prestack seismic migration on a cluster of 64 GPUs and 256 CPU cores. Porting and optimization of the application hot spot (98.2% of a single CPU core execution time) to a single GPU reduces ...
Accelerating aerial image simulation using improved CPU/GPU collaborative computing

Aerial image simulation is a fundamental problem in advanced lithography for chip fabrication. Since it requires a huge number of mathematical computations, an efficient yet accurate implementation becomes a necessity. In the literature, graphic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design

October 2022

1467 pages

ISBN:9781450392174

DOI:10.1145/3508352

Conference Chair:
Tulika Mitra
National University of Singapore
,
Program Chairs:
Evangeline Young
The Chinese University of Hong Kong
,
Jinjun Xiong
University at Buffalo (UB)

Copyright © 2022 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

SIGDA: ACM Special Interest Group on Design Automation

In-Cooperation

IEEE-EDS: Electronic Devices Society
IEEE CAS
IEEE CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 December 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICCAD '22

Sponsor:

SIGDA

ICCAD '22: IEEE/ACM International Conference on Computer-Aided Design

October 30 - November 3, 2022

California, San Diego

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
583
Total Downloads

Downloads (Last 12 months)170
Downloads (Last 6 weeks)19

Reflects downloads up to 08 Feb 2025

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
Wang RWei BLi ZLu XWang K(2024)TFHE Bootstrapping: Faster, Smaller and Time-Space Trade-OffsInformation Security and Privacy10.1007/978-981-97-5025-2_11(196-216)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_11
Putra APrasetiyo Chen YKim JKim J(2023)Strix: An End-to-End Streaming Architecture with Two-Level Ciphertext Batching for Fully Homomorphic Encryption with Programmable BootstrappingProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614264(1319-1331)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614264
Wang RLi ZWei BChen CLu XWang K(2023)Revisiting Key Switching Techniques with Applications to Light-Key FHEInformation Security and Cryptology – ICISC 202310.1007/978-981-97-1235-9_3(41-64)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-97-1235-9_3
Lee YNam KJoo YKim JOh HPaek Y(2023)Area-Efficient Accelerator for the Full NTRU-KEM AlgorithmComputational Science and Its Applications – ICCSA 2023 Workshops10.1007/978-3-031-37111-0_14(186-201)Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37111-0_14

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten