Paper 2022/535

Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round

Damiano Abram, Peter Scholl, and Sophia Yakoubov

Abstract

Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys. In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things, indistinguishability obfuscation. We introduce what we call a distributed sampler, which enables $n$ parties to sample a single public value (SRS) from any distribution. We construct a semi-malicious distributed sampler in the plain model, and use it to build a semi-malicious public-key PCF (Boyle et al, FOCS 2020) in the plain model. A public-key PCF can be thought of as a distributed correlation sampler; instead of producing a public SRS, it gives each party a private random value (where the values satisfy some correlation). We introduce a general technique called an anti-rusher which compiles any one-round protocol with semi-malicious security without inputs to a similar one-round protocol with active security by making use of a programmable random oracle. This gets us actively secure distributed samplers and public-key PCFs in the random oracle model. Finally, we explore some tradeoffs. Our first PCF construction is limited to reverse-sampleable correlations (where the random outputs of honest parties must be simulatable given the random outputs of corrupt parties); we additionally show a different construction without this limitation, but which does not allow parties to hold secret parameters of the correlation. We also describe how to avoid the use of a random oracle at the cost of relying on sub-exponentially secure indistinguishability obfuscation.

Note: Minor fix to Section 5.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
Keywords
Indistinguishability obfuscationmulti-party computationround complexity
Contact author(s)
damiano abram @ cs au dk
peter scholl @ cs au dk
sophia yakoubov @ cs au dk
History
2022-05-13: revised
2022-05-10: received
See all versions
Short URL
https://ia.cr/2022/535
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/535,
      author = {Damiano Abram and Peter Scholl and Sophia Yakoubov},
      title = {Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/535},
      year = {2022},
      url = {https://eprint.iacr.org/2022/535}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.