TU Darmstadt / ULB / TUbiblio

Searching for ELFs in the Cryptographic Forest

Fischlin, Marc ; Rohrbach, Felix
eds.: Rothblum, Guy N. ; Wee, Hoeteck (2023)
Searching for ELFs in the Cryptographic Forest.
21st Theory of Cryptography Conference (TCC 2023). Taipei, Taiwan (29.11.-02.12.2023)
doi: 10.1007/978-3-031-48621-0_8
Conference or Workshop Item, Bibliographie

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

Item Type: Conference or Workshop Item
Erschienen: 2023
Editors: Rothblum, Guy N. ; Wee, Hoeteck
Creators: Fischlin, Marc ; Rohrbach, Felix
Type of entry: Bibliographie
Title: Searching for ELFs in the Cryptographic Forest
Language: English
Date: 27 November 2023
Publisher: Springer
Book Title: TCC 2023: Theory of Cryptography
Series: Lecture Notes in Computer Science
Series Volume: 14371
Event Title: 21st Theory of Cryptography Conference (TCC 2023)
Event Location: Taipei, Taiwan
Event Dates: 29.11.-02.12.2023
DOI: 10.1007/978-3-031-48621-0_8
Corresponding Links:
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

Additional Information:

- 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part III

Divisions: 20 Department of Computer Science
20 Department of Computer Science > Cryptography and Complexity Theory
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Forschungsfelder
Forschungsfelder > Information and Intelligence
Forschungsfelder > Information and Intelligence > Cybersecurity & Privacy
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Date Deposited: 11 Apr 2024 12:32
Last Modified: 18 Jul 2024 14:20
PPN: 520008529
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details