Amortizing Rate-1 OT and Applications to PIR and PSI

Melissa Chase, Sanjam Garg, Mohammad Hajiabadi, Jialin Li, Peihan Miao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Recent new constructions of rate-1 OT [Döttling, 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(λ· log N) group elements for security parameter λ 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+ λ) 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· 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(λ2mlog N) group elements.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 19th International Conference, TCC 2021, Proceedings
EditorsKobbi Nissim, Brent Waters, Brent Waters
PublisherSpringer Science and Business Media Deutschland GmbH
Pages126-156
Number of pages31
ISBN (Print)9783030904555
DOIs
StatePublished - 2021
Event19th International Conference on Theory of Cryptography, TCC 2021 - Raleigh, United States
Duration: Nov 8 2021Nov 11 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13044 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Conference on Theory of Cryptography, TCC 2021
Country/TerritoryUnited States
CityRaleigh
Period11/8/2111/11/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Amortizing Rate-1 OT and Applications to PIR and PSI'. Together they form a unique fingerprint.

Cite this