On the concurrent composition of quantum zero-knowledge (Q2120082)

Quantum zero-knowledge is zero-knowledge where the verifier is modeled as a quantum polynomial-time algorithm. Ever since the threat of quantum computer has become real, researchers have worked on quantum zero-knowledge, with an almost exclusive focus on standalone protocols, i.e. protocols that work in isolation. As noted by many authors, the mentioned scenario is not the most realistic. A more realistic one is indeed obtained assuming that the party can also play in other protocol executions; this can be modeled assuming that there is a single prover simultaneously interacting with multiple verifiers controlled by a single malicious quantum polynomial-time adversary. However, security in this relevant scenario, called concurrent composition, has remained unaddressed in the quantum setting. This paper is aimed at closing this gap. In particular, the authors' focus is on the bounded concurrent setting, where the prover can interact with a predetermined number of verifiers, the bound being fixed at the time of protocol specification. In this regard, the authors show a quantum zero-knowledge proof system for each language in NP, which satisfy soundness. Moreover, they show that there exists a quantum zero-knowledge proof system satisfying the quantum proof of knowledge property, i.e. the classical proof of knowledge property adapted to the quantum case (cf. Definition 8). The proposed construction is inspired to the bounded concurrent (classical) zero-knowledge construction of \textit{R. Pass} et al. [Lect. Notes Comput. Sci. 5677, 160--176 (2009; Zbl 1252.94092)]. The quantum zero-knowledge property is proved by means of the use of a new classical simulation strategy, that the authors called block rewinding, combined with Watrous rewinding. The quantum proof of knowledge property is instead obtained by means of a novel extraction mechanism that uses oblivious transfer to extract a bit from a quantum adversary. Similar results are obtained for the quantum version of MA protocols in the bounded concurrency setting. For the entire collection see [Zbl 1483.94004].