Paper 2023/863

On the (Im)possibility of Distributed Samplers: Lower Bounds and Party-Dynamic Constructions

Damiano Abram, Aarhus University
Maciej Obremski, National University of Singapore
Peter Scholl, Aarhus University

Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the standard model, even with a CRS, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Secondly, we study the question of building distributed samplers in the party-dynamic setting, where parties can join in an ad-hoc manner, and the total number of parties is unbounded. Here, we obtain positive results. First, we build a special type of unbounded universal sampler, which after a trusted setup, allows sampling from any distributed with unbounded size. Our construction is in the shared randomness model, where the parties have access to a shared random string, and uses indistinguishability obfuscation and somewhere statistically binding hashing. Next, using our unbounded universal sampler, we construct distributed universal samplers in the party-dynamic setting. Our first construction satisfies one-time selective security in the shared randomness model. Our second construction is reusable and secure against a malicious adversary in the random oracle model. Finally, we show how to use party-dynamic, distributed universal samplers to produce ideal, correlated randomness in the party-dynamic setting, in a single round of interaction.

Note: Updated related work

Available format(s)
Cryptographic protocols
Publication info
MPCNIMPCCRSObfuscationRandom oracleDynamic participantsEntropyImpossibilitySamplingTrusted setups
Contact author(s)
damiano abram @ cs au dk
obremski math @ gmail com
peter scholl @ cs au dk
2023-10-11: last of 3 revisions
2023-06-07: received
See all versions
Short URL
No rights reserved


      author = {Damiano Abram and Maciej Obremski and Peter Scholl},
      title = {On the (Im)possibility of Distributed Samplers: Lower Bounds and Party-Dynamic Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/863},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.