# V-LDAA: A New Lattice-Based Direct Anonymous Attestation Scheme for VANETs System

Authors: Liquan Chen; Tianyang Tu; Kunliang Yu; Mengnan Zhao; Yingchao Wang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Privacy protection and message authentication issues in VANETs have received great attention in academia. Many authentication schemes in VANETs have been proposed, but most of them are based on classical difficult problems such as factorization in RSA setting or Elliptic Curve setting and are therefore not quantum resistant. If a quantum computer becomes available in the next few decades, the security of these schemes will be at stake. This paper presents a vehicular lattice-based direct anonymous attestation (V-LDAA) scheme adopting an optimized signature scheme based on automorphism stability which achieves postquantum security. A distributed pseudonym update and vehicle revocation mechanism based on the lattice is introduced in this paper, which means vehicles can update their pseudonyms and revoke the identity certificate by themselves without the need for pseudonym resolutions or CRLs checking. Compared with the existing lattice-based attestation schemes in VANETs, computation costs during signing and verification operations in V-LDAA are no longer related to the number of users, which makes it suitable for large-scale VANETs. Security analysis shows that V-LDAA resists TPM theft attacks and provides users with user-controlled anonymity, user-controlled unlinkability, and unforgeability against quantum adversaries. Experimental results show that V-LDAA reduces the blind signature size by 18%. The speed of blind signing is increased by 30%, and blind verification operation is accelerated 3 times compared with the existing lattice-based direct anonymous attestation (LDAA) scheme.


---

## Body

## 1. Introduction

The Intelligent Transportation System (ITS) provides vehicles with intelligent and efficient services, such as collision avoidance, traffic condition reports, and entertainment services, etc. Messages are sent to various network nodes through vehicular ad hoc networks (VANETs) [1]. VANET is a key facility of an intelligent transportation system, which is composed of Certification Authority (CA), roadside units (RSUs), and on-board units (OBUs) [2]. Among them, the OBU is responsible for supporting the V2I communication between the roadside units and the vehicle and V2V communication between vehicles. These nodes are connected to each other to form a network, and the communications in the entire network are achieved through the information transferring among adjacent nodes. The key issue that needs to be solved in the implementations for ITS is how to protect the security and privacy of users in VANETs. Vehicle users in ITS need to send information about their location, speed, and other driving conditions, or traffic jams, icy roads, and other surrounding road conditions to adjacent users. If this information is maliciously tracked or tampered with by an adversary, it will cause serious privacy leakage accidents and even threaten the life of the driver. For example, the adversary can obtain the real location information of the vehicle by tracing the navigation route information or modify the traffic information, which may lead to traffic paralysis or even serious traffic accidents. Therefore, an anonymous attestation protocol in VANETs needs to be established to ensure the anonymity of users and the integrity and untraceability of messages.In addition, with the development of quantum computing technology, the security of traditional public key cryptosystems has received an impact. Most of the existing authentication protocols in VANETs have their security supported on classic difficult problems such as factorization in RSA setting or Elliptic Curve setting. Under traditional computing conditions, these difficult problems can only be solved in exponential or subexponential time. However, according to Shor’s algorithm, quantum computers can efficiently solve these problems, leading to the failure of traditional cryptosystems. Thus, there is a need to introduce quantum-resistant authentication schemes in VANETs.We have proposed the following major contributions in this paper.(1)
A vehicular lattice-based direct anonymous attestation scheme that achieves postquantum security is proposed in this paper. In this scheme, a lattice-based distributed pseudonym update and certificate revocation mechanism is introduced. By embedding a trusted platform module (TPM) in each vehicle, trust is distributed from Certification Authority (CA), pseudonym provider (PP), Revocation Authority (RA), and other authoritative institutions to each legitimate user, transforming a centralized trust system into a distributed trust system. “Distributed trust” is reflected in the processes of pseudonym update and vehicle revocation. Users can generate pseudonyms by themselves without the need for regular updates and distributions by PP. TPM performs the revocation operation independently, without RA performing pseudonym resolution operations, and there is no need to maintain the certificate revocation lists CRLs. Moreover, the calculation costs in signing operations are no longer related to the number of members. Thus, it is more suitable for large-scale VANETs.(2)
V-LDAA optimizes the signature scheme based on automorphism stability which is used in theBlindSign and BlindVerify protocols of the original LDAA scheme. The optimized signature scheme reduces the number of automorphisms that need to be proven stable, which simplifies the processes of signing and verification and reduces the signature size. Based on the experimental implementation of the V-LDAA scheme, the high computation and storage efficiency of the proposed scheme is confirmed.(3)
V-LDAA binds TPM and Host to jointly generate an identity certificate in Join protocol to resist TPM theft attacks. This is important in VANETs because it prevents TPM from being transplanted to a new vehicle platform by an adversary and signed with the replaced identity certificate.The rest of this paper is organized as follows. We first introduce related works, the background knowledge, an optimized signature scheme used in V-LDAA and VANET architectures based on V-LDAA. Then, the construction of the proposed V-LDAA scheme is described. After that, security and performance analysis are detailed. Finally, the conclusion of this paper is presented.


## 2. Related Works

In recent years, research studies on authentication schemes mainly focused on the following aspects. The first is based on a symmetric key mechanism [2]. The sender uses a shared key to generate the message authentication code (MAC), while the receiver verifies it before accepting the message. However, because both parties need to share the private key, the mechanism based on message authentication code cannot withstand a large number of node tampering attacks in the network. In addition, the adversary can cheat any individual node to obtain the private key, which can be used for message authentication. The second is an identity-based encryption system [3, 4], where the trusted authority is responsible for the generation and distribution of public and private key pairs for legitimate members. However, under this mechanism, the adversary can easily obtain the user’s real identity from the signature and track the signature. The third one is an authentication scheme based on vehicle public key infrastructures (VPKIs), which is also the design idea of this paper. CA is responsible for registering and managing long-term identity certificates of members, while members sign messages through short-term pseudonym certificates. The VPKIs scheme can meet the anonymity property and provide a pseudonym mechanism, but there are still many shortcomings. In this scheme, the security risk and computation burden are caused by different pseudonym update strategies. In order to prevent users from being maliciously tracked, CA needs to change pseudonyms for all users regularly [1]. In the case of unconditional security, the pseudonym should be changed every time the signature is signed, which causes a huge computational and storage burden when PP generates new pseudonym certificates and distributes them to every legitimate user periodically. In [5], an optimized pseudonym update scheme is proposed, but its computation costs still burden the vehicle and the Pseudonym Provider (PP). In addition, in order to revoke the identity certificate of an illegal vehicle, the Revocation Authority (RA) needs to resolute the user’s long-term identity ID value from the user’s pseudonym and save it to certificate revocation lists (CRLs) for all users to query. The update, query, maintenance, and storage of CRLs cause heavy computation and storage costs.The existing authentication schemes for VANETs which achieve postquantum security are mainly lattice-based ring signature schemes [6–8]. In the lattice-based ring signature scheme, each member needs to use its private key and the public keys of all other members to sign the message, and the members in a ring need to change with the specific driving position of the vehicle. In recent years, several lattice-based direct anonymous attestation (LDAA) schemes are proposed by updating the cryptographic primitives to be quantum resistant in direct anonymous attestation (DAA) [9–11]. The first LDAA in [9] is based on a lattice-based MAC scheme and a CMA-secure digital signature scheme, but it suffers from high computation costs in signing protocol. LDAA in [10] adopts a noninteractive sigma protocol construction and a modified Boyen’s signature scheme, which can improve signing and storage efficiency compared to LDAA in [9]. Among them, the lattice-based direct anonymous attestation in [11] is most suitable for a future quantum-resistant TPM for its high efficiency. LDAA becomes an interesting candidate for the postquantum secure authentication protocol in VANETs because of its balance in authentication and anonymity.


