Foundations of Secure Interactive Computing

摘要: The problem of secure multiparty computation is usually described as follows: each n players in a network holds private input xi. Together they would like to compute function F(x1,...,xn) without revealing the inputs, even though no particular player can be trusted. Attempts contrive formal definitions for have treated properties solution separately (correctness, privacy, etc.), giving an ad hoc collection desirable and varied that do not support clear or comparable proofs.We propose clear, concise, unified definition security reliability interactive computations. We develop reduction called relative resilience captures all desired at single blow. Relative allows one classify compare arbitrary protocols terms reliability, same way Turing reductions allow algorithms complexity. Security reduce simple statement: protocol F resilient if it ideal which trusted host available F. notions wide variety computations, including zero-knowledge proof systems, Byzantine Agreement, oblivious transfer, two-party circuit evaluation, among others.Relative provides modular techniques other approaches lack: may sequence ranging from real-world protocol, proving successive with greater clarity less Folk theorems about "transitivity" concatenated are now provable; proofs reveal such folk fail under subtle conditions previously gone unnoticed. conciseness modularity our provide great designing reasoning already lead provably significantly more efficient than those appearing literature.