Paper 2023/1403

Searching for ELFs in the Cryptographic Forest

Marc Fischlin, TU Darmstadt
Felix Rohrbach, TU Darmstadt
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2023
Keywords
Extremely Lossy FunctionOracle SeparationRandom Oracle
Contact author(s)
marc fischlin @ cryptoplexity de
felix rohrbach @ cryptoplexity de
History
2023-09-24: approved
2023-09-18: received
See all versions
Short URL
https://ia.cr/2023/1403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1403,
      author = {Marc Fischlin and Felix Rohrbach},
      title = {Searching for {ELFs} in the Cryptographic Forest},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1403},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.