1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

"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:

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.

$\endgroup$
1
  • $\begingroup$ Yes, I thought about OT extension, but in my application I need to use OPRF for the same key several times. Thank you for clarifying. Now, I've realized that an effective algorithm(for my application) most likely does not exist. But nevertheless your answer is very useful for me. $\endgroup$ Apr 3 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.