{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:48:39Z","timestamp":1762004919250,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>Somewhat Homomorphic Encryption (SHE) schemes can be used to carry out operations on ciphered data. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. The principle limitation of SHE is the size of ciphertext compared to the size of the message. This issue can be addressed by using a batching technique that \u201cpacks\u201d several messages into one ciphertext. However, this method leads to important drawbacks in standard implementations. This paper presents a fast hardware\/software co-design implementation of an encryption procedure using the Karatsuba algorithm. Our hardware accelerator is 1.5 times faster than the state of the art for 1 encryption and 4 times faster for 4 encryptions.<\/jats:p>","DOI":"10.1145\/3126558","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["A High-Speed Accelerator for Homomorphic Encryption using the Karatsuba Algorithm"],"prefix":"10.1145","volume":"16","author":[{"given":"Vincent","family":"Migliore","sequence":"first","affiliation":[{"name":"Univ. Bretagne-Sud, UMR CNRS 6285, Lab-STICC, F-56100 Lorient, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e9dric","family":"Seguin","sequence":"additional","affiliation":[{"name":"Univ. Bretagne-Sud, UMR CNRS 6285, Lab-STICC, F-56100 Lorient, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria M\u00e9ndez","family":"Real","sequence":"additional","affiliation":[{"name":"Univ. Bretagne-Sud, UMR CNRS 6285, Lab-STICC, F-56100 Lorient, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vianney","family":"Lapotre","sequence":"additional","affiliation":[{"name":"Univ. Bretagne-Sud, UMR CNRS 6285, Lab-STICC, F-56100 Lorient, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Tisserand","sequence":"additional","affiliation":[{"name":"CNRS, Lab-STICC UMR 6285, and Univ. Bretagne Sud, Lorient, 56321 France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caroline","family":"Fontaine","sequence":"additional","affiliation":[{"name":"CNRS Lab-STICC and IMT-Atlantique, CS83818, 29238 Brest cedex 3, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Gogniat","sequence":"additional","affiliation":[{"name":"Univ. Bretagne-Sud, UMR CNRS 6285, Lab-STICC, F-56100 Lorient, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Tessier","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA, USA 01003"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. of CRYPTO.","author":"Gamal T. E.","year":"1984","unstructured":"T. E. Gamal . 1984 . A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms . In Proc. of CRYPTO. T. E. Gamal. 1984. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Proc. of CRYPTO."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.5555\/1756123.1756146"},{"volume-title":"Proc. of CRYPTO.","author":"Aguilar Melchor C.","unstructured":"C. Aguilar Melchor , P. Gaborit , and J. Herranz . 2010. Additively Homomorphic Encryption with D-Operand Multiplications . In Proc. of CRYPTO. C. Aguilar Melchor, P. Gaborit, and J. Herranz. 2010. Additively Homomorphic Encryption with D-Operand Multiplications. In Proc. of CRYPTO.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/2090236.2090262"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/978-3-642-32009-5_50"},{"unstructured":"J. Fan and F. Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive Report 2012\/144.  J. Fan and F. Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive Report 2012\/144.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","volume-title":"Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Proc. of CRYPTO.","author":"Gentry C.","year":"2013","unstructured":"C. Gentry , A. Sahai , and B. Waters . 2013 . Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Proc. of CRYPTO. C. Gentry, A. Sahai, and B. Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Proc. of CRYPTO."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/2554797.2554799"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1109\/TC.2015.2500576"},{"volume-title":"Proc. of AFRICACRYPT.","author":"Lepoint T.","unstructured":"T. Lepoint and M. Naehrig . 2014. A Comparison of the Homomorphic Encryption Schemes FV and YASHE . In Proc. of AFRICACRYPT. T. Lepoint and M. Naehrig. 2014. A Comparison of the Homomorphic Encryption Schemes FV and YASHE. In Proc. of AFRICACRYPT.","key":"e_1_2_1_11_1"},{"volume-title":"Proc. of EUROCRYPT.","author":"Cheon J. H.","unstructured":"J. H. Cheon , J.-S. Coron , J. Kim , M. S. Lee , T. Lepoint , M. Tibouchi , and A. Yun . 2013. Batch Fully Homomorphic Encryption over the Integers . In Proc. of EUROCRYPT. J. H. Cheon, J.-S. Coron, J. Kim, M. S. Lee, T. Lepoint, M. Tibouchi, and A. Yun. 2013. Batch Fully Homomorphic Encryption over the Integers. In Proc. of EUROCRYPT.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"crossref","unstructured":"J. Pollard. 1971. The Fast Fourier Transform in a Finite Field. In Mathematics of Computation.  J. Pollard. 1971. The Fast Fourier Transform in a Finite Field. In Mathematics of Computation.","key":"e_1_2_1_13_1","DOI":"10.1090\/S0025-5718-1971-0301966-0"},{"volume-title":"Proc. of CHES.","author":"Sinha Roy S.","unstructured":"S. Sinha Roy , K. J\u00e4rvinen , F. Vercauteren , V. Dimitrov , and I. Verbauwhede . 2015. Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation . In Proc. of CHES. S. Sinha Roy, K. J\u00e4rvinen, F. Vercauteren, V. Dimitrov, and I. Verbauwhede. 2015. Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation. In Proc. of CHES.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","article-title":"Hardware\/Software co-Design of an Accelerator for FV Homomorphic Encryption Scheme using Karatsuba Algorithm","author":"Migliore V.","year":"2016","unstructured":"V. Migliore , M. Mendez Real , V. Lapotre , A. Tisserand , C. Fontaine , and G. Gogniat . 2016 . Hardware\/Software co-Design of an Accelerator for FV Homomorphic Encryption Scheme using Karatsuba Algorithm . IEEE Transactions on Computers. V. Migliore, M. Mendez Real, V. Lapotre, A. Tisserand, C. Fontaine, and G. Gogniat. 2016. Hardware\/Software co-Design of an Accelerator for FV Homomorphic Encryption Scheme using Karatsuba Algorithm. IEEE Transactions on Computers.","journal-title":"IEEE Transactions on Computers."},{"unstructured":"A. Karatsuba and Y. Ofman. 1962. Multiplication of Multi-Digit Numbers on Automata (in Russian). Doklady Akad. Nauk SSSR. Translation in Soviet Physics-Doklady.  A. Karatsuba and Y. Ofman. 1962. Multiplication of Multi-Digit Numbers on Automata (in Russian). Doklady Akad. Nauk SSSR. Translation in Soviet Physics-Doklady.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_2_1_18_1","volume-title":"Proc. of CRYPTO.","author":"Barrett P.","year":"1986","unstructured":"P. Barrett . 1986 . Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor . In Proc. of CRYPTO. P. Barrett. 1986. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. In Proc. of CRYPTO."},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/2815631"},{"key":"e_1_2_1_20_1","volume-title":"MArc-Olivier","author":"Aguilar-Melchor C.","year":"2016","unstructured":"C. Aguilar-Melchor , J. Barrier , S. Guelton , A. Guinet , and L. T. Killijian , MArc-Olivier . 2016 . NFLlib: NTT- Based Fast Lattice Library . C. Aguilar-Melchor, J. Barrier, S. Guelton, A. Guinet, and L. T. Killijian, MArc-Olivier. 2016. NFLlib: NTT-Based Fast Lattice Library."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126558","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:02Z","timestamp":1750273502000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":19,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126558"],"URL":"https:\/\/doi.org\/10.1145\/3126558","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}