On the Impossibility of Actively Secure Distributed Samplers

Lecture notes in computer science, pp. 547–581

Abstract

One-round secure computation is generally believed impossible due to the residual function attack : any honest-but-curious participant can replay the protocol in their head changing their input, and learn, in this way, a new output. Inputless functionalities are among the few that are immune to this problem. This paper studies one-round, multi-party computation protocols (MPC) that implement the most natural inputless functionality: one that generates a random sample from a fixed distribution. These are called distributed samplers . At Eurocrypt 2022, Abram, Scholl and Yakoubov showed how to build this primitive in the semi-honest model with dishonest majority. In this work, we give a lower bound for constructing distributed samplers with a malicious adversary in the standard model. More in detail, we show that for any construction in the stand-alone model with black-box simulation, even with a CRS and honest majority, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Our proof is based on an entropic argument, drawing a new connection between computationally secure MPC, information theory and learning theory.

Authors 4

1. Damiano Abram

   University of Edinburgh

   Affiliation as printed

   The University of Edinburgh, Edinburgh, UK

2. Serge Fehr Aachen

   Leiden University · Centrum Wiskunde & Informatica

   Affiliation as printed

   CWI Amsterdam and Leiden University, Amsterdam, The Netherlands

3. Maciej Obremski

   National University of Singapore

   Affiliation as printed

   National University of Singapore, Singapore, Singapore

4. Peter Schöll corresponding

   Aarhus University

   Affiliation as printed

   Aarhus University, Aarhus, Denmark