International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: ROTed: Random Oblivious Transfer for embedded devices

Authors:
P. Branco , Instituto de Telecomunicações, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
L. Fiolhais , INESC-ID, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
M. Goulão , Instituto de Telecomunicações, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
P. Martins , INESC-ID, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
P. Mateus , Instituto de Telecomunicações, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
L. Sousa , INESC-ID, Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
Download:
DOI: 10.46586/tches.v2021.i4.215-238
URL: https://tches.iacr.org/index.php/TCHES/article/view/9065
Search ePrint
Search Google
Abstract: 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.
Video from TCHES 2021
BibTeX
@article{tches-2021-31316,
  title={ROTed: Random Oblivious Transfer for embedded devices},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 4},
  pages={215-238},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9065},
  doi={10.46586/tches.v2021.i4.215-238},
  author={P. Branco and L. Fiolhais and M. Goulão and P. Martins and P. Mateus and L. Sousa},
  year=2021
}