Aarhus University Seal

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

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

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 yearMay 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
LandNorway
ByTrondheim
Periode30/05/202203/06/2022
SeriesLecture Notes in Computer Science (LNCS)
Volume13275
ISSN0302-9743

Bibliographical note

Publisher Copyright:
© 2022, International Association for Cryptologic Research.

See relations at Aarhus University Citationformats

ID: 276779396