Paper 2018/036

Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs

Peter Scholl

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2018
Keywords
oblivious transferlearning with errorsmulti-party computation
Contact author(s)
peter scholl @ cs au dk
History
2018-01-08: received
Short URL
https://ia.cr/2018/036
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/036,
      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{https://eprint.iacr.org/2018/036}},
      url = {https://eprint.iacr.org/2018/036}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.