Welcome to the resource topic for 2023/1145
Title:
New Random Oracle Instantiations from Extremely Lossy Functions
Authors: Chris Brzuska, Geoffroy Couteau, Christoph Egger, Pihla Karanko, Pierre Meyer
Abstract: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.
ePrint: https://eprint.iacr.org/2023/1145
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .