{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T15:46:02Z","timestamp":1784216762131,"version":"3.55.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["SaTC-2020625 and NIST-60NANB20D203"],"award-info":[{"award-number":["SaTC-2020625 and NIST-60NANB20D203"]}]},{"DOI":"10.13039\/501100004410","name":"TUBITAK","doi-asserted-by":"crossref","award":["1001-121F348"],"award-info":[{"award-number":["1001-121F348"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            Increasing attention has been paid to code-based post-quantum cryptography (PQC) schemes, e.g., HQC (Hamming Quasi-Cyclic) and BIKE (Bit Flipping Key Encapsulation), since they\u2019ve been selected as the fourth-round National Institute of Standards and Technology (NIST) PQC standardization candidates. Though sparse polynomial multiplication is one of the critical components for HQC and BIKE, hardware-implemented high-performance sparse polynomial multiplier is rarely reported in the literature (due to its high-dimension and sparsity of polynomials involved in the computation). Based on this consideration, in this article, we propose two novel\n            <jats:bold>H<\/jats:bold>\n            igh-throughput\n            <jats:bold>S<\/jats:bold>\n            parse\n            <jats:bold>P<\/jats:bold>\n            olynomial multiplication\n            <jats:bold>A<\/jats:bold>\n            ccelerators (HSPA) for the mentioned two code-based PQC schemes. Specifically, we have designed the two accelerators based on two different implementation strategies targeting potential applications with different resource availability, i.e., one accelerator deploys a memory-based structure for computation while the other does not need memory usage. We have proposed three layers of coherent interdependent efforts to obtain the proposed accelerators. First, we have proposed two implementation strategies to execute the targeted sparse polynomial multiplication, i.e., a new parallel segment based accumulation (PSA) approach and a novel permutating-with-power (PWP)-based method. Then, the proposed two hardware accelerators are presented with detailed structural descriptions. Finally, field-programmable gate array (FPGA)-based implementation is presented to showcase the superior performance of the proposed accelerators. A proper comparison is also carried out to confirm the efficiency of the proposed designs. For instance, the proposed accelerator (using memory-based structure) has 56.84% and 80.25% less area-delay product (ADP) than the existing memory-based design (an extended high-speed version) on the UltraScale+ device, respectively, for\n            <jats:italic>n<\/jats:italic>\n            =17,669 and \u03c9 =75 (HQC) and\n            <jats:italic>n<\/jats:italic>\n            = 12,323 and \u03c9 =142 (BIKE). The proposed design strategy fits well with the two targeted code-based PQC schemes, which can be extended further to construct high-performance hardware cryptoprocessors. We hope the results of this work will be useful for the ongoing NIST PQC standardization process.\n          <\/jats:p>","DOI":"10.1145\/3703837","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T12:48:28Z","timestamp":1733834908000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["HSPA: High-Throughput Sparse Polynomial Multiplication for Code-based Post-Quantum Cryptography"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3461-4548","authenticated-orcid":false,"given":"Pengzhou","family":"He","sequence":"first","affiliation":[{"name":"Electrical and Computer Engineering, Villanova University, Villanova, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1624-9500","authenticated-orcid":false,"given":"Yazheng","family":"Tu","sequence":"additional","affiliation":[{"name":"Electrical and Computer Engineering, Villanova University, Villanova, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3321-5123","authenticated-orcid":false,"given":"Tianyou","family":"Bao","sequence":"additional","affiliation":[{"name":"Electrical and Computer Engineering, Villanova University, Villanova, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2572-9565","authenticated-orcid":false,"given":"\u00c7etin \u00c7etin","family":"Ko\u00e7","sequence":"additional","affiliation":[{"name":"Computer Science, University of California Santa Barbara, Santa Barbara, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4814-1318","authenticated-orcid":false,"given":"Jiafeng","family":"Xie","sequence":"additional","affiliation":[{"name":"Electrical and Computer Engineering, Villanova University, Villanova, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,10]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2024. Are we there yet? An Update on the NIST PQC Standardization Project. NIST 5th PQC Standardization Conference. Retrieved from https:\/\/csrc.nist.gov\/Presentations\/2024\/update-on-the-nist-pqc-standardization-project"},{"key":"e_1_3_2_3_2","unstructured":"2022. PQC Standardization Process: Announcing Four Candidates to be Standardized Plus Fourth Round Candidates. Retrieved from https:\/\/csrc.nist.gov\/News\/2022\/pqc-candidates-to-be-standardized-and-round-4. (2022)."},{"key":"e_1_3_2_4_2","unstructured":"Nicolas Aragon et\u00a0al. 2022. BIKE: Bit Flipping Key Encapsulation (Round 4 Submission). Retrieved from https:\/\/bikesuite.org\/#content. (2022)."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/HOST54066.2022.9839980"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Andrea Basso and Sujoy Sinha Roy. 2021. Optimized polynomial multiplier architectures for post-quantum KEM saber. In 2021 58th ACM\/IEEE Design Automation Conference (DAC). IEEE 1285\u20131290.","DOI":"10.1109\/DAC18074.2021.9586219"},{"key":"e_1_3_2_7_2","article-title":"Towards a Fast and Efficient Hardware Implementation of HQC","author":"Deshpande Sanjay","year":"2022","unstructured":"Sanjay Deshpande, Mamuri Nawan, Kashif Nawaz, Jakub Szefer, and Chuanqi Xu. 2022. Towards a Fast and Efficient Hardware Implementation of HQC. Cryptology ePrint Archive, Paper 2022\/1183. (2022). Retrieved from https:\/\/eprint.iacr.org\/2022\/1183","journal-title":"Cryptology ePrint Archive, Paper 2022\/1183"},{"key":"e_1_3_2_8_2","article-title":"Fast and efficient hardware implementation of HQC","author":"Deshpande Sanjay","year":"2022","unstructured":"Sanjay Deshpande, Chuanqi Xu, Mamuri Nawan, Kashif Nawaz, and Jakub Szefer. 2022. Fast and efficient hardware implementation of HQC. Cryptology ePrint Archive (2022), 1\u201330.","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.19"},{"key":"e_1_3_2_10_2","first-page":"231","volume-title":"2019 International Conference on Field-Programmable Technology (ICFPT)","author":"Hu Jingwei","year":"2019","unstructured":"Jingwei Hu, Wen Wang, Ray CC Cheung, and Huaxiong Wang. 2019. Optimized polynomial multiplier over commutative rings on FPGAs: A case study on BIKE. In 2019 International Conference on Field-Programmable Technology (ICFPT). IEEE, 231\u2013234."},{"issue":"1","key":"e_1_3_2_11_2","first-page":"58","article-title":"High-speed polynomial basis multipliers over  \\(GF (2^m)\\)  for special pentanomials","volume":"63","author":"Ima\u00f1a Jos\u00e9 L","year":"2015","unstructured":"Jos\u00e9 L Ima\u00f1a. 2015. High-speed polynomial basis multipliers over \\(GF (2^m)\\) for special pentanomials. IEEE Transactions on Circuits and Systems I: Regular Papers 63, 1 (2015), 58\u201369.","journal-title":"IEEE Transactions on Circuits and Systems I: Regular Papers"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2022.3169471"},{"key":"e_1_3_2_13_2","article-title":"Area-optimized constant-time hardware implementation for polynomial multiplication","author":"Khan Safiullah","year":"2022","unstructured":"Safiullah Khan, Wai-Kong Lee, Ayesha Khalid, Abdul Majeed, and Seong Oun Hwang. 2022. Area-optimized constant-time hardware implementation for polynomial multiplication. IEEE Embedded Systems Letters 15, 1 (2022), 5\u20138.","journal-title":"IEEE Embedded Systems Letters"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2004.842923"},{"issue":"1","key":"e_1_3_2_15_2","first-page":"203","article-title":"Digit-serial versatile multiplier based on a novel block recombination of the modified overlap-free karatsuba algorithm","volume":"66","author":"Lee Chiou-Yng","year":"2018","unstructured":"Chiou-Yng Lee and J. Xie. 2018. Digit-serial versatile multiplier based on a novel block recombination of the modified overlap-free karatsuba algorithm. IEEE Transactions on Circuits and Systems I: Regular Papers 66, 1 (2018), 203\u2013214.","journal-title":"IEEE Transactions on Circuits and Systems I: Regular Papers"},{"issue":"1","key":"e_1_3_2_16_2","first-page":"203","article-title":"Digit-serial versatile multiplier based on a novel block recombination of the modified overlap-free karatsuba algorithm","volume":"66","author":"Lee Chiou-Yng","year":"2018","unstructured":"Chiou-Yng Lee and Jiafeng Xie. 2018. Digit-serial versatile multiplier based on a novel block recombination of the modified overlap-free karatsuba algorithm. IEEE Transactions on Circuits and Systems I: Regular Papers 66, 1 (2018), 203\u2013214.","journal-title":"IEEE Transactions on Circuits and Systems I: Regular Papers"},{"key":"e_1_3_2_17_2","first-page":"21","volume-title":"2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)","author":"Lee Chiou-Yng","year":"2019","unstructured":"Chiou-Yng Lee and J. Xie. 2019. High capability and low-complexity: Novel fault detection scheme for finite field multipliers over \\({GF}(2^m)\\) based on MSPB. In 2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST). IEEE, 21\u201330."},{"issue":"10","key":"e_1_3_2_18_2","first-page":"2459","article-title":"Optimized schoolbook polynomial multiplication for compact lattice-based cryptography on FPGA","volume":"27","author":"Liu Weiqiang","year":"2019","unstructured":"Weiqiang Liu, Sailong Fan, Ayesha Khalid, Ciara Rafferty, and M\u00e1ire O\u2019Neill. 2019. Optimized schoolbook polynomial multiplication for compact lattice-based cryptography on FPGA. IEEE TVLSI Systems 27, 10 (2019), 2459\u20132463.","journal-title":"IEEE TVLSI Systems"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/LCA.2022.3160394"},{"key":"e_1_3_2_20_2","first-page":"114","article-title":"A public-key cryptosystem based on algebraic","volume":"4244","author":"McEliece Robert J.","year":"1978","unstructured":"Robert J. McEliece. 1978. A public-key cryptosystem based on algebraic. Coding Thv 4244 (1978), 114\u2013116.","journal-title":"Coding Thv"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2008.916622"},{"key":"e_1_3_2_22_2","unstructured":"Carlos Aguilar Melchor et\u00a0al. Hamming Quasi-Cyclic (HQC) (NIST Round 3 Submission). Retrieved from https:\/\/pqc-hqc.org\/index.html. (n.d.)."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220336.2220343"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2019.2903289"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.46586\/tches.v2022.i1.557-588"},{"issue":"5","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/TC.2021.3078294","article-title":"Folding BIKE: Scalable hardware implementation for reconfigurable devices","volume":"71","author":"Richter-Brockmann Jan","year":"2021","unstructured":"Jan Richter-Brockmann, Johannes Mono, and Tim G\u00fcneysu. 2021. Folding BIKE: Scalable hardware implementation for reconfigurable devices. IEEE Trans. Comput. 71, 5 (2021), 1204\u20131215.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3078294"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/3-540-44499-8_22","volume-title":"Cryptographic Hardware and Embedded SystemsCHES 2000: Second International Workshop Worcester, MA, USA, August 17\u201318, 2000 Proceedings 2","author":"Sava\u0161 Erkay","year":"2000","unstructured":"Erkay Sava\u0161, Alexandre F Tenca, and Cetin K Ko\u00e7. 2000. A scalable and unified multiplier architecture for finite fields \\(GF (p)\\) and \\(GF (2^m)\\) . In Cryptographic Hardware and Embedded SystemsCHES 2000: Second International Workshop Worcester, MA, USA, August 17\u201318, 2000 Proceedings 2. Springer, 277\u2013292."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/978-3-662-53008-5_11","volume-title":"Advances in Cryptology\u2013CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, August 14-18, 2016, Proceedings, Part II 36","author":"Schneider Tobias","year":"2016","unstructured":"Tobias Schneider, Amir Moradi, and Tim G\u00fcneysu. 2016. ParTI\u2013towards combined hardware countermeasures against side-channel and fault-injection attacks. In Advances in Cryptology\u2013CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, August 14-18, 2016, Proceedings, Part II 36. Springer, 302\u2013332."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2017.3151345"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2023.3251847"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2023.3246923"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS48785.2022.9937606"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1047755"},{"key":"e_1_3_2_36_2","first-page":"1","volume-title":"IEEE VTS","year":"2020","unstructured":"J. Xie, K. Basu, K. Gaj, and U. Guin. 2020. Special session: The recent advance in hardware implementation of post-quantum cryptography. In IEEE VTS. 1\u201310."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2019.2918836"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703837","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3703837","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:42Z","timestamp":1750295382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703837"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3703837"],"URL":"https:\/\/doi.org\/10.1145\/3703837","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"2023-05-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}