Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 54 min ago
PreprintarXiv licencearXiv

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
Open at sourcePDFDOICite

Abstract

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

Related

  1. Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
    Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Succinct Arguments for QMA in the Quantum Random Oracle Model
    Alessandro Chiesa, Zihan Hu
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. The equivalence of quantum deletion and insertion errors on permutation-invariant codes
    Lewis Bulled, Yingkai Ouyang
    npj Quantum InformationPeer-reviewedCC BY 4.0Full textQuantum physics & quantum informationCrossref
  4. Quantum Stochastic Walks on the Permutation Group
    Feng He, Arthur Hutsalyuk, Giuseppe Mussardo +1
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationStatistical & nonlinear physicsarXiv
  5. Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
    Dantong Li, Shifan Xu, Yongshan Ding
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{dupuis2026postquantum,
  title = {{Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation}},
  author = {Frédéric Dupuis and Rémi Ligez and Khaireddine Medhioub and Louis Salvail and Louis-Charles Thibodeau},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.33185},
  eprint = {2610.33185},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33185},
}
RIS
TY  - UNPB
TI  - Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
AU  - Frédéric Dupuis
AU  - Rémi Ligez
AU  - Khaireddine Medhioub
AU  - Louis Salvail
AU  - Louis-Charles Thibodeau
PY  - 2026
DA  - 2026/10/23
PB  - arXiv
DO  - 10.48550/arxiv.2610.33185
UR  - https://arxiv.org/abs/2610.33185
AB  - 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. 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. 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.
ER  -