Arrow Research search

Author name cluster

Christian Majenz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

STOC Conference 2025 Conference Paper

Permutation Superposition Oracles for Quantum Query Lower Bounds

  • Christian Majenz
  • Giulio Malavolta
  • Michael Walter 0005

We propose a generalization of Zhandry’s compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry’s technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use the strictly monotone factorization of a permutation, which also underlies the well-known Fisher-Yates shuffle, to represent it in the oracle’s database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model, for all parameter choices. This proves a conjecture by Unruh.

Details

FOCS Conference 2025 Conference Paper

The Sponge Is Quantum Indifferentiable

  • Gorjan Alagic
  • Joseph Carolan
  • Christian Majenz
  • Saliha Tokat

The sponge is a cryptographic construction that turns a public permutation into a hash function. When the Keccak permutation is used, the resulting design constitutes the Secure Hash Algorithm 3 (SHA-3), standardized by the National Institute of Standards and Technology (NIST). SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption. While one can consider many security properties for the sponge, the ultimate one is indifferentiability from a random oracle, or simply indifferentiability. The sponge was proved indifferentiable against classical adversaries by Bertoni et al. in 2008. Despite significant efforts in the years since, little is known about sponge security against quantum adversaries, even for simple properties like preimage or collision resistance beyond a single round. This is primarily due to the lack of a satisfactory quantum analog of the lazy sampling technique for permutations. In this work, we develop a specialized technique that overcomes this barrier in the case of the sponge. We prove that the sponge is in fact indifferentiable from a random oracle against quantum adversaries. Our result establishes that the domain extension technique behind SHA-3 is secure in the post-quantum setting. Our indifferentiability bound for the sponge is a loose, but we also give bounds on preimage and collision resistance that are tighter.

Details
v2026.09.13