進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1308202013062500
論文名稱(中文) 應用於BGV全同態加密之低複雜度多項式乘法器架構設計
論文名稱(英文) Low-Complexity VLSI Architecture of Polynomial Multiplication for BGV Fully Homomorphic Encryption
校院名稱 成功大學
系所名稱(中) 電機工程學系
系所名稱(英) Department of Electrical Engineering
學年度 108
學期 2
出版年 109
研究生(中文) 許軒瑞
研究生(英文) Hsuan-Jui Hsu
學號 N26074906
學位類別 碩士
語文別 英文
論文頁數 55頁
口試委員 指導教授-謝明得
口試委員-黃穎聰
口試委員-黃稚存
口試委員-郭致宏
中文關鍵字 全同態加密  聚合明文  重加密  分圓多項式  互質因子算法  雷德演算法 
英文關鍵字 Fully Homomorphic Encryption  Aggregate Plaintext  Recryption  Cyclotomic Polynomial  Prime-factor FFT Algorithm  Rader’s FFT Algorithm 
學科別分類
中文摘要 全同態加密 (Fully Homomorphic Encryption, FHE) 可以直接對密文進行運算,等效於對其未加密的明文元素進行相同的運算,而不用對密文執行解密程序,可確保資料的安全與隱密性,因此目前被廣泛地關注與討論。BGV全同態加密方案是目前討論較熱烈,且可配合使用聚合明文技術來大幅提高明文的使用率;結合重加密技術,可使其應用的範圍不再受限制。BGV全同態加密的數學運算定義在多項式環,本論文探索針對使用分圓多項式環的聚合明文,以及重加密的應用之多項式乘法的硬體架構。並展示如何有效地結合分圓多項式、互質因子算法以及雷德演算法的特性,以得出基於中國餘數定理 (CRT) 的新穎架構設計想法。實驗結果顯示,在足夠安全性下的參數考量下與現有的技術相比,本論文所提出的解決方案可以顯著地提高運算的效率,並且大幅降低運算過程中所需的記憶體空間。舉例而言,當使用參數為21845次分圓多項式時,與Chen所提出的架構在足夠安全的條件之下相比,可以將一次多項式乘法所需的模加法與模乘法的運算量分別減少3.11倍與13.02倍,並且是在僅使用32個明文槽且皆僅加密一位元的情況下比較。如果是在所有的明文槽皆可使用的情況下相比,本論文所提出架構設計的效能改進是非常可觀的。若與HElib的實現方式相比,假設參數為21845次分圓多項式,本論文提升使用基數為4與8的蝴蝶形單元所實現的快速傅立葉轉換架構運算速度分別約提升2.85倍以及1.56倍,並且隨機存取記憶體 (RAM) 的記憶空間需求量減少為HElib所需的33%,唯讀記憶體 (ROM) 的記憶空間需求量大幅減少至HElib的0.42%。
英文摘要 Fully homomorphic encryption (FHE) has attracted a lot of attention because computations can be directly performed on ciphertexts. This work explores the hardware architecture of polynomial multiplication defined in BGV-FHE, targeting the applications of aggregate plaintext using cyclotomic polynomials. We show how to effectively combine the characteristics of cyclotomic polynomials, the prime-factor FFT algorithm and the Rader’s FFT algorithm to obtain a novel design derived by the concept of Chinese Remainder Theorem. Experimental results show that a significant improvement in terms of operation reduction and memory requirements can be achieved by adopting the proposed schemes as compared to existing works assuming a comparable security level. For example, about 3.11 and 13.02 times improvement in the total number of required modular addition and multiplication, respectively, can be obtained by using 32 one-bit aggregate slots as compared to Chen’s work when the 21845-th cyclotomic polynomial is considered. The improvement could be huge if all of the available slots are involved in applications. Compared with the results using HElib, the proposed architecture obtains about 2.85 times and 1.56 times speedup by using radix-4 and radix-8 butterfly units in FFT design, respectively. In addition, the required RAM and ROM size are reduced to 33% and 0.42%, respectively, when adopting the 21845-th cyclotomic polynomial.
論文目次 摘要 i
Abstract ii
Contents iii
List of Tables v
List of Figures vi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Thesis Organization 4
Chapter 2 Background 5
2.1 Fully Homomorphic Encryption 5
2.2 Ring Learning with Error Based Fully Homomorphic Encryption 7
2.2.1 BGV-FHE Scheme 7
2.2.2 Homomorphic Operation 8
2.2.3 Noise Management 9
2.3 Aggregate Plaintext 11
2.4 Recryption 13
2.5 Cyclotomic Polynomial Operation on Ciphertext 15
2.6 FFT Algorithms 17
2.6.1 Bluestein’s FFT Algorithm 17
2.6.2 Prime-factor FFT Algorithm 18
2.6.3 Rader’s FFT Algorithm 19
2.7 FFT Architectures 20
2.7.1 Pipeline FFT Architecture 20
2.7.2 Memory-based FFT Architecture 22
Chapter 3 Proposed Cyclotomic Polynomial Multiplier 25
3.1 Architecture of Polynomial Multiplier 25
3.1.1 Architecture of 2nd-CRT in double-CRT 25
3.1.2 Property of Cyclotomic Polynomial 28
3.1.3 Architecture of 2nd-ICRT in double-CRT 30
3.2 Small-FFTs Optimization 35
3.2.1 Architecture of Rader’s FFT 35
3.2.2 Efficient Memory Management Solution 38
3.2.3 Special Case of Rader’s FFT 40
Chapter 4 Experimental Results 44
4.1 Complexity Analysis with and without using Aggregate 44
4.2 Complexity Comparison with Bluestein’s FFT 48
Chapter 5 Conclusion and Future work 52
5.1 Conclusion 52
5.2 Future work 53
References 54


