Paper 2014/255

Certification and Efficient Proofs of Committed Topology Graphs

Thomas Gross


Digital signature schemes are a foundational cryptographic building block in certification and the projection of trust. Based on a signature scheme on committed graphs, we propose a toolkit of certification and proof methods to sign committed topology graphs and to prove properties of their certificates in zero-knowledge. This toolkit allows an issuer, such as an auditor, to sign the topology representation of an infrastructure. The prover, such as an infrastructure provider, can then convince a verifier of topology properties, such as partitions, connectivity or isolation, without disclosing the structure of the topology itself. By that, we can achieve the certification of the structure of critical systems, such as infrastructure clouds or outsourced systems, while still maintaining confidentiality. We offer zero-knowledge proofs of knowledge for a general specification language of security goals for virtualized infrastructures, such that high-level security goalscan be proven over the topology certificate. Our method builds upon the Camenisch-Lysyanskaya signature scheme, is based on honest-verifier proofs and the strong RSA assumption.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Graph signatures and proofs
Contact author(s)
thomas gross @ ncl ac uk
2014-04-20: received
Short URL
Creative Commons Attribution


      author = {Thomas Gross},
      title = {Certification and Efficient Proofs of Committed Topology Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/255},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.