Toggle Main Menu Toggle Search

Open Access padlockePrints

Signatures and Efficient Proofs on Committed Graphs and NP-Statements

Lookup NU author(s): Dr Thomas Gross

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.


Abstract

Digital signature schemes are a foundational building block enabling integrity and non-repudiation. We propose a graph signature scheme and corresponding proofs that allow a prover (1) to obtain a signature on a committed graph and (2) to subsequently prove to a verifier knowledge of such a graph signature. The graph signature scheme and proofs are a building block for certification systems that need to establish graph properties in zero-knowledge, as encountered in cloud security assurance or provenance. We extend the Camenisch-Lysyanskaya (CL) signature scheme to graphs and enable efficient zero-knowledge proofs of knowledge on graph signatures, notably supporting complex statements on graph elements. Our method is based on honest-verifier proofs and the strong RSA assumption. In addition, we explore the capabilities of graph signatures by establishing a proof system on graph 3-colorability (G3C). As G3C is NP-complete, we conclude that there exist Camenisch-Lysyanskaya proof systems for statements of NP languages.


Publication metadata

Author(s): Gross T

Publication type: Conference Proceedings (inc. Abstract)

Publication status: Published

Conference Name: 19th International Conference on Financial Cryptography and Data Security 2015

Year of Conference: 2015

Pages: 293-314

Print publication date: 25/07/2015

Online publication date: 16/07/2015

Acceptance date: 12/12/2014

ISSN: 0302-9743

Publisher: Springer

URL: https://doi.org/10.1007/978-3-662-47854-7_18

DOI: 10.1007/978-3-662-47854-7_18

Notes: http://fc15.ifca.ai/preproceedings/paper_98.pdf

Library holdings: Search Newcastle University Library for this item

Series Title: Lecture Notes in Computer Science

ISBN: 9783662478530


Actions

Link to this publication


Share