Blogging about OPRFs, accepted papers, talks...

Please *click* on a post summary to view its full content.

[Paper] OPRFs from Isogenies: Design and Analysis

Our recent paper on Oblivious Pseudorandom Functions (OPRFs) from CSIDH has been accepted at AsiaCCS 2024! The main contributions are: 1. discussing the generic method to construct Naor-Reingold PRFs, where we showed how to do so efficiently. 2. showing how to securely evaluate the generic Naor-Reingold OPRF from CSIDH when using isogenies, and 3. proposing a new way to evaluate OPRFs without using Oblivious Transfer. In addition, we implemented two protocols with the OPRFs: the password-based authentication protocol OPAQUE and a private set intersection protocol. The paper also inspired the big table of post-quantum OPRFs, where I try to keep track of all post-quantum OPRFs to compare them more easily. If you would like a high-level introduction to the paper, please expand the post (:


To make the blog post self-contained, I'll briefly explain OPRFs, Naor-Reingold constructions and CSIDH.

Oblivious Pseudorandom Functions (OPRFs)

An OPRF is a two-party protocol between a party with a key, which we will call server, and a party with an input, called a client. The OPRF takes both the key and the input from the parties and computes a pseudorandom output only the client can see. The oblivious trait comes from the guarantee that the server learns nothing from the client, especially not the input and the output of the OPRF, and the client learns nothing from the server except the output, especially not the key. The abstract functionality enables us to design a wide range of protocols, two of which we detail in our paper. My favourite intuition for OPRFs is that an OPRF takes a low-entropy input (for example, a client's password) and produces an online high-entropy output. The OPRF is denoted as a function, F, such that F(k, x) = y, and can have additional properties. A verifiable OPRF gives a guarantee to the client that a certain, pre-committed key was used by the server (think of a certificate). A partially oblivious OPRF includes a public tag in the computation, which is useful for e.g. timestamps, similar to a salt in hashing.

Naor-Reingold PRF (NR-PRF)

The NR-PRF allows us to compute a PRF while simultaneously hashing an arbitrary input to a group element of an Abelian group. If the input is not binary, it is bit-decomposed, so x becomes (x1, ..., xn), with any xi lies in {0,1}. To process an input of n bits, n+1 group elements are sampled randomly (though the exact process depends on the group the OPRF uses). We will call the random elements (k0, ..., kn), since they are used as the server's key. The PRF is computed as F(k,x)=k0+(k1*x1)+(k2*x2)+...+(kn*xn). Clearly, if the group elements are random (and large enough to satisfy cryptographic guarantees, as well as having enough input bits), it is hard to distinguish the output from a random group element of the same group.
Note that I used additive notation here, but the exact notation of course depends on the underlying group.

Naor-Reingold OPRF (NR-OPRF)

To evaluate the NR-PRF obliviously, we need the help of a primitive called Oblivious Transfer (OT). In the simplest form, OT takes two messages (m0, m1) from the server and a choice bit c from the client. Depending on the choice bit, the client gets the message mc when executing the OT protocol. The protocol is secure when the server learns nothing about c and the client learns nothing about the message that is not mc. To combine OT and the NR-PRF, we sample n additional random group elements from the same group (r1, r2, ..., rn). The input to the OT is (ri, ri+ki) for each i in [1, ..., n]. After the OT, the client holds the blinded result r1+(k1*x1)+r2+(k2*x2)+...+rn+(kn*xn), depending on the input. To finalize the computation, we take k0 and add the inverted r elements so we get k0-r1-r2-...-rn and send the result to the client. Adding k0-r1-r2-...-rn and r1+(k1*x1)+r2+(k2*x2)+...+rn+(kn*xn) gives the result k0+(k1*x1)+(k2*x2)+...+(kn*xn), which is exactly the NR-PRF, but with oblivious evaluation!


CSIDH is short for Commutative Supersingular Isogeny Diffie Hellman. Even though it includes isogenies, to understand the NR-constructions it suffices to think of the CSIDH group action as a random walk on a graph. The public key is the node of the graph (a supersingular elliptic curve), and the private key is the walk, or the isogeny computation between the curves. Describing the walk is as simple as giving the steps on the isogenies. CSIDH-512, the smallest instance that claims 128 bits of security (which is debated) uses 74 different isogenies, so from any node in the graph, we can go to 2*74 different nodes using different walks- going forward and backwards. This gives the commutative property of CSIDH.
CSIDH-512 restricts the number of steps that can be made using one of the 74 walks to the bound of [-5, 5], as this gives good enough diffusion to make it difficult to guess the path.
Naor-Reingold PRF + CSIDH
To compute the NR-PRF with CSIDH, we sample n keys with 74 entries between -5 and 5. Instead of a sequential execution, we can just add the keys together which makes the computation of the PRF a lot faster, as the group action only has to be computed once.
For example, adding two keys that are (1, 3, ...) and (2, -4, ...) results in the key (3, -1, ...), as walking one step and then two more steps is equivalent to walking three steps.


You probably already see a problem with adding keys: They leak what was added depending on the context. For example, adding two keys where the coefficients are 5 in both keys results in 10, which immediately leaks the sums. This is normally not a problem as the group elements are computed modulo a number, but in CSIDH, we can't just sample a random element and add it to a key without leaking at least a part of a key. That makes constructing the NR-OPRF more difficult.
The solution here is to use CSI-FiSh, which allows to add keys and then reduce modulo the class structure. In simple terms, this means that we find an equivalent representation that does not leak the terms of the addition using lattices. The consequence for the CSIDH-NR-OPRF is that we need an additional reduction step before inputting ki+ri to the OT. We provide an implementation that is actually somewhat efficient, but only using lattice OT, as performing a trusted setup computation is still hard in CSIDH. Throughout the paper we call the construction the NR-OPRF.


Originally, we just wanted to implement the NR-OPRF to benchmark against some other post-quantum OPRFs. When we found the issue with the leaking keys, we didn't immediately think about CSI-FiSh as a mitigation. Instead, we thought: What if we use the result of the OT computation directly instead of encrypting the blinded keys? It turns out that this works in CSIDH, because knowing a node in a graph does not tell you anything about the graph.
To compute the OPRF directly, the client starts with a randomized curve produced by sampling a random element rc and sends E'=r*E to the server. The server replies with two curves (rs*E', (k1+rs)*E'). They continue doing this for n times, with the client re-blinding the curve before sending it to the server in every turn. In the end, the server then unblinds a final curve, and the client can then unblind the entire result. If this is a bit confusing, I'd advise to look at the figure in the paper.
The protocol is nice because we eliminated the need for sending around keys. The nodes of the graph are quite useless, as the path is unknown. However, while the new OPRF needs only 60% of the CSIDH group action computations compared to the OT construction when computing the NR-OPRF (and using an isogeny OT protocol), the protocol needs a linear number of rounds (messages sent depending on each other) with respect to the input bits. This is why we called our resulting OPRF OPUS (latin for "work"), because of the many computations and rounds it takes to compute the OPRF. Coincidentally, a band from Styria is also called OPUS.


So are isogeny-based OPRFs the future? Looking at our runtimes, probably not. Nevertheless, it is really cool to see how using different primitives to realize a functionality can result in eliminating a previously necessary subprotocol (concretely OT). Also, here is the obligatory disclaimer: I would not recommend using any of our protocols immediately, even if you don't care about efficiency. The protocols, especially OPUS, have not been analyzed a lot and the code is not side-channel free (or audited). If you want to know even more, read the details in our paper: OPRFs from Isogenies: Designs and Analysis.