2022 IEEE 29th Symposium on Computer Arithmetic (ARITH)

Efﬁcient Word Size Modular Multiplication over
Signed Integers
Daichi Aoki

Kazuhiko Minematsu

Toshihiko Okamura

Secure System Platform Research Labs. Secure System Platform Research Labs. Secure System Platform Research Labs.
NEC Corporation
NEC Corporation
NEC Corporation
Japan
Japan
Japan
daichi aoki@nec.com
k-minematsu@nec.com
t okamura@nec.com

Tsuyoshi Takagi
Department of Mathematical Informatics
University of TokyoJapan
takagi@mist.i.u-tokyo.ac.jp
signiﬁcantly improved their speed in ARM Microcontrollers
and Intel platforms.
The efﬁciency of the modular arithmetic is also importantfor speeding up lattice-based cryptography. This is also true
for RSA [6] and Elliptic Curve Cryptography (ECC) [7],which have been actively studied for a long time. Popular
techniques, such as Montgomery reduction [8] and Barrett
reduction [9], perform modular arithmetic and are particularly
suitable for large moduli, say hundreds or larger. Since latticebased cryptography typically uses smaller moduli, such as afew dozen bits, these techniques are not necessarily the fastest
way to calculate the modular arithmetic.
At ARITH 2021, Plantard [10] proposed a novel algorithm
to compute modular multiplications for one word size moduli,i.e. 32 or 64bits1 . Plantard’s algorithm increases the speedof NTTs with word-size moduli by reducing the number ofmultiplications. It is natural to expect that Chung et al.’s
NTT [5] could improve the overall performance by using [10]as the internal modular arithmetic routine. Unfortunately, thisis not possible as [5] requires the use of signed integers
while [10] assumes unsigned integers. A simple ﬁx, such as
converting a signed integer to an unsigned integer and thenusing Plantard’s technique, would cause a slowdown and a
non-constant-time operation. Constant-time implementations
are one of the major countermeasures against timing attacks,
which extract secret information by measuring the differencesin execution time that depend on secret elements. Since thetiming attack on RSA [11] was proposed, research has been
active and various timing attacks on modular arithmetic andlattice-based schemes have been proposed [12]–[18].
To overcome this problem, we propose a modular multiplication algorithm for signed integers based on [10]. We
provide experimental results on a lattice-based cryptography
Saber [19]. In 2016, the U.S. National Institute of Standards

Abstract—As an efﬁcient multiplication method for polynomial
rings, Number Theoretic Transform (NTT) is a fundamental
algorithm that is both practically useful and theoretically established. Chung et al. proposed a method to perform NTTbased polynomial multiplication for NTT-unfriendly rings that
do not have suitable primitive roots. They applied their proposal
to lattice-based cryptography using NTT-unfriendly rings andspeeded up several schemes. At ARITH 2021, Plantard proposeda modular multiplication algorithm that improves the speed of
NTT if moduli are not large (a few dozen of bits), which isthe case for typical lattice-based cryptography. It is natural toexpect that Plantard’s method improves Chung et al.’s NTT
when applied to them, however, this is not possible as Chunget al. requires the use of signed integers while Plantard’s method
assumes unsigned integers. A simple ﬁx would cause a slowdown
and a non-constant-time operation. To overcome this problem,
we propose an efﬁcient method for calculating the modular
multiplication for signed integers based on Plantard’s method.
Our proposal generally incurs no overhead from the original andworks in a constant-time fashion. To show the effectiveness of
our proposal, we provide experimental implementation results ona lattice-based cryptographic scheme Saber. Currently, NIST is
selecting candidates for standardization of post-quantum cryptography in preparation for the compromise of current publickey cryptography by quantum computers, and has completed
the selection of the ﬁnal candidates. Saber is one of the ﬁnalists
for the NIST standardization project.
Index Terms—Modular Multiplication, Polynomial Multiplication, Number Theoretic Transform, Post-Quantum Cryptography, Saber.

I. I NTRODUCTION
Various efﬁcient multiplication techniques for large integers
or polynomials are known, including Karatsuba [1], ToomCook [2], [3] and Number Theoretic Transform [4]. Number
Theoretic Transform (NTT) is a practically useful and theoretically established fundamental algorithm as a polynomial
multiplication method. Chung et al. [5] proposed an effective
way of performing NTT-based polynomial multiplication for
NTT-unfriendly rings that do not have suitable primitiveroots of unity. They applied their proposal to several latticebased cryptographic schemes using NTT-unfriendly rings and2576-2265/22/$31.00 ©2022 IEEE
DOI 10.1109/ARITH54963.2022.00026

1 Reference [10] was ﬁrst published at ARITH 2021 and later its journalversion was published at IEEE TDSC.

94

division by powers of two can be implemented using the shiftoperation, which is less expensive. Therefore, Montgomery
multiplication [8] is often used, which can compute modular
multiplications using division by a power of two. The calculation procedure of Montgomery multiplication is shown in
Algorithm 1.
We brieﬂy check that the algorithm is correct. First, thefollowing equation holds;

