Paper 2023/866

Decoding LTFs in the Generic Group Model

Dennis Hofheinz, ETH Zurich
Julia Kastner, ETH Zurich
Akin Ünal, ETH Zurich
Bogdan Ursu, ETH Zurich

Lossy trapdoor functions (LTFs) constitute a useful and versatile cryptographic building block. LTFs have found applications in various types of encryption schemes, are closely connected to statistically secure oblivious transfer protocols, and have led to the first constructions of group-based trapdoor functions. However, with one recent exception, all known group-based LTFs are comparatively inefficient, and in particular suffer from large images. In this work, we attempt to explain this inefficiency, and derive lower bounds for the image size of group-based LTFs. In essence, we find that purely algebraic group-based LTFs (i.e., LTFs that use the underlying group in a generic way, without considering group representations) must suffer from a large image size (of an at least super-constant number of group elements). Our results also help to explain the mentioned exceptional group-based LTF with compact images.

Available format(s)
Publication info
Lossy Trapdoor FunctionsLower BoundsGeneric Group Model
Contact author(s)
hofheinz @ inf ethz ch
julia kastner @ inf ethz ch
akin uenal @ inf ethz ch
bogdan ursu @ inf ethz ch
2023-06-12: approved
2023-06-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz and Julia Kastner and Akin Ünal and Bogdan Ursu},
      title = {Decoding LTFs in the Generic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2023/866},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.