## CryptoDB

### Melissa Chase

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Amortizing Rate-1 OT and Applications to PIR and PSI
📺
Abstract

Recent new constructions of rate-1 OT [D\"ottling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender's input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver.
In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.
1. PIR: We obtain a rate-1 PIR scheme with client communication cost of $O(\lambda\cdot\log N)$ group elements for security parameter $\lambda$ and database size $N$. Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication cost $O(\log N)$ number of group elements.
2. PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication of $O((m+\lambda) \log N)$ group elements where $m, N$ are the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication cost $O(m \cdot \log N)$ number of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at least $O(\lambda^2 m \log N)$ group elements.

2020

CRYPTO

Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF
📺
Abstract

We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., 30 - 100 Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably.
Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.

2020

ASIACRYPT

Secret-Shared Shuffle
📺
Abstract

Generating additive secret shares of a shuffled dataset - such that neither party knows the order in which it is permuted - is a fundamental building block in many protocols, such as secure collaborative filtering, oblivious sorting, and secure function evaluation on set intersection. Traditional approaches to this problem either involve expensive public-key based crypto or using symmetric crypto on permutation networks. While public-key-based solutions are bandwidth efficient, they are computation-heavy. On the other hand, constructions based on permutation networks are communication-bound, especially when the dataset contains large elements, for e.g., feature vectors in an ML context.
We design a new 2-party protocol for this task of computing secret shares of shuffled data, which we refer to as secret-shared shuffle. Our protocol is secure against a static semi-honest adversary.
At the heart of our approach is a new primitive we define (which we call ``Share Translation'') that generates two sets of pseudorandom values ``correlated via the permutation''. This allows us to reduce the problem of shuffling the dataset to the problem of shuffling pseudorandom values, which enables optimizations both in computation and communication. We then design a Share Translation protocol based on oblivious transfer and puncturable PRFs.
Our final protocol for secret-shared shuffle uses lightweight operations like XOR and PRGs, and in particular doesn't use public-key operations besides the base OTs. As a result, our protocol is concretely more efficient than the existing solutions. In particular, we are two-three orders of magnitude faster than public-key-based approach and one order of magnitude faster compared to the best known symmetric-key approach when the elements are moderately large.

2019

CRYPTO

Reusable Non-Interactive Secure Computation
📺
Abstract

We consider the problem of Non-Interactive Two-Party Secure Computation (NISC), where Rachel wishes to publish an encryption of her input x, in such a way that any other party, who holds an input y, can send her a single message which conveys to her the value f(x, y), and nothing more. We demand security against malicious parties. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver’s first message is reused.Motivated by the failure of the OT-based approach, we consider the problem of basing reusable NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. We also get reusable NISC in the OLE-hybrid model for general Boolean circuits using any one-way function.We complement this by a negative result, showing that reusable NISC is impossible to achieve in the OT-hybrid model. This provides a formal justification for the need to replace OT by OLE.We build a universally composable 2-message reusable OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008).By combining our NISC protocol in the OLE-hybrid model and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols for NP where following a statement-independent preprocessing, both proving and verifying are entirely “non-cryptographic” and involve only a constant computational overhead. Furthermore, we get the first statistical designated-verifier NIZK argument for NP under an assumption related to factoring.

2016

CRYPTO

2016

ASIACRYPT

2016

JOFC

2012

ASIACRYPT

#### Program Committees

- Crypto 2020
- Asiacrypt 2019
- Eurocrypt 2019
- Eurocrypt 2018
- Eurocrypt 2017
- Crypto 2016
- TCC 2016
- PKC 2016
- Crypto 2015
- PKC 2015
- Eurocrypt 2013
- TCC 2011
- PKC 2011
- Crypto 2008

#### Coauthors

- Masayuki Abe (2)
- Shashank Agrawal (2)
- Foteini Baldimtsi (1)
- Mira Belenkiy (2)
- Jan Camenisch (1)
- Nishanth Chandran (2)
- Bernardo David (2)
- Yevgeniy Dodis (1)
- Georg Fuchsbauer (1)
- Chaya Ganesh (1)
- Sanjam Garg (1)
- Esha Ghosh (1)
- Mohammad Hajiabadi (1)
- Alexander Healy (1)
- Yuval Ishai (1)
- Seny Kamara (1)
- Markulf Kohlweiss (8)
- Daniel Kraschewski (1)
- Jialin Li (1)
- Tianren Liu (1)
- Feng-Hao Liu (1)
- Anna Lysyanskaya (8)
- Tal Malkin (1)
- Mary Maller (1)
- Sarah Meiklejohn (5)
- Peihan Miao (2)
- Payman Mohassel (1)
- Ryo Nishimaki (3)
- Miyako Ohkubo (2)
- Rafail Ostrovsky (2)
- Oxana Poburinnaya (1)
- Leonid Reyzin (1)
- Hovav Shacham (1)
- Vinod Vaikuntanathan (2)
- Ivan Visconti (2)
- Keita Xagawa (1)