34
T. Oder et al.
– Lines 6, 7, 9, 11: Each of these lines operates on only one of the shares. Therefore,
each of them follows a distribution independent of x assuming A2B to be secured.
– Line 13: The first operand of the sum is the random value r ∈ {0, 1} bits .
Therefore, all following operations are perfectly masked by r and follow a
distribution independent of x.
– Line 14: A random value is subtracted from only one share. Therefore, the result
does not leak about x.
As shown above, the distribution of every intermediate variable of Algorithm 1 is
independent of the sensitive variable x. The output shares y 1 and y 2 with x = y 1 +
y 2 mod 2 bits are both uniformly distributed in {0, 1} bits .
For MDecode, the security properties are formalized in the following lemma.
Lemma 2.2 When a 1 , a 2 , b 1 , b 2 , c 1 , c 2 , d 1 , d 2 ∈ Z q are uniform shares a = a 1 +
a 2 (mod q), b = b 1 + b 2 (mod q), c = c 1 + c 2 (mod q), d = d 1 + d 2 (mod q)
which are independent of each other, all intermediate variables in Algorithm 2 have
a distribution independent of the sensitive variables a, b, c, d, and m.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 2 and show that their distributions are independent of the sensitive
variables.
– Lines 1–4: A constant value is subtracted from only one share. If the input
sharings are uniform, the result is still a uniform sharing independent of the
sensitive variables.
– Lines 5–8: The security depends on the security of TransformPower2 which
is analyzed in the previous lemma.
– Lines 9, 10: Assuming the output sharings of the four calls to Transform
Power2 are still uniform and independent, processing only one share of each
sharing is always independent of the sensitive variables.
– Line 11: (e 1 , e 2 ) are a uniform sharing of e = a + b + c + d. Since only one
share is processed, the result is independent of the sensitive variables.
– Line 12: Again the security depends on the chosen algorithm for A2B.
– Lines 13, 14: Each of these lines operates on only one of the shares. Therefore,
each of them follows a distribution independent of the sensitive variables
assuming A2B to be secured.
As shown above, the distribution of every intermediate variable of Algorithm 2 is
independent of the sensitive variables a, b, c, d, and m. The output shares m 1 and
m 2 with m = m 1 ⊕ m 2 are both uniformly distributed in {0, 1}.
G, H, and H (SHAKE) We choose to instantiate G, H , and H with the
commonly used extendable-output function SHAKE that is based on the KECCAK
algorithm [10] and apply the masking scheme presented in [9]. Therefore, we do
not include the security analysis of this module and instead refer the reader to the
original publications. We use a different initialization vector for each instantiation
of the random oracles to make G, H , and H distinct from each other.
T. Oder et al.
– Lines 6, 7, 9, 11: Each of these lines operates on only one of the shares. Therefore,
each of them follows a distribution independent of x assuming A2B to be secured.
– Line 13: The first operand of the sum is the random value r ∈ {0, 1} bits .
Therefore, all following operations are perfectly masked by r and follow a
distribution independent of x.
– Line 14: A random value is subtracted from only one share. Therefore, the result
does not leak about x.
As shown above, the distribution of every intermediate variable of Algorithm 1 is
independent of the sensitive variable x. The output shares y 1 and y 2 with x = y 1 +
y 2 mod 2 bits are both uniformly distributed in {0, 1} bits .
For MDecode, the security properties are formalized in the following lemma.
Lemma 2.2 When a 1 , a 2 , b 1 , b 2 , c 1 , c 2 , d 1 , d 2 ∈ Z q are uniform shares a = a 1 +
a 2 (mod q), b = b 1 + b 2 (mod q), c = c 1 + c 2 (mod q), d = d 1 + d 2 (mod q)
which are independent of each other, all intermediate variables in Algorithm 2 have
a distribution independent of the sensitive variables a, b, c, d, and m.
Proof For the proof, we analyze the distributions of the variables of each line
from Algorithm 2 and show that their distributions are independent of the sensitive
variables.
– Lines 1–4: A constant value is subtracted from only one share. If the input
sharings are uniform, the result is still a uniform sharing independent of the
sensitive variables.
– Lines 5–8: The security depends on the security of TransformPower2 which
is analyzed in the previous lemma.
– Lines 9, 10: Assuming the output sharings of the four calls to Transform
Power2 are still uniform and independent, processing only one share of each
sharing is always independent of the sensitive variables.
– Line 11: (e 1 , e 2 ) are a uniform sharing of e = a + b + c + d. Since only one
share is processed, the result is independent of the sensitive variables.
– Line 12: Again the security depends on the chosen algorithm for A2B.
– Lines 13, 14: Each of these lines operates on only one of the shares. Therefore,
each of them follows a distribution independent of the sensitive variables
assuming A2B to be secured.
As shown above, the distribution of every intermediate variable of Algorithm 2 is
independent of the sensitive variables a, b, c, d, and m. The output shares m 1 and
m 2 with m = m 1 ⊕ m 2 are both uniformly distributed in {0, 1}.
G, H, and H (SHAKE) We choose to instantiate G, H , and H with the
commonly used extendable-output function SHAKE that is based on the KECCAK
algorithm [10] and apply the masking scheme presented in [9]. Therefore, we do
not include the security analysis of this module and instead refer the reader to the
original publications. We use a different initialization vector for each instantiation
of the random oracles to make G, H , and H distinct from each other.