Abstract
Modular multiplication of very long integers is a key building block of fully homomorphic encryption and elliptic curve cryptography. The Karatsuba algorithm reduces the multiplication complexity by decomposing the operands into shorter segments. However, in the case of long numbers, adding up the segment products to derive the final product and then carrying out modular reduction as in previous designs can take many clock cycles. This paper focuses on moduli in the format of Solinas prime and proposes to integrate modular reduction into every segment product of the Karatsuba integer multiplication. As a result, the length of the intermediate results is further reduced and they can be added up simultaneously by using a carry-save adder at the cost of small area increase. Additionally, the computation scheduling are optimized to reduce the required number of registers and multiplexers. Complexity analysis shows that, for decomposition factors of 2, 3 and 4, our design requires on average 18.5% less clock cycles with only 5.9% area overhead and similar critical path compared to carrying out the modular reduction on the final product.
Original language | English (US) |
---|---|
Title of host publication | Proceedings - 2021 IEEE Workshop on Signal Processing Systems, SiPS 2021 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 146-151 |
Number of pages | 6 |
ISBN (Electronic) | 9781665401449 |
DOIs | |
State | Published - 2021 |
Event | 2021 IEEE Workshop on Signal Processing Systems, SiPS 2021 - Coimbra, Portugal Duration: Oct 19 2021 → Oct 21 2021 |
Publication series
Name | IEEE Workshop on Signal Processing Systems, SiPS: Design and Implementation |
---|---|
Volume | 2021-October |
ISSN (Print) | 1520-6130 |
Conference
Conference | 2021 IEEE Workshop on Signal Processing Systems, SiPS 2021 |
---|---|
Country/Territory | Portugal |
City | Coimbra |
Period | 10/19/21 → 10/21/21 |
Bibliographical note
Publisher Copyright:© 2021 IEEE.
Keywords
- Carry-save adder
- Karatsuba algorithm
- Modular multiplication
- Solinas Prime