Decoding LTFs in the Generic Group Model

Dennis Hofheinz; Julia Kastner; Akin Ünal; Bogdan Ursu

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Lossy Trapdoor Functions Lower Bounds Generic Group Model
Contact author(s): hofheinz @ inf ethz ch
julia kastner @ inf ethz ch
akin uenal @ inf ethz ch
bogdan ursu @ inf ethz ch
History: 2023-06-12: approved; 2023-06-07: received; See all versions
Short URL: https://ia.cr/2023/866
License: CC BY

BibTeX

@misc{cryptoeprint:2023/866,
      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{https://eprint.iacr.org/2023/866}},
      url = {https://eprint.iacr.org/2023/866}
}