ペアリングを用いたラベル付きグラフにおける接続性のゼロ知識証明

ネットワークで接続されたシステムは，グラフとして表現することができる. システムを利用するテナントは，自らのシステムが正しく接続されていること (接続性)，自らのシステムが他のテナントのシステムから正しく分離されていること (分離性) について，システムの提供者であるプロバイダに確認する必要がある．プロバイダは複数のテナントのシステムを管理しているため，ネットワークトポロジーを開示せずに正しい情報を証明する手法が求められている．その解決策として，ペアリングアキュームレータを用いたグラフ情報のゼロ知識証明が提案されており，検証時間や証明データサイズがグラフの点数，辺数に依存しないという特徴がある．しかし，この方式はラベルを含めた証明が行われていないため，ネットワークの帯域やコストなどを考慮した接続性の証明ができない．本研究ではこのペアリングベースの従来方式を拡張し，各辺がラベルを持つグラフにおける接続性のゼロ知識証明を提案する．そして提案方式を PC 上で実装し，処理時間を測定することによって評価を行う．

A networked system can be represented as a graph. Tenants who use the system need to check with the provider of the system that their systems are properly connected (connectivity) and that their systems are properly separated from the systems of other tenants (isolation). Since providers manage systems for multiple tenants, a method to prove the connectivity and isolation without disclosing the network topology is required. As a solution, a zero-knowledge proof of graph information using a pairing accumulator has been proposed, where the verification time and the size of the proof data do not depend on the number of graph vertexes and edges. However, since this scheme does not address labels in the graph, the provider cannot prove the connectivity w.r.t the network bandwidth and cost. In this study, we extend the previous pairing-based scheme and propose a zero-knowledge proof of the connectivity for graphs where each edge has labels. We implement the scheme on a PC and evaluate it by measuring the processing time.