and Technology (NIST) announced the standardization projectfor post-quantum cryptography in preparation for the compromise of current public key cryptography. NIST called forcandidates and 82 schemes were submitted in 2017. Then,
15 schemes (7 ﬁnalists and 8 alternates) were selected inthe 3rd round started in July 2020, and Saber was one of
the ﬁnalists. Saber’s security is based on the hardness of
the Module Learning With Rounding (MLWR) problem [20].
NIST rated Saber as a highly efﬁcient scheme and suitable forgeneral-purpose applications [21].
As mentioned earlier, we propose an efﬁcient algorithm toquickly compute modular multiplication for signed integers
based on [10], which is originally deﬁned over unsigned
integers. The number of multiplications in our proposal is
the same as [10], and the total number of instructions isalmost the same. The instructions used in our method are
only basic operations, as Plantard’s one. Since our algorithm
does not have a branching based on a secret value, we expectthat constant-time implementation is possible (if constant-time
implementation of [10] is possible). We provide experimental implementation results on a lattice-based cryptographic
scheme Saber [19]. The experimental results show that NTTbased polynomial multiplication using our technique is fasterthan that using Montgomery multiplication.
Organization of the paper: In Section II, we introduce
notations on Montgomery reduction, NTT and Chung etal.’s method. In Section III, we describe Plantard’s modular
multiplication algorithm. In Section IV, we present our new
modular multiplication for signed integers. In Section V, weshow experimental results compared to Montgomery multiplication. Section VI will conclude this work.

(AB + P · (ABR mod 2n )) mod 2n=(AB + P · (AB(−P −1 ) mod 2n )) mod 2n=(AB − AB) mod 2n=0.
Therefore, there is an integer k exists such thatAB + P · (ABR mod 2n ) = k2n
holds. Then we get AB2−n mod P = k mod P . The rangeof value of k is0≤k=

AB + P · (ABR mod 2n )P 2 + P 2n
<
< 2P.
2n
2n

Finally, the correction step (line 3-5 of Algorithm 1) yields an
output that satisﬁes 0 ≤ C < P and C = AB2−n mod P .
If P < 2n−2 , then the correction step can be omitted.
Precisely, 0 ≤ C < 2n−1 holds for 0 ≤ A, B < 2n−1 without
correction. This is because
AB + P · (ABR mod 2n )2n(2n−1 )2 + P 2n
<
2n
n−2
<2
+ 2n−2 = 2n−1 .

0≤k=

II. P RELIMINARIES
A. Rounding
We deﬁne two operations to round real numbers to integers.

This redundancy is often used in Montgomery multiplication.

Deﬁnition 1 (Rounding). For a real number x, we denote byx the integer n satisfying n ≤ x < n + 1. We also denoteby x the integer n satisfying n − 12 ≤ x < n + 12 .

Algorithm 1 Montgomery Multiplication [8]Input: A, B, P, R, n with odd modulus P < 2n , 0 ≤ A, B <P and R := (−P −1 ) mod 2n
Output: C = AB2−n mod P with 0 ≤ C < P
1: t ← AB
2: C ← (t + P · (tR mod 2n ))/2n
3: if C ≥ P then4:
return C = C − P
5: end if
6: return C

For any real number x and any integer N , x + N  =x + N , x + N  = x + N and x + 12 = x hold.
For an integer N > 0, we denote the unsigned intervalUN  := {0,1, .. . , N − 1}
 and the signed interval SN :={− N2 , − N2 + 1, . . . , N 2−1 − 1, N 2−1 }. For z ∈ Z, wedenote z mod N ∈ UN and z mod± N ∈ SN the uniquerepresentatives in UN and SN respectively. The following
equations hold;zz, z mod± N = z − N(1)
z mod N = z − N
NNN< 1, − 12 ≤Each of them follows from 0 ≤ z mod
N
z mod± N
1< 2 respectively.
N

Here we consider the case where signed integers − P −1
2 ≤are input to Algorithm 1. In this case, there still
A, B < P −12exists an integer k such that AB + P · (ABR mod 2n ) = k2n .
However, the range of value of k is different;

B. Montgomery Multiplication
The calculation of modular multiplication AB mod N canbe done by using (1), but it is very costly to perform division by general integers on a computer. On the other hand,

−

95

P
|AB|
|AB| + P 2n
P<− n ≤k≤
+ P.
<
4
2
2n
4

and its inverse as follows
⎧
n−1
⎪
⎪
⎪
⎪
R[X]/(X − ζω i ) → R[X]/(X n − ζ n )
⎪
⎨
i=0
NTT−1
.
n:ζ:ω :
n−1 n−1
⎪
⎪
1
−1
−i
j
⎪
ˆ
ˆ
ˆ
ˆ
⎪
(ζ ω ) fi(f , f , . . . , fn−1 ) →⎪⎩ 0 1
n i=0 j=0

Algorithm 2 Signed Montgomery Multiplication [8]Input: A, B, P, R, n with odd modulus P < 2n−1 , |A|, |B| ≤2n−1 and R := (−P −1 ) mod± 2n
Output: C = AB2−n mod± P with |C| ≤ 2n−1
1: t ← AB±
2: return C = (t + P · (tR mod 2n ))/2n

The multiplication of polynomials f, g ∈ R[X]/(X n − ζ n )can be computed as follows (where ◦ is the element-wise
multiplication)

