A Post-Quantum Interactive Hashing Theorem

arXiv:2611.06124 · quant-ph, cs.CR · Submitted 2026-11-04 · Read on arXiv

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

Related papers