2 Secure Implementation of Lattice-Based Encryption Schemes
35
Ring-LWE Encryption For the masked RLWE.CPA enc
NTT (i.e., the re-encryption
in RLWE.CCA dec
NTT ), every input or internally PRNG-generated variable is sensitive
(i.e., m cpa , e 1 , e 2 , e 3 ) since they can be used to recover the secret key r 2 as detailed in
the beginning of this section. Therefore, the computation of c 1 and c 2 is done in the
shared domain. For the former this is trivial, since it only requires linear operations
which can be performed on each input share separately as
c
1 = a · e
1 + e
2 ,
c
1 = a · e
1 + e
2 .
Due to the simplicity of this computation we omit the security analysis.
For c 2 , however, we have to consider the rounding error from Encode to obtain
the correct result, i.e., it is not sufficient to compute
c
2 = p · e
1 + e
3 + Encode(m
cpa ),
c
2 = p · e
1 + e
3 + Encode(m
cpa ).
In this equation, m
cpa ⊕ m
cpa = m cpa . Since our modulus q is odd and therefore
2
q
2 = q, we have to adjust this operation so that the correct result is computed, i.e.,
the result of the re-encryption has to be exactly the same as the result of the original
encryption. The naive approach would be to multiply one of the intermediate results,
e.g., c
2 (without the message), by 2, encode the shares of m cpa as {0, q}, perform
two additions modulo 2q, and divide the result by 2. While this approach indeed
yields the correct result, it introduces an easily detectable side-channel leakage as
the last bit of the intermediate results before the division is always set to 1 if and only
if the unshared message bit is 1, i.e., q has been added exactly one time. Similarly,
the last bit is always set to 0 if and only if the unshared message bit is 0. We cannot
apply the technique described in [37] as adding a random bit yields a different result
if the value that bit is added to is odd. In the CCA2 setting, it is required that both
the original encryption and the re-encryption output exactly the same result and thus
even a single bit error is not tolerable.
We thus decided to only return a false result in case both shares, m
cpa and m
cpa ,
have the value 1. In this case, the floor operation cuts off
1
2 two times and thus
the result is off by one. To get the correct result, we have to add m
cpa AND m
cpa .
Obviously, we cannot compute this multiplication of the shares directly without
leakage. Thus, we split the shares into subshares.
m
cpa = m
cpa,1 + m
cpa,2
m
cpa = m
cpa,1 + m
cpa,2
Notice that for this calculation m
cpa and m
cpa are implicitly treated as polynomials in R q and not as bit vectors. For simplicity, we assume in this description
35
Ring-LWE Encryption For the masked RLWE.CPA enc
NTT (i.e., the re-encryption
in RLWE.CCA dec
NTT ), every input or internally PRNG-generated variable is sensitive
(i.e., m cpa , e 1 , e 2 , e 3 ) since they can be used to recover the secret key r 2 as detailed in
the beginning of this section. Therefore, the computation of c 1 and c 2 is done in the
shared domain. For the former this is trivial, since it only requires linear operations
which can be performed on each input share separately as
c
1 = a · e
1 + e
2 ,
c
1 = a · e
1 + e
2 .
Due to the simplicity of this computation we omit the security analysis.
For c 2 , however, we have to consider the rounding error from Encode to obtain
the correct result, i.e., it is not sufficient to compute
c
2 = p · e
1 + e
3 + Encode(m
cpa ),
c
2 = p · e
1 + e
3 + Encode(m
cpa ).
In this equation, m
cpa ⊕ m
cpa = m cpa . Since our modulus q is odd and therefore
2
q
2 = q, we have to adjust this operation so that the correct result is computed, i.e.,
the result of the re-encryption has to be exactly the same as the result of the original
encryption. The naive approach would be to multiply one of the intermediate results,
e.g., c
2 (without the message), by 2, encode the shares of m cpa as {0, q}, perform
two additions modulo 2q, and divide the result by 2. While this approach indeed
yields the correct result, it introduces an easily detectable side-channel leakage as
the last bit of the intermediate results before the division is always set to 1 if and only
if the unshared message bit is 1, i.e., q has been added exactly one time. Similarly,
the last bit is always set to 0 if and only if the unshared message bit is 0. We cannot
apply the technique described in [37] as adding a random bit yields a different result
if the value that bit is added to is odd. In the CCA2 setting, it is required that both
the original encryption and the re-encryption output exactly the same result and thus
even a single bit error is not tolerable.
We thus decided to only return a false result in case both shares, m
cpa and m
cpa ,
have the value 1. In this case, the floor operation cuts off
1
2 two times and thus
the result is off by one. To get the correct result, we have to add m
cpa AND m
cpa .
Obviously, we cannot compute this multiplication of the shares directly without
leakage. Thus, we split the shares into subshares.
m
cpa = m
cpa,1 + m
cpa,2
m
cpa = m
cpa,1 + m
cpa,2
Notice that for this calculation m
cpa and m
cpa are implicitly treated as polynomials in R q and not as bit vectors. For simplicity, we assume in this description