OPRF based on symmetric encryption

Question

We need to use OPRF(oblivious pseudo random function) on very large sets. Unfortunately most of algorithms use elliptic curves and so this algorithms are very slow. Does exist some relaxation of oprf(like the function is random only on generic input) which is based on symmetric cryptography or something similar and so is very effective?

Answer 1

"Minicrypt" refers to all cryptography that can be constructed unconditionally in the random oracle model. All "cheap" symmetric-key cryptography (block ciphers, symmetric-key encryption, hashing) is in minicrypt.

Oblivious PRF implies oblivious transfer (if you have a secure OPRF protocol, you can easily obtain a secure OT protocol). Impagliazzo & Rudich famously showed that there is no construction of oblivious transfer in minicrypt. Thus, there is no OPRF construction based solely on black-box use of symmetric-key cryptography.

---

The Impagliazzo-Rudich result only says that some public-key cryptography is necessary for OPRF. It doesn't say how much public-key cryptography is needed. You can use techniques from OT extension to get millions of OPRF instances using only a small amount of public-key cryptography (e.g., 128 exponentiations) and otherwise using only cheap symmetric-key cryptography. A lot of these constructions appear in the literature on private set intersection (PSI). One such result is the following:

• Pinkas, Rosulek, Trieu, Yanai: PSI from PaXoS: Fast, Malicious Private Set Intersection

The paper doesn't explicitly formalize an OPRF abstraction, but if you understand the fundamental connection between PSI and OPRF, you can appreciate that the main result is essentially an OPRF.

One problem with these kinds of "batch" OPRF constructions is that they don't allow the OPRF sender to choose the PRF key. Rather, the key is whatever "falls out" of the protocol. So this kind of OPRF may not be useful for all applications. As far as I know, it is an open problem to have an OPRF using only a tiny amount of public-key cryptography (and otherwise only black-box use of symmetric-key cryptography), where the OPRF sender can choose the PRF key.