Paper 2020/1532

Oblivious Pseudorandom Functions from Isogenies

Dan Boneh, Dmitry Kogan, and Katharine Woo

Abstract

An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key $k$ for a secure pseudorandom function $F$, and the client has an input $x$ for the function. At the end of the protocol the client learns $F(k,x)$, and nothing else, and the server learns nothing. An OPRF is verifiable if the client is convinced that the server has evaluated the PRF correctly with respect to a prior commitment to $k$. OPRFs and verifiable OPRFs have numerous applications, such as private-set-intersection protocols, password-based key-exchange protocols, and defense against denial-of-service attacks. Existing OPRF constructions use RSA-, Diffie-Hellman-, and lattice-type assumptions. The first two are not post-quantum secure. In this paper we construct OPRFs and verifiable OPRFs from isogenies. Our main construction uses isogenies of supersingular elliptic curves over $\mathbb{F}_{p^{2}}$ and tries to adapt the Diffie-Hellman OPRF to that setting. However, a recent attack on supersingular-isogeny systems due to Galbraith et al. [ASIACRYPT 2016] makes this approach difficult to secure. To overcome this attack, and to validate the server's response, we develop two new zero-knowledge protocols that convince each party that its peer has sent valid messages. With these protocols in place, we obtain an OPRF in the SIDH setting and prove its security in the UC framework. Our second construction is an adaptation of the Naor-Reingold PRF to commutative group actions. Combining it with recent constructions of oblivious transfer from isogenies, we obtain an OPRF in the CSIDH setting.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
DOI
10.1007/978-3-030-64834-3_18
Keywords
oblivious pseudorandom functionsisogeny-based cryptography
Contact author(s)
dkogan @ cs stanford edu
History
2020-12-08: received
Short URL
https://ia.cr/2020/1532
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1532,
      author = {Dan Boneh and Dmitry Kogan and Katharine Woo},
      title = {Oblivious Pseudorandom Functions from Isogenies},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1532},
      year = {2020},
      doi = {10.1007/978-3-030-64834-3_18},
      url = {https://eprint.iacr.org/2020/1532}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.