## 3. Preliminaries

### 3.1. Notation

Symbols used in this paper are illustrated in Table1 with their definitions.Table 1
Notation.
NotationDescriptionℤqQuotient ringZ/qZqThe moduli used in the commitment schemeK=ℚX/Xd+1A cyclotomic ringdThe dimension of ringKy⟵Dy is drawn according to the distribution DG=GalK/ℚThe Galois group ofK over ℚG=σ−1,σ5Galois groupG is generated by σ−1 and σ5NThe number of userseLowercase bold letters denote a vector of polynomialsACapital bold letters denote a matrix whose entities are polynomials


### 3.2. Trapdoor Sampling

Sample two short vectorss1,s2 satisfying(1)ab+i1q⋅s1s2=u+a2⋅e,where i is a nonzero element in ℤq. According to [12], there is a set of basis S∈ℤ4d×4d for Λ⊥=x∈ℛ4|a|b+i⋅1q⋅x≡0modq. The Gram–Schmidt orthogonalization of S∈ℤ4d×4d satisfies S˜≤s1R+1δ2+1 with δ=q. To sample s1,s2, first calculate an arbitrary solution (not necessarily short solutions) that satisfies (1). Then express it in basis S, and use the randomized nearest plane discrete Gaussian sampling algorithm in [13] to get solutions distributed as the discrete Gaussian distribution with s=2⋅S˜≤23d+1δ2+1. The algorithm is called MP−Sampler.


### 3.3. Lattice-Based Commitment Scheme

We use the commitment scheme from [14] with M-LWE based hiding property and M-SIS based binding property. Define public parameters A1∈ℛq11×k, A2∈ℛq2l×k, where A1=1A1′,A1′←$ℛq1k−1 and A2=0lIlA2′,A2′←$ℛq2l×k−1−l. To commit to a message m∈ℛq2l×l, sample r←$S1k and compute Comm;r=t1t2=A1A2r+0m. If there exists r≤Bcom and c∈ℛ satisfying ct1t2=A1A2r+c0m, then the opening t1t2 is valid.


### 3.4. Lattice-Based Zero-Knowledge Proof

Lattice-based encryption schemes usually include a publicA and small coefficient secret value e, which satisfies Ae=t. In order to prove that t is a legal ciphertext, a zero-knowledge proof about e needs to be generated, which satisfies Ae=t. There are several protocols to achieve zero-knowledge proof about e. The first one is based on a Stern-type protocol to prove a norm bounded e satisfying exactly Ae=t, which is the most accurate but also the most expensive protocol. In V-LDAA, this method can be used in the zero-knowledge proof of TPM and Host secret values in the Join phase because each user only needs to perform it once in the entire certificate lifecycle. The second is to use rejection sampling and lattice-based Fiat–Shamir [15], which proves that Ae′=ct, where cis the difference between two challenge values.


## 3.1. Notation

Symbols used in this paper are illustrated in Table1 with their definitions.Table 1
Notation.
NotationDescriptionℤqQuotient ringZ/qZqThe moduli used in the commitment schemeK=ℚX/Xd+1A cyclotomic ringdThe dimension of ringKy⟵Dy is drawn according to the distribution DG=GalK/ℚThe Galois group ofK over ℚG=σ−1,σ5Galois groupG is generated by σ−1 and σ5NThe number of userseLowercase bold letters denote a vector of polynomialsACapital bold letters denote a matrix whose entities are polynomials


## 3.2. Trapdoor Sampling

Sample two short vectorss1,s2 satisfying(1)ab+i1q⋅s1s2=u+a2⋅e,where i is a nonzero element in ℤq. According to [12], there is a set of basis S∈ℤ4d×4d for Λ⊥=x∈ℛ4|a|b+i⋅1q⋅x≡0modq. The Gram–Schmidt orthogonalization of S∈ℤ4d×4d satisfies S˜≤s1R+1δ2+1 with δ=q. To sample s1,s2, first calculate an arbitrary solution (not necessarily short solutions) that satisfies (1). Then express it in basis S, and use the randomized nearest plane discrete Gaussian sampling algorithm in [13] to get solutions distributed as the discrete Gaussian distribution with s=2⋅S˜≤23d+1δ2+1. The algorithm is called MP−Sampler.


## 3.3. Lattice-Based Commitment Scheme

We use the commitment scheme from [14] with M-LWE based hiding property and M-SIS based binding property. Define public parameters A1∈ℛq11×k, A2∈ℛq2l×k, where A1=1A1′,A1′←$ℛq1k−1 and A2=0lIlA2′,A2′←$ℛq2l×k−1−l. To commit to a message m∈ℛq2l×l, sample r←$S1k and compute Comm;r=t1t2=A1A2r+0m. If there exists r≤Bcom and c∈ℛ satisfying ct1t2=A1A2r+c0m, then the opening t1t2 is valid.


## 3.4. Lattice-Based Zero-Knowledge Proof

Lattice-based encryption schemes usually include a publicA and small coefficient secret value e, which satisfies Ae=t. In order to prove that t is a legal ciphertext, a zero-knowledge proof about e needs to be generated, which satisfies Ae=t. There are several protocols to achieve zero-knowledge proof about e. The first one is based on a Stern-type protocol to prove a norm bounded e satisfying exactly Ae=t, which is the most accurate but also the most expensive protocol. In V-LDAA, this method can be used in the zero-knowledge proof of TPM and Host secret values in the Join phase because each user only needs to perform it once in the entire certificate lifecycle. The second is to use rejection sampling and lattice-based Fiat–Shamir [15], which proves that Ae′=ct, where cis the difference between two challenge values.


## 4. An Optimized Signature Scheme Based on Automorphism Stability of the Cyclotomic Field

The signature schemes of the LDAA schemes in [9, 10] both use Boyen’s signature framework under the standard security model [16]. Although there are studies using polynomial lattices to improve the efficiency of Boyen’s signature mechanism [17], the size of its group signature is still around 50 MB [18]. The LDAA framework proposed in [11] uses a selectively secure signature mechanism based on the lattice [19]. The so-called selective security refers to the security of messages that can be fixed in advance (fixed before the attacker communicates with the system). In the case of selectively secure, in order to prove the security of the message to be signed, we have to prove the invertibility of the signed message μ and its stability in a special subset. In [19], a Galois extension of the cyclotomic field was used to prove that μ belongs to a certain subset and is invertible. In this paper, we optimize the selective-secure signature scheme used in [11], reducing the number of automorphisms that need to be proven stable from two to one.


### 4.1. Galois Group of Cyclotomic Rings

IfTn−1 is separable from K , then Kμn is the splitting field of Tn−1 on K and Kμn/K is called a Galois extension. Suppose K=ℚX/ΦmX is a m−th cyclotomic field of degree d=φm with an integer ringℛ=ℤX/ΦmX and its subring S⊂ℛ. Then, the Galois group G is defined as G=GalK/ℚ, which consists of all automorphisms of K. The Galois group on the cyclotomic field is isomorphic to ℤm×, that is j↦σj:ℤm×⟶GalK/ℚ where σjX=Xj. For the subfield L⊂K, there must be a subgroup H<G which is the Galois group K on L, that is H=GalK/L=σ∈G|σx=x∀x∈L. According to [19], if μ∈ℛq satisfies σμ≡μmodqℛfor allσ∈H, then μ is in the subfield Sq of ℛq. Thus, in order to prove μ∈Sq, we need to prove the stability of μ by all Galois automorphisms in H. In other words, we need to prove the stability of μ under the generators of H.


### 4.2. Power-of-Two Cyclotomic Rings

