Paper 2023/1176

Composable Oblivious Pseudo-Random Functions via Garbled Circuits

Sebastian Faller, IBM Research - Zurich, ETH Zurich
Astrid Ottenhues, Karlsruhe Institute of Technology, KASTEL Security Research Labs
Johannes Ottenhues, University of St. Gallen

Oblivious Pseudo-Random Functions (OPRFs) are a central tool for building modern protocols for authentication and distributed computation. For example, OPRFs enable simple login protocols that do not reveal the password to the provider, which helps to mitigate known shortcomings of password-based authentication such as password reuse or mix-up. Reliable treatment of passwords becomes more and more important as we login to a multitude of services with different passwords in our daily life. To ensure the security and privacy of such services in the long term, modern protocols should always consider the possibility of attackers with quantum computers. Therefore, recent research has focused on constructing post-quantum-secure OPRFs. Unfortunately, existing constructions either lack efficiency, or they are based on complex and relatively new cryptographic assumptions, some of which have lately been disproved. In this paper, we revisit the security and the efficiency of the well-known “OPRFs via Garbled Circuits” approach. Such an OPRF is presumably post-quantum-secure and built from well-understood primitives, namely symmetric cryptography and oblivious transfer. We investigate security in the strong Universal Composability model, which guarantees security even when multiple instances are executed in parallel and in conjunction with arbitrary other protocols, which is a realistic scenario in today’s internet. At the same time, it is faster than other current post-quantumsecure OPRFs. Our implementation and benchmarks demonstrate that our proposed OPRF is currently among the best choices if the privacy of the data has to be guaranteed for a long time.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Latincrypt 2023
Oblivious Pseudo-Random FunctionGarbled CircuitsPost-Quantum CryptographyUniversal Composability
Contact author(s)
sebastian faller @ ibm com
astrid ottenhues @ kit edu
johannes ottenhues @ posteo org
2023-10-11: last of 2 revisions
2023-08-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Faller and Astrid Ottenhues and Johannes Ottenhues},
      title = {Composable Oblivious Pseudo-Random Functions via Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1176},
      year = {2023},
      doi = {},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.