Paper 2022/783
Augmented Random Oracles
, NTT Research, Princeton UniversityAbstract
We propose a new paradigm for justifying the security of random oracle-based protocols, which we call the Augmented Random Oracle Model (AROM). We show that the AROM captures a wide range of important random oracle impossibility results. Thus a proof in the AROM implies some resiliency to such impossibilities. We then consider three ROM transforms which are subject to impossibilities: Fiat-Shamir (FS), Fujisaki-Okamoto (FO), and Encrypt-with-Hash (EwH). We show in each case how to obtain security in the AROM by strengthening the building blocks or modifying the transform. Along the way, we give a couple other results. We improve the assumptions needed for the FO and EwH impossibilities from indistinguishability obfuscation to circularly secure LWE; we argue that our AROM still captures this improved impossibility. We also demonstrate that there is no "best possible" hash function, by giving a pair of security properties, both of which can be instantiated in the standard model separately, which cannot be simultaneously satisfied by a single hash function.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- random oracle uninstantiability deterministic encryption fiat-shamir cca-security
- Contact author(s)
- mzhandry @ gmail com
- History
- 2022-06-20: approved
- 2022-06-17: received
- See all versions
- Short URL
- https://ia.cr/2022/783
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/783,
author = {Mark Zhandry},
title = {Augmented Random Oracles},
howpublished = {Cryptology ePrint Archive, Paper 2022/783},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/783}},
url = {https://eprint.iacr.org/2022/783}
}
