{"id":1048,"date":"2015-09-20T07:58:38","date_gmt":"2015-09-20T07:58:38","guid":{"rendered":"https:\/\/prismacloud.eu\/?p=1048"},"modified":"2017-05-22T13:48:40","modified_gmt":"2017-05-22T13:48:40","slug":"signatures-and-efficient-proofs-on-committed-graphs-and-np-statements","status":"publish","type":"post","link":"https:\/\/prismacloud.eu\/signatures-and-efficient-proofs-on-committed-graphs-and-np-statements\/","title":{"rendered":"Signatures and Efficient Proofs on Committed Graphs and NP-Statements"},"content":{"rendered":"<p><strong>Author<\/strong><\/p>\n<p>Thomas Gross (School of Computing Science, Newcastle University, UK)<\/p>\n<p><strong>Abstract<\/strong><\/p>\n<p style=\"text-align: justify;\">Digital signature schemes are a foundational building block enabling\u00a0integrity and non-repudiation. We propose a graph signature scheme and corresponding\u00a0proofs that allow a prover (1) to obtain a signature on a committed graph\u00a0and (2) to subsequently prove to a verifier knowledge of such a graph signature.\u00a0The graph signature scheme and proofs are a building block for certification systems\u00a0that need to establish graph properties in zero-knowledge, as encountered in\u00a0cloud security assurance or provenance. We extend the Camenisch-Lysyanskaya\u00a0(CL) signature scheme to graphs and enable efficient zero-knowledge proofs of\u00a0knowledge on graph signatures, notably supporting complex statements on graph\u00a0elements. Our method is based on honest-verifier proofs and the strong RSA assumption.\u00a0In addition, we explore the capabilities of graph signatures by establishing\u00a0a proof system on graph 3-colorability (G3C). As G3C is NP-complete,\u00a0we conclude that there exist\u00a0Camenisch-Lysyanskaya proof systems for statements\u00a0of NP languages.<\/p>\n<p><strong>Venue<\/strong><\/p>\n<p>10th International Conference on\u00a0Financial Cryptography and Data Security 2015\u00a0(<a href=\"http:\/\/fc15.ifca.ai\/\">http:\/\/fc15.ifca.ai\/<\/a>)<\/p>\n<p><strong>Place and Date<\/strong><\/p>\n<p>Puerto Rico, January 26th-30th 2015<\/p>\n<p><strong>Publication Reference<\/strong><\/p>\n<p>Thomas Gross. \"Signatures and Efficient Proofs on Committed Graphs and NP-Statements\", Financial Cryptography and Data Security 2015 - 19th International Conference, Puerto Rico, January 26-30, 2015.<\/p>\n<p>[<a href=\"http:\/\/fc15.ifca.ai\/preproceedings\/paper_98.pdf\">Download<\/a>]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Author Thomas Gross (School of Computing Science, Newcastle University, UK) Abstract Digital signature schemes are a foundational building block enabling\u00a0integrity and non-repudiation. We propose a graph signature scheme and corresponding\u00a0proofs that allow a prover (1) to obtain a signature on a committed graph\u00a0and (2) to subsequently prove to a verifier knowledge of such a graph [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":746,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,8],"tags":[],"_links":{"self":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/1048"}],"collection":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/comments?post=1048"}],"version-history":[{"count":2,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/1048\/revisions"}],"predecessor-version":[{"id":1931,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/1048\/revisions\/1931"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/media\/746"}],"wp:attachment":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/media?parent=1048"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/categories?post=1048"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/tags?post=1048"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}