You are looking at a specific version 20170620:201719 of this paper. See the latest version.

Paper 2015/126

Perfect Structure on the Edge of Chaos

Nir Bitansky and Omer Paneth and Daniel Wichs

Abstract

We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class SZK - indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
omerpa @ gmail com
History
2017-06-20: revised
2015-02-26: received
See all versions
Short URL
https://ia.cr/2015/126
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.