Paper 2023/1145

New Random Oracle Instantiations from Extremely Lossy Functions

Chris Brzuska, Aalto University
Geoffroy Couteau, Université Paris Cité, CNRS, IRIF
Christoph Egger, Université Paris Cité, CNRS, IRIF
Pihla Karanko, Aalto University
Pierre Meyer, Université Paris Cité, CNRS, IRIF, Reichman University

We instantiate two random oracle (RO) transformations using Zhandry's extremely lossy function (ELF) technique (Crypto'16). Firstly, using ELFs and indistinguishabililty obfuscation (iO), we instantiate a modified version of the Fujisaki-Okamoto (FO) transform which upgrades a public-key encryption scheme (PKE) from indistinguishability under chosen plaintext attacks (IND-CPA) to indistinguishability under chosen ciphertext attacks (IND-CCA). We side-step a prior uninstantiability result for FO by Brzuska, Farshim, and Mittelbach (TCC'15) by (1) hiding the randomness from the (potentially ill-designed) IND-CPA encryption scheme and (2) embedding an additional secret related to the hash-function into the secret-key of the IND-CCA-secure PKE, an idea brought forward by Murphy, O’Neill, Zaheri (Asiacrypt 2022) who also instantiate a modified FO variant also under ELFs and iO for the class of lossy PKE. Our transformation applies to all PKE which can be inverted given their randomness. Secondly, we instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), $\mathsf{PRF}_\mathsf{new}(k,x):=\mathsf{wPRF}(k,\mathsf{RO}(x))$. Our construction replaces $\mathsf{RO}$ by $\mathsf{PRF}_\mathsf{old}(k_\mathsf{pub},\mathsf{elf}(x))$ with a key $k_\mathsf{pub}$, that, unusually, is known to the distinguishing adversary against $\mathsf{PRF}_\mathsf{new}$. We start by observing that several existing weak PRF candidates are plausibly also secure under such distributions of pseudorandom inputs, generated by $\mathsf{PRF}_\mathsf{old}$. Firstly, analogous cryptanalysis applies and/or an attack with such pseudorandom inputs would imply surprising results such as key agreement from the high-noise version of the Learning Parity with Noise (LPN) assumption. Our simple transformation applies to the entire family of PRF-style functions. Specifically, we obtain results for oblivious PRFs, which are a core building block for password-based authenticated key exchange (PAKE) and private set intersection (PSI) protocols, and we also obtain results for pseudorandom correlation functions (PCF), which are a key tool for silent oblivious transfer (OT) extension.

Available format(s)
Publication info
Random OraclesExtremely Lossy FunctionFujisaki-OkamotoPseudorandom Correlation Function
Contact author(s)
chris brzuska @ aalto fi
couteau @ irif fr
christoph egger @ irif fr
pihla karanko @ aalto fi
pierre meyer @ irif fr
2023-07-27: approved
2023-07-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Brzuska and Geoffroy Couteau and Christoph Egger and Pihla Karanko and Pierre Meyer},
      title = {New Random Oracle Instantiations from Extremely Lossy Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1145},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.