Contributed Talks 5a: Theory in multiparty interactions (Chair: Christian Majenz)
contributed
Fri, 27 Aug
, 11:00  11:30

A BlackBox Approach to PostQuantum ZeroKnowledge in Constant RoundsNaiHui Chia (University of Maryland); KaiMin Chung (Academia Sinica); Takashi Yamakawa (NTT Secure Platform Laboratories)[abstract]Abstract: In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zeroknowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on nonblackbox simulation. In this paper, we resolve these issues at the cost of weakening the notion of zeroknowledge to what is called $\epsilon$zeroknowledge. Concretely, we construct the following protocols:  We construct a constant round interactive proof for NP that satisfies statistical soundness and blackbox $\epsilon$zeroknowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collisionresistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$zeroknowledge property against quantum adversaries requires novel ideas.  We construct a constant round interactive argument for NP that satisfies computational soundness and blackbox $\epsilon$zeroknowledge against quantum attacks only assuming the existence of postquantum oneway functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.Presenter live session: Takashi YamakawaOn the Impossibility of PostQuantum BlackBox ZeroKnowledge in Constant RoundsNaiHui Chia (University of Maryland); KaiMin Chung (Academia Sinica); Qipeng Liu (Princeton University); Takashi Yamakawa (NTT Secure Platform Laboratories)[abstract]Abstract: We investigate the existence of constantround postquantum blackbox zeroknowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constantround postquantum blackbox zeroknowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constantround blackbox zeroknowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between postquantum and classical zeroknowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constantround postquantum zeroknowledge protocols for $\mathbf{NP}$ exist if and only if we use nonblackbox techniques or relax certain security requirements such as relaxing standard zeroknowledge to $\epsilon$zeroknowledge. Additionally, we also prove that threeround and publiccoin constantround postquantum blackbox $\epsilon$zeroknowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.Presenter live session: Takashi Yamakawa

Postquantum ResettablySound Zero KnowledgeNir Bitansky (Tel Aviv University); Michael Kellner (Tel Aviv University); Omri Shmueli (Tel Aviv University)[abstract]Abstract: We study postquantum zeroknowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (BarakGoldreichGoldwasserLindell, FOCS `01), providing a malicious efficient prover with oracle access to the verifier's nextmessagefunction, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier's function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding postquantum zero knowledge. We prove the following results: BlackBox Barriers: Quantum resetting exactly captures the power of blackbox zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with blackbox zero knowledge, except for languages in \BQP. Leveraging this, we prove that constantround publiccoin, or three message, protocols cannot be blackbox postquantum zeroknowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is significantly more challenging due to the essential difference between classical and quantum resetting. A ResettablySound NonBlackBox ZeroKnowledge Protocol: Under the (quantum) Learning with Errors assumption and quantum fullyhomomorphic encryption, we construct a postquantum resettablysound zero knowledge protocol for \NP. We rely on nonblackbox simulation techniques, thus overcoming the blackbox barrier for such protocols. From Resettable Soundness to The Impossibility of Quantum Obfuscation: Assuming oneway functions, we prove that any quantumlyresettablysound zeroknowledge protocol for \NP implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.Presenter live session: Michael Kellner

Positionbased cryptography: Singlequbit protocol secure against multiqubit attacksAndreas Bluhm (QMATH, University of Copenhagen); Matthias Christandl (QMATH, University of Copenhagen); Florian Speelman (QuSoft and University of Amsterdam)[abstract]Abstract: While it is known that unconditionally secure positionbased cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. In this work, we consider the security of the qubit routing protocol. The protocol has the advantage that an honest prover only has to manipulate a single qubit and a classical string of length 2n. We show that the protocol is secure if each of the attackers holds at most n/2  3 qubits. With this, we show for the first time that there exists a quantum position verification protocol where the ratio between the quantum resources an honest prover needs and the quantum resources the attackers need to break the protocol is unbounded. The verifiers need only increase the amount of classical resources to force the attackers to use more quantum resources. Finally, we show that the qubit routing protocol is robust with respect to noise, making it appealing for applications.Presenter live session: Andreas Bluhm