PaperfootJoin free
arXiv

One-way permutations suffice for quantum zero-knowledge

Assuming certain functions are hard for quantum computers to reverse, the proof established classical verification that reveals no extra information, even against efficient quantum attackers.

Paper by Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, Louis-Charles Thibodeau
A closed loop connects circular joints beside a covered stack, with scattered gray tiles and closely grouped dark blue-green tiles nearby.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

The paper proved that perfect zero-knowledge arguments—checks that reveal no extra information—can use ordinary messages and resist efficient quantum attackers for all problems with efficiently checkable solutions. These problems form the class called NP. The result assumed that post-quantum one-way permutations exist: functions that rearrange possible inputs but are hard for efficient quantum computers to reverse.

The researchers first proved two quantum-security properties of the NOVY commitment scheme, which lets someone lock in a hidden choice. They then used one property to prove that Blum’s existing argument remained perfectly zero-knowledge against quantum attackers without any changes. That argument checks whether a network contains a loop visiting every point exactly once.

Why it matters

The mathematical proof showed that this classical verification method did not need redesigning to preserve perfect zero-knowledge against quantum attackers under the stated assumption.

Caveats

The guarantee depended on the stated hardness assumption and covered efficient quantum attackers, not attackers with unlimited computing power. The paper is an arXiv preprint.

In this paper

post-quantum perfect zero-knowledge arguments for NP

Methods
WatRefl (this paper)Rec (this paper)NOVY scheme (evaluated)Blum's perfect zero-knowledge argument for HAMCYCLE (evaluated)ValEstRepair

What it shows

Post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries.

In 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.

Abstract

The NOVY scheme is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way.

We first establish that Naor, Ostrovsky,Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way.

Abstract

The collapse-binding property of the NOVY scheme allows Blum's perfect zero-knowledge argument for HAMCYCLE to remain perfect zero-knowledge against quantum adversaries.

We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.

Abstract

Rewinding algorithm Rec has circuit complexity in O(N*T*Size(MeasExpt)*(1/epsilon)*log(1/delta)).

Moreover, the algorithm has circuit complexity in O(N\cdot T\cdot\textnormal{Size}(\mathsf{MeasExpt})\cdot\frac{1}{\varepsilon}\log\frac{1}{\delta}).

Theorem 2.1

The novy bit commitment scheme instantiated with a classical one-way permutation family is classical computational binding.

Let \pi be a (classical) one-way permutation family, then the novy bit commitment scheme, instantiated with \pi, is classical computational binding.

Theorem 2.2

Quoted word for word from the full text on arXiv.

The paper

Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation

Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, Louis-Charles Thibodeau

arXiv, Oct 23, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.33185

arXiv:2610.33185v1 in quant-ph, also cs.CR

AbstractPDFHTML

Cite as BibTeX
@misc{dupuis2026postquantum,
  title = {Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation},
  author = {Dupuis, Fr'ed'eric and Ligez, R'emi and Medhioub, Khaireddine and Salvail, Louis and Thibodeau, Louis-Charles},
  year = {2026},
  eprint = {2610.33185},
  archivePrefix = {arXiv},
  primaryClass = {quant-ph},
  doi = {10.48550/arxiv.2610.33185},
  url = {https://arxiv.org/abs/2610.33185}
}

Related