24
T. Oder et al.
information about the secret key from the given pair. The difference to a chosenplaintext attack (CPA) setting is that in this case the attacker has access to a
plaintext–ciphertext pair that was generated from a plaintext that the attacker
was able to choose. An even stronger assumption is the chosen-ciphertext (CCA)
setting. In this case, the attacker has access to a decryption oracle and can generate
plaintext–ciphertext pairs by performing a decryption operation on a ciphertext of
his choice. In an adaptive chosen-ciphertext attack (CCA2), the attacker can even
adapt his queries to the decryption oracle.
Number-Theoretic Transform The number-theoretic transform (NTT) is a discrete Fourier transform over a finite field. An interesting property of the discrete
Fourier transform, which is also highly interesting for lattice-based cryptography,
is the ability to reduce the overall complexity of (polynomial) multiplication to
O(n · log n). To allow efficient computation of the NTT the coefficient ring has
to contain primitive roots of unity.
Definition 2.1 (Primitive Roof of Unity [57]) Let R be a ring, n ∈ N ≥1 , and
ω ∈ R. The value ω is an n-th root of unity if ω n = 1. The value ω is a primitive
n-th root of unity (or root of unity of order n) if it is an n-th root of unity, n ∈ R is
a unit in R, and ω n/t − 1 is not a zero divisor for any prime divisor t of n.
For a given primitive n-th root of unity ω in Z q , the NTT of a vector a =
(a n−1 , . . . , a 0 ) is the vector ˜
a = ( ˜
a n−1 , . . . , ˜
a 0 ) that is computed as
˜
a i =
0≤j
b n−1 · x n−1 + · · · + b 0 into their NTT representations ˜
a = ˜
a n−1 · x n−1 + · · · + ˜
a 0
and ˜
b = ˜
b n−1 · x n−1 + · · · + ˜
b 0 and computing the coefficient-wise multiplication
as ˜
c =
0≤i
b i · x i . The result c = a · b is obtained after applying the inverse
transform to ˜
c. For q = 1 mod 2n the way the result has to be interpreted depends
on the input.
– Assuming one expanded a and b to vectors of length 2n by padding n zeros, the
result c equals the schoolbook multiplication of a and b without reduction.
– Without padding, the result c is already reduced modulo f = x n − 1. This is
called the positive wrapped convolution. In contrast to the first case, the resulting
polynomial is only of degree n.
This reduction for free is beneficial concerning the computation time, but in schemes
based on ring-LWE arithmetic is performed in Z[x]/x n +1. Thus, the input and
output have to be modified so that the negative wrapped convolution gets computed
to exploit the reduction property. Let ψ be the square root of ω. Now one computes
a =
0≤i
0≤i
has to multiply c , the output of the inverse transform (INTT) of ˜
c, by powers of the
inverse of ψ.
T. Oder et al.
information about the secret key from the given pair. The difference to a chosenplaintext attack (CPA) setting is that in this case the attacker has access to a
plaintext–ciphertext pair that was generated from a plaintext that the attacker
was able to choose. An even stronger assumption is the chosen-ciphertext (CCA)
setting. In this case, the attacker has access to a decryption oracle and can generate
plaintext–ciphertext pairs by performing a decryption operation on a ciphertext of
his choice. In an adaptive chosen-ciphertext attack (CCA2), the attacker can even
adapt his queries to the decryption oracle.
Number-Theoretic Transform The number-theoretic transform (NTT) is a discrete Fourier transform over a finite field. An interesting property of the discrete
Fourier transform, which is also highly interesting for lattice-based cryptography,
is the ability to reduce the overall complexity of (polynomial) multiplication to
O(n · log n). To allow efficient computation of the NTT the coefficient ring has
to contain primitive roots of unity.
Definition 2.1 (Primitive Roof of Unity [57]) Let R be a ring, n ∈ N ≥1 , and
ω ∈ R. The value ω is an n-th root of unity if ω n = 1. The value ω is a primitive
n-th root of unity (or root of unity of order n) if it is an n-th root of unity, n ∈ R is
a unit in R, and ω n/t − 1 is not a zero divisor for any prime divisor t of n.
For a given primitive n-th root of unity ω in Z q , the NTT of a vector a =
(a n−1 , . . . , a 0 ) is the vector ˜
a = ( ˜
a n−1 , . . . , ˜
a 0 ) that is computed as
˜
a i =
0≤j
b n−1 · x n−1 + · · · + b 0 into their NTT representations ˜
a = ˜
a n−1 · x n−1 + · · · + ˜
a 0
and ˜
b = ˜
b n−1 · x n−1 + · · · + ˜
b 0 and computing the coefficient-wise multiplication
as ˜
c =
0≤i
b i · x i . The result c = a · b is obtained after applying the inverse
transform to ˜
c. For q = 1 mod 2n the way the result has to be interpreted depends
on the input.
– Assuming one expanded a and b to vectors of length 2n by padding n zeros, the
result c equals the schoolbook multiplication of a and b without reduction.
– Without padding, the result c is already reduced modulo f = x n − 1. This is
called the positive wrapped convolution. In contrast to the first case, the resulting
polynomial is only of degree n.
This reduction for free is beneficial concerning the computation time, but in schemes
based on ring-LWE arithmetic is performed in Z[x]/x n +1. Thus, the input and
output have to be modified so that the negative wrapped convolution gets computed
to exploit the reduction property. Let ψ be the square root of ω. Now one computes
a =
0≤i
0≤i
has to multiply c , the output of the inverse transform (INTT) of ˜
c, by powers of the
inverse of ψ.