Group signature

Last updated

A group signature scheme is a method for allowing a member of a group to anonymously sign a message on behalf of the group. The concept was first introduced by David Chaum and Eugene van Heyst in 1991. For example, a group signature scheme could be used by an employee of a large company where it is sufficient for a verifier to know a message was signed by an employee, but not which particular employee signed it. Another application is for keycard access to restricted areas where it is inappropriate to track individual employee's movements, but necessary to secure areas to only employees in the group.

Contents

Essential to a group signature scheme is a group manager, who is in charge of adding group members and has the ability to reveal the original signer in the event of disputes. In some systems the responsibilities of adding members and revoking signature anonymity are separated and given to a membership manager and revocation manager respectively. Many schemes have been proposed, however all should follow these basic requirements:

Soundness and completeness
Valid signatures by group members always verify correctly, and invalid signatures always fail verification.
Unforgeable
Only members of the group can create valid group signatures.
Anonymity
Given a message and its signature, the identity of the individual signer cannot be determined without the group manager's secret key.
Traceability
Given any valid signature, the group manager should be able to trace which user issued the signature. (This and the previous requirement imply that only the group manager can break users' anonymity.)
Unlinkability
Given two messages and their signatures, we cannot tell if the signatures were from the same signer or not.
No framing
Even if all other group members (and the managers) collude, they cannot forge a signature for a non-participating group member.
Unforgeable tracing verification
The revocation manager cannot falsely accuse a signer of creating a signature he did not create.
Coalition resistance
A colluding subset of group members cannot generate a valid signature that the group manager cannot link to one of the colluding group members. [1]

The ACJT 2000, [1] BBS04, [2] and BS04 (in CCS) group signature schemes are some of the state of the art. (Note: this might be an incomplete list.)

Boneh, Boyen and Shacham published in 2004 (BBS04, Crypto04) a novel group signature scheme based on bilinear maps. [2] Signatures in this scheme are approximately the size of a standard RSA signature (around 200 bytes). The security of the scheme is proven in the random oracle model and relies on the Strong Diffie Hellman assumption (SDH) and a new assumption in bilinear groups called the Decision linear assumption (DLin).

A more formal definition that is geared towards provable security was given by Bellare, Micciancio and Warinschi. [3]

See also

Related Research Articles

<span class="mw-page-title-main">David Chaum</span> American computer scientist and cryptographer (born 1955)

David Lee Chaum is an American computer scientist, cryptographer, and inventor. He is known as a pioneer in cryptography and privacy-preserving technologies, and widely recognized as the inventor of digital cash. His 1982 dissertation "Computer Systems Established, Maintained, and Trusted by Mutually Suspicious Groups" is the first known proposal for a blockchain protocol. Complete with the code to implement the protocol, Chaum's dissertation proposed all but one element of the blockchain later detailed in the Bitcoin whitepaper. He has been referred to as "the father of online anonymity", and "the godfather of cryptocurrency".

Identity-based encryption (IBE), is an important primitive of identity-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user. This means that a sender who has access to the public parameters of the system can encrypt a message using e.g. the text-value of the receiver's name or email address as a key. The receiver obtains its decryption key from a central authority, which needs to be trusted as it generates secret keys for every user.

An undeniable signature is a digital signature scheme which allows the signer to be selective to whom they allow to verify signatures. The scheme adds explicit signature repudiation, preventing a signer later refusing to verify a signature by omission; a situation that would devalue the signature in the eyes of the verifier. It was invented by David Chaum and Hans van Antwerpen in 1989.

In cryptography, a random oracle is an oracle that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.

In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent e (for e ≥ 3). More specifically, given a modulus N of unknown factorization, and a ciphertext C, it is infeasible to find any pair (Me) such that C ≡ M e mod N.

In cryptography, a password-authenticated key agreement (PAK) method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.

A deterministic encryption scheme is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include RSA cryptosystem, and many block ciphers when used in ECB mode or with a constant initialization vector.

<span class="mw-page-title-main">Merkle–Damgård construction</span> Method of building collision-resistant cryptographic hash functions

In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2.

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a set of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular set of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the set's members' keys was used to produce the signature. Ring signatures are similar to group signatures but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature; and second, any set of users can be used as a signing set without additional setup.

Digital credentials are the digital equivalent of paper-based credentials. Just as a paper-based credential could be a passport, a driver's license, a membership certificate or some kind of ticket to obtain some service, such as a cinema ticket or a public transport ticket, a digital credential is a proof of qualification, competence, or clearance that is attached to a person. Also, digital credentials prove something about their owner. Both types of credentials may contain personal information such as the person's name, birthplace, birthdate, and/or biometric information such as a picture or a finger print.

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.

Distributed key generation (DKG) is a cryptographic process in which multiple parties contribute to the calculation of a shared public and private key set. Unlike most public key encryption models, distributed key generation does not rely on Trusted Third Parties. Instead, the participation of a threshold of honest parties determines whether a key pair can be computed successfully. Distributed key generation prevents single parties from having access to a private key. The involvement of many parties requires Distributed key generation to ensure secrecy in the presence of malicious contributions to the key calculation.

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field . In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-complete. That's why those schemes are often considered to be good candidates for post-quantum cryptography. Multivariate cryptography has been very productive in terms of design and cryptanalysis. Overall, the situation is now more stable and the strongest schemes have withstood the test of time. It is commonly admitted that Multivariate cryptography turned out to be more successful as an approach to build signature schemes primarily because multivariate schemes provide the shortest signature among post-quantum algorithms.

A BLS digital signature, also known as Boneh–Lynn–Shacham (BLS), is a cryptographic signature scheme which allows a user to verify that a signer is authentic.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

In cryptography, server-based signatures are digital signatures in which a publicly available server participates in the signature creation process. This is in contrast to conventional digital signatures that are based on public-key cryptography and public-key infrastructure. With that, they assume that signers use their personal trusted computing bases for generating signatures without any communication with servers.

<span class="mw-page-title-main">PALISADE (software)</span>

PALISADE is an open-source cross platform software library that provides implementations of lattice cryptography building blocks and homomorphic encryption schemes.

References

  1. 1 2 Ateniese, Giuseppe; Camenisch, Jan; Joye, Marc; Tsudik, Gene (2000). "A Practical and Provably Secure Coalition-Resistant Group Signature Scheme". Advances in Cryptology — CRYPTO 2000 (PDF). Lecture Notes in Computer Science. Vol. 1880. pp. 225–270. doi:10.1007/3-540-44598-6_16. ISBN   978-3-540-67907-3 . Retrieved 24 June 2012.
  2. 1 2 Boneh, Dan; Boyen, Xavier; Shacham, Hovav (2004). "Short Group Signatures" (PDF). Advances in Cryptology – CRYPTO 2004. Lecture Notes in Computer Science. Vol. 3152. Springer. pp. 227–242. doi:10.1007/978-3-540-28628-8_3. ISBN   978-3-540-22668-0. ISSN   0302-9743 . Retrieved 24 June 2012.
  3. Bellare, Mihir; Micciancio, Daniele; Warinschi, Bogdan (May 2003). "Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions". Advances in Cryptology — EUROCRYPT 2003. Lecture Notes in Computer Science. Vol. 2656. Warsaw, Poland: Springer. pp. 614–629. doi: 10.1007/3-540-39200-9_38 . ISBN   978-3-540-14039-9.