Paper 2021/895

Targeted Lossy Functions and Applications

Willy Quach, Brent Waters, and Daniel Wichs


Lossy trapdoor functions, introduced by Peikert and Waters (STOC '08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of number-theoretic or algebraic ``Cryptomania'' assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. First, they do not require an inversion trapdoor in injective mode. Second, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from ``Minicrypt'' assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: -Pseudo-entropy functions from one-way functions. -Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. -Extractors for extractor-dependent sources from one-way functions. -Selective-opening secure symmetric-key encryption from one-way functions. -A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Lossy functionsminicrypt
Contact author(s)
quach w @ northeastern edu
bwaters @ cs utexas edu
wichs @ ccs neu edu
2021-07-01: received
Short URL
Creative Commons Attribution


      author = {Willy Quach and Brent Waters and Daniel Wichs},
      title = {Targeted Lossy Functions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/895},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.