###
**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 |

**Options (only for editors)**

Show editorial Details |