SupposeK=ℚX/Xd+1 is a power-of-two cyclotomic fields, we getG=GalK/ℚ≅ℤ2d×≅ℤ2×ℤd/2, which is generated by σ−1 and σ5, that is G=σ−1,σ5. Consider a subgroup H=σ−1,σ5k, according to [19], the fixed field L of H is generated by α=Xd−d/2k−Xd/2k. Consider the parameter used in [11] when k=1, then H=G=σ−1,σ5 and the corresponding fixed field L=ℚ and Sq=ℤq. For every prime number q, Sq is a field. In this case, it is enough to prove that the message μ∈ℛq remains unchanged under σ−1 and σ5. This means that every time the zero-knowledge proof of the identity certificate is performed, similar calculations have to be repeated twice (on σ−1 and σ5), which increases the computational complexity of the protocol and the size of the commitments.In this paper, we change the subfield tok=2, which means H=σ−1,σ52 or H=σ5. When H=σ5, the generator of its fixed field L is α=Xd/2 and the minimal polynomial is Y2+1. In this case, only one automorphism stability σ5 needs to be proved during zero-knowledge proof. We select μ∈Sq, where Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq of size q2 and q≡3mod4. When TPM chooses its identity value, it computes μ=c0+c1α=c0+c1Xd/2∈ℛq with arbitrary c0,c1∈ℤq and proves that μ remains unchanged under σ5μ=μ. The process of signing and verification is shown in Table 2.Table 2
An optimized signature scheme based on automorphism stability of the cyclotomic field.
SignerMessage:M∈0,1∗Public:t,σ5Private:rVerifierMessage:M∈0,1∗Public:t,σ5y,y5⟵Dξ3W1=a1TyW1,5=σ5−1a1Ty5W2,5=a2Ty−σ5−1a2Ty5c=Ht,σ5,W1,W1,5W2,5,Mz=rc+yz5=σ5−1rc+y5ifrejz|z5,rc|σ5−1c,ξ=1,abort⟶z,z5W1′=a1Tz−t1cW1,5′=σ5−1a1Tz5−σ5−1t1cW2,5′=a2Tz−σ5−1a2Tz5ifz,z5≤βz andc=Ht,σ5,W1′,W1,5′W2,5′,MOutput 1elseOutput 0


## 4.1. Galois Group of Cyclotomic Rings

IfTn−1 is separable from K , then Kμn is the splitting field of Tn−1 on K and Kμn/K is called a Galois extension. Suppose K=ℚX/ΦmX is a m−th cyclotomic field of degree d=φm with an integer ringℛ=ℤX/ΦmX and its subring S⊂ℛ. Then, the Galois group G is defined as G=GalK/ℚ, which consists of all automorphisms of K. The Galois group on the cyclotomic field is isomorphic to ℤm×, that is j↦σj:ℤm×⟶GalK/ℚ where σjX=Xj. For the subfield L⊂K, there must be a subgroup H<G which is the Galois group K on L, that is H=GalK/L=σ∈G|σx=x∀x∈L. According to [19], if μ∈ℛq satisfies σμ≡μmodqℛfor allσ∈H, then μ is in the subfield Sq of ℛq. Thus, in order to prove μ∈Sq, we need to prove the stability of μ by all Galois automorphisms in H. In other words, we need to prove the stability of μ under the generators of H.


## 4.2. Power-of-Two Cyclotomic Rings

SupposeK=ℚX/Xd+1 is a power-of-two cyclotomic fields, we getG=GalK/ℚ≅ℤ2d×≅ℤ2×ℤd/2, which is generated by σ−1 and σ5, that is G=σ−1,σ5. Consider a subgroup H=σ−1,σ5k, according to [19], the fixed field L of H is generated by α=Xd−d/2k−Xd/2k. Consider the parameter used in [11] when k=1, then H=G=σ−1,σ5 and the corresponding fixed field L=ℚ and Sq=ℤq. For every prime number q, Sq is a field. In this case, it is enough to prove that the message μ∈ℛq remains unchanged under σ−1 and σ5. This means that every time the zero-knowledge proof of the identity certificate is performed, similar calculations have to be repeated twice (on σ−1 and σ5), which increases the computational complexity of the protocol and the size of the commitments.In this paper, we change the subfield tok=2, which means H=σ−1,σ52 or H=σ5. When H=σ5, the generator of its fixed field L is α=Xd/2 and the minimal polynomial is Y2+1. In this case, only one automorphism stability σ5 needs to be proved during zero-knowledge proof. We select μ∈Sq, where Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq of size q2 and q≡3mod4. When TPM chooses its identity value, it computes μ=c0+c1α=c0+c1Xd/2∈ℛq with arbitrary c0,c1∈ℤq and proves that μ remains unchanged under σ5μ=μ. The process of signing and verification is shown in Table 2.Table 2
An optimized signature scheme based on automorphism stability of the cyclotomic field.
SignerMessage:M∈0,1∗Public:t,σ5Private:rVerifierMessage:M∈0,1∗Public:t,σ5y,y5⟵Dξ3W1=a1TyW1,5=σ5−1a1Ty5W2,5=a2Ty−σ5−1a2Ty5c=Ht,σ5,W1,W1,5W2,5,Mz=rc+yz5=σ5−1rc+y5ifrejz|z5,rc|σ5−1c,ξ=1,abort⟶z,z5W1′=a1Tz−t1cW1,5′=σ5−1a1Tz5−σ5−1t1cW2,5′=a2Tz−σ5−1a2Tz5ifz,z5≤βz andc=Ht,σ5,W1′,W1,5′W2,5′,MOutput 1elseOutput 0


## 5. VANET Architectures Based on V-LDAA

The traditional VPKI is shown in Figure1, which is composed of a Certification Authority (CA), a pseudonym provider (PP), a vehicle Revocation Authority (RA), and user vehicles. The vehicle registers its identity with CA, and CA signs the long-term identity certificate VID to the vehicle after confirming that the vehicle is in a trustworthy state. After the vehicle shows VID to the pseudonym provider PP, PP generates a pseudonym certificate based on VID and issues it to the vehicle user. During V2V communication, the illegal behavior of the vehicle will be reported to PP, and PP will determine whether to revoke the user certificate. When deciding to revoke the user certificate, RA cooperates with PP and CA to resolute the pseudonymous certificate to obtain the user's real identity ID. The violation ID is updated to the certificate revocation lists (CRLs). Every time before the user verifies the signature, it needs to first check whether the sender is in the CRLs. The main shortcomings of the traditional VPKI architecture are high storage and calculation consumption for updating, maintaining and querying CRLs; pseudonym resolution is required when certificate revocation, computing efficiency, and security issues are brought by PP's regular update of pseudonym certificates, etc.Figure 1
Traditional VPKI architectures.VANET architecture based on V-LDAA is shown in Figure2. Compared with the traditional VPKI system, a hardware chip TPM is embedded in each user's vehicle platform. Through the identity certificate, we distribute trust from CA to TPM embedded in each legitimate user, transforming a centralized trust system into a distributed trust system. “Distributed Trust” is reflected in the processes of pseudonym update and vehicle revocation. Users can generate pseudonyms by themselves without the need for regular updates and distribution by PP. During certificate revocation, RA only needs to broadcast the revocation instruction of a certain vehicle, while the target vehicle will check its identity, perform the revocation operation, and return the revocation certificate to RA. The whole process does not involve any pseudonym resolution or operations related to the revocation list CRLs.Figure 2
VANET architecture based on V-LDAA.


## 6. Proposed V-LDAA Scheme

