Skip to main content

The Magic of ELFs

Author(s): Zhandry, Mark

To refer to this page use:
Abstract: We introduce the notion of an Extremely Lossy Function (ELF). An ELF is a family of functions with an image size that is tunable anywhere from injective to having a polynomial-sized image. Moreover, for any efficient adversary, for a sufficiently large polynomial r (necessarily chosen to be larger than the running time of the adversary), the adversary cannot distinguish the injective case from the case of image size r. We develop a handful of techniques for using ELFs, and show that such extreme lossiness is useful for instantiating random oracles in several settings. In particular, we show how to use ELFs to build secure point function obfuscation with auxiliary input, as well as polynomially many hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions—for example, polynomially many hardcore bits were only known from differing inputs obfuscation, a notion whose plausibility has been seriously challenged. We also use ELFs to build a simple hash function with output intractability, a new notion we define that may be useful for generating common reference strings. Next, we give a construction of ELFs relying on the exponential hardness of the decisional Diffie–Hellman problem, which is plausible in elliptic curve groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different—and arguably better—assumptions than prior works.
Publication Date: 2019
Citation: Zhandry, Mark. "The Magic of ELFs." Journal of Cryptology 32, no. 3 (2019): 825-866. doi:10.1007/s00145-018-9289-9
DOI: 10.1007/s00145-018-9289-9
ISSN: 0933-2790
EISSN: 1432-1378
Pages: 825 - 866
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Cryptology
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.