IET Information Security

Witness indistinguishability and witness hiding against quantum attacks

Huiqin Xie, Li Yang

Published Apr 30, 2019• 2 citations

Abstract

The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post‐quantum world. To this end, the authors study the witness indistinguishability (WI) and witness hiding (WH) of proof systems against quantum adversaries. They give formal definitions of quantum WI (QWI) and quantum WH (QWH), present proof systems satisfying these definitions, and specify a condition under which QWI implies QWH. Regarding the non‐interactive proof systems, they prove that, even if a common reference string is used to generate polynomially many non‐interactive proofs, the QWI is still preserved, while quantum zero‐knowledge has no such beneficial property. To show the strength of QWI, they present two applications of them. First, they prove that the construction proposed by Feige et al . that transforms any non‐interactive bounded zero‐knowledge proof system to a general one is also feasible against quantum adversaries. Second, they construct a quantum‐secure signature scheme in the CRS model, which is existentially unforgeable against quantum adversaries and remains secure even if a common random string is used to sign polynomially many messages.

DOI: 10.1049/iet-ifs.2018.5460

Related papers

Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks

Ivan Damgård, Serge Fehr, Louis Salvail

The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting. We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK. As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks. Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.

BRICS Report SeriesMay 11, 200410 citations

Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions

Mohammed Barhoush, Tomoyuki Morimae, Ramis Movassagh

Quantum indistinguishability obfuscation (qIO) aims to make a quantum circuit unintelligible while preserving its functionality. It serves as a foundational primitive for advanced applications, such as witness encryption (WE) for QMA, non-interactive zero-knowledge arguments for QMA, and attribute-based encryption for BQP. Despite its importance, constructing qIO from standard assumptions remains a major open problem. In this work, we prove that the security of WE for QMA cannot be based on any falsifiable cryptographic assumption via a restricted class of quantum black-box reductions. Because qIO for null quantum circuits implies WE for QMA, this also separates null-qIO from falsifiable assumptions. Since almost all standard cryptographic assumptions are falsifiable, our result presents a barrier to basing qIO on standard cryptographic assumptions. The reductions we rule out are restricted: the reduction must query the adversary classically, non-adaptively, at the same security parameter, and only on honestly generated ciphertexts. Moreover, our impossibility applies only to WE with classical ciphertexts, and therefore does not rule out qIO with obfuscators whose output is a quantum state. Ruling out more general reductions, as well as more general forms of WE and qIO, remains open. Our impossibility relies on the existence of a QMA-QCIP[2] gap problem, an average-case assumption postulating a QMA language that cannot be verified with two messages of classical communication.

quant-pharXiv:2608.25195Aug 27, 20260 citations

Zero-knowledge against quantum attacks

John Watrous

This paper proves that several interactive proof systems are zero-knowledge against quantum attacks. This includes a few well-known classical zero-knowledge proof systems as well as quantum interactive proof systems for the complexity class HVQSZK, which comprises all problems having "honest verifier" quantum statistical zero-knowledge proofs. It is also proved that zero-knowledge proofs for every language in NP exist that are secure against quantum attacks, assuming the existence of quantum computationally concealing commitment schemes. Previously no non-trivial proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest-verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.

arXiv:quant-ph/0511020Nov 3, 20052 citations

Quantum Statistical Witness Indistinguishability

Shafik Nassar, Ramachandran, Ronak

Statistical witness indistinguishability is a relaxation of statistical zero-knowledge which guarantees that the transcript of an interactive proof reveals no information about which valid witness the prover used to generate it. In this paper we define and initiate the study of QSWI, the class of problems with quantum statistically witness indistinguishable proofs. Using inherently quantum techniques from Kobayashi (TCC 2008), we prove that any problem with an honest-verifier quantum statistically witness indistinguishable proof has a 3-message public-coin malicious-verifier quantum statistically witness indistinguishable proof. There is no known analogue of this result for classical statistical witness indistinguishability. As a corollary, our result implies SWI is contained in QSWI. Additionally, we extend the work of Bitansky et al. (STOC 2023) to show that quantum batch proofs imply quantum statistically witness indistinguishable proofs with inverse-polynomial witness indistinguishability error.

arXiv:2509.01945Sep 2, 20250 citations

Constant-Round Concurrent NMWI and its relation to NMZK

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).

Jan 1, 20067 citations

A Unified Framework For Quantum Unforgeability

Mina Doosti, Mahshid Delavar, Elham Kashefi +1 more

In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically, for classical message authentication codes and classical digital signatures schemes. We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions allowing us for the first time to present a complete quantum cryptanalysis framework for unforgeability. In particular, we prove how our definitions subsume previous ones while considering more fine-grained adversarial models, capturing the full spectrum of superposition attacks. The subtlety here resides in the characterisation of a forgery. We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only orthogonal to previously queried messages are considered to be forgeries. In particular, we present a non-trivial attack if any overlap between the forged message and previously queried ones is allowed. We further show that deterministic constructions can only achieve the weaker notion of unforgeability, that is selective unforgeability, against such restricted adversaries, but that selective unforgeability breaks if general quantum adversaries (capable of general superposition attacks) are considered. On the other hand, we show that PRF is sufficient for constructing a selective unforgeable classical primitive against full quantum adversaries. Moreover, we show similar positive results relying on Pseudorandom Unitaries (PRU) for quantum primitives. These results demonstrate the generality of our framework that could be applicable to other primitives beyond the cases analysed in this paper.

arXiv:2103.13994Mar 25, 20215 citations