Paper 2024/1751

Offline-Online Indifferentiability of Cryptographic Systems

Ashrujit Ghoshal, Carnegie Mellon University
Ilan Komargodski, Hebrew University of Jerusalem and NTT Research
Gil Segev, Hebrew University of Jerusalem
Abstract

The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the security of a construction is captured by a ``single-stage'' security game, it may generally provide no meaningful guarantees when the security is captured by a ``multi-stage'' one. In particular, the indifferentiability framework does not capture offline-online games, where the adversary can perform an extensive offline computation to later speed up the online phase. Such security games are extremely common, both in practice and in theory. Over the past decade, there has been numerous attempts to meaningfully extend the indifferentiability framework to offline-online games, however, they all ultimately met with little success. In this work, our contribution is threefold. First, we propose an extension of the classical indifferentiability framework, we refer to as *offline-online-indifferentiability*, that applies in the context of attackers with an expensive offline phase (á la Ghoshal and Tessaro, CRYPTO '23). Second, we show that our notion lends itself to a natural and meaningful composition theorem for offline-online security games. Lastly, as our main technical contribution, we analyze the offline-online-indifferentiability of two classical variants of the Merkle-Damg\aa rd hashing mechanism, one where the key is fed only to the first block in the chain and the other where the key is fed to each block in the chain. For both constructions, we prove a *tight* bound on their offline-online-indifferentiability (i.e., an upper bound and an attack that matches it). Notably, our bound for the second variant shows that the construction satisfies *optimal* offline-online-indifferentiability.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Offline-online tradeoffsindifferentiabilityrandom oracles
Contact author(s)
aghoshal @ andrew cmu edu
ilank @ cs huji ac il
segev @ cs huji ac il
History
2024-10-28: approved
2024-10-26: received
See all versions
Short URL
https://ia.cr/2024/1751
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1751,
      author = {Ashrujit Ghoshal and Ilan Komargodski and Gil Segev},
      title = {Offline-Online Indifferentiability of Cryptographic Systems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1751},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1751}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.