CryptoDB
Seung Geol Choi
Publications
Year
Venue
Title
2022
TCC
Secure Sampling with Sublinear Communication
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 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.
2019
JOFC
(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens
Abstract
We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware tokens for universally composable secure computation. As our main result, we show an oblivious-transfer (OT) protocol in which two parties each create and transfer a single, stateless token and can then run an unbounded number of OTs. We also show a more efficient protocol, based only on standard symmetric-key primitives (block ciphers and collision-resistant hash functions), that can be used if a bounded number of OTs suffice. Motivated by this result, we investigate the number of stateless tokens needed for universally composable OT. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.
2014
TCC
2013
ASIACRYPT
2008
TCC
Coauthors
- Seung Geol Choi (15)
- Carlos Cid (1)
- Dana Dachman-Soled (5)
- Ariel Elbaz (2)
- S. Dov Gordon (1)
- Ari Juels (1)
- Jonathan Katz (6)
- Aggelos Kiayias (1)
- Ranjit Kumaresan (2)
- Dong Hoon Lee (1)
- Kwangsu Lee (1)
- Linsheng Liu (1)
- Tal Malkin (7)
- Alex J. Malozemoff (1)
- Jong Hwan Park (1)
- Dominique Schröder (2)
- Hoeteck Wee (5)
- Arkady Yerukhimovich (3)
- Moti Yung (3)
- Hong-Sheng Zhou (4)
- Vassilis Zikas (1)