Paper 2016/933

Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection

Michele Orrù, Emmanuela Orsini, and Peter Scholl


This paper describes a 1-out-of-N oblivious transfer (OT) extension protocol with active security, which achieves very low overhead compared with the passively secure protocol of Kolesnikov and Kumaresan (Crypto 2011). Our protocol obtains active security using a consistency check which requires only simple computation and has a communication overhead that is independent of the total number of OTs to be produced. We prove its security in both the random oracle model and the standard model, assuming a variant of correlation robustness. We describe an implementation, which demonstrates our protocol only incurs an overhead of around 5–30% on top of the passively secure protocol. Random 1-out-of-N OT is a key building block in recent, very efficient, passively secure private set intersection (PSI) protocols. Our random OT extension protocol has the interesting feature that it even works when N is exponentially large in the security parameter, provided that the sender only needs to obtain polynomially many outputs. We show that this can be directly applied to improve the performance of PSI, allowing the core private equality test and private set inclusion subprotocols to be carried out using just a single OT each. This leads to a reduction in communication of up to 3 times for the main component of PSI.

Note: Full version

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CT-RSA 2017
Oblivious transferprivate set intersectionmulti-party computation
Contact author(s)
Emmanuela Orsini @ bristol ac uk
Peter Scholl @ bristol ac uk
michele orru @ ens fr
2019-01-29: last of 4 revisions
2016-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Orrù and Emmanuela Orsini and Peter Scholl},
      title = {Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2016/933},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.