Secure Sampling with Sublinear Communication

Seung Geol Choi; Dana Dachman-Soled; S. Dov Gordon; Linsheng Liu; Arkady Yerukhimovich

Paper 2022/660

Secure Sampling with Sublinear Communication

Seung Geol Choi, United States Naval Academy

Dana Dachman-Soled, University of Maryland, College Park

S. Dov Gordon, George Mason University

Linsheng Liu, George Washington University

Arkady Yerukhimovich, George Washington University

Abstract

Random sampling from specified distributions is an important tool with wide applications for analysis of large-scale data. In this paper we study how to randomly sample when the distribution is partitioned among two parties' private inputs. Of course, a trivial solution is to have one party send a (possibly encrypted) description of its weights to the other party who can then sample over the entire distribution (possibly using homomorphic encryption). However, this approach requires communication that is linear in the input size which is prohibitively expensive in many settings. In this paper, we investigate secure 2-party sampling with \emph{sublinear communication} for many standard distributions. We develop protocols for $L_1$, and $L_2$ sampling. Additionally, we investigate the feasibility of sublinear product sampling, showing impossibility for the general problem and showing a protocol for a restricted case of the problem. We additionally show how such product sampling can be used to instantiate a sublinear communication 2-party exponential mechanism for differentially-private data release.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Secure Sampling multiparty computation sublinear communication
Contact author(s): choi @ usna edu
danadach @ umd edu
gordon @ gmu edu
lls @ gwu edu
arkady @ gwu edu
History: 2022-09-16: revised; 2022-05-27: received; See all versions
Short URL: https://ia.cr/2022/660
License: CC BY

BibTeX

@misc{cryptoeprint:2022/660,
      author = {Seung Geol Choi and Dana Dachman-Soled and S. Dov Gordon and Linsheng Liu and Arkady Yerukhimovich},
      title = {Secure Sampling with Sublinear Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2022/660},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/660}},
      url = {https://eprint.iacr.org/2022/660}
}