Paper 2018/900

Enhancements Are Blackbox Non-Trivial: Impossibility of Enhanced Trapdoor Permutations from Standard Trapdoor Permutations

Mohammad Hajiabadi

Abstract

Trapdoor permutations (TDP) are a fundamental primitive in cryptography. Over the years, several variants of this notion have emerged as a result of various applications. However, it is not clear whether these variants may be based on the standard notion of TDPs. We study the question of whether enhanced trapdoor permutations can be based on classical trapdoor permutations. The main motivation of our work is in the context of existing TDP-based constructions of oblivious transfer and non-interactive zero-knowledge protocols, which require enhancements to the classical TDP notion. We prove that these enhancements are non-trivial, in the sense that there does not exist fully blackbox constructions of enhanced TDPs from classical TDPs. At a technical level, we show that the enhanced TDP security of any construction in the random TDP oracle world can be broken via a polynomial number of queries to the TDP oracle as well as a weakening oracle, which provides inversion with respect to randomness. We also show that the standard one-wayness of a random TDP oracle stays intact in the presence of this weakening oracle.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2018
Keywords
Black-box separationsEnhanced Trapdoor PermutationsTrapdoor Permutations
Contact author(s)
mdhajiabadi @ berkeley edu
History
2018-09-25: received
Short URL
https://ia.cr/2018/900
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/900,
      author = {Mohammad Hajiabadi},
      title = {Enhancements Are Blackbox Non-Trivial: Impossibility of Enhanced Trapdoor Permutations from Standard Trapdoor Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2018/900},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/900}},
      url = {https://eprint.iacr.org/2018/900}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.