Structure vs. Hardness Through the Obfuscation Lens

被引:15
作者
Bitansky, Nir [1 ]
Degwekar, Akshay [1 ]
Vaikuntanathan, Vinod [1 ]
机构
[1] MIT, 77 Massachusetts Ave, Cambridge, MA 02139 USA
来源
ADVANCES IN CRYPTOLOGY - CRYPTO 2017, PT I | 2017年 / 10401卷
关键词
Indistinguishability obfuscation; Statistical zero-knowledge; NP boolean AND coNP; Structured hardness; Collision-resistant hashing; STATISTICAL ZERO-KNOWLEDGE; GENERIC CRYPTOGRAPHIC CONSTRUCTIONS; PUBLIC-KEY ENCRYPTION; SECURE HASH FUNCTIONS; FINDING COLLISIONS; LOWER BOUNDS; HOMOMORPHIC ENCRYPTION; LATTICE PROBLEMS; PROMISE PROBLEMS; COMPLEXITY;
D O I
10.1007/978-3-319-63688-7_23
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 complexity classes such as NP boolean AND 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 boolean AND coNP and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by fully 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 boolean AND coNP or SZK via fully 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.
引用
收藏
页码:696 / 723
页数:28
相关论文
共 82 条
  • [51] A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP
    Haitner, Iftach
    Mahmoody, Mohammad
    Xiao, David
    [J]. 25TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - CCC 2010, 2010, : 76 - 87
  • [52] Haitner I, 2009, LECT NOTES COMPUT SC, V5444, P202
  • [53] DUAL VECTORS AND LOWER BOUNDS FOR THE NEAREST LATTICE POINT PROBLEM
    HASTAD, J
    [J]. COMBINATORICA, 1988, 8 (01) : 75 - 81
  • [54] Hsiao CY, 2004, LECT NOTES COMPUT SC, V3152, P92
  • [55] Impagliazzo R., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P44, DOI 10.1145/73007.73012
  • [56] Ishai Y, 2005, LECT NOTES COMPUT SC, V3378, P445
  • [57] Jeong Han Kim, 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P535, DOI 10.1109/SFFCS.1999.814627
  • [58] The Dual BKR Inequality and Rudich's Conjecture
    Kahn, Jeff
    Saks, Michael
    Smyth, Clifford
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (02) : 257 - 266
  • [59] Kleinberg J. M., 2006, P 38 ANN ACM S THEOR
  • [60] One-Way Functions and (Im)perfect Obfuscation
    Komargodski, Ilan
    Moran, Tal
    Naor, Moni
    Pass, Rafael
    Rosen, Alon
    Yogev, Eylon
    [J]. 2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, : 374 - 383