Tightly Secure Lossy Trapdoor Functions: Constructions and Applications

Abstract EN

Lossy trapdoor functions (LTFs), introduced by Peiker and Waters in STOC’08, are functions that may be working in another injective mode or a lossy mode.

Given such a function key, it is impossible to distinguish an injective key from a lossy key for any (probabilistic) polynomial-time adversary.

This paper studies lossy trapdoor functions with tight security.

First, we give a formal definition for tightly secure LTFs.

Loosely speaking, a collection of LTFs is tightly secure if the advantage to distinguish a tuple of injective keys from a tuple of lossy keys does not degrade in the number of function keys.

Then, we show that tightly secure LTFs can be used to construct public-key encryption schemes with tight CPA security in a multiuser, multichallenge setting, and with tight CCA security in a multiuser, one-challenge setting.

Finally, we present a construction of tightly secure LTFs from the decisional Diffie-Hellman assumption.