New elliptic-curve based graph signature scheme released

We have released a new graph signature scheme to the IACR Cryptology ePrint Archive. The scheme allows for the signing of arbitrary labeled graphs and to prove properties over the signed graph structure without disclosing confidential information. This is an interesting tool for topology certification and security assurance: For instance, an infrastructure provider could convince its tenants that certain security properties are fulfilled without giving the game away by leaking sensitive data about the infrastructure's blueprint.

The novel scheme is distinct from our earlier work on SRSA-based graph signatures, because it allows graphs over arbitrary bit-strings, get by with much smaller public key sizes, and offers comprehensive security proofs over the overall system. The new scheme comes with an efficient zero-knowledge proof protocol suite that allows provers to ascertain graph properties to others. In terms of performance it compares favorably to our previous scheme. Our 16k lines-of-code implementation shows that most signing and proof operations are quite fast, even on larger graphs.

The new scheme is based on our earlier work on MoniPoly commitments and attribute-based credential systems, also availabe from our cryptography outputs. The preliminary version of our new graph signature scheme is available from our outputs in cryptography.

Last modified: Thu, 26 Nov 2020 07:57:12 GMT