Paper 2022/415

Efficient and Tight Oblivious Transfer from PKE with Tight Multi-User Security

Saikrishna Badrinarayanan, Daniel Masny, and Pratyay Mukherjee


We propose an efficient oblivious transfer in the random oracle model based on public key encryption with pseudorandom public keys. The construction is as efficient as the state of art though it has a significant advantage. It has a tight security reduction to the multi-user security of the underlying public key encryption. In previous constructions, the security reduction has a multiplicative loss that amounts in at least the amount of adversarial random oracle queries. When considering this loss for a secure parameter choice, the underlying public key encryption or elliptic curve would require a significantly higher security level which would decrease the overall efficiency. Our OT construction can be instantiated from a wide range of assumptions such as DDH, LWE, or codes based assumptions as well as many public key encryption schemes such as the NIST PQC finalists. Since tight multi-user security is a very natural requirement which many public key encryption schemes suffice, many public key encryption schemes can be straightforwardly plugged in our construction without the need of reevaluating or adapting any parameter choices.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Oblivious TransferPublic Key EncryptionMPCMulti User SettingTightness
Contact author(s)
daniel masny @ rub de
2022-04-04: revised
2022-04-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Daniel Masny and Pratyay Mukherjee},
      title = {Efficient and Tight Oblivious Transfer from PKE with Tight Multi-User Security},
      howpublished = {Cryptology ePrint Archive, Paper 2022/415},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.