Paper 2021/935

ROTed: Random Oblivious Transfer for embedded devices

Pedro Branco, Luís Fiolhais, Manuel Goulão, Paulo Martins, Paulo Mateus, and Leonel Sousa


Oblivious Transfer (OT) is a fundamental primitive in cryptography, supporting protocols such as Multi-Party Computation and Private Set Intersection (PSI), that are used in applications like contact discovery, remote diagnosis and contact tracing. Due to its fundamental nature, it is utterly important that its execution is secure even if arbitrarily composed with other instances of the same, or other protocols. This property can be guaranteed by proving its security under the Universal Composability model. Herein, a 3-round Random Oblivious Transfer (ROT) protocol is proposed, which achieves high computational efficiency, in the Random Oracle Model. The security of the protocol is based on the Ring Learning With Errors assumption (for which no quantum solver is known). ROT is the basis for OT extensions and, thus, achieves wide applicability, without the overhead of compiling ROTs from OTs. Finally, the protocol is implemented in a server-class Intel processor and four application-class ARM processors, all with different architectures. The usage of vector instructions provides on average a 40% speedup. The implementation shows that our proposal is at least one order of magnitude faster than the state-of-the-art, and is suitable for a wide range of applications in embedded systems, IoT, desktop, and servers. From a memory footprint perspective, there is a small increase (16%) when compared to the state-of-the-art. This increase is marginal and should not prevent the usage of the proposed protocol in a multitude of devices. In sum, the proposal achieves up to 37k ROTs/s in an Intel server-class processor and up to 5k ROTs/s in an ARM application-class processor. A PSI application, using the proposed ROT, is up to 6.6 times faster than related art.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCHES 2021
Oblivious TransferEmbedded SystemsPrivate Set IntersectionUniversal ComposabilityPost-Quantum Cryptography
Contact author(s)
mgoulao @ math tecnico ulisboa pt
2021-07-09: received
Short URL
Creative Commons Attribution


      author = {Pedro Branco and Luís Fiolhais and Manuel Goulão and Paulo Martins and Paulo Mateus and Leonel Sousa},
      title = {ROTed: Random Oblivious Transfer for embedded devices},
      howpublished = {Cryptology ePrint Archive, Paper 2021/935},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.