2 Secure Implementation of Lattice-Based Encryption Schemes
25
Learning with Errors In 2005, Oded Regev introduced the learning with errors
problem [42]. The idea behind the LWE problem is to find a secret vector s given
a public matrix A and a vector b = As + e, where e is a noise vector with small
coefficients. In [33], Lyubashevsky et al. present a ring variant of the LWE problem
over finite fields, called ring-LWE. The (ring-)LWE problem can be used to create
encryption schemes as shown in [32, 34, 35]. Several variants of the scheme exist
and the concrete instantiation we are using is defined as follows:
– RLWE.CPA gen
NTT (): Sample the binomial noise ˜
r 1
$
←NTT(SampleNoisePoly()),
˜
r 2
$
←NTT(SampleNoisePoly()), sample uniform ˜
a
$
← SampleUniformPoly(),
and compute ˜
p = ˜
r 1 − ˜
a◦˜ r 2 . Output the secret key ˜
r 2 and the public key ( ˜
p, ˜
a).
– RLWE.CPA enc
NTT (˜ a, ˜
p, m cpa ∈{0, 1} n ): Sample ˜
e 1 =NTT(SampleNoisePoly()),
˜
e 2 = NTT(SampleNoisePoly()), and ˜
c 1 = ˜
a◦˜ e 1 + ˜
e 2 and compute ˜
h 2 = ˜
p◦˜ e 1 ,
e 3 ← SampleNoisePoly(), and c 2 = INTT( ˜
h 2 )+e 3 +LWEEncode(m cpa ).
Output the ciphertext (˜ c 1 , c 2 ).
– RLWE.CPA dec
NTT (˜ r 2 , ˜
c 1 , c 2 ): Output LWEDecode(INTT(˜ c 1 ◦˜ r 2 )+c 2 ) ∈ {0, 1} n .
In the scheme all elements are polynomials over R q = Z q [x]/x n + 1 where
we always assume implicit reduction modulo q and reduction modulo x n + 1
and only allow parameters for which it holds that 1 ≡ q mod 2n for q being
a prime and n being a power of two. For efficiency, we make explicit use of
the NTT in a way that has been previously described in [38, 47]. For efficiency
we transmit and store keys and some ciphertexts in the NTT domain. Note that
for the discussion of the masking scheme it is sometimes not relevant whether
polynomials are stored in NTT format or whether the NTT is used at all (other
options would be schoolbook or Karatsuba) and thus we sometimes omit the NTT
notations to simplify the presentation. The public key (p = r 1 − ar 2 , a) is an
ring-LWE sample and an attacker trying to extract the secret key basically has to
solve the search version of the ring-LWE problem [33]. In earlier works [11, 24]
RLWE.CPA , or derived key-exchange schemes, was usually instantiated with a
(high-precision) discrete Gaussian distribution with parameter σ . However, newer
results show that security can also be achieved with distributions that are close
to a discrete Gaussian. Examples are the binomial distribution [3, 13], a fixed
distribution [12], a binary distribution [15], or a uniform distribution [4, 26]. We
define SampleNoisePoly() to be a function that samples a polynomial in R q
with coefficients coming from a binomial distribution with parameter k where each
coefficient is sampled independently as
k−1
i=0 b i − b
i , where the b i , b
i ∈ {0, 1} are
uniform independent bits. 1 The binomial distribution is centered with a zero mean,
has variance k/2, and gives a standard deviation of ς =
√
k/2. For distributions
that roughly follow a discrete Gaussian the standard deviation ς can be considered
as the most important measure when describing and comparing security levels for
1 In [3] the definition of the binomial distribution contains a typo in which the sum goes from zero
to k.
25
Learning with Errors In 2005, Oded Regev introduced the learning with errors
problem [42]. The idea behind the LWE problem is to find a secret vector s given
a public matrix A and a vector b = As + e, where e is a noise vector with small
coefficients. In [33], Lyubashevsky et al. present a ring variant of the LWE problem
over finite fields, called ring-LWE. The (ring-)LWE problem can be used to create
encryption schemes as shown in [32, 34, 35]. Several variants of the scheme exist
and the concrete instantiation we are using is defined as follows:
– RLWE.CPA gen
NTT (): Sample the binomial noise ˜
r 1
$
←NTT(SampleNoisePoly()),
˜
r 2
$
←NTT(SampleNoisePoly()), sample uniform ˜
a
$
← SampleUniformPoly(),
and compute ˜
p = ˜
r 1 − ˜
a◦˜ r 2 . Output the secret key ˜
r 2 and the public key ( ˜
p, ˜
a).
– RLWE.CPA enc
NTT (˜ a, ˜
p, m cpa ∈{0, 1} n ): Sample ˜
e 1 =NTT(SampleNoisePoly()),
˜
e 2 = NTT(SampleNoisePoly()), and ˜
c 1 = ˜
a◦˜ e 1 + ˜
e 2 and compute ˜
h 2 = ˜
p◦˜ e 1 ,
e 3 ← SampleNoisePoly(), and c 2 = INTT( ˜
h 2 )+e 3 +LWEEncode(m cpa ).
Output the ciphertext (˜ c 1 , c 2 ).
– RLWE.CPA dec
NTT (˜ r 2 , ˜
c 1 , c 2 ): Output LWEDecode(INTT(˜ c 1 ◦˜ r 2 )+c 2 ) ∈ {0, 1} n .
In the scheme all elements are polynomials over R q = Z q [x]/x n + 1 where
we always assume implicit reduction modulo q and reduction modulo x n + 1
and only allow parameters for which it holds that 1 ≡ q mod 2n for q being
a prime and n being a power of two. For efficiency, we make explicit use of
the NTT in a way that has been previously described in [38, 47]. For efficiency
we transmit and store keys and some ciphertexts in the NTT domain. Note that
for the discussion of the masking scheme it is sometimes not relevant whether
polynomials are stored in NTT format or whether the NTT is used at all (other
options would be schoolbook or Karatsuba) and thus we sometimes omit the NTT
notations to simplify the presentation. The public key (p = r 1 − ar 2 , a) is an
ring-LWE sample and an attacker trying to extract the secret key basically has to
solve the search version of the ring-LWE problem [33]. In earlier works [11, 24]
RLWE.CPA , or derived key-exchange schemes, was usually instantiated with a
(high-precision) discrete Gaussian distribution with parameter σ . However, newer
results show that security can also be achieved with distributions that are close
to a discrete Gaussian. Examples are the binomial distribution [3, 13], a fixed
distribution [12], a binary distribution [15], or a uniform distribution [4, 26]. We
define SampleNoisePoly() to be a function that samples a polynomial in R q
with coefficients coming from a binomial distribution with parameter k where each
coefficient is sampled independently as
k−1
i=0 b i − b
i , where the b i , b
i ∈ {0, 1} are
uniform independent bits. 1 The binomial distribution is centered with a zero mean,
has variance k/2, and gives a standard deviation of ς =
√
k/2. For distributions
that roughly follow a discrete Gaussian the standard deviation ς can be considered
as the most important measure when describing and comparing security levels for
1 In [3] the definition of the binomial distribution contains a typo in which the sum goes from zero
to k.