36
T. Oder et al.
that one bit is encoded into one coefficient but this approach trivially generalizes to
multi-coefficient encodings as well. As a consequence of the splitting into shares,
we have to compute (m
cpa,1 +m
cpa,2 )◦(m
cpa,1 +m
cpa,2 ) instead of m
cpa AND m
cpa .
To obtain the correct result, we compute
c
2 = (p · e
1 + e
3 + Encode(m
cpa ))
+ m
cpa,1 m
cpa,1 + m
cpa,1 m
cpa,2 + m
cpa,2 m
cpa,1 + m
cpa,2 m
cpa,2
Note that the term p · e
1 + e
3 provides the randomness to protect the masked AND
computation akin to Trichina’s masked AND [55]. Therefore, the order of operations
in the computation of c
2 is important for the security. Our complete masked reencryption is shown in Algorithm 3.
Lemma 2.3 When e
1 + e
1 = e 1 ∈ R q , e
3 + e
3 = e 3 ∈ R q , m
cpa + m
cpa =
m cpa ∈ {0, 1} n/4 are uniform, independent shared representations of the sensitive
input variables and m
cpa,1 , m
cpa,1 ∈ R q are uniform and independent random
variables, all intermediate variables in Algorithm 3 have a distribution independent
of the sensitive variables m cpa , e 1 , and e 3 .
Proof For the proof, we analyze the distributions of the variables of each line from
Algorithm 3 and show that they are independent of the sensitive variables m cpa , e 1 ,
and , e 3 .
– Lines 1, 2: Each of these lines only uses one of the shares and is therefore
independent of the sensitive variables. The shared representation of the error
vectors is independent of the shared representation of m cpa due to the mask
refresh inside the shared sampler.
– Lines 3, 4: m
cpa,1 (resp. m
cpa,1 ) are new random masks that are used to mask the
shares of m cpa . Since only one share of m cpa is involved in each line, the result
is still independent of m cpa .
Algorithm 3 Masked ring-LWE encryption
Input: p, e
1 , e
3 , e
1 , e
3 , m
cpa , m
cpa , m
cpa, 1 , m
cpa, 1
Output: c
2 , c
2
1: c
2 ← p · e
1 + e
3 + Encode(m
cpa )
2: c
2 ← p · e
1 + e
3 + Encode(m
cpa )
3: m
cpa, 2 ← m
cpa − m
cpa, 1
4: m
cpa, 2 ← m
cpa − m
cpa, 1
5: t 11 ← m
cpa, 1 ◦m
cpa, 1
6: t 12 ← m
cpa, 1 ◦m
cpa, 2
7: t 21 ← m
cpa, 2 ◦m
cpa, 1
8: t 22 ← m
cpa, 2 ◦m
cpa, 2
9: c
2 ← ((((c
2 + t 11 ) + t 12 ) + t 21 ) + t 22 )
T. Oder et al.
that one bit is encoded into one coefficient but this approach trivially generalizes to
multi-coefficient encodings as well. As a consequence of the splitting into shares,
we have to compute (m
cpa,1 +m
cpa,2 )◦(m
cpa,1 +m
cpa,2 ) instead of m
cpa AND m
cpa .
To obtain the correct result, we compute
c
2 = (p · e
1 + e
3 + Encode(m
cpa ))
+ m
cpa,1 m
cpa,1 + m
cpa,1 m
cpa,2 + m
cpa,2 m
cpa,1 + m
cpa,2 m
cpa,2
Note that the term p · e
1 + e
3 provides the randomness to protect the masked AND
computation akin to Trichina’s masked AND [55]. Therefore, the order of operations
in the computation of c
2 is important for the security. Our complete masked reencryption is shown in Algorithm 3.
Lemma 2.3 When e
1 + e
1 = e 1 ∈ R q , e
3 + e
3 = e 3 ∈ R q , m
cpa + m
cpa =
m cpa ∈ {0, 1} n/4 are uniform, independent shared representations of the sensitive
input variables and m
cpa,1 , m
cpa,1 ∈ R q are uniform and independent random
variables, all intermediate variables in Algorithm 3 have a distribution independent
of the sensitive variables m cpa , e 1 , and e 3 .
Proof For the proof, we analyze the distributions of the variables of each line from
Algorithm 3 and show that they are independent of the sensitive variables m cpa , e 1 ,
and , e 3 .
– Lines 1, 2: Each of these lines only uses one of the shares and is therefore
independent of the sensitive variables. The shared representation of the error
vectors is independent of the shared representation of m cpa due to the mask
refresh inside the shared sampler.
– Lines 3, 4: m
cpa,1 (resp. m
cpa,1 ) are new random masks that are used to mask the
shares of m cpa . Since only one share of m cpa is involved in each line, the result
is still independent of m cpa .
Algorithm 3 Masked ring-LWE encryption
Input: p, e
1 , e
3 , e
1 , e
3 , m
cpa , m
cpa , m
cpa, 1 , m
cpa, 1
Output: c
2 , c
2
1: c
2 ← p · e
1 + e
3 + Encode(m
cpa )
2: c
2 ← p · e
1 + e
3 + Encode(m
cpa )
3: m
cpa, 2 ← m
cpa − m
cpa, 1
4: m
cpa, 2 ← m
cpa − m
cpa, 1
5: t 11 ← m
cpa, 1 ◦m
cpa, 1
6: t 12 ← m
cpa, 1 ◦m
cpa, 2
7: t 21 ← m
cpa, 2 ◦m
cpa, 1
8: t 22 ← m
cpa, 2 ◦m
cpa, 2
9: c
2 ← ((((c
2 + t 11 ) + t 12 ) + t 21 ) + t 22 )