Publikationen

Autor	Fischlin, Marc; Rohrbach, Felix
Datum	2023
Art	Conference Proceedings
Abstrakt	Extremely Lossy Functions (ELFs) are families of functions that, depending on the choice during key generation, either operate in injective mode or instead have only a polynomial image size. The choice of the mode is indistinguishable to an outsider. ELFs were introduced by Zhandry (Crypto 2016) and have been shown to be very useful in replacing random oracles in a number of applications. One open question is to determine the minimal assumption needed to instantiate ELFs. While all constructions of ELFs depend on some form of exponentially-secure public-key primitive, it was conjectured that exponentially-secure secret-key primitives, such as one-way functions, hash functions or one-way product functions, might be sufficient to build ELFs. In this work we answer this conjecture mostly negative: We show that no primitive, which can be derived from a random oracle (which includes all secret-key primitives mentioned above), is enough to construct even moderately lossy functions in a black-box manner. However, we also show that (extremely) lossy functions themselves do not imply public-key cryptography, leaving open the option to build ELFs from some intermediate primitive between the classical categories of secret-key and public-key cryptography
Konferenz	21st Theory of Cryptography Conference (TCC 2023)
ISBN	978-3-031-48620-3
Serie	Lecture Notes in Computer Science
In	TCC 2023: Theory of Cryptography, p.207-236
Publisher	Springer
Url	https://tubiblio.ulb.tu-darmstadt.de/id/eprint/143698