Number theoretic transform with parallel coefficient processing
Electronic device and method for performing number theoretic transforms (NTTs) on polynomials for cryptography uses an arithmetic transformation on an input polynomial with n coefficients to divide the input polynomial into multiple polynomials each with less than n coefficients such that the coefficients of the multiple polynomials add up to n. An NTT transformation is executed on the multiple polynomials such that the coefficients of each of the multiple polynomials are processed in parallel butterfly operations. A cryptographic operation is performed based on the results of the NTT transformation.
1 . A computer-implemented method for performing number theoretic transforms (NTTs) on polynomials for cryptography, the method comprising:
receiving, by a coprocessor, a data structure storing n values, each value representing a corresponding integer coefficient of an input polynomial function of an independent variable;
segmenting the data structure into m segments having bit-lengths that are equal to a word length w of the coprocessor using an arithmetic transformation of the input polynomial function into multiple polynomial functions, each segment storing n/m values of the data structure;
performing, in registers of the coprocessor having the word length w of the coprocessor, a recursive divide-and-conquer butterfly computation using each of the segments m to produce a vector output having integer values corresponding to a number theoretic transform (NTT) of the data structure; and
performing, by the coprocessor, a cryptographic operation based on the vector output; and
wherein the cryptographic operation comprises one or more of generating secret keys, generating public keys, creating digital signatures, verifying digital signatures, encrypting digital messages, and decrypting digital messages.
2 . The method of claim 1 , wherein the number of the multiple polynomial functions is M=n/m, where n is the number of coefficients for each of the multiple polynomial functions.
3 . The method of claim 2 , wherein m equals the word length w divided by 2l, where l is the smallest power of two larger than log q and q is a prime number.
4 . The method of claim 3 , wherein the input polynomial function is f=Σ i=0 n f i X i in a ring R q =F q [X]/(X n +1).
5 . The method of claim 2 , wherein the coefficients of each of the multiple polynomial functions fit in a w-bit register of the coprocessor.
6 . The method of claim 2 , wherein the input polynomial function includes a variable X and wherein the arithmetic transformation includes replacing X m in the input polynomial function with a variable Y.
7 . The method of claim 6 , wherein performing the recursive divide-and-conquer butterfly computation includes executing the following transformation:
F
(
X
,
Y
)
↦
(
F
(
X
,
ζ
)
,
F
(
X
,
ζ
3
)
…
,
F
(
X
,
ζ
2
n
m
-
1
)
)
,
where ζ is a root of unity for F (X, Y).
8 . The method of claim 1 further comprising executing a transformation on the vector output to convert the vector output to Gentleman-Sande style NTT results.
9 . A non-transitory computer-readable storage medium containing program instructions for performing number theoretic transforms (NTTs) on polynomials for cryptography, wherein execution of the program instructions by one or more processors of a computer causes the one or more processors to perform a method comprising:
receiving, by a coprocessor, a data structure storing n values, each value representing a corresponding integer coefficient of an input polynomial function of an independent variable;
segmenting the data structure into m segments having bit-lengths that are equal to a word length w of the coprocessor using an arithmetic transformation of the input polynomial function into multiple polynomial functions, each segment storing n/m values of the data structure;
performing, in registers of the coprocessor having the word length w of the coprocessor, a recursive divide-and-conquer butterfly computation using each of the segments to produce a vector output having integer values corresponding to a number theoretic transform of the data structure; and
performing a cryptographic operation based on the vector output; and
wherein the cryptographic operation comprises one or more of generating secret keys, generating public keys, creating digital signatures, verifying digital signatures, encrypting digital messages, and decrypting digital messages.
10 . The non-transitory computer-readable storage medium of claim 9 , wherein the number of the multiple polynomial functions is M=n/m, where n is the number of coefficients for each of the multiple polynomial functions.
11 . The non-transitory computer-readable storage medium of claim 10 , wherein m equals the word length w divided by 2l, where l is the smallest power of two larger than log q and q is a prime number.
12 . The non-transitory computer-readable storage medium of claim 11 , wherein the input polynomial function is f=Σ i=0 n f i X i in a ring R q =F q [X]/(X n +1).
13 . The non-transitory computer-readable storage medium of claim 10 , wherein the coefficients of each of the multiple polynomial functions fit in a w-bit register of the coprocessor.
14 . The non-transitory computer-readable storage medium of claim 10 , wherein the input polynomial function includes a variable X and wherein the arithmetic transformation includes replacing X m in the input polynomial function with a variable Y.
15 . The non-transitory computer-readable storage medium of claim 14 , wherein performing the recursive divide-and-conquer butterfly computation includes executing the following transformation:
F
(
X
,
Y
)
↦
(
F
(
X
,
ζ
)
,
F
(
X
,
ζ
3
)
…
,
F
(
X
,
ζ
2
n
m
-
1
)
)
,
where ζ is a root of unity for F(X, Y).
16 . The non-transitory computer-readable storage medium of claim 9 , wherein the steps further comprise executing a transformation on the vector output to convert the vector output to Gentleman-Sande style NTT results.
17 . An electronic device comprising:
memory; and
at least one processor, including a coprocessor, configured to:
receive, by the coprocessor, a data structure storing n values, each value representing a corresponding integer coefficient of an input polynomial function of an independent variable;
segment, by the coprocessor, the data structure into m segments having bit-lengths that are equal to a word length w of the coprocessor using an arithmetic transformation of the input polynomial function into multiple polynomial functions, each segment storing n/m values of the data structure;
perform, in registers of the coprocessor having the word length w of the coprocessor, a recursive divide-and-conquer butterfly computation using each of the segments to produce a vector output having integer values corresponding to a number theoretic transform of the data structure; and
perform, by the coprocessor, a cryptographic operation based on the vector output; and
wherein the cryptographic operation comprises one or more of generating secret keys, generating public keys, creating digital signatures, verifying digital signatures, encrypting digital messages, and decrypting digital messages.
18 . The electronic device of claim 17 , wherein the number of the multiple polynomial functions is M=n/m, where n is the number of coefficients for each of the multiple polynomial functions.
19 . The electronic device of claim 18 , wherein m equal the word length w divided by 2l, where l is the smallest power of two larger than log q and q is a prime number.
20 . The electronic device of claim 19 , wherein the input polynomial function is f=Σ i=0 n f i X i in a ring R q =F q [X]/(X n +1).