TY - JOUR
T1 - A million-bit multiplier architecture for fully homomorphic encryption
AU - Doröz, Yarkin
AU - Öztürk, Erdinҫ
AU - Sunar, Berk
N1 - Funding Information:
Funding for this research was in part provided by the US National Science Foundation CNS Award #1117590. Funding was also provided by The Scientific and Technological Research Council of Turkey , Project Number 113C019.
Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.
PY - 2014/11
Y1 - 2014/11
N2 - In this work we present a full and complete evaluation of a very large multiplication scheme in custom hardware. We designed a novel architecture to realize a million-bit multiplication scheme based on the Schönhage-Strassen Algorithm. We constructed our scheme using Number Theoretical Transform (NTT). The construction makes use of an innovative cache architecture along with processing elements customized to match the computation and access patterns of the NTT-based recursive multiplication algorithm. We realized our architecture with Verilog and using a 90 nm TSMC library, we could get a maximum clock frequency of 666 MHz. With this frequency, our architecture is able to compute the product of two million-bit integers in 7.74 ms. Our data shows that the performance of our design matches that of previously reported software implementations on a high-end 3 GHz Intel Xeon processor, while requiring only a tiny fraction of the area. 1
AB - In this work we present a full and complete evaluation of a very large multiplication scheme in custom hardware. We designed a novel architecture to realize a million-bit multiplication scheme based on the Schönhage-Strassen Algorithm. We constructed our scheme using Number Theoretical Transform (NTT). The construction makes use of an innovative cache architecture along with processing elements customized to match the computation and access patterns of the NTT-based recursive multiplication algorithm. We realized our architecture with Verilog and using a 90 nm TSMC library, we could get a maximum clock frequency of 666 MHz. With this frequency, our architecture is able to compute the product of two million-bit integers in 7.74 ms. Our data shows that the performance of our design matches that of previously reported software implementations on a high-end 3 GHz Intel Xeon processor, while requiring only a tiny fraction of the area. 1
KW - Fully homomorphic encryption
KW - Number theoretic transform
KW - Very-large number multiplication
UR - http://www.scopus.com/inward/record.url?scp=85027955426&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027955426&partnerID=8YFLogxK
U2 - 10.1016/j.micpro.2014.06.003
DO - 10.1016/j.micpro.2014.06.003
M3 - Article
AN - SCOPUS:85027955426
SN - 0141-9331
VL - 38
SP - 766
EP - 775
JO - Microprocessors and Microsystems
JF - Microprocessors and Microsystems
IS - 8
ER -