2 Secure Implementation of Lattice-Based Encryption Schemes
39
Algorithm 5 Masked comparison of public ˜
c 1 with internal ˜
c
∗
1
Input: ˜
c 1 , ˜
c
∗∗
1 , ˜
c
∗∗∗
1
Output: eq
1: ˜
c
∗∗
1 ← ˜
c 1 − ˜
c
∗∗
1
2: ˜
c
∗∗
1 ← H (˜ c
∗∗
1 )
3: ˜
c
∗∗∗
1 ← H (˜ c
∗∗∗
1 )
4: eq ← ˜
c
∗∗
1 ⊕ ˜
c
∗∗∗
1
5: eq ← (eq == 0)
Relying on the collision resistance of H , this comparison is only true if the
ciphertext is valid and thus ˜
c ∗∗
1 = c 1 .
Lemma 2.5 When ˜
c ∗∗
1 + ˜
c ∗∗∗
1
= ˜
c ∗
1 ∈ R q is a uniform, independent shared
representation of the sensitive input variable ˜
c ∗
1 and H is a cryptographic hash
function, every intermediate variable of Algorithm 5 is independent of the sensitive
variable ˜
c ∗
1 .
Proof For the proof, we analyze the distributions of the variables of each line from
Algorithm 5 and show that they are independent of the sensitive variable.
– Lines 1–3: Each line uses only one share of ˜
c ∗
1 and, therefore, the computation is
independent of ˜
c ∗
1 .
– Line 4: The adversary can probe H (˜ c ∗
1 − ˜
c 1 + ˜
c ∗∗
1 ) ⊕ H (˜ c ∗∗
1 ) which depends on
both shares. However, we rely on the properties of H to break the linear relation
between the shares and make a direct recovery of ˜
c ∗
1 impossible. Nevertheless, a
computationally unbounded adversary would be able to distinguish the sensitive
variable ˜
c ∗
1 by iterating over all possible ˜
c ∗∗
1 . Since ˜
c ∗∗
1 ∈ R q this task is more
complex than directly iterating over the whole key space of ˜
r 2 . Therefore, we do
not consider this attack vector a viable threat. Furthermore, in the special case of
˜
c ∗
1 = ˜
c 1 the variable ˜
c ∗
1 is not sensitive.
However, it is only secure to have a function of both shares, because the
comparison is always negative, i.e., eq is false, in a chosen-ciphertext setting.
Therefore, the attacker does not gain additional knowledge from the output of the
comparison. This does not apply to the comparison of c 2 and c 4 . In this case, the
adversary can adaptively change c 2 or c 4 without removing the sensitivity from
m cpa (which is not possible for ˜
c 1 ) and use the output of compare(c ∗∗
2 , c ∗∗∗
2 ) (resp.
compare(c ∗∗
4 , c ∗∗∗
4 )) to distinguish m cpa . This problem can be solved by performing
the other comparison (i.e., ˜
c 1 ) beforehand and only if it returns true the other two
comparisons (i.e., c 2 , c 4 ) are conducted. A timing-constant solution would be to
perform dummy comparisons for c 2 and c 4 in case the prior comparison failed.
Furthermore, for these comparisons it is not even necessary to perform a masked
comparison, since they are only ever done for valid ˜
c 1 and in this setting m cpa is not
sensitive.