Paper 2018/036

Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs

Peter Scholl


We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic primitives. Our main technique is a novel twist on the classic OT extension of Ishai et al. (Crypto 2003), using an additively key-homomorphic PRF to reduce interaction. We first use this to construct a protocol for a large batch of 1-out-of-$n$ OTs on random inputs, with amortized $o(1)$ communication. Converting these to 1-out-of-2 OTs on chosen strings requires logarithmic communication. The key-homomorphic PRF used in the protocol can be instantiated under the learning with errors assumption with exponential modulus-to-noise ratio.

Available format(s)
Publication info
Published by the IACR in PKC 2018
oblivious transferlearning with errorsmulti-party computation
Contact author(s)
peter scholl @ cs au dk
2018-01-08: received
Short URL
Creative Commons Attribution


      author = {Peter Scholl},
      title = {Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/036},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.