The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Para provar as relações de grafos, como conectividade e isolamento para um grafo certificado, foi proposto um sistema de assinatura de grafos e provas. Neste sistema, um emissor gera uma assinatura certificando a topologia de um grafo não direcionado e emite a assinatura para um provador. O provador pode provar o conhecimento da assinatura e do grafo no conhecimento zero, ou seja, a assinatura e o grafo assinado estão ocultos. Além disso, o provador pode provar relações no grafo certificado, como a conectividade e o isolamento entre dois vértices. No sistema anterior, utilizando compromissos inteiros no módulo RSA, as relações gráficas são provadas. No entanto, o módulo RSA necessita de um tamanho maior para cada elemento. Além disso, o tamanho da prova e o custo de verificação dependem do número total de vértices e arestas. Neste artigo, propomos um sistema de assinatura e prova de grafos, onde estes são calculados em grupos bilineares sem o módulo RSA. Além disso, usando um acumulador de mapas bilinear, o provador pode provar a conectividade e o isolamento em um grafo, onde o tamanho da prova e o custo de verificação tornam-se independentes do número total de vértices e arestas.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -