Towards defeating backdoored random oracles: Indifferentiability with bounded adaptivity

Yevgeniy Dodis, Pooya Farshim, Sogol Mazaheri, Stefano Tessaro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the backdoored random-oracle (BRO) model, besides access to a random function H, adversaries are provided with a backdoor oracle that can compute arbitrary leakage functions f of the function table of H. Thus, an adversary would be able to invert points, find collisions, test for membership in certain sets, and more. This model was introduced in the work of Bauer, Farshim, and Mazaheri (Crypto 2018) and extends the auxiliary-input idealized models of Unruh (Crypto 2007), Dodis, Guo, and Katz (Eurocrypt 2017), Coretti et al. (Eurocrypt 2018), and Coretti, Dodis, and Guo (Crypto 2018). It was shown that certain security properties, such as one-wayness, pseudorandomness, and collision resistance can be re-established by combining two independent BROs, even if the adversary has access to both backdoor oracles. In this work we further develop the technique of combining two or more independent BROs to render their backdoors useless in a more general sense. More precisely, we study the question of building an indifferentiable and backdoor-free random function by combining multiple BROs. Achieving full indifferentiability in this model seems very challenging at the moment. We however make progress by showing that the xor combiner goes well beyond security against preprocessing attacks and offers indifferentiability as long as the adaptivity of queries to different backdoor oracles remains logarithmic in the input size of the BROs. We even show that an extractor-based combiner of three BROs can achieve indifferentiability with respect to a linear adaptivity of backdoor queries. Furthermore, a natural restriction of our definition gives rise to a notion of indifferentiability with auxiliary input, for which we give two positive feasibility results. To prove these results we build on and refine techniques by Göös et al. (STOC 2015) and Kothari et al. (STOC 2017) for decomposing distributions with high entropy into distributions with more structure and show how they can be applied in the more involved adaptive settings.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 18th International Conference, TCC 2020, Proceedings
EditorsRafael Pass, Krzysztof Pietrzak
PublisherSpringer Science and Business Media Deutschland GmbH
Pages241-273
Number of pages33
ISBN (Print)9783030643805
DOIs
StatePublished - 2020
Event18th International Conference on Theory of Cryptography, TCCC 2020 - Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12552 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Theory of Cryptography, TCCC 2020
CountryUnited States
CityDurham
Period11/16/2011/19/20

Keywords

  • Auxiliary input
  • Backdoors
  • Communication complexity
  • Hash functions
  • Indifferentiability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Towards defeating backdoored random oracles: Indifferentiability with bounded adaptivity'. Together they form a unique fingerprint.

Cite this