Therefore, in order for output C to fulﬁll |C| ≤ P −1
2 , we needto modify the correction step;f (x)g(x) = NTT−1
n:ζ:ω (NTTn:ζ:ω (f ) ◦ NTTn:ζ:ω (g)).
Let n be a power of two. By using Cooley-Tukey butterﬂy [22] CT : ((f0 , f1 ), ω) → (f0 + ωf1 , f0 − ωf1 )and Gentleman-Sande butterﬂy [23] GS : ((f0 , f1 ), ω) →(f0 + f1 , (f0 − f1 )ω) recursively, NTT and inverse NTT
can be computed efﬁciently. CT and GS are inverse transformations of each other except for the doubling factor;
GS(CT(f0 , f1 , ω), ω −1 ) = 2(f0 , f1 ).
NTT’s calculation method using CT is shown in Algorithm 3, where rev(i) is n-bit reverse of i.

if C ≥ P/2 then return C ← C − P.
n2<
As unsigned version, if P < 2n−2 , then |C| ≤ |AB|+P
2n
n−1
n−1
2
for |A|, |B| < 2without correction.
However, by changing mod to mod± we can use a larger
P , namely, P < 2n−1 . Montgomery multiplication with signed
integers as input and output is shown in Algorithm 2. We cancheck the correctness of Algorithm 2 with almost the same
logic as Algorithm 1. For R = (−P −1 ) mod± P ,Algorithm 3 Number Theoretic Transform(AB + P · (ABR mod± 2n )) mod± 2n

Input: N = 2n , f ∈ (Z/pZ)[X]/(X N − ζ N ) and N -thprimitive root of unity ωOutput: fˆ = {f (ζω rev(i) )}0≤i<N
1: For each i, fˆi ← ζ i fi
2: c ← 1
3: for i = 0 to n − 1 do
4:
for j = 0 to 2i − 1 do
5:
for k = 0 to 2n−1−i − 1 do
6:s ← j2n−i + k
7:t ← j2n−i + k + 2n−1−i8:
tmp ← fˆt ω rev(c) mod p
9:fˆt = (fˆs − tmp) mod p
10:fˆs = (fˆs + tmp) mod p
11:
c←c+1
12:
end for13:
end for
14: end for=(AB − AB) mod± 2n=0.
Therefore, an integer k such that AB+P ·(ABR mod± 2n ) =k2n exists and AB2−n mod± P = k mod± P holds. In thiscase, if P < 2n−1 , the range of value of k is
|AB + P · (AB(−P −1 ) mod± 2n )|2n|AB| + P 2n−1
≤
2n
2n−2
+ 2n−1 2n−1
2<
= 2n−1 .
2n|k| =Therefore, |C| ≤ 2n−1 holds for |A|, |B| ≤ 2n−1 without
correction step.
C. NTT-based Multiplication

D. NTT Multiplication for NTT-unfriendly Rings
Chung et al. [5] proposed a method to perform NTT-based
multiplication for NTT-unfriendly rings. The lattice-based
cryptographic scheme Saber [19] uses an NTT-unfriendly
polynomial ringNumber Theoretic Transform (NTT) is well known as a
useful algorithm for efﬁciently computing polynomial multiplication.
Let be n ≥ 1 an integer and p be prime. Suppose that thequotient ring R := Z/pZ has a n-th root of unity ω and an
invertible element ζ ∈ R . We deﬁne NTTn:ζ:ω as follows

NTTn:ζ:ω :

R = (Z/qZ) [X]/(X n + 1), q = 213 , n = 256.

⎧n−1⎪
⎨R[X]/(X n − ζ n ) →R[X]/(X − ζω i )⎪⎩The reference implementation of Saber performs polynomial
multiplication by Toom-Cook and Karatsuba methods. According to [5], performing Saber’s polynomial multiplications
by NTT-based multiplication improved the computation speed
by about 20% on Cortex-M4.

i=0

f (X) → (f (ζ), f (ζω), . . . , f (ζω n−1 ))96We check the key points of the proof of this theorem. We
denote Q := ABP −1 mod 22n and obtain

Algorithm 4 NTT-based multiplication for Saber [5]Input: f[256], g[256] for f, g ∈ R := (Z/qZ) [X]/(X n + 1),
q = 213 , n = 256 and prime p = 25231359
Output: h[256] for h = f g ∈ R
1: Compute NTT256 (f) and NTT256 (g) over Z/pZ±
2: For each i, compute h[i] = f[i] · g[i] mod p−1
3: Compute NTT256 (h)4: For each i, h[i] ← h[i] & (q − 1)

QP − AB,(3)22n
as did Montgomery multiplication. We further transform theright-hand of (3) and bring together all the ABs. Let Q1 :=Q/2n  and Q0 := Q − Q1 2n = Q mod 2n . If P < 2n /φ,then
P 2n − Q0 P + AB
0<
< 1.
(4)
22n
Consequently, we obtain
QP − ABP 2n − Q0 P + AB
QP − AB
(5)
=
+
22n
22n
22n


(Q − Q0 + 2n )P
(6)
=
22n


(Q1 2n + 2n )P
=
22n


(Q1 + 1)P
=
2n

 ⎥
