A Relational Credential System from q-SDH-based Graph Signatures PDF 690Kb

An attribute-based credential system enables users to prove possession of a credential and statements over certified attributes to verifiers in zero-knowledge while maintaining anonymity and unlinkability. In a relational anonymous credential system, users can further prove their relationship to other entities in their social graph, such as position in an organizational hierarchy or friends-of-friends status in an online social network graph, while protecting their own privacy and that of other users involved in the social graph. While traditional anonymous credential schemes make no provisions for privacy-preserving relationship predicates, a relational credential system is more usable, because it can facilitate relationship-based access control with a wide range of predicates and offers strong privacy guarantees for relationship proofs. We propose the first relational credential scheme, based on a new q-SDH graph signature scheme and an efficient zero-knowledge proof system for graph predicates. We rigorously prove the security for the proposed scheme and provide a benchmark using Facebook social graphs.

The paper is published as pre-print under Syh-Yuan Tan, Ioannis Sfyrakis and Thomas Groß. A Relational Credential System from q-SDH-based Graph Signatures. Cryptology ePrint Archive, Paper 2023/1181, 2023.

Hashing to Prime in Zero-Knowledge PDF 474Kb

We establish a set of zero-knowledge arguments that allow for the hashing of a committed secret a-bit input x to a committed secret (k+1)-bit prime number px. The zero-knowledge arguments can convince a verifier that a commitment indeed is the correctly generated prime number derived from x with a soundness error probability of at most 2−k+2−t dependent on the number of zero-knowledge argument rounds k and the number of primality bases t to establish primality. Our constructions offer a range of contributions including enabling dynamic encodings for prime-based accumulator, signature and attribute-based credential schemes allowing to reduce these schemes' public key size and setup requirements considerably and rendering them extensible. While our new primality zero-knowledge arguments are of independent interest, we also show improvements on proving that a secret number is the product of two secret safe primes significantly more efficient than previously known results, with applications to setting up secure special RSA moduli.

This work was first published in Thomas Groß. "Hashing to Prime in Zero-Knowledge." In Proceedings of the 18th International Conference on Security and Cryptography-SECRYPT. 2021.

An extended version of this work appeared in Thomas Groß. "Zero-Knowledge Predicates for Hashing to Prime: Theory and Applications." In International Conference on E-Business and Telecommunications, pp. 161-194. Cham: Springer Nature Switzerland, 2021.

A q-SDH-based Graph Signature Scheme on Full-Domain Messages PDF 1,446Kb

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.

MoniPoly - An Expressive q-SDH-Based Anonymous Attribute-Based Credential System PDF 978Kb

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.

GSL: A Cryptographic Library for the strong RSA Graph Signature Scheme PDF 858Kb

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.

Correction to "Improving Privacy and Security in Decentralizing Multi-Authority" PDF 1,020Kb

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.

A Pairing-Based Anonymous Credential System with Efficient Attribute Encoding PDF 879Kb

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.

Signatures and Efficient Proofs on Committed Graphs and NP-Statements PDF 591Kb

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