2 Secure Implementation of Lattice-Based Encryption Schemes
37
– Lines 5, 6, 7, 8: Both terms of each line are uniformly and independently
distributed in R q . Therefore, the multiplication of these terms does not create
a new dependency on m cpa and the results can be easily simulated.
– Line 9: The term (p · e
1 + e
3 ) is independent of m cpa and therefore provides
sufficient fresh randomness to protect the masked AND. Each intermediate
variable of this line follows a uniform distribution in R q independent of the
sensitive variables m cpa , e 1 , and e 3 .
As shown above, the distribution of every intermediate variable of Algorithm 3
is independent of the sensitive variables m cpa , e 1 , and e 3 . Therefore, the aforementioned chosen-ciphertext attack is not possible.
Masked Binomial Sampler As detailed in the beginning of this section, the error
vectors can be target for a chosen-ciphertext adversary in the side-channel setting.
Therefore, we have to perform the sampling in a shared domain. We are using a
binomial sampler that computes the Hamming weight of two bit vectors α and β
and outputs the difference out of those Hamming weights. If we split α and β into
two Boolean shares each, we can compute the output of the sampler as follows:
out =
k−1
i=0
(α 1 [i] + α 2 [i] − 2α 1 [i]α 2 [i]) −
k−1
i=0
(β 1 [i] + β 2 [i] − 2β 1 [i]β 2 [i])
=
k−1
i=0
(α 1 [i] − β 1 [i]) +
k−1
i=0
(α 2 [i] − β 2 [i]) − 2
k−1
i=0
(α 1 [i]α 2 [i])
+ 2
k−1
i=0
(β 1 [i]β 2 [i]).
Obviously, we cannot compute α 1 [i]α 2 [i] and β 1 [i]β 2 [i] directly. Instead, we
compute them securely with the help of three random values X, Y, Z ∈ [0, q − 1]
as shown in Algorithm 4.
Lemma 2.4 When α 2 ∈ {0, 1} k with α 1 ⊕ α 2 = α, β 2 ∈ {0, 1} k with β 1 ⊕ β 2 = β,
X ∈ [0, q − 1], Y ∈ [0, q − 1], and Z ∈ [0, q − 1] are uniformly and independently
distributed in their respective value space, all intermediate variables in Algorithm 4
have a distribution independent of the sensitive unshared input variables α and β.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 4 and show that their distributions are independent of the sensitive
variables α and β.
– Lines 5, 6: Only one share is used in each of the two operations. Therefore, the
result is independent of the unshared values α and β.
– Lines 8–13: The proof works analogous to the proof for Lines 5–9 of Lemma 2.3.
37
– Lines 5, 6, 7, 8: Both terms of each line are uniformly and independently
distributed in R q . Therefore, the multiplication of these terms does not create
a new dependency on m cpa and the results can be easily simulated.
– Line 9: The term (p · e
1 + e
3 ) is independent of m cpa and therefore provides
sufficient fresh randomness to protect the masked AND. Each intermediate
variable of this line follows a uniform distribution in R q independent of the
sensitive variables m cpa , e 1 , and e 3 .
As shown above, the distribution of every intermediate variable of Algorithm 3
is independent of the sensitive variables m cpa , e 1 , and e 3 . Therefore, the aforementioned chosen-ciphertext attack is not possible.
Masked Binomial Sampler As detailed in the beginning of this section, the error
vectors can be target for a chosen-ciphertext adversary in the side-channel setting.
Therefore, we have to perform the sampling in a shared domain. We are using a
binomial sampler that computes the Hamming weight of two bit vectors α and β
and outputs the difference out of those Hamming weights. If we split α and β into
two Boolean shares each, we can compute the output of the sampler as follows:
out =
k−1
i=0
(α 1 [i] + α 2 [i] − 2α 1 [i]α 2 [i]) −
k−1
i=0
(β 1 [i] + β 2 [i] − 2β 1 [i]β 2 [i])
=
k−1
i=0
(α 1 [i] − β 1 [i]) +
k−1
i=0
(α 2 [i] − β 2 [i]) − 2
k−1
i=0
(α 1 [i]α 2 [i])
+ 2
k−1
i=0
(β 1 [i]β 2 [i]).
Obviously, we cannot compute α 1 [i]α 2 [i] and β 1 [i]β 2 [i] directly. Instead, we
compute them securely with the help of three random values X, Y, Z ∈ [0, q − 1]
as shown in Algorithm 4.
Lemma 2.4 When α 2 ∈ {0, 1} k with α 1 ⊕ α 2 = α, β 2 ∈ {0, 1} k with β 1 ⊕ β 2 = β,
X ∈ [0, q − 1], Y ∈ [0, q − 1], and Z ∈ [0, q − 1] are uniformly and independently
distributed in their respective value space, all intermediate variables in Algorithm 4
have a distribution independent of the sensitive unshared input variables α and β.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 4 and show that their distributions are independent of the sensitive
variables α and β.
– Lines 5, 6: Only one share is used in each of the two operations. Therefore, the
result is independent of the unshared values α and β.
– Lines 8–13: The proof works analogous to the proof for Lines 5–9 of Lemma 2.3.