⎢ 
⎢ ABP −1 mod 22n + 1 P ⎥
⎥
⎢
2n
⎦.
=⎣
2n
AB(−2−2n ) mod P =The following is a brief description of the method usedby [5]. For integer polynomials f, g with coefﬁcients in[−q/2, q/2), the magnitude of each coefﬁcient of the convolution f g mod (X n + 1) is at most nq 2 /4. Then, if we choosea prime p such that p > nq 2 /2 and 2n | (p − 1) are satisﬁed,then
f g mod± (p, X n + 1) = f g mod (X n + 1)
±

(2)

n

holds, where f g mod (p, X + 1) denotes the convolution
f g mod (X n + 1) with all coefﬁcients in [−p/2, p/2). We
can compute the left-hand side of (2) by NTT and recover
the correct result f g mod (q, X n + 1). The methods describedabove are shown in Algorithm 4.
III. P LANTARD M ETHODThis transformation of equation from the sum of products in
Montgomery multiplication to the form of a product by an
integer approximation function is the core idea of Plantard
multiplication.
When we use Algorithm 5 to compute the modular multiplication in NTT (8th line of Algorithm 3), we can precomputeω rev(c) p−1 mod 22n . Therefore, to compute modular multiplication fˆt ω rev(c) mod p, Plantard multiplication requires
two single-word size multiplications (MUL), one single-wordsize addition (ADD) and two shift operations (SHIFT). On
the other hand, Montgomery multiplication without correction
requires three MUL, one ADD, one SHIFT and one logicalAND operation. Plantard method reduces the number of MUL
operations by one. Plantard multiplication needs one more
SHIFT operation than Montgomery multiplication, however,this does not affect efﬁciency as n-bit shifts on a 2n-bit word
are generally cheap.

