4
$\begingroup$

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-time (i.e. lowest latency) algorithm for repeatedly squaring $x$ modulo $N$ a trillion times?

For context, I am looking to build a Verifiable Delay Function ASIC to squeeze out opportunities for parallelisation that CPUs/GPUs cannot capture.

I have found hundreds of papers in the literature that cover modular multiplication. Families of algorithms include Montgomery, Barrett, Residue Number System (RNS), sum of residues, Kochanski, Brickell. Often the optimised parameter is not latency—e.g. it can be throughput, power consumption, die area, simplicity, side channel leak resistance, etc. The fastest implementation I found does a 4096-bit modular multiplication in 607ns.

Sub-questions:

  1. What is the optimal parallel-time algorithm for squaring a 4096-bit integer? One brute-force approach is to implement a 4096-by-4096 multiplier with $4096^2$ gates and a tree of 3-to-2 adders of depth 4096. Can we do better than that?
  2. The algorithms discussed in the literature often do modular multiplication (as opposed to modular squaring). What latency gains can be had from designing a circuit specific to modular squaring?
$\endgroup$
  • $\begingroup$ (I wish you had defined w for a word size and directed thoughts specifying a value of 4⁶. The given link to Yinan Kong ; Yufeng Lai: "Low latency modular multiplication for public-key cryptosystems using a scalable array of parallel processing elements" provided gets blocked (at least by my provider) due to intellectual rights concerns.) 1) better than [w carry-save adders in series]? yes and no: you can can devise a "Wallace tree" of logarithmic depth, but you cannot route it (make the necessary connections). 2) I don't see but the symmetry halving your gate count an saving one level. $\endgroup$ – greybeard Aug 25 '18 at 6:15
  • $\begingroup$ (What about Hamano, Takagi, Yajima, Preparata: "O(n)-Depth Modular Exponentiation Circuit Algorithm", IEEE ToC '97 pp 701-704? (No cites known?! Ah, not to the ACM, but IEEE knows Walter, C.D.: "Improved linear systolic array for fast modular exponentiation")) $\endgroup$ – greybeard Aug 25 '18 at 6:59
  • $\begingroup$ modular squaring is faster than modular multiplication, these leaks information in the side-channel attack. Therefore it is preferable to perform on squaring. $\endgroup$ – kelalaka Oct 10 '18 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.