Abstract. A graph signature scheme is a digital signature scheme that allows a recipient to obtain a signature on a graph and subsequently prove properties thereof in zero-knowledge proofs of knowledge. While known to be expressive enough to encode statements from NP languages, one main use of graph signatures is in topology certification and confidentiality-preserving security assurance. In this paper, we present an efficient and provably secure graph signature scheme in the standard model with tight reduction. Based on the MoniPoly attribute-based credential system, this new graph signature scheme offers zero-knowledge proofs of possession of the signature itself as well as confidentiality-preserving show proofs on logical statements such as the existence of vertices, graph connectivity or isolation.
Published as Syh-Yuan Tan, Ioannis Sfyrakis and Thomas Groß. A q-SDH-based Graph Signature Scheme on Full-Domain Messages with Efficient Protocols. Cryptology ePrint Report 2020/1403, 2020.
Abstract. Modern attribute-based anonymous credential (ABC) systems benefit from special encodings that yield expressive and highly efficient show proofs on logical statements. The technique was first proposed by Camenisch and Groß, who constructed an SRSA-based ABC system with prime-encoded attributes that offers effcient AND, OR and NOT proofs. While other ABC frameworks have adopted constructions in the same vein, the Camenisch-Groß ABC has been the most expressive and asymptotically most efficient proof system to date, even if it was constrained by the requirement of a trusted message-space setup and an inherent restriction to finite-set attributes encoded as primes. In this paper, combining a new set commitment scheme and a SDH-based signature scheme, we present a provably secure ABC system that supports show proofs for complex statements. This construction is not only more expressive than existing approaches, it is also highly effcient under unrestricted attribute space due to its ECC protocols only requiring a constant number of bilinear pairings by the verifier; none by the prover. Furthermore, we introduce strong security models for impersonation and unlinkability under adaptive active and concurrent attacks to allow for the expressiveness of our ABC as well as for a systematic comparison to existing schemes. Given this foundation, we are the first to comprehensively formally prove the security of an ABC with expressive show proofs. Specifically, we prove the security against impersonation under the q-(co-)SDH assumption with a tight reduction.
Published as Syh-Yuan Tan and Thomas Groß. MoniPoly - An Expressive q-SDH-Based Anonymous Attribute-Based Credential System. Cryptology ePrint Report 2020/587, 2020. To appear in Proceedings of ASIACRYPT 2020, LNCS 12493, Springer Verlag 2020.
Abstract. Current cloud and network infrastructures do not employ privacy-preserving methods to protect their assets. Anonymous credential schemes are a cryptographic building block that enables the certification of data structures and prove properties over their representations without disclosing the innards of their data structures in zero-knowledge. The Graph Signature (GRS) scheme enables the certification and proof methods to sign infrastructure topologies represented as graph data structures and use zero-knowledge to prove properties over their certificates. As such, they represent a powerful privacy-preserving method that proves properties over a signed topology graph to another party without disclosing the blueprint of its topology. In this paper, we report our efforts in designing, implementing and benchmarking a Graph Signature Library (GSL). GSL is a cryptographic library realized in Java that implements the graph signature scheme.
Note. Ioannis Sfyrakis and Thomas Groß. GSL: A Cryptographic Library for the Strong RSA Graph Signature Scheme. arXiv:2005.12447, 2020.
Abstract. In 2018, Yang et al. proposed a decentralized multi-authority attribute-based encryption scheme for cloud computing applications and proved its security using the dual system encryption technique. In this comment, we show that Yang et al. ’s scheme does not achieve encryption one-wayness under the key-only attack and the user collusion attack, respectively. In the key-only attack, with the knowledge of public parameters only, an adversary can impersonate the attribute authorities to forge user attribute secret keys. In the user collusion attack, malicious users can collude by sharing their secret keys to unauthorizedly decrypt a ciphertext. In order to fix the scheme, we suggest adopting a pairing-based proof of knowledge protocol and the decryption algorithm from Lewko and Water’s ABE scheme.
Note. Syh-Yuan Tan. Correction to "Improving Privacy and Security in Decentralizing Multi-Authority Attribute-Based Encryption in Cloud Computing." IEEE Access (Vol. 7), IEEE, 2019, pp. 17045-17049. 10.1109/ACCESS.2019.2894289.
Abstract. We propose new multi-show anonymous attribute-based credential system that is provably secure in the standard model under the q-SDH assumption. The corresponding proof system incorporates efficient show proofs for logical statements AND, OR and NOT. Each statement requires only a constant number of bilinear pairing operations by the verifier and none by the prover. The system is based on the pairing-based Camenisch-Lysyanskaya signature scheme and offers a novel efficient attribute encoding method, which is of independent interest.
Note. This report was published as Newcastle University Technical Report TR-1527. Subsequently, we submitted a further report to the IACR Cryptology ePrint Archive.
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
Note. This is not an output as CASCAde, yet was a crucial foundation of the grant proposal and is included here for contextualization. It lays the foundations for the concept of a graph signature, the feasibility proof in an SRSA setting, and the proof of expressivity.
The definitive version of this work are published under:
Thomas Groß. Signatures and efficient proofs on committed graphs and NP-statements. In International Conference on Financial Cryptography and Data Security, LNCS, vol. 8975, pp. 293-314. Springer, Berlin, Heidelberg, 2015.
Graph Signatures and Topology Proofs PDF 502Kb
Abstract. 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 goals can 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.
Note. This is not an output of CASCAde, but contextualized and informed the research agenda of CASCAde.
This report was published on the IACR Cryptology ePrint Archive: Thomas Groß. Certification and Efficient Proofs of Committed Topology Graphs. IACR Cryptology ePrint 2014/255, 2014.
Definitive version: Thomas Groß. Efficient certification and zero-knowledge proofs of knowledge on infrastructure topology graphs. In proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security (CCSW '2014), November 2014, pp. 69–80