The magic of ELFs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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 polynomiallymany hardcore bits for any one-way function. Such applications were previously known from strong knowledge assumptions — for example polynomiallymany hardcore bits were only know 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 pairing-based groups. Combining with the applications above, our work gives several practical constructions relying on qualitatively different — and arguably better — assumptions than prior works.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings
EditorsMatthew Robshaw, Jonathan Katz
PublisherSpringer Verlag
Pages479-508
Number of pages30
ISBN (Print)9783662530177
DOIs
StatePublished - Jan 1 2016
Event36th Annual International Cryptology Conference, CRYPTO 2016 - Santa Barbara, United States
Duration: Aug 14 2016Aug 18 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9814

Other

Other36th Annual International Cryptology Conference, CRYPTO 2016
CountryUnited States
CitySanta Barbara
Period8/14/168/18/16

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Zhandry, M. (2016). The magic of ELFs. In M. Robshaw, & J. Katz (Eds.), Advances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings (pp. 479-508). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9814). Springer Verlag. https://doi.org/10.1007/978-3-662-53018-4_18