Efficient Post-Quantum Instantiations of OPRF Framework

The 2Hash OPRF Framework and Efficient Post-Quantum Instantiations Ward Beullens1 1, Lucas Dodgson2 2, Sebastian Faller Sebastian Faller1,2 1,2, Julia Hesse1 1 1 1 IBM Research Europe 2 2ETH Z rich

Oblivious Pseudo- Random Functions (OPRF) Security Client Privacy - Server does not see x Server Privacy - Client does not see key Pseudo-Random Output - F is a PRF x OPRF PRF( . , . ) key PRF(key,x) Server Client The 2Hash OPRF Framework 2

OPRFs: The silver bullet for password- authentication The 2Hash OPRF Framework 3

Conventional password-over-TLS Problems: Server sees the password attempt pw' in the clear stores salt, Hash(pw,salt) pw' Server TLS channel Client check Hash(pw',salt) == Hash(pw,salt) The 2Hash OPRF Framework 4

Conventional password-over-TLS Problems: Server sees the password attempt pw' in the clear stores salt, Hash(pw,salt) TLS hijacking reveals the password attempt pw' in the clear pw' Server TLS channel Client check Hash(pw',salt) == Hash(pw,salt) The 2Hash OPRF Framework 5

Better solution: Authentication with an OPRF Security Server never sees pw' pw' not visible to network attackers pw' OPRF PRF( . , . ) key PRF(key,pw') Server Client PRF(key,pw') as good as a salted hash of pw' The 2Hash OPRF Framework 6

Tons of other applications: WhatsApps End-to- End Encrypted Backups pw' OPRF PRF( . , . ) key Securing your Bitcoin Wallet with a PIN (PPSS) PRF(key,pw') Server Client Single-Sign-On Private Set Intersection ... The 2Hash OPRF Framework 7

OPRFs are cool. But how expensive are they? The 2Hash OPRF Framework 8

2HashDH [JKK14,JKKX16] Efficiency 3 exponentiations 2 Hashes Sending two group elements ~ 66 Bytes r p A = H1(x)r A B=Ak Server B Client y=H2(x,B1/r) The 2Hash OPRF Framework 9

Quantum-safe OPRFs? Not yet there.... Not yet there.... The 2Hash OPRF Framework 10

Quantum-safe OPRFs (shown are only construction with security for both parties) 2023 2021 2024 Lattice-based [ADDS21] FHE+Dark Matter [ADDG24] Our work More constructions Standard lattice assumptions [AG24] ~500 KB network traffic Feasibility result. ~128 GB network traffic Based on new assumption ~3 MB network traffic Legendre Symbol assumption ~900 KB network traffic 7 sec only running the server ~180ms whole protocol run From new (interactive) lattice assumptions [ESTX24] ~200 KB network traffic Legendre Symbol assumption [YBHKR24] ~970 KB network traffic The 2Hash OPRF Framework 11

A framework for building OPRFs The 2Hash OPRF Framework 12

2HashDH [JKK14,JKKX16] Ingredients: Two hash functions PRF uses H1 and H2 Inner function f is unpredictable PRF( k, x ) = H2(x, H1(x)k )) Blind-unblind to evaluate f Inner function f(k,h) = hk Oblivious Evaluation of inner function f: r p A = H1(x)r A B = Ak Server B Client Output H2(x,B1/r) The 2Hash OPRF Framework 13

Unpredictable and key- collision resistant Multi-Party Computation 2 Hash functions The 2Hash Framework For a secure OPRF you need: f f # # 0100010 0111001 We show two instantiations: - From block ciphers - From Legendre symbols The 2Hash OPRF Framework 14

Instantiation from Legendre symbols The 2Hash OPRF Framework 16

Decisional Shifted Legendre Symbol Assumption [Dam88,GRRSS16] The 2Hash OPRF Framework 17

The inner function The 2Hash OPRF Framework 18

The inner function Function defined bitwise. Need to prevent overlap. Offsets need to be random. The 2Hash OPRF Framework 19

The outer function Two hash functions Inner function f(h,k) The 2Hash OPRF Framework 20

Efficient MPC protocol for inner function The 2Hash OPRF Framework 21

Core idea: Computing one Legendre symbol Add-and-blind Random s2 blinds k Output e is square iff (x+k) is Need to execute this in a batched way s ?p Compute s2(x + k) x s, k e Server Client ( p ) e output The 2Hash OPRF Framework 22

VOLE and VOLE+ Suppose ui = (k + li)si2 vi= si2 h u,v u,v VOLE o o = u u + h v v Server Client Then oi = ui + h vi = (k + li)si2 + h si2 = (h + k + li)si2 The 2Hash OPRF Framework 23

VOLE and VOLE+ ru u, ,rv v ?p h u,v, u,v,ru u, ,rv v VOLE+ o o = u u + h v v cu u = = <u, u, >+ru cv = <v v, >+rv Server Client The 2Hash OPRF Framework 24

The OPRF protocol (simplified) si,ru u, ,rv v ?p ui i = (k + li)si2 vi i = si i2 2 Server(k) Client(x) h = H(x) u,v, u,v,ru u, ,rv v VOLE+ o, o, cu u, , cv, oi = ui + h vi = (k + li)si2 + h si2 si2 Prove in ZK Same k for all ui v is squares output ( ) ( p ), , ( p ) o1 ol H' x, The 2Hash OPRF Framework 25

Security: Relaxed OPRF definition Our functionality: Our functionality: Allows to delay extraction of malicious keys until first online execution No change for honest keys Provably sufficient for applications like OPAQUE and PPSS The 2Hash OPRF Framework 26

1 Take-Aways We show a generic framework for UC-secure OPRFs Paper 2 We give two instantiations: from block ciphers from Legendre symbols ia.cr/2024/450 Implementation 3 We achieve sufficient security for applications like OPAQUE and PPSS github.com/2Hash Framework/Legen dreOPRF The 2Hash OPRF Framework 27

References [JKK14] [JKK14] https://ia.cr/2014/650 [JKKX16] [JKKX16] https://ia.cr/2016/144 [Dam88] [Dam88] https://link.springer.com/chapter/10.1007/0-387-34799-2_13 [GSRR16] [GSRR16] https://ia.cr/2016/542 The 2Hash OPRF Framework 28

Why not MPC-evaluate the whole PRF? We aim for UC security (i.e., [JKKX16]) Client output must be programmable. (Hash) Pseudo-randomness must even hold for malicious keys. (key-collision resistance) x OPRF PRF( . , . ) key PRF(key,x) Server Client The 2Hash OPRF Framework 29