The search functionality is under construction.
The search functionality is under construction.

Efficient Zero-Knowledge Proofs of Graph Signature for Connectivity and Isolation Using Bilinear-Map Accumulator

Toru NAKANISHI, Hiromi YOSHINO, Tomoki MURAKAMI, Guru-Vamsi POLICHARLA

  • Full Text Views

    0

  • Cite this

Summary :

To prove the graph relations such as the connectivity and isolation for a certified graph, a system of a graph signature and proofs has been proposed. In this system, an issuer generates a signature certifying the topology of an undirected graph, and issues the signature to a prover. The prover can prove the knowledge of the signature and the graph in the zero-knowledge, i.e., the signature and the signed graph are hidden. In addition, the prover can prove relations on the certified graph such as the connectivity and isolation between two vertexes. In the previous system, using integer commitments on RSA modulus, the graph relations are proved. However, the RSA modulus needs a longer size for each element. Furthermore, the proof size and verification cost depend on the total numbers of vertexes and edges. In this paper, we propose a graph signature and proof system, where these are computed on bilinear groups without the RSA modulus. Moreover, using a bilinear map accumulator, the prover can prove the connectivity and isolation on a graph, where the proof size and verification cost become independent from the total numbers of vertexes and edges.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.3 pp.389-403
Publication Date
2022/03/01
Publicized
2021/09/08
Online ISSN
1745-1337
DOI
10.1587/transfun.2021TAP0003
Type of Manuscript
Special Section PAPER (Special Section on Information Theory and Its Applications)
Category
Cryptography and Information Security

Authors

Toru NAKANISHI
  Hiroshima University
Hiromi YOSHINO
  Hiroshima University
Tomoki MURAKAMI
  Hiroshima University
Guru-Vamsi POLICHARLA
  Indian Institute of Technology

Keyword