Based on the LDAA scheme in [11], we propose a V-LDAA scheme in VANETs. The overall V-LDAA scheme includes Setup, Join, Create, Sign/verify, Revoke protocols. The structure of the DAA protocol is redesigned. After the Join phase, each user needs to pass through the Create phase to generate identity credentials PSCert=nymsig1sig2, where nym is a pseudonym public key, sig1 is the certificate used to determine the identity when the certificate is revoked, and sig2 is a blind signature on VID used to verify the identity of its legitimate users. Users can complete the anonymous authentication of the message and the self-revocation of the certificate by holding PSCert. TPM executes the destruction operation of the identity certificate and the pseudonymous certificate, generates the revocation certificate, and returns it to RA. RA verifies the identity certificate and the revocation certificate and confirms that the target vehicle has revoked its identity certificate.Moreover, we optimize the signature scheme based on automorphism stability of the power-of-two cyclotomic fields. When the user interacts with the CA to generate the VID, the identity ID is selected in the more optimalk=2 cyclotomic field, where Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq. At this time, it is enough to prove automorphism stability once instead of twice as in [11], which optimizes the computational efficiency and signature size during BlindSign. Finally, in the Join phase, the platform secret value sent to CA is changed to be generated by TPM and Host together instead of TPM alone. This is very important in VANETs, because the TPM chip embedded in the vehicle may be in an unmanned environment, and the adversary can directly steal the TPM chip and transplant it to another Host platform to cheat the verifier.


### 6.1. Setup

We consider a cyclotomic ringℛ=ℤX/Xd+1 , k=2 and identity ID in VID i∈Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq , which keeps stable under σ5. Randomly choose at=a1a2 as TPM public parameters, ah=a3a4 as Host public parameters and u←Rq as CA public parameter. The private key of CA is a trapdoor R←R2×2 while the public key is a←Rq, b=a1R. By Ring-LWE assumption, a,b is indistinguishable from uniform. Thus, we write CA public key as a|b, where a=a1.


### 6.2. Join

TPM randomly select a secret valuee=e1e2←R32 and a private key sk∈0,1256. Compute ut=a⋅e=a1e1+a2e2 and send ut to the Host. Similarly, the Host chooses its secret e′=e1e2←R32 and computes uh=a3e3+a4e4. Then, the Host adds ut and uh to generate u1. TPM and Host jointly give a zero-knowledge proof π1 of short e and e′. u1,π1 is sent by Host to CA. Because the Join protocol only needs to be executed once, the calculation of zero-knowledge proof has little effect on the efficiency of the entire protocol. We can choose the “Stern-type” protocol with the largest amount of calculation but the most accurate. CA first confirms the zero-knowledge proof and then uses MP−sampleralgorithm to sample s=s1s2 satisfying a|b+i⋅1q⋅s1s2=u+u1. Note that i∈Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq instead of an arbitrary i∈Rq. Finally, CA sends the generated identity certificate s,i to the Host and the Host saves it as VID.


### 6.3. Create

The Create protocol generatesPScert for vehicles to send and receive messages in VANETs, including pseudonym key pairs, identity certificate sig1 in revocation, and legal member certificates sig2. To generate pseudonym key pairs, TPM picks a basename bsn and creates a value d=HRqbsn as well as the pseudonym private key e1,e′, where e1 is a part of the TPM secret value and e′=HR3sk,bsn. TPM outputs nym=de1+e′∈Rq as pseudonym public key and creates sig1=HRqnym,e.Using theBlindSign protocol in Table 3, TPM and Host jointly sign the message “certified” with TPM private key e and the pseudonymous private key e1,e′ to generate a legal identity certificate sig2. BlindSign is a zero-knowledge proof of VID s,i completed by the Host and TPM interaction. That is, to prove that the Host has s,i satisfying a|b+i⋅1q⋅s1s2=u+a2⋅e. However, the verifier needs to know the value of a|b+i⋅1q in the scheme, among which a,b,1q are all public parameters, so the identity can be easily deduced, and the user’s identity will be leaked. Therefore, the zero-knowledge proof is not directly performed on i, but the commitment value about i is first generated, and the zero-knowledge proof is generated by replacing i with the commitment value. Bring the commitment value into the trapdoor function to get the following:(2)aT|bT+t2t2′|a2Ts1s2e−rr′s2=u,where t=t1t2=Comi,r and t′=t1′t2′=Comiδ,r′. Suppose vT=aT|bT+t2t2′|a2T and s′=s1s2e−rr′s2, then (2) can be expressed as vTs′=u.Table 3
BlindSign.
TPMPublic:nym,dPrivate:e′,e1HostMessage:μPublic:σ5,δ,vT,t,t′Private:r,r′,iye1,ye′⟵Dξt=dye1+ye′⟶ty,y′,y5←Dξ3ys1←Dξ14ys2←Dξ12ys=ys1,ys2π1′:W1=a1TyW1′=a1Ty′W2=δa2Ty−a2Ty′π2′:W1,5=σ5−1a1Ty5W2,5=a2Ty−σ5−1a2Ty5π3′:Ws=vTysSe1=ye1+ce1⟵cc=Hδ,σ5,W1,W1′,W2,W1,5,W2,5,Ws,μ,t,t,t′,vSe′=ye′+ce′if rejSe1|Se′,ce1,ce′,ξ=1,rebort⟶Se1,Se′π1′:z=rc+yz′=r′c+y′π2′:z5=σ5−1rc+y5π3′:zs=sc+ysif rejz|z|z5|zs,rc,r′c,σ5−1rc,sc,ξ=1,rebort⟶z,z′,z5,c,Se1,Se′In summary, the Host needs to generate three zero-knowledge proofs in parallel, that is,π1′: prove t, t' open to messages m, m' satisfying m′=δmπ2′: prove t opens to message m satisfying m=σ5mπ3′: prove s' satisfying vTs′=uFinally, the identity credentialsPSCert=nymsig1sig2 are generated and saved on the Host platform.


### 6.4. Sign/Verify

When the vehicle is moving in VANETs, the Host generates messages about the location and speed of the vehicle and transmits them to TPM. TPM signs messages usingSign protocol in Table 5 with pseudonym private key e1,e′ and pseudonym public key nym=de1+e′∈Rq and returns msign to Host. The Host creates msg=mplainmsignPSCert and sends it to the receiver. After receiving msg, the receiver first calls BlindVerify Protocol as in Table 4 to verify sig2, confirming that the message comes from a legal user. Then use pseudonym public key nym to verify msign as in Table 5.Table 4
BlindVerify.
HostVerifier⟶z,z′,z5,zs,c,Se1,Se′z,z′,z5,zs,Se1,Se′≤βz,π1′:W1′=a1Tz−t1cW1′=a1Tz′−t1′cW2′=δa2Tz−a2Tz′−δt2−t2′cπ2′:W1,5′=σ5−1a1Tz5−σ5−1t1cW2,5′=a2Tz−σ5−1a2Tz5−t2−σ5−1t2cπ3′:Ws′=vTzs−uct=dSe1+Se′−cnymifc=Hδ,σ5,W1′,W1′,W2′,W1,5′,W2,5′,Ws′,μ,t,t,t′,vOutput 1elseOutput 0Table 5
Sign and verify.
TPMPublic:a,y=as+ePrivate:s,eVerifierPublic:y,a,βzrs,re⟵Dξ,t=ars+rec=Ht,μzs=cs+rsze=ce+reif rejzs,ze,cs,ce,ξ=1,abort⟶t,c,zs,zet=azs+ze−cyifzs,ze≤βzandc=Ht,μOutput 1 else Output 0


### 6.5. Revoke

