Studies in incoercible and adaptively secure computation

Despite being a relatively young field, cryptography taught us how to perform seemingly-impossible tasks, which now became part of our everyday life. One of them is secure multiparty computation (MPC), which allows mutually distrustful parties to jointly perform a computation on their private inputs, so that each party only learns its prescribed output, but nothing else. In this work we deal with two longstanding challenges of MPC: adaptive security and deniability (or, incoercibility). A protocol is said to be adaptively secure, if it still guarantees security for the remaining honest parties, even if some parties turn dishonest during the execution of the protocol, or even after the execution. (In contrast, statically secure protocols give security guarantees only when the set of dishonest parties is fixed before the execution starts.) While adaptive security threat model is often more realistic than the static one, there is a huge gap between efficiency of statically and adaptively secure protocols: adaptively secure protocols often require more complicated constructions, stronger assumptions, and more rounds of interaction. We improve in efficiency over the state of the art in adaptive security for a number of settings, including the first adaptively secure MPC protocol in constant number of rounds, under assumptions comparable to those of static protocols (previously known protocols required as many rounds of interaction as the depth of the circuit being computed). The second challenge we deal with is providing resilience in the situation where an external coercer demands that participants disclose their private inputs and all their secret keys - e.g. via threats, bribe, or court order. Deniable (or, incoercible) protocols allow coerced participants to convincingly lie about their inputs and secret keys, thereby still maintaining their privacy. While the concept was proposed more than twenty years ago, to date secure protocols withstanding coercion of all participants were not known, even for the simple case of encryption. We present the first construction of such an encryption scheme, and then show how to combine it with adaptively secure protocols to obtain the first incoercible MPC which withstands coercion of all parties