Paper 2016/574

Structure vs Hardness through the Obfuscation Lens

Nir Bitansky, Akshay Degwekar, and Vinod Vaikuntanathan


Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so called structured) complexity classes such as NP$\cap$coNP or statistical zero-knowledge (SZK). Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes — they imply hard problems in NP$\cap$coNP and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer. We show that the above primitives, and many others, do not imply hard problems in NP$\cap$coNP or SZK via black-box reductions. In fact, we first show that even the very powerful notion of Indistinguishability Obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO.

Note: Fixed typo in Def 4.2.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Indistinguishability ObfuscationStatistical Zero-knowledgeStructured HardnessCollision-Resistant Hashing
Contact author(s)
akshayd @ mit edu
2021-01-23: last of 3 revisions
2016-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Akshay Degwekar and Vinod Vaikuntanathan},
      title = {Structure vs Hardness through the Obfuscation Lens},
      howpublished = {Cryptology ePrint Archive, Paper 2016/574},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.