Bounds and constructions for mutually distrustful information theoretically secure cryptographic protocols

Reo Eriguchi, Kazumasa Shinagawa

Secure computation is a cryptographic primitive that enables mutually distrustful parties to jointly realize a possibly randomized functionality in a secure manner. Card-based secure computation studies the problem of implementing secure computation protocols visually by using physical cards, to help non-experts understand their mechanisms. Although many card-based secure computation protocols have been proposed, most of them focus on deterministic functionalities and only a few protocols for randomized functionalities are tailored to specific applications. In this work, we initiate the study of card-based protocols for generating uniformly random bits, which is the most fundamental randomized functionality in secure computation. We present four constructions of such protocols differing in the types of shuffles they use. We also show a lower-bound result that the number of shuffles required for protocols using complete shuffles must be at least the number of output bits. Furthermore, we demonstrate that our protocols for generating uniformly random bits can be extended to those for generating possibly non-uniform random numbers, when combined with existing card-based protocols for computing deterministic functions.

Shouhuai Xu, Gendu Zhang, Hong Zhu

Carsten Rudolph

Deepesh Data, Vinod M. Prabhakaran, Manoj Prabhakaran

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.

Jiawei Wu, Yanglin Hu, Akshay Bansal +1 more

Weak coin flipping is a cryptographic primitive in which two mutually distrustful parties generate a shared random bit to agree on a winner via remote communication. While a stand-alone secure weak coin flipping protocol can be constructed from noiseless quantum communication channels, its composability remains unexplored. In this work, we demonstrate that no weak coin flipping protocol can be abstracted as a simple black-box resource with composable security. Despite this, we also establish the overall stand-alone security of quantum weak coin flipping protocols under composition in sequential order.

Bartosz Przydatek