International Association
for Cryptologic Research

Carsten Baum , Technical University of Denmark

Jens Berlips , SecureDNA Foundation

Walther Chen , SecureDNA Foundation

Ivan B. Damgård , Aarhus University

Kevin M. Esvelt , MIT

Leonard Foner , SecureDNA Foundation

Dana Gretton , MIT

Martin Kysel , SecureDNA Foundation

Ronald L. Rivest , MIT

Lawrence Roy , Aarhus University

Francesca Sage-Ling , SecureDNA Foundation

Adi Shamir , Weizmann Institute

Vinod Vaikuntanathan , MIT

Lynn Van Hauwe , SecureDNA Foundation

Theia Vogel , SecureDNA Foundation

Benjamin Weinstein-Raun , SecureDNA Foundation

Daniel Wichs , Northeastern University, NTT Research

Stephen Wooster , SecureDNA Foundation

Andrew C. Yao , Tsinghua University

Yu Yu , Shanghai Jiao Tong University

DOI: 10.62056/a66cy7qiu

URL: https://cic.iacr.org//p/1/3/10

Search ePrint

Search Google

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor $o(1)$ as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead $o(1)$ over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.