Tighter proofs of CCA security in the quantum random oracle model

Nina Bindel, Mike Hamburg, Andreas Hülsing, Edoardo Persichetti

Research output: Other contributionAcademic

Abstract

We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE).
We give new, tighter security reductions for several constructions. Our
main result is a tight reduction for the security of the U 6⊥-transform of
Hofheinz, H¨ovelmanns, and Kiltz (TCC’17) which turns OW-CPA secure
deterministic PKEs into IND-CCA secure KEMs. This result is enabled
by a new one-way to hiding (O2H) lemma which gives a tighter bound
than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the U 6⊥- transform discussed in the literature on the security of the final scheme. We consider the difference between explicit (U ⊥) and implicit (U
6⊥) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from
a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (U 6⊥) or just from the message (U
6⊥ m)
LanguageEnglish
Number of pages29
StatePublished - 2019

Fingerprint

Random Oracle Model
Rejection
Lemma
Transform
Public Key Encryption
Failure Probability
Encapsulation
Imply

Bibliographical note

https://eprint.iacr.org/2019/590

Cite this

Bindel, Nina ; Hamburg, Mike ; Hülsing, Andreas ; Persichetti, Edoardo. / Tighter proofs of CCA security in the quantum random oracle model. 29 p.
@misc{37f2dd76a9174b1c809b38e0ed3c9b06,
title = "Tighter proofs of CCA security in the quantum random oracle model",
abstract = "We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE).We give new, tighter security reductions for several constructions. Ourmain result is a tight reduction for the security of the U 6⊥-transform ofHofheinz, H¨ovelmanns, and Kiltz (TCC’17) which turns OW-CPA securedeterministic PKEs into IND-CCA secure KEMs. This result is enabledby a new one-way to hiding (O2H) lemma which gives a tighter boundthan previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the U 6⊥- transform discussed in the literature on the security of the final scheme. We consider the difference between explicit (U ⊥) and implicit (U6⊥) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least froma theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (U 6⊥) or just from the message (U6⊥ m)",
author = "Nina Bindel and Mike Hamburg and Andreas H{\"u}lsing and Edoardo Persichetti",
note = "https://eprint.iacr.org/2019/590",
year = "2019",
language = "English",
type = "Other",

}

Tighter proofs of CCA security in the quantum random oracle model. / Bindel, Nina; Hamburg, Mike; Hülsing, Andreas; Persichetti, Edoardo.

29 p. 2019, .

Research output: Other contributionAcademic

TY - GEN

T1 - Tighter proofs of CCA security in the quantum random oracle model

AU - Bindel,Nina

AU - Hamburg,Mike

AU - Hülsing,Andreas

AU - Persichetti,Edoardo

N1 - https://eprint.iacr.org/2019/590

PY - 2019

Y1 - 2019

N2 - We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE).We give new, tighter security reductions for several constructions. Ourmain result is a tight reduction for the security of the U 6⊥-transform ofHofheinz, H¨ovelmanns, and Kiltz (TCC’17) which turns OW-CPA securedeterministic PKEs into IND-CCA secure KEMs. This result is enabledby a new one-way to hiding (O2H) lemma which gives a tighter boundthan previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the U 6⊥- transform discussed in the literature on the security of the final scheme. We consider the difference between explicit (U ⊥) and implicit (U6⊥) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least froma theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (U 6⊥) or just from the message (U6⊥ m)

AB - We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE).We give new, tighter security reductions for several constructions. Ourmain result is a tight reduction for the security of the U 6⊥-transform ofHofheinz, H¨ovelmanns, and Kiltz (TCC’17) which turns OW-CPA securedeterministic PKEs into IND-CCA secure KEMs. This result is enabledby a new one-way to hiding (O2H) lemma which gives a tighter boundthan previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability, partially non-injective PKEs, and non-deterministic PKEs. In addition, we analyze the impact of different variations of the U 6⊥- transform discussed in the literature on the security of the final scheme. We consider the difference between explicit (U ⊥) and implicit (U6⊥) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least froma theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (U 6⊥) or just from the message (U6⊥ m)

M3 - Other contribution

ER -