2 Secure Implementation of Lattice-Based Encryption Schemes
33
Algorithm 2 MDecode
Input: a 1 , a 2 , b 1 , b 2 , c 1 , c 2 , d 1 , d 2
Output: m 1 , m 2
1: a 1 ← a 1 − −
q
4
2: b 1 ← b 1 − −
q
4
3: c 1 ← c 1 − −
q
4
4: d 1 ← d 1 − −
q
4
5: [a 1 , a 2 ] ← TransformPower2(a 1 , a 2 , 16)
6: [b 1 , b 2 ] ← TransformPower2(b 1 , b 2 , 16)
7: [c 1 , c 2 ] ← TransformPower2(c 1 , c 2 , 16)
8: [d 1 , d 2 ] ← TransformPower2(d 1 , d 2 , 16)
9: e 1 ← a 1 + b 1 + c 1 + d 1
10: e 2 ← a 2 + b 2 + c 2 + d 2
11: e 1 ← e 1 − 2q
12: [e 1 , e 2 ] ← A2B(e 1 , e 2 )
13: m 1 = MSB(e 1 )
14: m 2 = MSB(e 2 )
keeping the same error probability, we have to increase the number of bits for
TransformPower2 to bits ≥ log 2 (2 · 4 ·
q
2 ), i.e., 16 for q = 12,289. After
the transformation, we can easily sum the coefficients sharewise. We also have to
adjust the last subtraction to 2q. If no error has occurred (i.e., all coefficients encode
the same m), there are two distributions with means 2 16 − q and +q and (m 1 , m 2 )
can be easily recovered with a final A2B. In this way, we save three calls to A2B
compared to the naive majority approach.
Security Analysis We analyze the security of Algorithms 1 and 2 by showing
that each intermediate variable follows a distribution independent of any sensitive
variable. For TransformPower2 this is formalized in the following lemma.
Lemma 2.1 When x 1 , x 2 ∈ Z q are a uniform sharing of x = x 1 + x 2 (mod q)
and y 1 , k
1 , k
2 , r ∈ {0, 1} bits are uniformly and independently distributed in
their respective value spaces, all intermediate variables in Algorithm 1 have a
distribution independent of the sensitive variable x.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 1 and show that their distributions are independent of the sensitive
variable x.
– Lines 2, 3: Since y 1 is a random value in {0, 1} bits , (x 1 − y 1 ) is also a random
variable following a distribution independent of x. The same applies to (x 1 −
y 1 ) + x 2 = x − y 1 .
– Line 4: A constant value is subtracted from a random value in {0, 1} bits which
does not leak about x.
– Line 5: The security strongly depends on the chosen transformation algorithm.
In our implementation, we use the algorithm from [21] and refer the interested
reader to their proof of security.
33
Algorithm 2 MDecode
Input: a 1 , a 2 , b 1 , b 2 , c 1 , c 2 , d 1 , d 2
Output: m 1 , m 2
1: a 1 ← a 1 − −
q
4
2: b 1 ← b 1 − −
q
4
3: c 1 ← c 1 − −
q
4
4: d 1 ← d 1 − −
q
4
5: [a 1 , a 2 ] ← TransformPower2(a 1 , a 2 , 16)
6: [b 1 , b 2 ] ← TransformPower2(b 1 , b 2 , 16)
7: [c 1 , c 2 ] ← TransformPower2(c 1 , c 2 , 16)
8: [d 1 , d 2 ] ← TransformPower2(d 1 , d 2 , 16)
9: e 1 ← a 1 + b 1 + c 1 + d 1
10: e 2 ← a 2 + b 2 + c 2 + d 2
11: e 1 ← e 1 − 2q
12: [e 1 , e 2 ] ← A2B(e 1 , e 2 )
13: m 1 = MSB(e 1 )
14: m 2 = MSB(e 2 )
keeping the same error probability, we have to increase the number of bits for
TransformPower2 to bits ≥ log 2 (2 · 4 ·
q
2 ), i.e., 16 for q = 12,289. After
the transformation, we can easily sum the coefficients sharewise. We also have to
adjust the last subtraction to 2q. If no error has occurred (i.e., all coefficients encode
the same m), there are two distributions with means 2 16 − q and +q and (m 1 , m 2 )
can be easily recovered with a final A2B. In this way, we save three calls to A2B
compared to the naive majority approach.
Security Analysis We analyze the security of Algorithms 1 and 2 by showing
that each intermediate variable follows a distribution independent of any sensitive
variable. For TransformPower2 this is formalized in the following lemma.
Lemma 2.1 When x 1 , x 2 ∈ Z q are a uniform sharing of x = x 1 + x 2 (mod q)
and y 1 , k
1 , k
2 , r ∈ {0, 1} bits are uniformly and independently distributed in
their respective value spaces, all intermediate variables in Algorithm 1 have a
distribution independent of the sensitive variable x.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 1 and show that their distributions are independent of the sensitive
variable x.
– Lines 2, 3: Since y 1 is a random value in {0, 1} bits , (x 1 − y 1 ) is also a random
variable following a distribution independent of x. The same applies to (x 1 −
y 1 ) + x 2 = x − y 1 .
– Line 4: A constant value is subtracted from a random value in {0, 1} bits which
does not leak about x.
– Line 5: The security strongly depends on the chosen transformation algorithm.
In our implementation, we use the algorithm from [21] and refer the interested
reader to their proof of security.