Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> In this paper we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature. Unlike group signatures, ring signatures have no group managers, no setup procedures, no revocation procedures, and no coordination: any user can choose any set of possible signers that includes himself, and sign any message by using his secret key and the others' public keys, without getting their approval or assistance. Ring signatures provide an elegant way to leak authoritative secrets in an anonymous way, to sign casual email in a way which can only be verified by its intended recipient, and to solve other problems in multiparty computations. The main contribution of this paper is a new construction of such signatures which is unconditionally signer-ambiguous, provably secure in the random oracle model, and exceptionally efficient: adding each ring member increases the cost of signing or verifying by a single modular multiplication and a single symmetric encryption. <s> BIB001 </s> Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> This paper addresses how to use public-keys of several different signature schemes to generate 1-out-of-n signatures. Previously known constructions are for either RSA-keys only or DL-type keys only. We present a widely applicable method to construct a 1-out-of-n signature scheme that allows mixture use of different flavors of keys at the same time. The resulting scheme is more efficient than previous schemes even if it is used only with a single type of keys. With all DL-type keys, it yields shorter signatures than the ones of the previously known scheme based on the witness indistinguishable proofs by Cramer, et al. With all RSA-type keys, it reduces both computational and storage costs compared to that of the Ring signatures by Rivest, et al. <s> BIB002 </s> Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> In this paper, we investigate the recent paradigm for group signatures proposed by Rivest et al. at Asiacrypt '01. We first improve on their ring signature paradigm by showing that it holds under a strictly weaker assumption, namely the random oracle model rather than the ideal cipher. Then we provide extensions to make ring signatures suitable in practical situations, such as threshold schemes or ad-hoc groups. Finally we propose an efficient scheme for threshold scenarios based on a combinatorial method and provably secure in the random oracle model. <s> BIB003 </s> Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> We propose a Reed-Solomon (RS) code construction of the 1-out-n (ring) signature scheme. It is obtained from the observation of the equivalency between the erasure correction technique of the RS code and the polynomial interpolation. The structure is very simple and yields a ring equation that can appropriately denoted by Z 1 + ... + Z n =v, which represents the summation of n evaluations of a polynomial. We also show how to extend the generic RST scheme [6] to a t-out-n threshold ring signature scheme. <s> BIB004 </s> Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> We construct a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi. <s> BIB005 </s> Anonymous Authentication Protocols for Vehicular Ad Hoc Networks: An Overview <s> Ring signature-based scheme <s> Vehicular networks have attracted extensive attentions in recent years for their promises in improving safety and enabling other value-added services. Security and privacy are two integrated issues in the deployment of vehicular networks. Privacy-preserving authentication is a key technique in addressing these two issues. We propose a random keyset based authentication protocol that preserves user privacy under the zero-trust policy, in which no central authority is trusted with the user privacy. We show that the protocol can efficiently authenticate users without compromising their privacy with theoretical analysis. Malicious user identification and key revocation are also described <s> BIB006
Ring signature scheme, introduced by Rivest, Shamir and Tauman BIB001 , offers two main properties: anonymity and spontaneity. In practice, anonymity in a ring signature means 1-out-of-n signer verifiability, which enables the signer to keep anonymous in these "rings" of diverse signers. Spontaneity is a property which makes the distinction between ring signatures and group signatures BIB005 ;  . Different from group signatures which allow the anonymity of a real signer in a group can be revoked by a group manager, the ring signature only gives the group manager the absolute power to control the formation of the group, and does not allow anyone to revoke the signer anonymity, while allowing the real signer to form a ring arbitrarily without being controlled by any other party. Since Rivest el al.'s scheme, many ring signature schemes have been proposed BIB002 ; BIB003 ;  ; BIB004 ; Xiong et al. (2009;   have introduced a new variant for the ring signature, called revocable ring signature. This scheme allows a real signer to form a ring arbitrarily while allowing a set of authorities to revoke the anonymity of the real signer. In other words, the real signer will be responsible for what has signed as the anonymity is revocable by authorities while the real signer still has full freedom on ring formation. To address the scalability concern in Lin et al. (2007), Xiong et al. Xiong et al. (2010a) proposed a spontaneous protocol based on the revocable ring signature  , which allows the vehicle to generate the message without requiring online assistance from the RSUs or the other vehicles. In this solution, the remaining vehicles are not required to update their system parameters regardless of the number of revoked vehicles. However, this protocol suffers larger communication overhead than that of other protocols because the length of ring signature depends on the size of the ring. Furthermore, Xi et al. BIB006  also introduced a random key-set-based authentication protocol to preserve the vehicle's privacy based on ring signature. However, this solution only provides unconditional anonymity without an effective and efficient mechanism to reveal message sender's identities when necessary.