A Post-Quantum Interactive Hashing Theorem
quant-ph, cs.CR
Submitted: 2026-11-04
Updated: 2026-11-04
License: http://creativecommons.org/licenses/by/4.0/
The gist: Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols…
Abstract
Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP and statistically hiding commitments from arbitrary one-way functions [NOV06,HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations.
Sources
- The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model
- Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements