Search papers, labs, and topics across Lattice.
This paper proves the straight-line extractability of the Fischlin transform in the quantum random oracle model (QROM), addressing a long-standing open problem. The proof leverages a compressed oracle-based extractor and establishes the post-quantum security of the transform. The result provides a post-quantum NIZK alternative to Pass' transform with smaller proof sizes.
The Fischlin transform, a classic technique for non-interactive zero-knowledge proofs, is now provably secure against quantum attacks, opening the door to smaller, post-quantum secure proofs.
The Fischlin transform yields non-interactive zero-knowledge proofs with straight-line extractability in the classical random oracle model. This is done by forcing a prover to generate multiple accepting transcripts through a proof-of-work mechanism. Whether the Fischlin transform is straight-line extractable against quantum adversaries has remained open due to the difficulty of reasoning about the likelihood of query transcripts in the quantum-accessible random oracle model (QROM), even when using the compressed oracle methodology. In this work, we prove that the Fischlin transform remains straight-line extractable in the QROM, via an extractor based on the compressed oracle. This establishes the post-quantum security of the Fischlin transform, providing a post-quantum straight-line extractable NIZK alternative to Pass' transform with smaller proof size. Our techniques include tail bounds for sums of independent random variables and for martingales as well as symmetrization, query amplitude and quantum union bound arguments.
