Cryptographic Complexity Classes and Computational Intractability Assumptions
Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the cryptographic complexity of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi-party computation functionalities. We consider a universally composable secure protocol for one task given access to another task as the most natural complexity reduction between the two tasks. Some of these cryptographic complexity reductions are unconditional, others are unconditionally impossible, but the vast majority appear to depend on computational assumptions; it is this relationship with computational assumptions that we study. In our detailed investigation of large classes of 2-party functionalities, we find that every reduction we are able to classify turns out to be unconditionally true or false, or else equivalent to the existence of one-way functions (OWF) or of semi-honest (equivalently, standalone-secure) oblivious transfer protocols (sh-OT). This leads us to conjecture that there are only a small finite number of distinct computational assumptions that are inherent among the infinite number of different cryptographic reductions in our framework. If indeed only a few computational intractability assumptions manifest in this framework, we propose that they are of an extraordinarily fundamental nature, since the framework contains a large variety of cryptographic tasks, and was formulated without regard to any of the prevalent computational intractability assumptions.
cryptographic complexity computational complexity intractability assumptions secure multiparty computation
Hemanta K. Maji Manoj Prabhakaran Mike Rosulek
Department of Computer Science, University of Illinois, Urbana-Champaign. Partially supported by NSF Department of Computer Science, University of Montana
国际会议
The First Symposium on Innovations in Computer Science(2010 计算机科学创新研讨会 ICS 2010)
北京
英文
266-289
2010-01-05（万方平台首次上网日期，不代表论文的发表时间）