參考文獻 [1] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proc. 41st Annu. ACM STOC, pp. 169-178, 2009.
[2] C. Gentry, S. Halevi, and N. Smart, “Homomorphic evaluation of the AES circuit,” in Proc. CRYPTO, 2012.
[3] S. Halevi and V. Shoup, “Bootstrapping for HElib,” in EUROCRYPT, pp. 641-670, 2015.
[4] S. Halevi and V. Shoup, “Faster homomorphic linear transformations in HElib,” Cryptol. ePrint Arch., Tech. Rep. 2018/244, 2018.
[5] M. Naehrig, K. Lauter, and V. Vaikuntanathan, “Can homomorphic encryption be practical?,” in Proceedings of the 3rd ACM workshop on Cloud computing security workshop, pp. 113-124, ACM, 2011.
[6] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti, “A survey on homomorphic encryption schemes: Theory and implementation,” ACM Comput. Surveys., vol. 51, no. 4, p. 79, 2018.
[7] J.-N. Ji and M.-D. Shieh, “Efficient Comparison and Swap on Fully Homomorphic Encrypted Data,” in Proc. IEEE Internation Symposium on Circuits and Systems, pp. 1-4, May. 2019.
[8] D. D. Chen et al.,“High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 62, no. 1, pp. 157-166, Jan. 2015.
[9] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” in Proc. 3rd Innovations in Theoretical computer Science Conf., pp. 309-325, 2012.
[10] N. P. Smart and F. Vercauteren, “Fully homomorphic SIMD operations,” Designs, Codes Cryptogr., vol. 71, no. 1, pp. 57-81, 2014.
[11] S. Halevi and V. Shoup, “HElib,” 2013.
[12] L.I. Bluestein, “A linear filering approach to the computation of the discrete Fourier transform,” in Northeast Electornics Research and Enginnering Meeting Rec., vol. 10, pp. 218-219, 1968.
[13] I. J. Good, “The interaction algorithm and practical Fourier analysis,” J. Roy. Stat. Soc., ser. B, vol. 20, pp, 361 -372, 1958.
[14] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, vol. 56, pp. 1107–1108, June 1968.
[15] C. Genrty, S. Halevi, and N. P. Smart, “Fully homomorphic encryption with polylog overhead,” in EUROCRYPT, 2012.
[16] J. M. Pollard, “The fast Fourier transform in a finite field,” Math.Comput., vol. 25, pp. 365–374, 1971.
[17] Y.-N. Chang and K. K. Parhi, “An Efficient Pipelined FFT Architecture,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 50, no. 6, pp. 322-325, June 2003.
[18] H. L. Groginsky and G. A. Works, “A Pipeline Fast Fourier Transform,” IEEE Trans. Comput., vol. c-19, no. 11, pp. 1015-1019, Nov. 1970.
[19] E. E. Swartzlander, W. K. W. Young, and S. J. Joseph, “A Radix 4 Delay Commutator for Fast Fourier Transform Processor Implementation,” IEEE J. Solid-State Circuits, vol. sc-19, no. 5, pp. 702-709, Oct. 1984.
[20] C.-K. Chang, C.-P. Hung, and S.-G. Chen, “An efficient memory-based FFT architecture,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 2. pp. 129-132, May. 2003.
[21] L. G. Johnson, “Conflict Free Memory Addressing for Dedicated FFT Hardware,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 39, no. 5, pp. 312-316, May. 1992.
[22] H.-F. Luo, Y.-J. Liu, and M.-D. Shieh, “Efficient memory-addressing algorithms for FFT processor design,” IEEE Trans, Very Large Scale Integr. (VLSI) Syst., vol. 23, no. 10, pp. 2162-2172, Oct. 2015.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-08-31起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-08-31起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw