28
T. Oder et al.
2.3.1 CCA2 Conversion for RLWE.CPA
In this work we use the Fujisaki–Okamoto [22] transformation to enable a semantically secured encryption with respect to adaptive chosen-ciphertext attack (CCA2).
For this transformation, Peikert came to the conclusion [37] that a passively
secured encryption scheme should be converted into an actively secured one (based
on the random oracle model; assuming adaptive attacks for CCA2). For this
transformation, two random oracles G : {0, 1} L → {0, 1} l and H : {0, 1} L+l →
{0, 1} λ are required. Targhi and Unruh pointed out that a third random oracle H :
{0, 1} L → {0, 1} l is necessary for the quantum security of the transformation [54].
The parameter L determines the size of the message to be encrypted, l the length
of the input to ring-LWE encryption, and λ the length of the seed for the pseudorandom number generator (PRNG). In our implementation, the parameters L, l, and
λ are set to 256 and we define RLWE.CCA enc
NTT and RLWE.CCA dec
NTT as follows:
– RLWE.CCA enc
NTT (˜ a, ˜
p, m cca ∈ {0, 1} L ):
Let ( ˜
c 1 , c 2 )= RLWE.CPA enc
NTT (˜ a, ˜
p, ν; H (ν||m cca )), where ν ∈ {0, 1} L is a
nonce and H (ν||m cca ) seeds the PRNG of RLWE.CPA enc
NTT . Compute c 3 =
G(ν) ⊕ m cca as well as c 4 = H (ν) and output (˜ c 1 , c 2 , c 3 , c 4 ).
– RLWE.CCA dec
NTT (˜ r 2 , ˜
a, ˜
p, ˜
c 1 , c 2 , c 3 , c 4 ):
Compute ν =m cpa = RLWE.CPA dec
NTT (˜ r 2 , ˜
c 1 , c 2 ), m cca = G(ν ) ⊕ c 3 ,
(˜ c ∗
1 , c ∗
2 ) = RLWE.CPA enc
NTT (˜ a, ˜
p, ν ; H (ν ||m cca )), and c ∗
4 = H (ν ). Check if
( ˜
c 1 , c 2 )
?
= (˜ c ∗
1 , c ∗
2 ) and c 4
?
= c ∗
4 . If so, output m cca , otherwise output f ail.
Using this transformation and our chosen parameters we obtain a theoretical
public-key size of |(˜ a, ˜
p)| = 2nlog 2 (q) = 2· 1024· 14 = 28,672 bits (3584 bytes)
and a theoretical ciphertext size of |(˜ c 1 , c 2 , c 3 , c 4 )| = 2nlog 2 (q) + 2l = 29,184
bits (3648 bytes). The secret key is |˜ r 2 | = nlog 2 (q) = 14,336 bits (1792 bytes).
2.3.2 Masked CCA2-Secured Ring-LWE Decryption
To achieve side-channel resistance, it is necessary to mask all vulnerable modules
of the CCA2-secured decryption. As depicted in Fig. 2.1 in bold notation, these
modules are RLWE.CPA dec
NTT , G, H , H , and RLWE.CPA enc
NTT , and the two
comparisons. Note that it is not sufficient to only protect RLWE.CPA dec
NTT , because
in a chosen-ciphertext setting an adversary can target the unmasked output of
RLWE.CPA dec
NTT (see Appendix B of [44]) to recover the secret key. This attack
trivially extends to any other intermediate variable which depends on m cpa . A DPAadversary would keep c 1 , c 2 constant while varying c 3 and c 4 . This way it is possible
to derive hypothetical values for every other module following RLWE.CPA dec
NTT
depending on a guess for m cpa (which only depends on one coefficient of r 2
in a chosen-ciphertext setting). Therefore, even the final comparison needs to be
protected against a side-channel adversary.
T. Oder et al.
2.3.1 CCA2 Conversion for RLWE.CPA
In this work we use the Fujisaki–Okamoto [22] transformation to enable a semantically secured encryption with respect to adaptive chosen-ciphertext attack (CCA2).
For this transformation, Peikert came to the conclusion [37] that a passively
secured encryption scheme should be converted into an actively secured one (based
on the random oracle model; assuming adaptive attacks for CCA2). For this
transformation, two random oracles G : {0, 1} L → {0, 1} l and H : {0, 1} L+l →
{0, 1} λ are required. Targhi and Unruh pointed out that a third random oracle H :
{0, 1} L → {0, 1} l is necessary for the quantum security of the transformation [54].
The parameter L determines the size of the message to be encrypted, l the length
of the input to ring-LWE encryption, and λ the length of the seed for the pseudorandom number generator (PRNG). In our implementation, the parameters L, l, and
λ are set to 256 and we define RLWE.CCA enc
NTT and RLWE.CCA dec
NTT as follows:
– RLWE.CCA enc
NTT (˜ a, ˜
p, m cca ∈ {0, 1} L ):
Let ( ˜
c 1 , c 2 )= RLWE.CPA enc
NTT (˜ a, ˜
p, ν; H (ν||m cca )), where ν ∈ {0, 1} L is a
nonce and H (ν||m cca ) seeds the PRNG of RLWE.CPA enc
NTT . Compute c 3 =
G(ν) ⊕ m cca as well as c 4 = H (ν) and output (˜ c 1 , c 2 , c 3 , c 4 ).
– RLWE.CCA dec
NTT (˜ r 2 , ˜
a, ˜
p, ˜
c 1 , c 2 , c 3 , c 4 ):
Compute ν =m cpa = RLWE.CPA dec
NTT (˜ r 2 , ˜
c 1 , c 2 ), m cca = G(ν ) ⊕ c 3 ,
(˜ c ∗
1 , c ∗
2 ) = RLWE.CPA enc
NTT (˜ a, ˜
p, ν ; H (ν ||m cca )), and c ∗
4 = H (ν ). Check if
( ˜
c 1 , c 2 )
?
= (˜ c ∗
1 , c ∗
2 ) and c 4
?
= c ∗
4 . If so, output m cca , otherwise output f ail.
Using this transformation and our chosen parameters we obtain a theoretical
public-key size of |(˜ a, ˜
p)| = 2nlog 2 (q) = 2· 1024· 14 = 28,672 bits (3584 bytes)
and a theoretical ciphertext size of |(˜ c 1 , c 2 , c 3 , c 4 )| = 2nlog 2 (q) + 2l = 29,184
bits (3648 bytes). The secret key is |˜ r 2 | = nlog 2 (q) = 14,336 bits (1792 bytes).
2.3.2 Masked CCA2-Secured Ring-LWE Decryption
To achieve side-channel resistance, it is necessary to mask all vulnerable modules
of the CCA2-secured decryption. As depicted in Fig. 2.1 in bold notation, these
modules are RLWE.CPA dec
NTT , G, H , H , and RLWE.CPA enc
NTT , and the two
comparisons. Note that it is not sufficient to only protect RLWE.CPA dec
NTT , because
in a chosen-ciphertext setting an adversary can target the unmasked output of
RLWE.CPA dec
NTT (see Appendix B of [44]) to recover the secret key. This attack
trivially extends to any other intermediate variable which depends on m cpa . A DPAadversary would keep c 1 , c 2 constant while varying c 3 and c 4 . This way it is possible
to derive hypothetical values for every other module following RLWE.CPA dec
NTT
depending on a guess for m cpa (which only depends on one coefficient of r 2
in a chosen-ciphertext setting). Therefore, even the final comparison needs to be
protected against a side-channel adversary.