Paper 2021/1525

Amortizing Rate-1 OT and Applications to PIR and PSI

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


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. - 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. - 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.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in Tcc 2021
Rate-1 OTSecure Multiparty ComputationCommunication ComplexityPIRPSI
Contact author(s)
melissac @ microsoft com
sanjamg @ berkeley edu
j li98 @ berkeley edu
mdhajiabadi @ uwaterloo ca
peihan @ uic edu
2021-11-22: received
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Sanjam Garg and Mohammad Hajiabadi and Jialin Li and Peihan Miao},
      title = {Amortizing Rate-1 OT and Applications to PIR and PSI},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1525},
      year = {2021},
      doi = {10.1007/978-3-030-90456-2_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.