Plantard [10] proposed an improved version of Montgomery
multiplication that efﬁciently computes n-bit modular multiplications when operating on a 2n-bit word (Algorithm 5).
This algorithm uses the fact that multiplication on a 2n-bit
word is equivalent to a modular multiplication modulo 22n .
The major advantage of this algorithm is that the numberof multiplications is less than Montgomery multiplication if
BR mod 22n can be precomputed, where NTT ﬁts in this case.
According to [10], NTT was about 10% faster by changing
modular multiplications from Montgomery multiplication to
Plantard’s method.
Algorithm 5 Plantard Multiplication [10]Input: A, B, P, R, n with 0 ≤ A, B ≤ P and R = P −1 mod22n−2n
Output: C) mod P with 0 ≤ C <2nP andC= AB(−2
1: C ←
ABR mod 2 /2n + 1 P /2n
2: if C = P then3:
return C − P
4: end if
5: return C

IV. P ROPOSED M ETHOD
Plantard’s Algorithm 5 computes the modular Multiplications in NTTs more efﬁciently than Montgomery Multiplication. However, to use Algorithm 5 with Chung et al.’s method
described in Section II-D, it is necessary to change the inputs
and outputs from unsigned integers to signed integers. Unlike Montgomery multiplication (Algorithm 1 and 2), simply
changing mod to mod± does not work well when the inputs
are signed integers. This is because (4) does not necessarily
hold if the inputs A, B are signed integers.
Another naı̈ve way is the following approach. First, weconvert input signed integers to unsigned integers. Then we

The following theorem holds with respect to the size of P .
Theorem 2 ( [10, Theorem1]). Let P be an odd modulo with√
P < 2n /φ and φ = 1+2 5 , then Algorithm 5 is correct.

97

Now, we analyze the size of k, knowing |A|, |B| ≤ 2n−1 , thenwe get QP − AB 
|k| = 22n
|QP | + |AB|≤22n22n−1 · P + 22n−2
≤
22n
1
P
+ .
=
2
4

process the ﬁrst line of Algorithm 5. Finally, we convert
from unsigned integers to signed integers just before output.
It basically works, however the conversions require additional
instructions. The conversions include operations to determine
whether the given integer is positive or negative, which causes
a branching by an if statement. This branching makes constanttime implementation difﬁcult.
In this study, we propose Algorithm 6, dubbed Signed
Plantard Multiplication, in which the inputs and outputs of Algorithm 5 are changed from unsigned integers to signed integers. This algorithm handles signed integers without branching
while maintaining efﬁciency. Since there is no branching by ifstatements, a constant-time implementation of this algorithm ispossible. The number of required multiplications is the sameas in Algorithm 5, and the number of additions, shifts, andlogical AND operations is almost the same.

Furthermore, since k is an integer and P is an odd integer,
we have − P −1
≤ k ≤ P −1
2
2 . Consequently, we obtain±k mod P = k andAB(−2−2n ) mod± P = k =Algorithm 6 Signed Plantard Multiplication
n−1

Input: A, B, P, R, n with |A|, |B| ≤ 2
P −1 mod± 22n±−2n
Output: CP = AB(−2 ±) mod
2n
1: C ←(ABR mod 2 )/2n P /2n
2: return C

Let Q0 := Q mod± 2n and Q1 := Q/2n  = (Q−Q0 )/2n ,and we assume

and R =−

Theorem 3. Let P be an odd modulo with P < 2n−1 . Then
Algorithm 6 is correct.

⎢⎤⎢ ABP −1 mod± 22n · P⎢
2n⎥ = AB(−2−2n ) mod± P.
⎣⎥2n⎥
To ﬁnish this proof, we show that assumption (8) holds if
P < 2n−1 ;As P is odd, there exists a Q := ABP −1 mod± 22n .
Therefore, we have
(QP − AB) mod2= (ABP−1

P − AB) mod

±

2

(8)

As Q1 = (ABP −1 mod± 22n )/2n , we obtain that

Proof of Theorem 3: We check the output of Algorithm 6
C = AB(−2−2n ) mod± P , i.e.,⎢⎤⎢ ABP −1 mod± 22n · P⎢
2n⎥ = AB(−2−2n ) mod± P.
⎣
⎥
2n
⎥

2n

1
AB − Q0 P
1
≤
< .
2
22n
2

We show at the end of the proof that (8) holds. From theassumption (8) and the fact that QP − AB is divisible by 22n ,the following holds;
QP − AB
QP − ABAB − Q0 P
=
+
22n
22n
22n


(Q − Q0 )P
=
22n


Q1 P
.
=
2n

To make Plantard multiplication work well when the inputs
are signed integers, we need to modify (4). The (−Q0 P +AB)
part of (4) plays an important role in the transformation (6).
If we deﬁne Q0 as Q mod± 22n , (−Q0 P + AB) is zerocentered. To take advantage of this property, we assume − 12 ≤−Q0 P +AB
< 12 and use the round function ·, not the ﬂoor
22nfunction · at (5) (see the proof of Theorem 3 for details).

±

QP − AB.
22n|AB − Q0 P | ≤ |AB| + |Q0 P |< 2n−1 · 2n−1 + 2n−1 · 2n−1

2n

= 22n−1 .

= 0.
We observe that there exists an integer k satisfying
QP − AB = k22n

By tightening the constraints on inputs A and B, the rangeof P can be increased.

(7)

and therefore

Corollary
4. Let P be an odd modulo with P <12n
3 − 2n−1− 1 + 1. Then Algorithm 6 is correct for(7) ⇒ (−AB) mod± P = k22n mod± P⇒ AB(−2−2n ) mod± P = k mod± P.

inputs A, B with |A|, |B| ≤ P −1
2 .

98

Proof of Corollary 4: We check that the assumption (8)in the proof is satisﬁed.

Source code 1
S IGNED P LANTARD M ULTIPLICATION
int64_t signedPlantardMul(int64_t A, int64_t B) {return (((A*B + 0x80000000)>>32)*P + 0x80000000)>>32;}|AB − Q0 P | ≤ |AB| + |Q0 P |
2

P −1
+ 2n−1 P
≤
2
2

P −1
+ 2n−1 − 22n−2 + 2n−1
=
2


2
1
n−1
n−1
< 2
3 − n−1 − 1 + 2
2

Source code 2
S IGNED M ONTGOMERY M ULTIPLICATION
int signedMontgomeryMul(int A, int B) {int64_t t = (int64_t) A*B;
return (t+(((t & 0xFFFFFFFF)*R) & 0xFFFFFFFF)*P)>>32;}− 22n−2 + 2n−1

1
= 22n−2 3 − n−1 − 22n−2 + 2n−1
2
= 22n−1

V. E XPERIMENTAL R ESULTS
In this section, we compare the performance of Signed
Plantard Multiplication (Algorithm 6) with that of signed
Montgomery multiplication (Algorithm 2). We also present
a comparison between the NTT-based multiplication using
signed Plantard multiplication and that using signed Montgomery multiplication.

Remark 5. In the proposed Algorithm 6, the output range is
P −1
already [− P −1
2 , 2 ], so there is no need to use if statements.
We show that this is also true for Plantard’s algorithm 5.
We check that in the following inequality

 ⎥
⎢ 
⎢ ABP −1 mod 22n + 1 P ⎥⎢⎥ ((2n − 1) + 1)P
2n
⎣
⎦≤
= P,
n
2
2n
the quality condition
ABP −1 mod 22n= 2n − 12n

A. C implementations
We implemented NTT-based multiplication for Saber [19]by Chung et al.’s method [5], i.e. size-256 NTT and inverse
NTT over a polynomial ring R = (Z/pZ) [X]/(X 256 + 1),
p = 25231361 = 49280 · 512 + 1 (see Algorithm 4).
In [5], Chung et al. implemented their NTT-based polynomial
multiplication with 25-bit modulus on ARM 32-bit Microcontrollers. On a 64-bit processor, however, we can use signed
Plantard multiplication instead of Montgomery multiplication
for modular multiplication with 25-bit modulus.
The C implementations of signed Plantard multiplicationand signed Montgomery multiplication for the NTT-based
multiplication are shown in source code 1 and 2. The inputs A, B satisfy −232 ≤ A, B < 232 . The parameters
P = 25231361, n = 32 and R = (−P −1 ) mod± 2n =25231359 for signed Montgomery multiplication. In signed
Plantard multiplication, the product BR mod± 22n for R =P −1 mod± 22n is precomputed and again denoted as B.
The rounding X/2n  is calculated as (X + 2n−1 )/2n . The
instructions used in both source codes and the number of times
they are used are summarized in the TABLE I. Since ourmethod used one less instruction each for MUL and the total
number of instructions, the proposed method is considered
to be more advantageous for platforms in particular, when
multiplication takes multiple cycles.

(9)

does not hold. Assuming that equality (9) holds, we derive acontradiction.
ABP −1 mod 22n(9) ⇒ 2n − 1 ≤< 2n2n⇒ ABP −1 mod 22n = 22n − r for ∃ r ∈ Z, 0 < r ≤ 2n
⇒ AB mod 22n = (22n − r)P mod 22n⇒ AB mod 22n = (−rP ) mod 22n⇒ AB = 22n − rP(∵ 0 ≤ AB < 22n , 0 < 22n − rP < 22n )⇒ AB + rP = 22n .

(10)

Now we evaluate the size of AB + rP .
|AB + rP | ≤ P 2 + 2n P
= (P + 2n−1 )2 − 22n−2< (2n /φ + 2n−1 )2 − 22n−2= 22n−2 (2/φ + 1)2 − 22n−2

B. Benchmarking for K210

= 22n−2 (4/φ2 + 4/φ)
1+φ
= 22n 2φ2n=2(∵ φ2 − φ − 1 = 0)

We measured performance on the Sipeed Maixduino2 development board based on the Kendryte SoC K2103 (64-bit
2 https://www.seeedstudio.com/Sipeed-Maixduino-Kit-for-RISC-V-AI-IoTp-4047.html
3 https://canaan.io/product/kendryteai

From the above, equation (10) does not hold, hence thecontradiction is revealed.

99

TABLE IIC OMPARISON BETWEEN OUR AND M ONTGOMERY ’ S MODULAR
MULTIPLICATION .

TABLE IC OMPARISON OF NUMBER OF INSTRUCTIONS BETWEEN OUR METHOD
AND M ONTGOMERY MULTIPLICATION .
Instruction
MUL (*)ADD (+)SHIFT ()AND (&)Total

Our method (Alg. 6)
2
2
2
0
6

Algorithm
Montgomery (Alg. 2)
Our method (Alg. 6)

Montgomery (Alg. 2)
3
1
1
2
7

CPU cycle
38
31

TABLE IIIC OMPARISON OF PQC LEAN T OOM -C OOK MULTIPLICATION AND
NTT- BASED POLYNOMIAL MULTIPLICATION (NTT-M UL ) WITH OURMETHOD AND M ONTGOMERY MULTIPLICATION FOR S ABER .

RISC-V RV64GC 400 MHz). Maixduino is a popular RISCV-based MCU and was used in the third-party evaluation of
NIST Lightweight cryptography by Renner et al. [24]4 . We
compiled our implementations with RISC-V GCC toolchain
for Kendryte 210 toolchain-kendryte2105 by PlatformIO with
-O3 options.
The portable C implementation of Saber is available atthe ofﬁcial web page6 . An almost identical implementation isprovided by PQClean project7 , an OSS project that provides
portable C implementations of the post-quantum schemes in
the NIST PQC project. These implementations use Karatsuba
and Toom-Cook multiplication for polynomial multiplications.
Toom-Cook algorithm splits each of the two given polynomialsof degree n into d + 1 polynomials of degree n/(d + 1),
evaluates the values at 2d + 1 different points, computes
pointwise multiplication, performs polynomial interpolation,and ﬁnally reconstructs the product of the given polynomials.
When d = 1, this algorithm is called Karatsuba multiplication.
In PQClean’s Toom-Cook, d = 3 and pointwise multiplications of degree 64 are calculated by Karatsuba multiplication.
In Kendryte K210, we compare PQClean’s Toom-Cook multiplication and our C implementations of NTT-based polynomial
multiplication using Montgomery multiplication and signed
Plantard multiplication, respectively.
TABLE II presents the measured CPU cycles for signed
Plantard multiplication (Source code 1) and signed Montgomery multiplication (Source code 2). The values in thetable are the minimum of 10,000 tests. In Kendryte K210,
our method was about 23% faster than signed Montgomery
multiplication. Since no assembly analysis was performed inthis study and the K210 datasheet does not provide information
on instruction cycles, an accurate analysis is difﬁcult. However, after some experiments on instruction cycles, we presume
the reduced number of MUL could be the main contributionof this gain. In this C implementation, the round function
was implemented with a ﬂoor function, which increased thenumber of ADD. In some environments, it is possible that
instructions corresponding to the round function could be used,
and the execution cycles could be even smaller.
TABLE III shows the cycle results for PQClean’s ToomCook multiplication vs. our NTT-based polynomial multipli-

Algorithm
PQClean Toom-Cook
NTT-Mul with Montgomery (Alg. 4 + Alg. 2)
NTT-Mul with our method (Alg. 4 + Alg. 6)

CPU cycle
184,919
115,050
98,952

cation using Montgomery multiplication and signed Plantard
multiplication, respectively. The values in the table are theminimum of 10,000 tests. Our method was about 16% faster
when used within NTT-based multiplication. Changing thealgorithm for calculating modular multiplications from signed
Montgomery multiplication to signed Plantard multiplication
improves the efﬁciency of computing of modular multiplication by a constant, especially in the butterﬂy operation in
NTT (line 8 of Algorithm 3). As can be seen from TABLE I,
the calculation of fˆt ω rev(c) mod± p with signed Plantard
multiplication saves one MUL instruction. Since we need toperform the butterﬂy operations n log2 n times in Algorithm 4,
the impact of this gain on the overall efﬁciency is signiﬁcant.
VI. C ONCLUSION
In this work, we proposed an efﬁcient method for computing
the modular multiplication of signed integers when operating
on a single word with reference to Plantard’s method [10],which is originally deﬁned over unsigned integers. The numberof operations of our method is almost the same as that of [10],and the efﬁciency is considered to be maintained. In addition,
since there is no branching in the algorithm, constant-time
implementation is possible. This features would be lost if we
apply a conventional conversion of Plantard method so that
it works on signed integers. A promising application of our
proposal is lattice-based cryptography using Number Theoretic
Transform deﬁned over signed integers.
To demonstrate the merit of our proposal, we implemented
our method for NTT-based multiplication in Saber [19] by
Chung et al.’s method [5] and achieved a speedup of about
16% on a RISC-V CPU K210 compared to using signed
Montgomery multiplication.
We expect our method improves the performance of otherlattice-based cryptography schemes that beneﬁt from NTT.
For example, CRYSTALS-Kyber [25], one of NIST PQC
ﬁnalists, uses NTT-based polynomial multiplication with 12bit modulus. Implementing Kyber on a 32-bit CPU with our
proposal is interesting, especially considering that Kyber is
now selected as one of the winners of NIST PQC. We can

4 https://lwc.las3.de/
5 https://registry.platformio.org/tools/platformio/toolchain-kendryte210
6 https://www.esat.kuleuven.be/cosic/pqcrypto/saber/
7 https://github.com/PQClean/PQClean100

apply NTT with our algorithm to lattice-based schemes deﬁned
over NTT-unfriendly rings by Chung et al.’s technique as well.
Such examples are NTRU [26], another NIST PQC ﬁnalist,and LAC [27], the award winner of the PQC competition
hosted by Chinese Association for Cryptologic Research (alsoa NIST PQC round 2 candidate). Implementation of NTRU
and LAC using our method is an interesting future work.

ser. Lecture Notes in Computer Science, J. Katz and M. Yung, Eds., vol.
4521. Springer, Heidelberg, Jun. 2007, pp. 129–140.
[14] M. Vielhaber, “Reduce-by-feedback: Timing resistant and DPA-aware
modular multiplication plus: How to break RSA by DPA,” in Cryptographic Hardware and Embedded Systems – CHES 2012, ser. Lecture
Notes in Computer Science, E. Prouff and P. Schaumont, Eds., vol. 7428.
Springer, Heidelberg, Sep. 2012, pp. 463–475.
[15] J. Mittmann and W. Schindler, “Timing attacks and local timing attacks
against barrett’s modular multiplication algorithm,” Cryptology ePrint
Archive, Report 2020/946, 2020, https://eprint.iacr.org/2020/946.
[16] J. H. Silverman and W. Whyte, “Timing attacks on NTRUEncrypt via
variation in the number of hash calls,” in Topics in Cryptology – CTRSA 2007, ser. Lecture Notes in Computer Science, M. Abe, Ed., vol.
4377. Springer, Heidelberg, Feb. 2007, pp. 208–224.
[18] Q. Guo, T. Johansson, and A. Nilsson, “A key-recovery timing attackon post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM,” in Advances in Cryptology– CRYPTO 2020, Part II, ser. Lecture Notes in Computer Science,
D. Micciancio and T. Ristenpart, Eds., vol. 12171. Springer, Heidelberg,
Aug. 2020, pp. 359–386.
[19] J.-P. D’Anvers, A. Karmakar, S. S. Roy, F. Vercauteren, J. M. B. Mera,
M. V. Beirendonck, and A. Basso, “SABER,” National Institute ofStandards and Technology, Tech. Rep., 2020, available at https://csrc.
nist.gov/projects/post-quantum-cryptography/round-3-submissions.
[20] J.-P. D’Anvers, A. Karmakar, S. S. Roy, and F. Vercauteren, “Saber:
Module-LWR based key exchange, CPA-secure encryption and CCAsecure KEM,” in AFRICACRYPT 18: 10th International Conference on
Cryptology in Africa, ser. Lecture Notes in Computer Science, A. Joux,
A. Nitaj, and T. Rachidi, Eds., vol. 10831. Springer, Heidelberg, May
2018, pp. 282–305.
[21] D. Moody, G. Alagic, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.K. Liu, C. Miller, R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone,
and J. Alperin-Sheriff, “Status report on the second round of the nist
post-quantum cryptography standardization process,” 2020-07-22 2020.
[22] J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculationof complex fourier series,” Mathematics of computation, vol. 19, no. 90,
pp. 297–301, 1965.
[23] W. M. Gentleman and G. Sande, “Fast fourier transforms: for fun andproﬁt,” in Proceedings of the November 7-10, 1966, fall joint computer
conference, 1966, pp. 563–578.
[24] S. Renner, E. Pozzobon, and J. Mottok, “A hardware in the loop
benchmark suite to evaluate NIST LWC ciphers on microcontrollers,”
in ICICS 20: 22nd International Conference on Information and Communication Security, ser. Lecture Notes in Computer Science, W. Meng,
D. Gollmann, C. D. Jensen, and J. Zhou, Eds., vol. 11999. Springer,
Heidelberg, Aug. 2020, pp. 495–509.
[25] P. Schwabe, R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, G. Seiler, and D. Stehlé,“CRYSTALS-KYBER,” National Institute of Standards and Technology, Tech. Rep., 2020, available at https://csrc.nist.gov/projects/
post-quantum-cryptography/round-3-submissions.
[26] C. Chen, O. Danba, J. Hoffstein, A. Hulsing, J. Rijneveld, J. M.
Schanck, P. Schwabe, W. Whyte, Z. Zhang, T. Saito, T. Yamakawa,
and K. Xagawa, “NTRU,” National Institute of Standards and Technology, Tech. Rep., 2020, available at https://csrc.nist.gov/projects/
post-quantum-cryptography/round-3-submissions.
[27] X. Lu, Y. Liu, D. Jia, H. Xue, J. He, Z. Zhang, Z. Liu, H. Yang,
B. Li, and K. Wang, “LAC,” National Institute of Standards andTechnology, Tech. Rep., 2019, available at https://csrc.nist.gov/projects/
post-quantum-cryptography/round-2-submissions.

R EFERENCES[1] A. Karatsuba, “Multiplication of multidigit numbers on automata,” inSoviet physics doklady, vol. 7, 1963, pp. 595–596.
[2] A. L. Toom, “The complexity of a scheme of functional elements
realizing the multiplication of integers,” in Soviet Mathematics Doklady,
vol. 3, no. 4, 1963, pp. 714–716.
[3] S. A. Cook and S. O. Aanderaa, “On the minimum computation
time of functions,” Transactions of the American MathematicalSociety, vol. 142, pp. 291–314, 1969. [Online]. Available: http://www.jstor.org/stable/1995359[4] R. Agarwal and C. Burrus, “Fast convolution using fermat number
transforms with applications to digital ﬁltering,” IEEE Transactions on
Acoustics, Speech, and Signal Processing, vol. 22, no. 2, pp. 87–97,
1974.
[5] C.-M. M. Chung, V. Hwang, M. J. Kannwischer, G. Seiler, C.-J. Shih,and B.-Y. Yang, “NTT multiplication for NTT-unfriendly rings,” IACR
Transactions on Cryptographic Hardware and Embedded Systems, vol.
2021, no. 2, pp. 159–188, 2021, https://tches.iacr.org/index.php/TCHES/
article/view/8791.
[6] R. L. Rivest, A. Shamir, and L. M. Adleman, “A method for obtaining
digital signatures and public-key cryptosystems,” Communications of the
Association for Computing Machinery, vol. 21, no. 2, pp. 120–126, 1978.
[7] V. S. Miller, “Use of elliptic curves in cryptography,” in Advances in
Cryptology – CRYPTO’85, ser. Lecture Notes in Computer Science,
H. C. Williams, Ed., vol. 218. Springer, Heidelberg, Aug. 1986, pp.
417–426.
[8] P. L. Montgomery, “Modular multiplication without trial division,”
Mathematics of computation, vol. 44, no. 170, pp. 519–521, 1985.
[9] P. Barrett, “Implementing the Rivest Shamir and Adleman public key
encryption algorithm on a standard digital signal processor,” in Advancesin Cryptology – CRYPTO’86, ser. Lecture Notes in Computer Science,
A. M. Odlyzko, Ed., vol. 263. Springer, Heidelberg, Aug. 1987, pp.
311–323.
[10] T. Plantard, “Efﬁcient word size modular arithmetic,” IEEE Transactions
on Emerging Topics in Computing, vol. 9, no. 3, pp. 1506–1518, 2021.
[11] P. C. Kocher, “Timing attacks on implementations of Difﬁe-Hellman,
RSA, DSS, and other systems,” in Advances in Cryptology –CRYPTO’96, ser. Lecture Notes in Computer Science, N. Koblitz, Ed.,
vol. 1109. Springer, Heidelberg, Aug. 1996, pp. 104–113.
[12] Y. Sakai and K. Sakurai, “Timing attack against implementation of aparallel algorithm for modular exponentiation,” in ACNS 03: 1st International Conference on Applied Cryptography and Network Security,ser. Lecture Notes in Computer Science, J. Zhou, M. Yung, and Y. Han,
Eds., vol. 2846. Springer, Heidelberg, Oct. 2003, pp. 319–330.
[13] B. Bakhshi and B. Sadeghiyan, “A timing attack on Blakley’s modular
multiplication algorithm, and applications to DSA,” in ACNS 07: 5th International Conference on Applied Cryptography and Network Security,[17] M. Tibouchi and A. Wallet, “One bit is all it takes: A devastating
timing attack on BLISS’s non-constant time sign ﬂips,” Cryptology
ePrint Archive, Report 2019/898, 2019, https://eprint.iacr.org/2019/898.

101