A graph signature scheme is a digital signature scheme, which signs graph datastructures as its messages.

A general graph signature scheme fulfills the following properties:

• a graph data structure can be signed and encoded in the digitial signature,
• the graph is represented in a well-formed way such that the structure of the graph is retained in the mathematical structure of the signature,
• a prover in possession of a graph signature is able to prove to verifiers a wide range of statements on the graph in zero-knowledge proofs of knowledge. These statements do not need to be known at signing time.

There different ways of achieving a graph signature scheme, however they commonly follow the commit-and-sign paradigm. That means that the graph data structure is first encoded in a suitable (set) commitment scheme. Then the resulting commitment is signed with a digital signature scheme. This approach has been already used in early anonymous credential schemes, for instance the Camenisch-Lysyanskaya signature scheme with was the foundation of IBM's Identity Mixer credential scheme.

Existing Schemes

SRSA Graph Signature Scheme

This first general graph signature scheme was proposed by Groß in 2015. The scheme uses the following way to encode graphs:

• Nodes are represented by unique prime numbers, so called vertex identifiers.
• Connections between nodes, edges in graph terminology, are represented as product of vertex identifiers.
• Labels are represented by unique prime numbers of their own, called label representatives. Possibly multiple such label representatives can be included in the products of vertex and edge representations.

The scheme enables the representation of a wide range of graphs from a finite alphabet. It is based on the SRSA Camenisch-Lysyanskaya signature scheme and a method by Camenisch and Groß to efficiently prime-encode finite-set attributes in anonymous credential schemes. It is expressive enough to encode and prove statements from arbitrary NP languages. The scheme carries a number of limitations though, first and foremost that all prime numbers of the alphabet needed to be certified in advance.

q-SDH Graph Signature Scheme

A new proposal for a graph signature scheme was established in elliptic curves cryptography by Tan and Groß. This q-SDH based graph signature scheme broke new ground in enabling arbitrary bitstrings/group elements to be used as vertices and labels. It thereby expands the expressiveness of the graph signatures, while overcoming the main restriction of the SRSA-based scheme. This realization is based on the q-SDH MoniPoly attribute-based credential scheme.

While maintaining the same expressiveness as the SRSA graph signature scheme in terms of proof types supported, this scheme is more efficient at same security levels than the original scheme, as long as the number of labels per vertex or edge is reasonably low.

Other Variants

There have been specialized proposals of graph signature schemes. For instance, Nakanishi et al. have proposed an accumulator-based graph signature scheme tailored to prove connectivity efficiently. At the same time, it does not reach the general expressiveness of graph signature schemes mentioned above on arbitrary graph statements.

Implementation

The SRSA graph signature scheme has been implemented in a dedicated cryptographic library called GSL. The library was first developed in the EU Horizon 2020 project PRISMACLOUD and then extended in the ERC grant Confidentiality-Preserving Security Assurance (CASCAde). 

In PRISMACLOUD the graph signature scheme has been used for an infrastructure auditing service and a topology certification tool, a concept first proposed by Groß in 2014. It was also used to create a showcase that proved separation by geo-location for virtualized infrastructures. The cryptographic specification of the cryptographic library GSL is documented in PRISMACLOUD Deliverable D5.7.

The design of the graph signature library is further explained in an overview paper by Newcastle's CASCAde team.