The revocation instructionmsg=revokenymreason generated by RA is encrypted with the RA private key skra and broadcast in VANETs so that all legitimate users can receive it. After receiving the message, the Host passes it on to TPM. TPM uses RA public key pkra to decrypt msg and recognizes that the target of the instruction is itself according to nym. Then TPM creates sig1ra=HRqnym,e and calls BlindSign to generate sig2ra on message “confirm,” which is used to prove that TPM has received the revocation instruction and completed the self-revocation. After that, TPM deletes its own public and private key pairs and all identity certificates independently. The Host sends sigrvk=sig1ra‖sig2ra to RA. Since RA has knowledge of the misbehaving vehicle’s PScert, it checks whether sig1=sig1ra and guarantees that the target vehicle has been revoked. Then, RA calls BlindVerify to confirm that sigrvk is indeed issued by the revoked vehicle.It can be seen from the entire revocation process that RA can correctly revoke the target vehicle without any pseudonym resolution operations. The vehicle provides RA with proof that the identity certificate has been forcibly revoked by TPM. If the vehicle wants to communicate with the users in VANETs again, it must rerun the Join phase to generate a new identity certificate.


## 6.1. Setup

We consider a cyclotomic ringℛ=ℤX/Xd+1 , k=2 and identity ID in VID i∈Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq , which keeps stable under σ5. Randomly choose at=a1a2 as TPM public parameters, ah=a3a4 as Host public parameters and u←Rq as CA public parameter. The private key of CA is a trapdoor R←R2×2 while the public key is a←Rq, b=a1R. By Ring-LWE assumption, a,b is indistinguishable from uniform. Thus, we write CA public key as a|b, where a=a1.


## 6.2. Join

TPM randomly select a secret valuee=e1e2←R32 and a private key sk∈0,1256. Compute ut=a⋅e=a1e1+a2e2 and send ut to the Host. Similarly, the Host chooses its secret e′=e1e2←R32 and computes uh=a3e3+a4e4. Then, the Host adds ut and uh to generate u1. TPM and Host jointly give a zero-knowledge proof π1 of short e and e′. u1,π1 is sent by Host to CA. Because the Join protocol only needs to be executed once, the calculation of zero-knowledge proof has little effect on the efficiency of the entire protocol. We can choose the “Stern-type” protocol with the largest amount of calculation but the most accurate. CA first confirms the zero-knowledge proof and then uses MP−sampleralgorithm to sample s=s1s2 satisfying a|b+i⋅1q⋅s1s2=u+u1. Note that i∈Sq=c0+c1Xd/2∈ℛq|c0,c1∈ℤq instead of an arbitrary i∈Rq. Finally, CA sends the generated identity certificate s,i to the Host and the Host saves it as VID.


## 6.3. Create

The Create protocol generatesPScert for vehicles to send and receive messages in VANETs, including pseudonym key pairs, identity certificate sig1 in revocation, and legal member certificates sig2. To generate pseudonym key pairs, TPM picks a basename bsn and creates a value d=HRqbsn as well as the pseudonym private key e1,e′, where e1 is a part of the TPM secret value and e′=HR3sk,bsn. TPM outputs nym=de1+e′∈Rq as pseudonym public key and creates sig1=HRqnym,e.Using theBlindSign protocol in Table 3, TPM and Host jointly sign the message “certified” with TPM private key e and the pseudonymous private key e1,e′ to generate a legal identity certificate sig2. BlindSign is a zero-knowledge proof of VID s,i completed by the Host and TPM interaction. That is, to prove that the Host has s,i satisfying a|b+i⋅1q⋅s1s2=u+a2⋅e. However, the verifier needs to know the value of a|b+i⋅1q in the scheme, among which a,b,1q are all public parameters, so the identity can be easily deduced, and the user’s identity will be leaked. Therefore, the zero-knowledge proof is not directly performed on i, but the commitment value about i is first generated, and the zero-knowledge proof is generated by replacing i with the commitment value. Bring the commitment value into the trapdoor function to get the following:(2)aT|bT+t2t2′|a2Ts1s2e−rr′s2=u,where t=t1t2=Comi,r and t′=t1′t2′=Comiδ,r′. Suppose vT=aT|bT+t2t2′|a2T and s′=s1s2e−rr′s2, then (2) can be expressed as vTs′=u.Table 3
BlindSign.
TPMPublic:nym,dPrivate:e′,e1HostMessage:μPublic:σ5,δ,vT,t,t′Private:r,r′,iye1,ye′⟵Dξt=dye1+ye′⟶ty,y′,y5←Dξ3ys1←Dξ14ys2←Dξ12ys=ys1,ys2π1′:W1=a1TyW1′=a1Ty′W2=δa2Ty−a2Ty′π2′:W1,5=σ5−1a1Ty5W2,5=a2Ty−σ5−1a2Ty5π3′:Ws=vTysSe1=ye1+ce1⟵cc=Hδ,σ5,W1,W1′,W2,W1,5,W2,5,Ws,μ,t,t,t′,vSe′=ye′+ce′if rejSe1|Se′,ce1,ce′,ξ=1,rebort⟶Se1,Se′π1′:z=rc+yz′=r′c+y′π2′:z5=σ5−1rc+y5π3′:zs=sc+ysif rejz|z|z5|zs,rc,r′c,σ5−1rc,sc,ξ=1,rebort⟶z,z′,z5,c,Se1,Se′In summary, the Host needs to generate three zero-knowledge proofs in parallel, that is,π1′: prove t, t' open to messages m, m' satisfying m′=δmπ2′: prove t opens to message m satisfying m=σ5mπ3′: prove s' satisfying vTs′=uFinally, the identity credentialsPSCert=nymsig1sig2 are generated and saved on the Host platform.


## 6.4. Sign/Verify

When the vehicle is moving in VANETs, the Host generates messages about the location and speed of the vehicle and transmits them to TPM. TPM signs messages usingSign protocol in Table 5 with pseudonym private key e1,e′ and pseudonym public key nym=de1+e′∈Rq and returns msign to Host. The Host creates msg=mplainmsignPSCert and sends it to the receiver. After receiving msg, the receiver first calls BlindVerify Protocol as in Table 4 to verify sig2, confirming that the message comes from a legal user. Then use pseudonym public key nym to verify msign as in Table 5.Table 4
BlindVerify.
HostVerifier⟶z,z′,z5,zs,c,Se1,Se′z,z′,z5,zs,Se1,Se′≤βz,π1′:W1′=a1Tz−t1cW1′=a1Tz′−t1′cW2′=δa2Tz−a2Tz′−δt2−t2′cπ2′:W1,5′=σ5−1a1Tz5−σ5−1t1cW2,5′=a2Tz−σ5−1a2Tz5−t2−σ5−1t2cπ3′:Ws′=vTzs−uct=dSe1+Se′−cnymifc=Hδ,σ5,W1′,W1′,W2′,W1,5′,W2,5′,Ws′,μ,t,t,t′,vOutput 1elseOutput 0Table 5
Sign and verify.
TPMPublic:a,y=as+ePrivate:s,eVerifierPublic:y,a,βzrs,re⟵Dξ,t=ars+rec=Ht,μzs=cs+rsze=ce+reif rejzs,ze,cs,ce,ξ=1,abort⟶t,c,zs,zet=azs+ze−cyifzs,ze≤βzandc=Ht,μOutput 1 else Output 0


## 6.5. Revoke

The revocation instructionmsg=revokenymreason generated by RA is encrypted with the RA private key skra and broadcast in VANETs so that all legitimate users can receive it. After receiving the message, the Host passes it on to TPM. TPM uses RA public key pkra to decrypt msg and recognizes that the target of the instruction is itself according to nym. Then TPM creates sig1ra=HRqnym,e and calls BlindSign to generate sig2ra on message “confirm,” which is used to prove that TPM has received the revocation instruction and completed the self-revocation. After that, TPM deletes its own public and private key pairs and all identity certificates independently. The Host sends sigrvk=sig1ra‖sig2ra to RA. Since RA has knowledge of the misbehaving vehicle’s PScert, it checks whether sig1=sig1ra and guarantees that the target vehicle has been revoked. Then, RA calls BlindVerify to confirm that sigrvk is indeed issued by the revoked vehicle.It can be seen from the entire revocation process that RA can correctly revoke the target vehicle without any pseudonym resolution operations. The vehicle provides RA with proof that the identity certificate has been forcibly revoked by TPM. If the vehicle wants to communicate with the users in VANETs again, it must rerun the Join phase to generate a new identity certificate.


