Loading...
Please wait, while we are loading the content...
Similar Documents
Completeness Theorems for All Finite Stateless 2-Party Primitives
| Content Provider | CiteSeerX |
|---|---|
| Author | Kraschewski, Daniel |
| Abstract | Since Kilian showed in 1988 that oblivious transfer (OT) is complete in the sense that every secure multi-party computation can be realized from this primitive, cryptographers are working on reductions of OT to various other primitives. A long-standing open question in this context is the classification of finite stateless 2-party primitives (so-called “cryptogates”), i.e. trusted black boxes that can be jointly queried by two parties, have finite input and output alphabets, and do not change behavior depending on time or input history. Over the decades, completeness criteria have been found for deterministic cryptogates (i.e. primitives without internal randomness), noisy channels, and symmetric (i.e., both parties receive the same output) or asymmetric (i.e., only one party receives any output at all) randomized cryptogates. However, the known criteria for randomized primitives other than noisy channels only hold in presence of passive adversaries (i.e., even corrupted parties still follow the protocol). We complete this line of research by providing simple but comprehensive combinatorial completeness criteria for all finite stateless 2-party primitives. I.e., for the first time there are completeness criteria for randomized primitives that are neither symmetric nor asymmetric (but |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Completeness Theorem Deterministic Cryptogates Internal Randomness Secure Multi-party Computation So-called Cryptogates Comprehensive Combinatorial Completeness Criterion Randomized Primitive Output Alphabet Noisy Channel Finite Stateless 2-party Primitive Various Primitive Trusted Black Box Oblivious Transfer Long-standing Open Question Completeness Criterion Passive Adversary |
| Content Type | Text |
