Low-Complexity Ciphertext Multiplication for CKKS Homomorphic Encryption

被引：2

作者：

Akherati, Sajjad ^{[1
]}

Zhang, Xinmiao ^{[1
]}

机构：

[1] Ohio State Univ, Dept Elect & Comp Engn, Columbus, OH 43210 USA

来源：

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS | 2024年 / 71卷 / 03期

关键词：

Complexity theory; Computer architecture; Silicon; Homomorphic encryption; Transforms; Sequential analysis; Runtime; Hardware architecture; homomorphic encryption; multiplication; relinearization; rescaling;

D O I：

10.1109/TCSII.2023.3318859

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

Homomorphic encryption (HE) allows direct computations on ciphertexts and is a key enabler of privacy-preserving cloud computing. The CKKS algorithm is among the most popular HE schemes and a ciphertext consists of a pair of polynomials with very large coefficients. The complexity of large coefficients can be greatly reduced by using the residue number system (RNS). However, the relinearization and rescaling that follow the coefficient multiplication in every ciphertext multiplication have even higher complexities. This brief proposes reformulations of the relinearization and rescaling using RNS representation. A novel integer division method is developed to enable the combination and simplification of all involved computations. Constants are pre-multiplied to reduce the number of required multipliers. As a result, the complexity of the ciphertext multiplication is greatly reduced. For an example case, the proposed design leads to 18% less silicon area and 42% shorter latency compared to prior work.

引用

页码：1396 / 1400

页数：5

共 21 条

[11]

Jung Hee Cheon, 2019, Selected Areas in Cryptography - SAC 2018. 25th International Conference. Revised Selected Papers: Lecture Notes in Computer Science (LNCS 11349), P347, DOI 10.1007/978-3-030-10970-7_16

[12] ARK: Fully Homomorphic Encryption Accelerator with Runtime Data Generation and Inter-Operation Key Reuse [J].

Kim, Jongmin ;

Lee, Gwangho ;

Kim, Sangpyo ;

Sohn, Gina ;

Rhu, Minsoo ;

Kim, John ;

Ahn, Jung Ho .

2022 55TH ANNUAL IEEE/ACM INTERNATIONAL SYMPOSIUM ON MICROARCHITECTURE (MICRO), 2022, :1237-1254

[13] Secure searching of biomarkers through hybrid homomorphic encryption scheme [J].

Kim, Miran ;

Song, Yongsoo ;

Cheon, Jung Hee .

BMC MEDICAL GENOMICS, 2017, 10

[14]

Langhammer Martin, 2021, FPGA '21: The 2021 ACM/SIGDA International Symposium on Field-Programmable, P160, DOI 10.1145/3431920.3439299

[15] Private Computation on Encrypted Genomic Data [J].

Lauter, Kristin ;

Lopez-Alt, Adriana ;

Naehrig, Michael .

PROGRESS IN CRYPTOLOGY - LATINCRYPT 2014, 2015, 8895 :3-27

[16] FPGA-based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data [J].

Roy, Sujoy Sinha ;

Turan, Furkan ;

Jarvinen, Kimmo ;

Vercauteren, Frederik ;

Verbauwhede, Ingrid .

2019 25TH IEEE INTERNATIONAL SYMPOSIUM ON HIGH PERFORMANCE COMPUTER ARCHITECTURE (HPCA), 2019, :387-398

[17]

Solinas J. A., 2011, Encyclopedia of Cryptography and Security

[18]

Tan WH, 2023, Arxiv, DOI arXiv:2303.02237

[19] HEALER: homomorphic computation of ExAct Logistic rEgRession for secure rare disease variants analysis in GWAS [J].

Wang, Shuang ;

Zhang, Yuchen ;

Dai, Wenrui ;

Lauter, Kristin ;

Kim, Miran ;

Tang, Yuzhe ;

Xiong, Hongkai ;

Jiang, Xiaoqian .

BIOINFORMATICS, 2016, 32 (02) :211-218

[20] VLSI Design of Karatsuba Integer Multipliers and Its Evaluation [J].

Yazaki, Syunji ;

Abe, Koki .

ELECTRONICS AND COMMUNICATIONS IN JAPAN, 2009, 92 (04) :9-20

← 1 2 3 →