Cryptographic Complexity Classes and Computational Intractability Assumptions

摘要: Which computational intractability assumptions are inherent to cryptography? We present a broad framework pose and investigate this question. first aim understand the “cryptographic complexity” of various tasks, independent any assumptions. In our cryptographic tasks modeled as multi-party computation functionalities. consider universally composable secure protocol for one task given access another most natural complexity reduction between two tasks. Some these reductions unconditional, others unconditionally impossible, but vast majority appear depend on assumptions; it is relationship with that we study. detailed investigation large classes 2-party functionalities, find every able classify turns out be true or false, else equivalent existence one-way functions (OWF) semi-honest (equivalently, standalone-secure) oblivious transfer protocols (sh-OT). This leads us conjecture there only small finite number distinct among infinite different in framework. If indeed few manifest framework, propose they an extraordinarily fundamental nature, since contains variety was formulated without regard prevalent