You are looking at a specific version 20201117:140710 of this paper. See the latest version.

Paper 2020/1403

A q-SDH-based Graph Signature Scheme on Full-Domain Messages with Efficient Protocols

Syh-Yuan Tan and Ioannis Sfyrakis and Thomas Gross

Abstract

A graph signature scheme is a digital signature scheme that allows a recipient to obtain a signature on a graph and subsequently prove properties thereof in zero-knowledge proofs of knowledge. While known to be expressive enough to encode statements from NP languages, one main use of graph signatures is in topology certification and confidentiality-preserving security assurance. In this paper, we present an efficient and provably secure graph signature scheme in the standard model with tight reduction. Based on the MoniPoly attribute-based credential system, this new graph signature scheme offers zero-knowledge proofs of possession of the signature itself as well as confidentiality-preserving show proofs on logical statements such as the existence of vertices, graph connectivity or isolation.

Note: This work was supported by the ERC Starting Grant "Confidentiality-Preserving Security Assurance," CASCAde (GA no 716980). This updated version contains a note on application scenarios and a performance benchmark on the Java implementation of the graph signature scheme.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
digital signaturesgraph signature scheme
Contact author(s)
syh-yuan tan @ newcastle ac uk,ioannis sfyrakis @ newcastle ac uk,thomas gross @ newcastle ac uk
History
2020-11-17: revised
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1403
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.