The table is roughly grouped by the used cryptographic primitives.
Communcation complexity, rounds and security assumptions are reported according to
the referenced papers. Entries marked with "?" indicate unavailable data.
The reported numbers are not analyzed independently.
Direct comparisons between the different constructions are challenging.
While some properties are straightforward (an OPRF is
either verifiable or it is not), others, like
preprocessing, are more nuanced. For instance, input-independent computation
may simply involve negotiating a reusable key (as in ADDG23) or performing a
number of OT calls (as in HKL+25) that could also be partially reused via extensions,
albeit less directly than a key.
An OPRF is marked "available" to link to a public implementation.
If you'd like your OPRF included, notice any inaccuracies, or want to suggest a missing paper,
please contact
me! I track the changes in the changelog.
| work | assumption | rounds | comm. cost | security(C-S) | preprocessing | no trusted setup | verifiable | available |
|---|---|---|---|---|---|---|---|---|
| TCRSTW22 | 3-Hash SDHI (not PQ) | 2 | 766 bits | malicious-malicious | - | YES | YES | YES |
| ADDS21 | (R)LWE+SIS | 2 | 2 MB | semihonest-semihonest | - | YES | NO | YES |
| ADDS21 | (R)LWE+SIS | 2 | 128 GB | malicious-malicious | - | YES | YES | NO |
| AG24 | (R)LWE+SIS | 2 | 222 kB* | malicious-malicious | 316 kB | YES | YES | NO |
| DDT25 | binary LWR | 2 | 11.9 kB | semihonest-semihonest | 1.5 MB | YES | NO | YES |
| ADDG23 | mod(2,3)+lattices | 2 | 10 kB | malicious-semihonest | 2.5 MB | YES | NO | NO |
| ADDG23 | mod(2,3)+lattices | 2 | 160 kB | malicious-malicious | 2.5 MB | YES | YES | NO |
| HKL+25 | heuristic LWR | 6 | 23 kB | semihonest-semihonest | 793 kB | YES | NO | YES |
| ESTX24 | iMLWE-RU-R+MLWE+SIS | 2 | 159 kB* | malicious-malicious | 20 kB | YES | YES | NO |
| APRR24 | mod(2,3) | 2 | 916 bits | malicious-semihonest | 38 bits | YES | YES | NO |
| DGH+21 | mod(2,3) | 2 | 641 bits | semihonest-semihonest | 1836 bits | NO | NO | NO |
| SHB23 | Legendre PRF | 3 | 13 kB | semihonest-semihonest | ? | YES | YES | NO |
| KCM24 | Legendre PRF | 2 | ~144 kB | semihonest-semihonest | ~432 kB | YES | YES | YES |
| BDFH24 | Legendre PRF as 2HashDH | 9 | 356 kB | malicious-malicious | 392 kB | YES | YES | YES |
| YBHKR24 | generalized power residue (Legendre) PRF | 3 | 774 kB | malicious-semihonest | - | YES | YES | NO |
| YBHKR24 | generalized power residue (Legendre) PRF | 3 | 970 kB | malicious-malicious | - | YES | YES | NO |
| FOO23 | AES+Garbled Circuits | 2 | 6.79MB | semihonest-semihonest | - | YES | NO | YES |
| HKLS24 | Minicrypt | ? | 22 bytes# | malicious-malicious | - | YES | NO | NO |
| Basso23 | Isogenies F_p^2 | 2 | 3.0 MB | malicious-malicious | - | NO | NO | NO |
| Basso23 | Isogenies F_p^2 | 2 | 8.7 MB | malicious-malicious | - | NO | YES | NO |
| BKW20 | Isogenies F_p + lattices | 2 | 20.54 kB | semihonest-semihonest | - | NO | NO | NO |
| BKW20 | Isogenies F_p + lattices | 4 | 34.88 kB | malicious-semihonest | - | NO | NO | NO |
| HHM+23 | Isogenies F_p + lattices + HE OT | 2 | 640 kB | semihonest-semihonest | - | YES | NO | YES |
| HHM+23 | Isogenies F_p | 258 | 24.7 kB | semihonest-semihonest | - | YES | NO | YES |
| dSP23 | Isogenies F_p | 2 | 384 bytes | malicious-semihonest | 68.4 kB | NO | YES | NO |
| dSP23 | Isogenies F_p | 2 | 16.38 kB | malicious-semihonest | - | NO | YES | NO |
Here is the latex code for (most of) the table. It uses Fontawesome5 and TiKz for symbols but is standalone otherwise. Feel free to use or adapt it in your paper, presentation or other tex-friendly environment, but please give credit for the use! It uses the article class to ensure the attributions are correctly.