The search functionality is under construction.

The search functionality is under construction.

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

Toru NAKANISHI

Hiroshima University

Hiromi YOSHINO

Hiroshima University

Tomoki MURAKAMI

Hiroshima University

Guru-Vamsi POLICHARLA

Indian Institute of Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toru NAKANISHI, Hiromi YOSHINO, Tomoki MURAKAMI, Guru-Vamsi POLICHARLA, "Efficient Zero-Knowledge Proofs of Graph Signature for Connectivity and Isolation Using Bilinear-Map Accumulator" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 3, pp. 389-403, March 2022, doi: 10.1587/transfun.2021TAP0003.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021TAP0003/_p

Copy

@ARTICLE{e105-a_3_389,

author={Toru NAKANISHI, Hiromi YOSHINO, Tomoki MURAKAMI, Guru-Vamsi POLICHARLA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Efficient Zero-Knowledge Proofs of Graph Signature for Connectivity and Isolation Using Bilinear-Map Accumulator},

year={2022},

volume={E105-A},

number={3},

pages={389-403},

abstract={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.},

keywords={},

doi={10.1587/transfun.2021TAP0003},

ISSN={1745-1337},

month={March},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 389

EP - 403

AU - Toru NAKANISHI

AU - Hiromi YOSHINO

AU - Tomoki MURAKAMI

AU - Guru-Vamsi POLICHARLA

PY - 2022

DO - 10.1587/transfun.2021TAP0003

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E105-A

IS - 3

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - March 2022

AB - 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.

ER -