One-Sided Adaptively Secure Two-Party Computation

Andrew Y. Lindell

Carmit Hazay, Arpita Patra

Ran Canetti, Shafi Goldwasser, Oxana Poburinnaya

Carmit Hazay, Arpita Patra

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where “hackers ” actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that is dependent both on the circuit size and the security parameter. In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, which we believe is the right security notion in the two-party setting. We study the feasibility of (1) NCE with constant number of public key operations for large message spaces. (2) Oblivious transfer with constant number of public key operations for large sender’s input spaces, and (3) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions, while this is not known for fully adaptive security (where both parties may get corrupted).

Thomas H. Schneider, Michael Zohner

Hoi‐Kwong Lo

It had been widely claimed that quantum mechanics can protect private information during public decision in, for example, the so-called two-party secure computation. If this were the case, quantum smart-cards, storing confidential information accessible only to a proper reader, could prevent fake teller machines from learning the PIN (personal identification number) from the customers' input. Although such optimism has been challenged by the recent surprising discovery of the insecurity of the so-called quantum bit commitment, the security of quantum two-party computation itself remains unaddressed. Here I answer this question directly by showing that all one-sided two-party computations (which allow only one of the two parties to learn the result) are necessarily insecure. As corollaries to my results, quantum one-way oblivious password identification and the so-called quantum one-out-of-two oblivious transfer are impossible. I also construct a class of functions that cannot be computed securely in any two-sided two-party computation. Nevertheless, quantum cryptography remains useful in key distribution and can still provide partial security in ``quantum money'' proposed by Wiesner.