Paper 2022/185

Statistically Sender-Private OT from LPN and Derandomization

Nir Bitansky and Sapir Freizeit


We construct a two-message oblivious transfer protocol with statistical sender privacy (SSP OT) based on the Learning Parity with Noise (LPN) Assumption and a standard Nisan-Wigderson style derandomization assumption. Beyond being of interest on their own, SSP OT protocols have proven to be a powerful tool toward minimizing the round complexity in a wide array of cryptographic applications from proofs systems, through secure computation protocols, to hard problems in statistical zero knowledge (SZK). The protocol is plausibly post-quantum secure. The only other constructions with plausible post quantum security are based on the Learning with Errors (LWE) Assumption. Lacking the geometric structure of LWE, our construction and analysis rely on a different set of techniques. Technically, we first construct an SSP OT protocol in the common random string model from LPN alone, and then derandomize the common random string. Most of the technical difficulty lies in the first step. Here we prove a robustness property of the inner product randomness extractor to a certain type of linear splitting attacks. A caveat of our construction is that it relies on the so called low noise regime of LPN. This aligns with our current complexity-theoretic understanding of LPN, which only in the low noise regime is known to imply hardness in SZK.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
oblivious transferlearning parity with noiselpn
Contact author(s)
nbitansky @ gmail com
sapirfreizeit @ gmail com
2022-02-28: last of 2 revisions
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Sapir Freizeit},
      title = {Statistically Sender-Private OT from LPN and Derandomization},
      howpublished = {Cryptology ePrint Archive, Paper 2022/185},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.