Skip to Main content Skip to Navigation
Conference papers

Combiners for Backdoored Random Oracles

Balthazar Bauer 1, 2 Pooya Farshim 2, 1 Sogol Mazaheri 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : We formulate and study the security of cryptographic hash functions in the backdoored random-oracle (BRO) model, whereby a big brother designs a "good" hash function, but can also see arbitrary functions of its table via backdoor capabilities. This model captures intentional (and unintentional) weaknesses due to the existence of collision-finding or inversion algorithms, but goes well beyond them by allowing, for example, to search for structured preimages. The latter can easily break constructions that are secure under random inversions. BROs make the task of bootstrapping cryptographic hardness somewhat challenging. Indeed, with only a single arbitrarily backdoored function no hardness can be bootstrapped as any construction can be inverted. However, when two (or more) independent hash functions are available, hardness emerges even with unrestricted and adaptive access to all backdoor oracles. At the core of our results lie new reductions from cryptographic problems to the communication complexities of various two-party tasks. Along the way we establish a communication complexity lower bound for set-intersection for cryptographically relevant ranges of parameters and distributions and where set-disjointness can be easy.
Document type :
Conference papers
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Pooya Farshim <>
Submitted on : Wednesday, October 24, 2018 - 5:55:20 PM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM


Files produced by the author(s)




Balthazar Bauer, Pooya Farshim, Sogol Mazaheri. Combiners for Backdoored Random Oracles. Advances in Cryptology – CRYPTO 2018, Aug 2018, Santa Barbara, United States. ⟨10.1007/978-3-319-96881-0_10⟩. ⟨hal-01866724v2⟩



Record views


Files downloads