## 7. Security Analysis

The security comparison between V-LDAA, the lattice-based ring signature schemes in [7, 8, 20], and the VPKI scheme in [1] are shown in Table 6. Compared with lattice-based ring signatures in VANETs, V-LDAA has the advantage of achieving user-controlled unlinkability and unforgeability. In contrast to the existing VPKI scheme, V-LDAA achieves postquantum security and realizes the user's independent pseudonym update scheme and the distributed vehicle certificate revocation scheme.Table 6
Security comparison.
Security requirementECPB in [20]DAPRS in [7]LRMA in [8]Scheme in [1]V-LDAAAnonymity✓✓✓✓✓Spontaneity✓✓✓✓✓Unforgeability✗✓✓✓✓Postquantum security✗✓✓✗✓User-controlled unlinkability✗✗✗✗✓Distributed revocation mechanism———✗✓Pseudonym update spontaneity———✗✓


### 7.1. Unforgeability

Suppose CA public parameters are set as follows:a|b,u,a2, where i∗∈Sq, R∈R12×2, R′←R4×2, su∈Dσ, g=1q, b=a⋅R−i∗g, a2=a|aR⋅R′, u=a|aR⋅su.Suppose we have a fake sampling algorithm. The adversary chooses the identityi∈Sq and secret value e. When i≠i∗, use the original MP−Sampler to generate s satisfying a|aR+i−i∗g⋅s=u+a2⋅e and output s to the adversary. When i=i∗, the gadget matrix vanishes and a|aR⋅s=u+a2⋅e. Therefore, compute s∗=su+R′e∗ , which is also a valid signature and output s∗ to the adversary and the adversary verifies a|aRs∗=u+a2⋅e∗. According to [11], based on Ring-LWE and NTRU assumptions, the adversary cannot distinguish whether it is generated by the real public parameters and the real preimage sampling algorithm or generated by the above public parameters and the fake preimage sampling algorithm.According to the above conclusion, we can prove the unforgeability of the V-LDAA signature.During BlindSign, the Host needs to generate a zero-knowledge proof aboutr,r′such that(3)a1′a2′⋅rr′+00ciciq=c⋅t11t12t21t22.In parallel, it will also prove that(4)a|b+t21t22⋅s1s2=cu+a2⋅e+a2′⋅r˜.Combine (3) and (4) to get the following:(5)ca|b+i⋅gs1s2+a2′r˜=c2u+ca2⋅e+ca2′⋅rr′s2.The adversary randomly selectsi∈Sq, and the probability of selecting i=i∗ is 1/q2. At this time i is vanished, that is,(6)ca|a⋅Rs1s2+a2′r˜=c2u+ca2⋅e+ca2′⋅rr′s2.Sampling algorithm outputse∗ satisfying the following:(7)c2a|bs1′s2′=c2u+a2⋅e∗.Subtract (6) and (7) to get the following:(8)acs1−c2s′+cRs2−c2Rs2′+a2c2e∗−ce+a2′r˜−crr′s2=0,which can be written as follows:(9)a|aR|a2|a2′⋅cs1−c2s′cs2−c2s′c2e∗−cer˜−rr′cs2=0.Becauses1, s′, c, e, e∗, s2 are all polynomials with small coefficients, (9) is a nonzero Ring-SIS solution to a|aR|a2|a2′ unless all multiplicands are 0. Therefore, if the adversary can successfully generate a zero-knowledge proof that satisfies (9), the Ring-SIS problem can be solved with a probability of 1/q2. To generate a zero solution, it requires c2e∗−ce=0. That is, ce∗=e, which means every e extracted from the zero-knowledge proof sig2 in the blind signing phase must be equal to a certain ce∗, where e∗ is a TPM secret value of a legal certificate VID generated in the Join phase. So far, the unforgeability of the V-LDAA signature can be proved. If the adversary wants to break the unforgeability, the difficulty of using the secret value of a platform without a legal identity certificate to generate a legal signature can be reduced to solve the Ring-SIS problem.


### 7.2. Anonymity

Anonymity means the adversary cannot extract the user identity valuei from the signature. Suppose the adversary knows the TPM private key sk1, sk2 and outputs the message m∗ to be signed and two identity values i1,i2 to the challenger. The challenger randomly selects an identity value i to sign and returns the signature to the adversary. After receiving the signature, the adversary guesses whether the identity value chosen by the challenger is i1 or i2. According to [19], the commitment scheme used in this article has hiding property based on the difficulty of M-LWE. That is, the adversary cannot distinguish the commitment value of two different messages. When signing, the challenger can replace the identity value at will to calculate the commitment value, and the generated signature is completely independent of the identity value i, so the difficulty of the adversary's guessing the id value used from the blind signature can be reduced to the M-LWE problem. In VANETs, the identity certificate generated in the Create stage only contains pseudonym information and does not contain any real identity information, and the TPM signing key cannot be associated with the vehicle user, so the adversary cannot distinguish different vehicles from the signature unless the user reveals his or her identity information.


### 7.3. User-Controlled Unlinkability

During Create protocol, the user can choose whether to use the same secret key sk to generate the same or different pseudonym private key so as to control whether the generated signature is linked. Once a different pseudonym is selected, the adversary cannot determine whether the two signatures are from the same user. Sincesig1 is generated by hashing the TPM private key and the pseudonym private key, the adversary cannot determine which TPM private key is used. In addition, sig2 is a blind signature and cannot be linked.


### 7.4. Unforgeability of Revocation Instruction

In order to prevent the adversary from maliciously revoking the legal vehicle, it should be ensured that the revocation instruction received by TPM is from the real RA and not forged by an adversary. Adding the signature of RA to each revocation instruction can meet this requirement. TPM can confirm the authenticity of the revocation instruction by verifying the RA signature.


### 7.5. Unforgeability of Revocation Certificate

When RA receives the revocation certificate returned by TPM, RA must ensure that it is from the correct target vehicle and has honestly performed certificate and key destruction operations. In V-LDAA, the credibility of the revocation operation is guaranteed by the trusted hardware chip TPM. By comparing the signatures in the revocation certificate, RA can confirm that the target vehicle has indeed performed the revocation operation. No other user can forge this signature as long as the TPM key is not leaked.


### 7.6. Consistency of Revocation Operation

When the revocation instruction is correctly delivered to TPM, TPM will perform a series of destruction operations. However, the revocation instruction needs to be passed through the Host. If the Host is controlled by an adversary and maliciously intercepts the transmission of the revocation instruction, TPM cannot receive the correct information from RA and cannot complete the revocation operation, which is a major challenge in the distributed revocation mechanism. In V-LDAA, TPM receives information from RA at fixed time intervals which include time stamps and RA’s signature. If TPM stops receiving the time stamp information, it is considered that the communication between TPM and RA interferes, and corresponding countermeasures should be taken.


## 7.1. Unforgeability

