Signatures and Efficient Proofs on Committed Graphs and NP-Statements

  1. Lookup NU author(s)
  2. Dr Thomas Gross
Author(s)Gross T
Publication type Conference Proceedings (inc. Abstract)
Conference Name19th International Conference on Financial Cryptography and Data Security 2015
Conference LocationSan Juan, Puerto Rico
Year of Conference2015
Source Publication Date
Full text for this publication is not currently held within this repository. Alternative links are provided below where available.
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.
PublisherInternational Financial Cryptography Association