This thesis’ major contribution is to propose an attribute based authentication scheme (AAS). An AAS scheme is a new cryptosystem that extends the field of public key
cryptography and more precisely digital signatures. An AAS scheme allows a verifier
to decide on the set of attributes (s)he would like the signer to possess. The verifier
sends the request to a group of possible signers as a monotone boolean expression. Any
member with sufficient attributes can sign. The scheme maintains certain properties
 No previous knowledge assumption: The signer and verifier may or may not have
met before; therefore we can not rely on any kind of previous knowledge.
 Unforgeable : It is hard to forge signatures and/or the proof of possession of
 Anonymous Identities: Given the signature it is hard to identify the signer.
 Unlinkable: Given two signatures it is hard to know whether the signer is the
same or not.
 Traceable: Each group of potential signers have a group manager and he is the
only one capable of revoking anonymity and discovering the signer’s identity. This
property is meant to ensure signers do not misuse anonymity.
 Anonymous Attributes: The attribute disclosure should be to the minimum.
 Coalition Resistant: If a verifier requires more than one attribute from the signers, the signers should not be able to get together their individual attributes and sign as one entity.
 Separability: The tasks of different authorities should be separable and each
entity should be capable of performing its task independently from others.
Different attribute oriented authentication schemes exist in literature, however each of
them is designed to serve a certain application. However the properties we listed above never co-existed in one scheme. This thesis goes through various designs for such a system, proofs security for them all and finally provides a general construction from any group signature to an AAS.