Suppose CA public parameters are set as follows:a|b,u,a2, where i∗∈Sq, R∈R12×2, R′←R4×2, su∈Dσ, g=1q, b=a⋅R−i∗g, a2=a|aR⋅R′, u=a|aR⋅su.Suppose we have a fake sampling algorithm. The adversary chooses the identityi∈Sq and secret value e. When i≠i∗, use the original MP−Sampler to generate s satisfying a|aR+i−i∗g⋅s=u+a2⋅e and output s to the adversary. When i=i∗, the gadget matrix vanishes and a|aR⋅s=u+a2⋅e. Therefore, compute s∗=su+R′e∗ , which is also a valid signature and output s∗ to the adversary and the adversary verifies a|aRs∗=u+a2⋅e∗. According to [11], based on Ring-LWE and NTRU assumptions, the adversary cannot distinguish whether it is generated by the real public parameters and the real preimage sampling algorithm or generated by the above public parameters and the fake preimage sampling algorithm.According to the above conclusion, we can prove the unforgeability of the V-LDAA signature.During BlindSign, the Host needs to generate a zero-knowledge proof aboutr,r′such that(3)a1′a2′⋅rr′+00ciciq=c⋅t11t12t21t22.In parallel, it will also prove that(4)a|b+t21t22⋅s1s2=cu+a2⋅e+a2′⋅r˜.Combine (3) and (4) to get the following:(5)ca|b+i⋅gs1s2+a2′r˜=c2u+ca2⋅e+ca2′⋅rr′s2.The adversary randomly selectsi∈Sq, and the probability of selecting i=i∗ is 1/q2. At this time i is vanished, that is,(6)ca|a⋅Rs1s2+a2′r˜=c2u+ca2⋅e+ca2′⋅rr′s2.Sampling algorithm outputse∗ satisfying the following:(7)c2a|bs1′s2′=c2u+a2⋅e∗.Subtract (6) and (7) to get the following:(8)acs1−c2s′+cRs2−c2Rs2′+a2c2e∗−ce+a2′r˜−crr′s2=0,which can be written as follows:(9)a|aR|a2|a2′⋅cs1−c2s′cs2−c2s′c2e∗−cer˜−rr′cs2=0.Becauses1, s′, c, e, e∗, s2 are all polynomials with small coefficients, (9) is a nonzero Ring-SIS solution to a|aR|a2|a2′ unless all multiplicands are 0. Therefore, if the adversary can successfully generate a zero-knowledge proof that satisfies (9), the Ring-SIS problem can be solved with a probability of 1/q2. To generate a zero solution, it requires c2e∗−ce=0. That is, ce∗=e, which means every e extracted from the zero-knowledge proof sig2 in the blind signing phase must be equal to a certain ce∗, where e∗ is a TPM secret value of a legal certificate VID generated in the Join phase. So far, the unforgeability of the V-LDAA signature can be proved. If the adversary wants to break the unforgeability, the difficulty of using the secret value of a platform without a legal identity certificate to generate a legal signature can be reduced to solve the Ring-SIS problem.


## 7.2. Anonymity

Anonymity means the adversary cannot extract the user identity valuei from the signature. Suppose the adversary knows the TPM private key sk1, sk2 and outputs the message m∗ to be signed and two identity values i1,i2 to the challenger. The challenger randomly selects an identity value i to sign and returns the signature to the adversary. After receiving the signature, the adversary guesses whether the identity value chosen by the challenger is i1 or i2. According to [19], the commitment scheme used in this article has hiding property based on the difficulty of M-LWE. That is, the adversary cannot distinguish the commitment value of two different messages. When signing, the challenger can replace the identity value at will to calculate the commitment value, and the generated signature is completely independent of the identity value i, so the difficulty of the adversary's guessing the id value used from the blind signature can be reduced to the M-LWE problem. In VANETs, the identity certificate generated in the Create stage only contains pseudonym information and does not contain any real identity information, and the TPM signing key cannot be associated with the vehicle user, so the adversary cannot distinguish different vehicles from the signature unless the user reveals his or her identity information.


## 7.3. User-Controlled Unlinkability

During Create protocol, the user can choose whether to use the same secret key sk to generate the same or different pseudonym private key so as to control whether the generated signature is linked. Once a different pseudonym is selected, the adversary cannot determine whether the two signatures are from the same user. Sincesig1 is generated by hashing the TPM private key and the pseudonym private key, the adversary cannot determine which TPM private key is used. In addition, sig2 is a blind signature and cannot be linked.


## 7.4. Unforgeability of Revocation Instruction

In order to prevent the adversary from maliciously revoking the legal vehicle, it should be ensured that the revocation instruction received by TPM is from the real RA and not forged by an adversary. Adding the signature of RA to each revocation instruction can meet this requirement. TPM can confirm the authenticity of the revocation instruction by verifying the RA signature.


## 7.5. Unforgeability of Revocation Certificate

When RA receives the revocation certificate returned by TPM, RA must ensure that it is from the correct target vehicle and has honestly performed certificate and key destruction operations. In V-LDAA, the credibility of the revocation operation is guaranteed by the trusted hardware chip TPM. By comparing the signatures in the revocation certificate, RA can confirm that the target vehicle has indeed performed the revocation operation. No other user can forge this signature as long as the TPM key is not leaked.


## 7.6. Consistency of Revocation Operation

When the revocation instruction is correctly delivered to TPM, TPM will perform a series of destruction operations. However, the revocation instruction needs to be passed through the Host. If the Host is controlled by an adversary and maliciously intercepts the transmission of the revocation instruction, TPM cannot receive the correct information from RA and cannot complete the revocation operation, which is a major challenge in the distributed revocation mechanism. In V-LDAA, TPM receives information from RA at fixed time intervals which include time stamps and RA’s signature. If TPM stops receiving the time stamp information, it is considered that the communication between TPM and RA interferes, and corresponding countermeasures should be taken.


## 8. Experimental Results and Analysis

We compare the performance of V-LDAA from two aspects: theoretical analysis and experimental simulation. Firstly, we compare V-LDAA with existing lattice-based authentication schemes in VANETs in Section8.1 to measure the advantages of V-LDAA in the scenario of the Internet of Vehicles. Secondly, the BlindSign protocol in V-LDAA is compared with that in existing LDAA in Section 8.2 to highlight the improvement of computing efficiency after adopting the optimized signature scheme as presented in Section 4.2. This article uses Python language and SageMath9.2 library to simulate V-LDAA, LRMA in [8], DAPRS in [7], and LDAA in [11], in which the polynomial multiplication is accelerated by the NTL library. Based on the Intel(R) Core (TM) i5-7500 CPU @3.40 GHz memory 8 GB processor, we tested the execution time and signature size of each scheme.


### 8.1. Comparison with Existing Lattice-Based Authentication Schemes in VANETs

We compare the proposed V-LDAA scheme with existing lattice-based authentication schemes in VANETs. Assuming that the time for a preimage sampling isTsamp, the time for a polynomial multiplication is Tmult, and the time for a zero-knowledge proof is TN. The signing and verification calculation costs and signature length of each scheme are shown in Table 7. The studies in [6–8, 21] are all lattice-based ring signature schemes. In the ring signature scheme, users need to use their private key and all other users’ public keys to sign messages. For a ring with numerous users, that is, when N is large, the computation burden is considerable. In addition, the members in a ring change as vehicles move. Thus, the member public key also needs to be updated consequently. However, in V-LDAA, users only need to sign with their pseudonym private keys each time, regardless of N.Table 7
Comparison of costs.
SignVerifySignature sizeScheme in [21]mTsamp+mN+1TmultMN+2TmultN+2mScheme in [6]5NTmultTN+5NTmult2N+1mDAPRS in [7]2NTmult2NTmultN+1mLRMA in [8]NTmultTmultN+1mV-LDAA2TmultTN+2Tmult3m+PSCertThe experimental results are shown in Figures3–6 . We implement Sign, Verify, BlindSign, and BlindVerify protocols and measure the running time. The results are shown in Figure 3. The execution time is averaged after 10 runs of each protocol. We also compare the V-LDAA scheme with DAPRS in [7] and LRMA in [8]. A lattice-based double-authentication-preventing ring signature (DAPRS) is introduced in [7] using double-authentication-preventing signatures (DAPSs) instead of conventional signatures. A lattice-based ring signature scheme for message authentication (LRMA) is presented in [8], providing unconditional privacy to vehicles. The number of users N varies from 50 to 200. The degree of cyclotomic d = 128, and q = 114356107. Since BlindSign protocol is called only when users want to update their pseudonyms and recreate PScert, we ignore the cost of BlindSign. In Figure 4, the signing time required for LRMA and DAPRS increases tremendously as the number of users rises, while in V-LDAA the execution time in signing operations maintains at a low level with slight fluctuations. In Figure 5, additional verification of PScert is required in V-LDAA, so the verification execution time is longer than LRMA when N is small but is exceeded as N increases. The size of the certificate generated by V-LDAA is significantly smaller than that of LRMA and DAPRS, as shown in Figure 6, and it will not increase with the growth of the number of users.Figure 3
V-LDAA protocol experimental results.Figure 4
Signing performance for V-LDAA, DAPRS in [7], and LRMA in [8].Figure 5
Verification performance for V-LDAA, DAPRS in [7], and LRMA in [8].Figure 6
Signature size for V-LDAA, DAPRS in [7], and LRMA in [8].


### 8.2. Comparison with the Existing LDAA Scheme

We compare the performance of the proposed V-LDAA protocol with the existing LDAA protocol in [11] during the blind signing and blind verification on computation and storage resource consumption. In the blind signing phase, V-LDAA adopts an optimized signature scheme which removes the proof for σ5m=m and thus reduces the number of response values to the challenge, so the number of polynomials that the generated signature contains is reduced from 40 in [11] to 36.In the Joining phase, V-LDAA adds public and secret values to the Host and enables the Host’s secret value to participate in the generation of the identity certificate. This change encourages TPM and Host to interact in the Joining phase to generate a zero-knowledge proof of their respective secret values. Although the amount of calculation is increased, considering that the long-term identity certificate of each legal user only needs to be generated once, it has little effect on the overall computing efficiency. In VANETs, the participation of TPM and Host in the generation of identity certificates can effectively resist TPM chip theft attacks and prevent TPM from being transplanted to a new vehicle platform by the adversary and signed with the replaced identity certificate. The experimental results are shown in Figure7, where d = 128, β = 128, and q = 114356107.Figure 7
Comparison among V-LDAA and LDAA in [12] in terms of signing execution time (a), verification execution time (b), and signature size (c).
(a)(b)(c)As shown in Figure7(a), the speed of the Host blind signing operation is increased by 30% by reducing the number of proofs for automorphism stability. The Host operation during blind verification is accelerated 3 times, according to Figure 7(b). Also, V-LDAA reduces the signature size by 18%, as in Figure 7(c).


## 8.1. Comparison with Existing Lattice-Based Authentication Schemes in VANETs

We compare the proposed V-LDAA scheme with existing lattice-based authentication schemes in VANETs. Assuming that the time for a preimage sampling isTsamp, the time for a polynomial multiplication is Tmult, and the time for a zero-knowledge proof is TN. The signing and verification calculation costs and signature length of each scheme are shown in Table 7. The studies in [6–8, 21] are all lattice-based ring signature schemes. In the ring signature scheme, users need to use their private key and all other users’ public keys to sign messages. For a ring with numerous users, that is, when N is large, the computation burden is considerable. In addition, the members in a ring change as vehicles move. Thus, the member public key also needs to be updated consequently. However, in V-LDAA, users only need to sign with their pseudonym private keys each time, regardless of N.Table 7
Comparison of costs.
SignVerifySignature sizeScheme in [21]mTsamp+mN+1TmultMN+2TmultN+2mScheme in [6]5NTmultTN+5NTmult2N+1mDAPRS in [7]2NTmult2NTmultN+1mLRMA in [8]NTmultTmultN+1mV-LDAA2TmultTN+2Tmult3m+PSCertThe experimental results are shown in Figures3–6 . We implement Sign, Verify, BlindSign, and BlindVerify protocols and measure the running time. The results are shown in Figure 3. The execution time is averaged after 10 runs of each protocol. We also compare the V-LDAA scheme with DAPRS in [7] and LRMA in [8]. A lattice-based double-authentication-preventing ring signature (DAPRS) is introduced in [7] using double-authentication-preventing signatures (DAPSs) instead of conventional signatures. A lattice-based ring signature scheme for message authentication (LRMA) is presented in [8], providing unconditional privacy to vehicles. The number of users N varies from 50 to 200. The degree of cyclotomic d = 128, and q = 114356107. Since BlindSign protocol is called only when users want to update their pseudonyms and recreate PScert, we ignore the cost of BlindSign. In Figure 4, the signing time required for LRMA and DAPRS increases tremendously as the number of users rises, while in V-LDAA the execution time in signing operations maintains at a low level with slight fluctuations. In Figure 5, additional verification of PScert is required in V-LDAA, so the verification execution time is longer than LRMA when N is small but is exceeded as N increases. The size of the certificate generated by V-LDAA is significantly smaller than that of LRMA and DAPRS, as shown in Figure 6, and it will not increase with the growth of the number of users.Figure 3
V-LDAA protocol experimental results.Figure 4
Signing performance for V-LDAA, DAPRS in [7], and LRMA in [8].Figure 5
Verification performance for V-LDAA, DAPRS in [7], and LRMA in [8].Figure 6
Signature size for V-LDAA, DAPRS in [7], and LRMA in [8].


## 8.2. Comparison with the Existing LDAA Scheme

We compare the performance of the proposed V-LDAA protocol with the existing LDAA protocol in [11] during the blind signing and blind verification on computation and storage resource consumption. In the blind signing phase, V-LDAA adopts an optimized signature scheme which removes the proof for σ5m=m and thus reduces the number of response values to the challenge, so the number of polynomials that the generated signature contains is reduced from 40 in [11] to 36.In the Joining phase, V-LDAA adds public and secret values to the Host and enables the Host’s secret value to participate in the generation of the identity certificate. This change encourages TPM and Host to interact in the Joining phase to generate a zero-knowledge proof of their respective secret values. Although the amount of calculation is increased, considering that the long-term identity certificate of each legal user only needs to be generated once, it has little effect on the overall computing efficiency. In VANETs, the participation of TPM and Host in the generation of identity certificates can effectively resist TPM chip theft attacks and prevent TPM from being transplanted to a new vehicle platform by the adversary and signed with the replaced identity certificate. The experimental results are shown in Figure7, where d = 128, β = 128, and q = 114356107.Figure 7
Comparison among V-LDAA and LDAA in [12] in terms of signing execution time (a), verification execution time (b), and signature size (c).
(a)(b)(c)As shown in Figure7(a), the speed of the Host blind signing operation is increased by 30% by reducing the number of proofs for automorphism stability. The Host operation during blind verification is accelerated 3 times, according to Figure 7(b). Also, V-LDAA reduces the signature size by 18%, as in Figure 7(c).


## 9. Conclusion

To solve the security and user privacy issues in VANETs, we propose a lattice-based direct anonymous attestation scheme in VANETs that achieves postquantum security. We introduce a lattice-based long-term certificate generation mechanism, a pseudonym certificate renewal mechanism, and a distributed certificate revocation mechanism. Users can update the pseudonym certificate by themselves and control the linkability of signatures. RA does not need to perform pseudonym resolution or maintain CRLs, which overcomes the shortcomings of the traditional VPKIs. We also demonstrate that V-LDAA has significant advantages in computing efficiency and storage consumption compared with the existing lattice-based direct anonymous attestation by adopting an optimized signature scheme based on automorphism stability. Experimental results show that V-LDAA reduces the signature size by 18%. And the speed of blind signing is increased by 30% and blind verification operations are accelerated 3 times compared with the existing LDAA scheme. The main shortcoming of the proposed V-LDAA scheme is the computation and storage costs in the BlindSign protocol. In future work, we will aim to further optimize the proposed scheme to make it more suitable for resource-constrained TPM chips and vehicle platforms.



---

*Source: 4660875-2021-09-02.xml*