International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the (In)Security of the Diffie-Hellman Oblivious PRF with Multiplicative Blinding

Authors:
Stanislaw Jarecki
Hugo Krawczyk
Jiayu Xu
Download:
Search ePrint
Search Google
Presentation: Slides
Abstract: Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns F_k(x) and nothing else while the server learns nothing. OPRF's have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is F_k(x)=H2(x,(H1(x))^k) computed using so-called exponential blinding, i.e., the client sends a=(H1(x))^r for random r, the server responds b=a^k, which the client ublinds as v=b^{1/r} to compute F_k(x)=H2(x,v). However, this protocol requires two variable-base exponentiations on the client, while a more efficient multiplicative blinding scheme replaces one or both client exponentiations with fixed-base exponentiation, leading to the decrease of the client's computational cost by a factor between two to six, depending on pre-computation. We analyze the security of the above OPRF with multiplicative blinding, showing surprising weaknesses that offer attack avenues which are not present using exponential blinding. We characterize the security of this OPRF implementation as a "Revised OPRF" functionality, a relaxation of UC OPRF functionality used in prior work. On the positive side, we show that the Revised OPRF suffices for the security of OPAQUE, the asymmetric PAKE protocol, hence allowing OPAQUE the computational advantages of multiplicative blinding. Unfortunately, we also show examples of other OPRF applications which become insecure when using such blinding. The conclusion is that usage of multiplicative blinding for F_k(x) defined as above, in settings where correct value g^k (needed for multiplicative blinding) is not authenticated, and OPRF inputs are of low entropy, must be carefully analyzed, or avoided all together. We complete the picture by showing a simple and safe alternative definition of function F_k(x) which offers (full) UC OPRF security using either form of blinding.
Video from PKC 2021
BibTeX
@article{pkc-2021-30977,
  title={On the (In)Security of the Diffie-Hellman Oblivious PRF with Multiplicative Blinding},
  booktitle={Public-Key Cryptography - PKC 2021},
  publisher={Springer},
  author={Stanislaw Jarecki and Hugo Krawczyk and Jiayu Xu},
  year=2021
}