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

arXiv:quant-ph/0511266 · Theoretical Computer Science

Statistical Zero Knowledge and quantum one-way functions

Elham Kashefi, Iordanis Kerenidis

Published Mar 13, 2007• 24 citations
arXivHTMLPDF
DOI
10.1016/j.tcs.2007.03.013

Related papers

Statistical Concurrent Non-Malleable Zero-Knowledge from One-Way Functions

Susumu Kiyoshima

Journal of Cryptology•Apr 22, 2020•4 citations

Statistical Concurrent Non-malleable Zero-Knowledge from One-Way Functions

Susumu Kiyoshima

Lecture notes in computer science•Jan 1, 2015•2 citations

Non-interactive Quantum Perfect and Statistical Zero-Knowledge

Hirotada Kobayashi

Lecture notes in computer science•Jan 1, 2003•46 citations

Simplified design for concurrent statistical zero-knowledge arguments

Puwen Wei, Guoyan Zhang, Lijiang Zhang +1 more

This paper shows that the protocol presented by Goyal et al. can be further simplified for a one-way function, with the simplified protocol being more practical for the decisional Diffie-Hellman assumption. Goyal et al. provided a general transformation from any honest verifier statistical zero-knowledge argument to a concurrent statistical zero-knowledge argument. Their transformation relies only on the existence of one-way functions. For the simplified transformation, the witness indistinguishable proof of knowledge protocols in “parallel” not only plays the role of preamble but also removes some computational zero-knowledge proofs, which Goyal et al. used to prove the existence of the valid openings to the commitments. Therefore, although some computational zero-knowledge proofs are replaced with a weaker notion, the witness indistinguishable protocol, the proof of soundness can still go through.

Tsinghua Science & Technology•Apr 1, 2009•0 citations

A Post-Quantum Interactive Hashing Theorem

Céline Chevalier, Laurent Holin, Quoc-Huy Vu

Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP and statistically hiding commitments from arbitrary one-way functions [NOV06,HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations.

arXiv:2611.06124•Nov 4, 2026•0 citations

Quantum protocols for zero-knowledge systems

José Cláudio do Nascimento, Rubens Viana Ramos

Quantum Information Processing•Aug 10, 2009•6 citations
This paper shows that the protocol presented by Goyal et al. can be further simplified for a one-way function, with the simplified protocol being more practical for the decisional Diffie-Hellman assumption. Goyal et al. provided a general transformation from any honest verifier statistical zero-knowledge argument to a concurrent statistical zero-knowledge argument. Their transformation relies only on the existence of one-way functions. For the simplified transformation, the witness indistinguishable proof of knowledge protocols in “parallel” not only plays the role of preamble but also removes some computational zero-knowledge proofs, which Goyal et al. used to prove the existence of the valid openings to the commitments. Therefore, although some computational zero-knowledge proofs are replaced with a weaker notion, the witness indistinguishable protocol, the proof of soundness can still go through.
Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP and statistically hiding commitments from arbitrary one-way functions [NOV06,HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations.