2013 | OriginalPaper | Buchkapitel
Building Lossy Trapdoor Functions from Lossy Encryption
verfasst von : Brett Hemenway, Rafail Ostrovsky
Erschienen in: Advances in Cryptology - ASIACRYPT 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we show how to derandomize lossy encryption (with long messages) to obtain lossy trapdoor functions, and hence injective one-way trapdoor functions.
Bellare, Halevi, Sahai and Vadhan (CRYPTO ’98) showed that if
Enc
is an IND-CPA secure cryptosystem, and
H
is a random oracle, then
x
↦
Enc
(
x
,
H
(
x
)) is an injective trapdoor function. In this work, we show that if
Enc
is a lossy encryption with messages at least 1-bit longer than randomness, and
h
is a pairwise independent hash function, then
x
↦
Enc
(
x
,
h
(
x
)) is a lossy trapdoor function, and hence also an injective trapdoor function.
The works of Peikert, Vaikuntanathan and Waters and Hemenway, Libert, Ostrovsky and Vergnaud showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption. In their construction, if the sender randomness is shorter than the message in the OT, it will also be shorter than the message in the lossy encryption. This gives an alternate interpretation of our main result. In this language, we show that
any
2-message statistically sender-private semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of
injective
one-way trapdoor functions. This is in contrast to the black box separation of injective trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption.