Paper 2018/958

On Tightly Secure Primitives in the Multi-Instance Setting

Dennis Hofheinz and Ngoc Khanh Nguyen


We initiate the study of general tight reductions in cryptography. There already exist a variety of works that offer tight reductions for a number of cryptographic tasks, ranging from encryption and signature schemes to proof systems. However, our work is the first to provide a universal definition of a tight reduction (for arbitrary primitives), along with several observations and results concerning primitives for which tight reductions have not been known. Technically, we start from the general notion of reductions due to Reingold, Trevisan, and Vadhan (TCC 2004), and equip it with a quantification of the respective reduction loss, and a canonical multi-instance extension to primitives. We then revisit several standard reductions whose tight security has not yet been considered. For instance, we revisit a generic construction of signature schemes from one-way functions, and show how to tighten the corresponding reduction by assuming collision-resistance from the used one-way function. We also obtain tightly secure pseudorandom generators (by using suitable rerandomisable hard-core predicates), and tightly secure lossy trapdoor functions.

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2019
Tight reductionsPrimitivesReductionsProvable Security
Contact author(s)
nkn @ zurich ibm com
2020-11-09: last of 2 revisions
2018-10-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz and Ngoc Khanh Nguyen},
      title = {On Tightly Secure Primitives in the Multi-Instance Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2018/958},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.