Distributed Quantum Proofs for Replicated Data

• Item type: SIG Technical Reports(1)
• 公開日: 2020-10-09
• タイトル: Distributed Quantum Proofs for Replicated Data
• タイトル / 言語: en
• タイトル: Distributed Quantum Proofs for Replicated Data
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: IRIF, CNRS and Université de Paris
• 著者所属: Graduate School of Mathematics, Nagoya University
• 著者所属: Graduate School of Informatics, Nagoya University
• 著者所属: Faculty of Computer Science, Universität Wien
• 著者所属(英): en
• 著者所属(英): IRIF, CNRS and Université de Paris
• 著者所属(英): en
• 著者所属(英): Graduate School of Mathematics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Faculty of Computer Science, Universität Wien
• 著者名: Pierre, Fraigniaud; François, Le Gall; Harumichi, Nishimura; Ami, Paz
• 著者名(英): Pierre, Fraigniaud; François, Le Gall; Harumichi, Nishimura; Ami, Paz
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2020-QS-1, 号 7, p. 1-8, 発行日 2020-10-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会