Post-quantum one-way permutations suffice for perfect zero-knowledge NP arguments
Original title: Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
The NOVY commitment is shown sum-binding and collapse-binding against quantum polynomial-time committers.
The paper argues that post-quantum one-way permutations are enough for perfect zero-knowledge classical arguments for all of NP, with security against quantum adversaries. It shows the NOVY bit-commitment scheme, built from any permutation using interactive hashing, is sum-binding and collapse-binding against quantum polynomial-time committers when the permutation is post-quantum one-way. That property lets Blum's perfect zero-knowledge argument for HAMCYCLE remain unchanged against quantum adversaries.
- The result covers classical arguments for all of NP.
- Security is claimed against quantum adversaries, not only classical ones.
- Collapse-binding lets Blum's HAMCYCLE argument stand as written.
- The assumption is that the permutation is post-quantum one-way.
From the original article
1 min read at arxiv.orgIn this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries.
By Frédéric Dupuis · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.