International Association for Cryptologic Research

International Association
for Cryptologic Research


A Framework for Statistically Sender Private OT with Optimal Rate

Pedro Branco , Max Planck Institute for Security and Privacy
Nico Döttling , Helmholtz Center for Information Security (CISPA)
Akshayaram Srinivasan , Tata Institute of Fundamental Research
DOI: 10.1007/978-3-031-38557-5_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Statistical sender privacy (SSP) is the strongest achievable security notion for two-message oblivious transfer (OT) in the standard model, providing statistical security against malicious receivers and computational security against semi-honest senders. In this work we provide a novel construction of SSP OT from the Decisional Diffie-Hellman (DDH) and the Learning Parity with Noise (LPN) assumptions achieving (asymptotically) optimal amortized communication complexity, i.e. it achieves rate 1. Concretely, the total communication complexity for $k$ OT instances is $2k(1+o(1))$, which (asymptotically) approaches the information-theoretic lower bound. Previously, it was only known how to realize this primitive using heavy rate-1 FHE techniques [Brakerski et al., Gentry and Halevi TCC'19]. At the heart of our construction is a primitive called statistical co-PIR, essentially a a public key encryption scheme which statistically erases bits of the message in a few hidden locations. Our scheme achieves nearly optimal ciphertext size and provides statistical security against malicious receivers. Computational security against semi-honest senders holds under the DDH assumption.
  title={A Framework for Statistically Sender Private OT with Optimal Rate},
  author={Pedro Branco and Nico Döttling and Akshayaram Srinivasan},