Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92) established that any probabilistically checkable proof for NP can be transformed into a succinct argument system for NP using only collision-resistant hash functions. In the quantum setting, recent works have established the feasibility of (classically-verifiable) succinct arguments for QMA, capturing statements that require quantum proofs. However, known constructions all rely on the highly structured assumption of learning with errors (LWE), which stands in stark contrast with the unstructured assumptions that suffice for NP. In this work, we develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA. We assume the existence of (i) an oblivious state preparation (OSP) protocol, which in turn can be constructed from plain trapdoor claw-free functions, and (ii) collapsing hash functions, the quantum analogue of collision-resistance. In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE. Our construction proceeds in two steps. First, we design a round-efficient classically-verifiable argument system for QMA based only on the assumption of OSP. Second, we introduce a generalized communication compression compiler, which, assuming collapsing hash function, transforms any T-round interactive protocol with a classical verifier into one in which the communication size is bounded by \(T \cdot {{\,\textrm{poly}\,}}(\lambda )\) for some fixed \({{\,\textrm{poly}\,}}\) independent of the original size of each message. Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25), and may be of independent interest.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Modular Approach to Succinct Arguments for QMA

  • James Bartusek,
  • Jiahui Liu,
  • Giulio Malavolta

摘要

Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92) established that any probabilistically checkable proof for NP can be transformed into a succinct argument system for NP using only collision-resistant hash functions. In the quantum setting, recent works have established the feasibility of (classically-verifiable) succinct arguments for QMA, capturing statements that require quantum proofs. However, known constructions all rely on the highly structured assumption of learning with errors (LWE), which stands in stark contrast with the unstructured assumptions that suffice for NP. In this work, we develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA. We assume the existence of (i) an oblivious state preparation (OSP) protocol, which in turn can be constructed from plain trapdoor claw-free functions, and (ii) collapsing hash functions, the quantum analogue of collision-resistance. In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE. Our construction proceeds in two steps. First, we design a round-efficient classically-verifiable argument system for QMA based only on the assumption of OSP. Second, we introduce a generalized communication compression compiler, which, assuming collapsing hash function, transforms any T-round interactive protocol with a classical verifier into one in which the communication size is bounded by \(T \cdot {{\,\textrm{poly}\,}}(\lambda )\) for some fixed \({{\,\textrm{poly}\,}}\) independent of the original size of each message. Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25), and may be of independent interest.