Studies In Group-Oriented Anonymous Protocols With Practicality

Nowadays, diversified applications over the Internet become ubiquitous in people's daily lives. This fact makes it a challenging task that how to sign anonymously on behalf of the group or authenticate incognito one's group membership. In many web-based applications, some kind of privilege is often assigned to valid users, i.e., registered group members. When exercising their rights, users need to convince others that they have authentic membership by showing certain digital signatures to the designated verifier or carrying out authentication protocols with the group authority. Meanwhile, users are gradually concerned with their sensitive personal information and become aware of the importance of privacy protection. As a result, they need effective means to hide their real identities in the group.From the viewpoint of modern cryptography, the above problems can be solved by employing the key techniques of the proof of knowledge, distributed cryptographic protocol, etc. Moreover, digital signature schemes, encryption schemes, anonymous authentication protocols are fundamental cryptographic primitives which are adopted as useful building blocks in the construction of various group-oriented secure cryptosystems. This dissertation investigates the design method of group-oriented anonymous protocols as well as the formal analysis of the resultant protocols. As the contribution, several schemes are proposed which pertain to the active research field of special group signatures, k-times anonymous authentications and multi-coupon systems.Group signatures are a kind of powerful private authentication tool in group-oriented cryptography. In the definition of this primitive, group members can anonymously sign arbitrary messages on behalf of the group. Anyone can check the validity of the given signature, but cannot obtain any information about the original signer. Moreover, it is computationally intractable to determine whether two or more signatures originate from the same group member. The group authority (GA), who has the ability of issuing membership certificates to new members, takes charge of the group. In special circumstance (e.g. when illegal behavior is caught), the designated tracing authority (TA) can revoke anonymity of the malicious signer by opening the suspectable signature. To date, the traditional definition of group signature has been further studied and it has been generalized to many variants, such as hierarchical group signatures, ad hoc group signatures, hidden identity-based signatures, data mining group signatures, expressive subgroup signatures, anonymous proxy signatures, etc.Generally, there are two ways for the opening of a standard group signature, i.e.,(â…°) the TA is able to revoke the anonymity of any signature, but it is required that the GA publish the list of users, i.e., membership directory;(â…±) the list of users is secretly maintained by the GA, and the TA can only open an offending signature with the help of the GA. Recently, Kiayias et al. pointed out that group signatures cannot be directly applied to anonymous credential systems. The reason is that, in case (â…°), publishing the membership directory would seriously violate the users'privacy; in case (â…±), the TA cannot assure a service provider that it can open an offending signature, which leads to restricted use of the anonymous system. For this reason, Kiayias et al. introduced a novel concept of hidden identity-based signatures (abbreviated asHTDS). InHIDS, the TA is independent of the IM (which corresponds to the GA in group signature schemes) for its opening operation and the IM does not have to publish a list of users of the anonymous system. Kiayias et al. firstly proposed the HIDS from bilinear pairings. Unfortunately, their scheme is vulnerable to the framing attack and the chosen ciphertext attack. Furthermore, the original scheme does not support the joint sharing of the tracing key. Two improved schemes were put forth by employing the techniques of the Shacham encryption based on the linear assumption, the joint random VSS (Verifiable Secret Sharing) protocol, the simultaneous zero-knowledge proof of knowledge, etc. Besides no framing and anonymity under the chosen ciphertext attack, the second new scheme achieves the deployment of distributed tracing servers and the resistance of the powerful dynamic attacker at the same time. To meet this goal, the threshold version of the underlying Shacham encryption was firstly provided by using the Canetti-Goldwasser paradigm and the erasure-free threshold protocols by Jarecki et al. Functionality and efficiency analysis indicates that the new schemes achieve the higher level of practicability and security.Typical anonymous authentication schemes allow the authentication of users without disclosing their real identities. In such schemes, anonymous users authenticate themselves by demonstrating the possession of membership credentials. Moreover, in many applications on the Internet (such as trial browsing of content, cloud storage services, etc), the application provider need to put restrictions on the number of times users can access. In ASIACRYPT2004, Teranishi et al. firstly proposed the notion of k-times anonymous authentication (abbreviated as k-TAA). The entities in k-TAA include a group manager, many users, and several service providers (SP). Initially, users should carry out a registration protocol with the group manager. Then, each AP announces the maximum number of times that users can access their application or resource. Before the process of anonymous access, the registered users should authenticate themselves to certain AP. To note that, compared with group signature schemes, k-TAA scheme can achieve a higher anonymity level. In other words, in k-TAA schemes, even the powerful group manager cannot revoke the anonymity of honest users, i.e., they authenticate themselves and enjoy the service provided by AP within the predetermined number (i.e., k). From AP's standpoint, k-TAA schemes provide stronger version of traceability, which means that any entity can make tracks for the dishonest user (who attempts to access the service more than he is allowed for) with the public authentication log without the help of the group manager or AP, while in group signature schemes only the group manager has this tracing ability. In ACNS2005, Nguyen et al. pointed out that in reality, APs would like to setup user group and manage the group on their own, i.e., they are able to grant or revoke users' access right. Activated by this motive, Nguyen et al. introduced a new concept, namely dynamic k-TAA. Unfortunately, the main problem with the schemes of Teranishi et al. and Nguyen et al. is that the computational cost of authentication phase is of order O(k). Later on, Nguyen and Teranishi et al. respectively suggested their revised schemes, in which the complexity of authentication protocol is independent of k. But their advantages in efficiency over authentication protocol were obtained at the sacrifice of the storage cost of AP's public key, i.e., O(k). In addition, their schemes required that AP must keep honest. In SCN2006, Au et al. put forth a dynamic k-TAA scheme with the authentication complexity of O(log(k)). Very recently, Emura et al. stressed that in previous k-TAA schemes, k is a fixed parameter, which implies that all users have the same maximum number for access. In some applications, it appears preferable to grant different maximum number for each user according to the money they has paid. To this end, Emura et al. put forward a k-TRAA scheme, which means k-times relaxed anonymous authentication. However, their scheme does not satisfy the property of anonymity required by typical k-TAA schemes, because two transcripts of authentication protocol generated with the same AP can be linked with each other. In previous works of k-times anonymous authentication, two problems have not been properly solved:1) how to allow application providers to assign different maximal numbers of access for each user without weakened anonymity, and2) how to protect against massive clone attacks mounted by malicious users. To overcome these obstacles, a revised scheme was proposed. It incorporated several crucial tools including the proof that a committed value is less than another committed value, dynamic accumulator, the method of cloning detection based on n-times show e-tokens, etc. The revised scheme is proved secure in the extended Teranishi-Furukawa-Sako model, i.e., correctness, total anonymity, exculpability of users, exculpability of the GM, exculpability of APs and detectability. Moreover, the registration protocol of the new scheme is concurrently-secure, so it is fit for the deployment in realistic asynchronous network setting (e.g., Internet).Coupons are usually issued by manufacturers or vendors and they often appear in newspapers, journals, or flyers. Coupons are effective means for advertisement and sales promotion. They push customers to buy certain merchandise by providing appealing discount prices or gifts. Nowadays, coupons can be distributed over the Internet, which means customers can freely download and print coupons placed on vendor's web site and use them as other paper-based coupons. Multi-coupons (MC) are special form of emerging e-coupons, and they can be viewed as a collection of e-coupons which can be redeemed only once. In practice, issuing a multi-coupon with the value of m is more efficient than issuing m regular e-coupons independently. A secure multi-coupon system (MCS) should fulfill two crucial properties, i.e., unsplittability and unlinkability. The unsplittability aims to protect the benefit of vendors, i.e., two customers cannot split a MC into multiple shares, so that they can redeem the shares independently. The unlinkability means customers should keep anonymous during the process of issuing or redeeming. It is worth noting that MCS is not equal to e-cash schemes, because MCS needs not provide the mechanisms for the participation of bank and the tracing of malicious users.So far, one main obstacle in constructing MCSs is how to devise an efficient issue protocol in which the value of the MCs can be chosen freely and the complexity of the resultant protocol is not dependent on the value of the MCs. Another obstacle is how to provide efficient and flexible mechanisms for redemption protocol. To overcome these problems, two revised systems with improved efficiency and functionality were put forth. In order to specify the value of MCs flexibly, the new systems employed the discrete logarithm based range proof by Chaabouni et al. and the knowledge proof of committed values by Canard et al. respectively. In addition, the computation complexities of redemption protocols were optimized by making use of the batch zero-knowledge proof and verification by Peng et al. It can be proved that the new systems are secure in Nguyen's security model for MCS. Moreover, the new systems for the first time achieve all the desirable features required in applications, i.e., concurrent issuing, compactness, batch redeeming, as well as supporting coupon's object and its expiration date. Furthermore, performance comparison shows that their communication and computation overheads are significantly lower than the previous systems of the same type.Previous MCSs do not explicitly consider the circumstance of concurrent execution and they are all designed in the random oracle model. Furthermore, these systems are based on the q-SDH (i.e., q-Strong Diffie-Hellman) assumption or the SRSA (i.e. Strong RSA) assumption. However, the q-SDH assumption was recently found to have some weakness in security, while the systems built on RSA groups require expensive communication bandwidth. These obstacles were remedied by providing two improved systems with concurrent security. The first system was obtained by extending the underlying scheme of Blanton with the precise range proof of two committed values and the Sigma-compiler for two round concurrent zero-knowledge argument. The second system (i.e., the strengthened version of the first one) achieved more efficient security reduction by incorporating the straight-line extraction paradigm and removed random oracles by using the non-interactive zero-knowledge argument from homomorphic encryption. Compared with other strongly unsplittable systems, the first system has better communicational efficiency and the second one does not rely on random oracles.