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

Damiano Abram*, Peter Scholl, Sophia Yakoubov

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 : 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
Number of pages31
PublisherSpringer
Publication dateMay 2022
Pages790-820
ISBN (Print)9783031069437
ISBN (Electronic)978-3-031-06944-4
DOIs
Publication statusPublished - May 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: 30 May 20223 Jun 2022

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
Country/TerritoryNorway
CityTrondheim
Period30/05/202203/06/2022
SeriesLecture Notes in Computer Science (LNCS)
Volume13275
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round'. Together they form a unique fingerprint.

Cite this