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 (:
Preliminaries
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
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.
CSI-FiSh
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.
OPUS
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.
Conclusion
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.