{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T15:50:22Z","timestamp":1781884222629,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62441234 and 62502151"],"award-info":[{"award-number":["62441234 and 62502151"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"crossref","award":["2024M750879 and BX20240111"],"award-info":[{"award-number":["2024M750879 and BX20240111"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010083","name":"Hunan Provincial Innovation Foundation for Postgraduate","doi-asserted-by":"crossref","award":["CX20240420"],"award-info":[{"award-number":["CX20240420"]}],"id":[{"id":"10.13039\/501100010083","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    Zero-Knowledge Proofs (ZKP) and Homomorphic Encryption (HE) are crucial for data privacy in applications like cloud, blockchain, and analytics. However, the real-world adoption often faces performance challenges, particularly in the execution of the Number Theoretic Transform (NTT) required for polynomial multiplication involving sizes beyond\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{20}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and large integer widths (e.g., 256\u2009bits). FPGAs offer a promising platform for acceleration, but efficiently implementing large-size NTTs remains difficult due to the limited on-chip resources. The widely adopted four-step NTT method, used to relieve the need for large on-chip memory, introduces performance bottlenecks. Initially, the traditional dataflow NTT architecture may not fully exploit available compute capability, which hinders achieving peak performance. Furthermore, during the matrix transpose phase, the non-sequential access to external High-Bandwidth Memory (HBM) causes inefficiency.\n                  <\/jats:p>\n                  <jats:p>To address these challenges, we introduce HiFA, an FPGA-based automatic accelerator framework designed for high-performance and flexible large-size NTT computations. HiFA utilizes a stacked NTT architecture for high parallelism, maximizing HBM throughput. It supports various decomposed polynomial sizes via a novel reordering module. Additionally, a specialized cyclic shuffle module is integrated to optimize data movement during the matrix transpose step, alleviating random memory access delay. HiFA also provides an automatic Design Space Exploration (DSE) framework that identifies optimal four-step decomposition parameters and generates corresponding hardware configurations. Our experiments show that the FPGA implementation of HiFA achieves an average speedup of 2.97\u00d7 and up to 7.25\u00d7 improvement in latency over prior state-of-the-art FPGA solutions. Compared to prior GPU-based methods, HiFA achieves an average energy efficiency gain of\u00a02.24\u00d7.<\/jats:p>","DOI":"10.1145\/3771769","type":"journal-article","created":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T12:27:41Z","timestamp":1760790461000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["HiFA: A High-Performance and Flexible Acceleration Framework for Large-Size Number Theoretic Transform"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3377-1656","authenticated-orcid":false,"given":"Qilin","family":"Hu","sequence":"first","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China and the Ministry of Education Key Laboratory of \u201cFusion Computing of Supercomputing and Artificial Intelligence\u201d, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0086-6301","authenticated-orcid":false,"given":"Haotian","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China and the Ministry of Education Key Laboratory of \u201cFusion Computing of Supercomputing and Artificial Intelligence\u201d, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2372-6715","authenticated-orcid":false,"given":"Chubo","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China and the Ministry of Education Key Laboratory of \u201cFusion Computing of Supercomputing and Artificial Intelligence\u201d, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5224-4048","authenticated-orcid":false,"given":"Keqin","family":"Li","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China and the Ministry of Education Key Laboratory of \u201cFusion Computing of Supercomputing and Artificial Intelligence\u201d, Changsha, China and State University of New York, New Paltz, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2635-7716","authenticated-orcid":false,"given":"Kenli","family":"Li","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China and the Ministry of Education Key Laboratory of \u201cFusion Computing of Supercomputing and Artificial Intelligence\u201d, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_3_1_2_2","article-title":"Cyclonentt: An ntt\/fft architecture using quasi-streaming of large datasets on ddr-and hbm-based fpga platforms","author":"Aasaraai Kaveh","year":"2022","unstructured":"Kaveh Aasaraai, Emanuele Cesena, Rahul Maganti, Nicolas Stalder, Javier Varela, and Kevin Bowers. 2022. Cyclonentt: An ntt\/fft architecture using quasi-streaming of large datasets on ddr-and hbm-based fpga platforms. Cryptology ePrint Archive.","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00060"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3560827.3563379"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3021238"},{"key":"e_1_3_1_6_2","unstructured":"AMD. 2021. Random Accesses. RetrievedJune 10 2025 from https:\/\/docs.amd.com\/r\/en-US\/Vitis-Tutorials-Vitis-Hardware-Acceleration\/Random-Accesses"},{"key":"e_1_3_1_7_2","unstructured":"AMD\/Xilinx. 2023. Alveo U280 Data Center Accelerator Card Data Sheet (DS963). Retrieved from https:\/\/docs.xilinx.com\/r\/en-US\/ds963-u280\/Summary"},{"key":"e_1_3_1_8_2","unstructured":"AMD\/Xilinx. 2023. Alveo U50 Data Center Accelerator Card Data Sheet (DS965). Retrieved from https:\/\/docs.amd.com\/r\/en-US\/ds965-u50\/Summary"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD57390.2023.10323612"},{"key":"e_1_3_1_10_2","first-page":"311","volume-title":"Conference on the Theory and Application of Cryptographic Techniques","author":"Barrett Paul","year":"1986","unstructured":"Paul Barrett. 1986. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Conference on the Theory and Application of Cryptographic Techniques. Springer, 311\u2013323."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS58744.2024.10558123"},{"key":"e_1_3_1_12_2","unstructured":"Filecoin Corp. 2022. Bellperson: GPU Parallel Acceleration for zk-SNARK. Retrieved from https:\/\/github.com\/filecoin-project\/bellperson"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656019.3676898"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2018.00029"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_1_16_2","first-page":"201","volume-title":"International Conference on Machine Learning","author":"Gilad-Bachrach Ran","year":"2016","unstructured":"Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning. PMLR, 201\u2013210."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3335741.3335750"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE58400.2024.10546833"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3609335"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2024.3377366"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3669940.3707241"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.55"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3676536.3697123"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM62733.2025.00024"},{"issue":"2","key":"e_1_3_1_25_2","first-page":"1","article-title":"Machine learning based framework for fast resource estimation of RTL designs targeting FPGAs","volume":"28","author":"Li Benzheng","year":"2022","unstructured":"Benzheng Li, Xi Zhang, Hailong You, Zhongdong Qi, and Yuming Zhang. 2022. Machine learning based framework for fast resource estimation of RTL designs targeting FPGAs. ACM Transactions on Design Automation of Electronic Systems 28, 2 (2022), 1\u201316.","journal-title":"ACM Transactions on Design Automation of Electronic Systems"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD57390.2023.10323790"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649476.3658734"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2023.i3.194-220"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575711"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00069"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2024.3470335"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2019.00045"},{"key":"e_1_3_1_33_2","unstructured":"Microsoft Research. 2025. Microsoft SEAL: Fast and Easy-to-Use Homomorphic Encryption Library. Retrieved June 24 2025 from https:\/\/github.com\/microsoft\/SEAL"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0777282-X"},{"key":"e_1_3_1_35_2","article-title":"Two algorithms for fast gpu implementation of ntt","author":"\u00d6zcan Ali \u015eah","year":"2023","unstructured":"Ali \u015eah \u00d6zcan and Erkay Sava\u015f. 2023. Two algorithms for fast gpu implementation of ntt. Cryptology ePrint Archive.","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD45719.2019.8942115"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71045-7_13"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614279"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD57390.2023.10323839"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2014.6927483"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD57390.2023.10323744"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3669940.3707228"},{"key":"e_1_3_1_43_2","first-page":"675","volume-title":"27th USENIX Security Symposium (USENIX Security \u201918)","author":"Wu Howard","year":"2018","unstructured":"Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. \\(\\{\\) DIZK \\(\\}\\) : A distributed zero knowledge proof system. In 27th USENIX Security Symposium (USENIX Security \u201918), 675\u2013692."},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3528416.3530225"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA61900.2025.00020"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jisa.2024.103782"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00040"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2024.3468033"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jisa.2023.103678"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771769","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T14:42:02Z","timestamp":1764859322000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771769"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3771769"],"URL":"https:\/\/doi.org\/10.1145\/3771769","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]},"assertion":[{"value":"2025-06-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}