New Monotones and Lower Bounds in Unconditional Two-Party Computation

Stefan Wolf, Jürg Wullschleger

Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.

Matthias Fitzi, Martin Hirt, Ueli M. Maurer

Sundara Rajan S, Shijin Rajakrishnan, Andrew Thangaraj +1 more

The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.

Matthias Fitzi, Martin Hirt, Ueli M. Maurer

Martin Hirt, Ueli M. Maurer

Stelvio Cimato, Antonella Cresti, Paolo D’Arco

A key distribution scheme is a method by means of which a trusted party distributes pieces of information among a set of users in such a way that each group of them can compute a common key for secure communication. In this paper we present a model for unconditionally secure key distribution schemes, i.e., schemes whose security is independent of the power of the adversary. We prove lower bounds on the amount of information the trusted party has to generate and each user has to keep secret in such schemes, and we show that some previous unconditionally secure models for key distribution fall in our model. As a consequence, the lower bounds given in the literature for these models can be seen as corollaries of our results. Hence, the main contribution of the paper consists in pointing out a sort of common structure underlying some apparently different key distribution techniques.