Fischlin, Marc ; Rohrbach, Felix
Hrsg.: 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
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (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
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2023 |
| Herausgeber: | Rothblum, Guy N. ; Wee, Hoeteck |
| Autor(en): | Fischlin, Marc ; Rohrbach, Felix |
| Art des Eintrags: | Bibliographie |
| Titel: | Searching for ELFs in the Cryptographic Forest |
| Sprache: | Englisch |
| Publikationsjahr: | 27 November 2023 |
| Verlag: | Springer |
| Buchtitel: | TCC 2023: Theory of Cryptography |
| Reihe: | Lecture Notes in Computer Science |
| Band einer Reihe: | 14371 |
| Veranstaltungstitel: | 21st Theory of Cryptography Conference (TCC 2023) |
| Veranstaltungsort: | Taipei, Taiwan |
| Veranstaltungsdatum: | 29.11.-02.12.2023 |
| DOI: | 10.1007/978-3-031-48621-0_8 |
| Zugehörige Links: | |
| Kurzbeschreibung (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 |
| Zusätzliche Informationen: | - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part III |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Kryptographie und Komplexitätstheorie DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche Profilbereiche Profilbereiche > Cybersicherheit (CYSEC) Forschungsfelder Forschungsfelder > Information and Intelligence Forschungsfelder > Information and Intelligence > Cybersecurity & Privacy DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
| Hinterlegungsdatum: | 11 Apr 2024 12:32 |
| Letzte Änderung: | 11 Apr 2024 12:32 |
| PPN: | |
| Zugehörige Links: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum