Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Zero-Knowledge Proofs Through Concrete and Generic Construction

Kyosuke Hatsugai

Published Jun 30, 2026• 0 citations
Publisher

Abstract

in the Fields of Mathematics and Cryptography" and provided the author with the opportunity to give a
DOI
10.18952/0002001258

Related papers

Physical Zero-Knowledge Proofs of Physical Properties

Ben Fisch, Daniel Freund, Moni Naor

Lecture notes in computer science•Jan 1, 2014•27 citations

More Efficient Lattice-Based Zero-Knowledge Proofs with Straight-Line Extractability

Ngoc Khanh Nguyen, George O'Rourke

In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 6, 2025•3 citations

Post-quantum Cryptography and Quantum Proofs

Zero-knowledge proofs are just the basic concept in proof technology. Many other sophisticated formulations of proofs and related quantum-secure technology are proposed. Earlier forms of zero-knowledge proof technology are not quantum-resistant. Proofs based on generic hash functions as opposed to classical PKI cryptography are thought to be post-quantum secure because the cryptography can be upgraded, whereas classical PKI cryptography is known not to be quantum-secure. STARKs are a new form of zero-knowledge proofs for blockchains with a sophisticated architecture based on error correction codes, random queries, and inconsistency checks. The two main approaches to post-quantum cryptography are lattice-based cryptography and hash function-based cryptography. Lattice-based cryptography is currently the main method being promulgated in next-generation US NIST algorithm development. Keeping public digital infrastructure safe is a key concern. Post-quantum cryptography suggests various approaches to prepare cryptographic infrastructure for a potential future of quantum computing.

Between science and economics•Apr 1, 2020•0 citations

From Laconic Zero-Knowledge to Public-Key Cryptography: Extended Abstract

Itay Berman, Akshay Degwekar, Ron D. Rothblum +1 more

Lecture notes in computer science•Jan 1, 2018•15 citations

Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General

Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plançon

Lecture notes in computer science•Jan 1, 2022•155 citations

Compressed Zero-Knowledge Proofs for Lattice-Based Accumulator

Shumin Si, Xiuhan Lin, Puwen Wei

Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$, where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.

The Computer Journal•Mar 10, 2023•4 citations
In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.
Zero-knowledge proofs are just the basic concept in proof technology. Many other sophisticated formulations of proofs and related quantum-secure technology are proposed. Earlier forms of zero-knowledge proof technology are not quantum-resistant. Proofs based on generic hash functions as opposed to classical PKI cryptography are thought to be post-quantum secure because the cryptography can be upgraded, whereas classical PKI cryptography is known not to be quantum-secure. STARKs are a new form of zero-knowledge proofs for blockchains with a sophisticated architecture based on error correction codes, random queries, and inconsistency checks. The two main approaches to post-quantum cryptography are lattice-based cryptography and hash function-based cryptography. Lattice-based cryptography is currently the main method being promulgated in next-generation US NIST algorithm development. Keeping public digital infrastructure safe is a key concern. Post-quantum cryptography suggests various approaches to prepare cryptographic infrastructure for a potential future of quantum computing.
Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with 2322^{32}232 members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in l⋅nsl\cdot n_{s}l⋅ns​, where lll and nsn_{s}ns​ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when l=32l=32l=32. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.