# Property-Based Anonymous Attestation in Trusted Cloud Computing

Authors: Zhen-Hu Ning; Wei Jiang; Jing Zhan; Peng Liang
Journal: Journal of Electrical and Computer Engineering
 (2014)

---

## Abstract

In the remote attestation on Trusted Computer (TC) computing mode TCCP, the trusted computer TC has an excessive burden, and anonymity and platform configuration information security of computing nodes cannot be guaranteed. To overcome these defects, based on the research on and analysis of current schemes, we propose an anonymous proof protocol based on property certificate. The platform configuration information is converted by the matrix algorithm into the property certificate, and the remote attestation is implemented by trusted ring signature scheme based on Strong RSA Assumption. By the trusted ring signature scheme based on property certificate, we achieve the anonymity of computing nodes and prevent the leakage of platform configuration information. By simulation, we obtain the computational efficiency of the scheme. We also expand the protocol and obtain the anonymous attestation based on ECC. By scenario comparison, we obtain the trusted ring signature scheme based on RSA, which has advantages with the growth of the ring numbers.


---

## Body

## 1. Introduction

With the development of information technology, cloud computing has been the important trend of the third revolution in information technology, after the personal computer and the Internet, and the focus of industry and, Science [1]. Many cloud providers offer services at various layers of the cloud computing. Weather providers offer services of basic computational infrastructure and allow their customers to develop their own applications and effectively control their own computations and data, PaaS providers allow their costumers to develop cloud applications of their own, or SaaS providers allow their costumers to create their own documents using the applications  and to get out of control of their computations and data. So the trustiness attestation to platforms becomes an important problem needed to be resolved in cloud computing [2].A security scheme was supported in [3, 4] based on the research on the potential security problems existing in current IasS. In this scheme, hardware, network connection, platform virtualization, software for cloud computing, utility computing, and service level agreement are enhanced in the IaaS.Trusted computing was introduced into IaaS firstly and a concept called Trusted Cloud Computing Platform (TCCP) was proposed in [5, 6]. All virtual computing nodes are guaranteed to be trusted by configuration-based remote attestation. However, since the configuration of the latest restart of the platform is static, the dynamic attacks such as buffer overflow and DMA attack cannot be handled. Moreover, since the signature is carried out by the Endorsement Key of TPM, the leakage of privacy may be caused based on the fact that the usage of Endorsement Key can be tracked.A remote attestation for virtual computing node was supported in [7, 8]. The following events such as changing, updating, and patching the configuration of virtual platform are updated in the attestation by TPM. However, this scheme is actually a static remote attestation based on configuration and it cannot attest the running states of virtual computing node.The authors in [7, 8] support remote attestation for virtual machine; virtual TPM is improved to update attestation by the means of the following events such as changing, updating, and patching the configuration of virtual platform. However, it is actually a static remote attestation based on configuration, while it cannot attest the running states of virtual platform. Additionally, this scheme only deals with the trust root based on software and lacks both trusted guarantee provided by TPM and attestation of physical platform on which the virtual machines are running.The goal of trusted computing is to improve the security and trustworthiness of computing platforms [9–12], and the well-known group—TCG—has published many specifications, such as the Trusted Platform Module (TPM) [13, 14] and library Trusted Software Stack (TSS) [15].Remote attestation is one of the core technologies of trusted computing. In TCG1.1 specification, the attestation is designed with challenge information in plain text [16, 17]. In the process of the remote attestation, one platform sends a challenge information and random number to obtain one or more PCR values in order to validate the platform state. Each TPM has only an Endorsement Key (EK), issued by the TPM manufacturers, to identify the identity of the Trusted Platform. For security and privacy, EK does not directly support encryption or remote attestation. Instead, using the signature key AIK generated by EK and registered by PCA to achieve the remote attestation, the attestor signs the PCR with AIK and sends the signature and the corresponding measure attached log SML and AIK certificate to the challenger. Then, the challenger verifies the proof to guarantee the trust and security of the platform.However, the proof protocol has some evident shortage. First, the protocol uses PCR to achieve the proof, which will expose the local platform configuration information (including hardware and software). Second, the proof protocol cannot guarantee the anonymity of attestor.In recent years, Direct Anonymous Attestation (DAA) [18, 19] has been proposed as the protocol of remote attestation between platforms. The protocol has become part of TCG1.2 specification. DAA protocol is based on three entities, that is, the TPM platform, DAA signatory, and DAA verifiers. The DAA protocol consists of two steps. First, the signatory validates TPM platform and generates the DAA certificate for the TPM platform. Second, the TPM platform interacts with verifiers using the DAA certificate. By zero-knowledge proof, verifiers verify the DAA certificate without violating the premise of the platform privacy. However, since the DAA protocol has many times of zero-knowledge proof, which induces very large computational complexity, the DAA protocol is difficult to be a viable protocol.A property-based attestation for computing platforms was introduced in [20]. A trusted third party converts the platform configuration information into the property certificates, which can avoid the leakage of information of platform. Based on [20], the paper in [21] proposed a protocol for property-based attestation. Property certificates corresponding to the platform configuration information are issued and managed by a trusted third-party CA; the protocol achieves anonymous proof by a series of complex interactions’ agreement. However, lots of zero-knowledge proofs may induce a high complexity. Moreover, the trusted third party must know all of the platform status information, which is actually to transfer part of work of the verifiers to a trusted third party and to increase the burden of CA. The paper [19] proposed an anonymous protocol of remote attestation based on property certificates. Due to involvement of lots of interactions, the computational complexity is very large.Remote attestation based on the TCCP has many defects. First, every proof involves the operation of TC, which aggravates the burden of TC. Second, the remote attestation cannot guarantee the anonymity of platform. To overcome these defects, we introduce a protocol based on trusted ring signature. In the protocol, the signature of both the public and the private keys is replaced with TPM signature key, so that the security of remote attestation is guaranteed by TPM. The proof does not directly require TC, and TC only provides a series of TPM signature public keys, which reduces the burden on TC. Trusted ring signature can guarantee unconditional anonymity of the signature party and protect the privacy of the platform.


## 2. Protocol Description

In this paper, the process of remote attestation consists of two steps. First, TC converts the platform configuration information PCR of computing nodes into property certificate. Second, computing nodes provide the property certificate for verifier by remote attestation. Figure1 shows the interactions of the protocol.Figure 1
The interactions of the remote attestation.


### 2.1. Property Certificate Issue

The Trusted Computer (TC) is responsible for the issue of the property certificates of the corresponding computing nodes. TC has all of the property certificates of the platform, denoted asP={P1,…,Pn}. Let {PCR1,…,PCRm} denote all of the platform configuration information PCRs. We define the set C={C1,….,Cm} as follows.If the remote attestation ofPCRi is verified as in [3, 4], then Ci=1. Otherwise, Ci=0. The map between property certificates and corresponding platform configuration information is defined as follows:
(1)P=AC,A=(a11⋯a1m⋮⋱⋮an1⋯anm),
where aij is 0 or 1 and Pi=⋂aij=1Cj. If Pi=⋂aij=1Cj, then TC issues a property certificate Pi, which identifies a platform that has the property Pi. Otherwise, TC issues the property certificate which indicates that the platform does not have the property Pi.For example, if the computing nodeNinvolves the property certificate Pi, then computing nodeNrequires a series of remote attestations of {PCRj∣aij=1}. Then, TC issues property certificate Pi in accordance with the above-described method and sends property certificate Pi to TPMNsecurely.We simplify the process as follows.(1)
TPMN checks the current PCR to determine whether it needs to start the process of generating the property certificates. If the current PCR is not equal to the PCR used to generate the latest property certificate by TC, TPMNstart the process of generating the property certificates.(2)
TC sends the challengeNT PCRs toN.(3)
TPMN sends the result of the remote signature Sig{PCR,NT}Sk,PCR,SML to TC.(4)
TC uses PCR to generate the property certificates.


## 2.1. Property Certificate Issue

The Trusted Computer (TC) is responsible for the issue of the property certificates of the corresponding computing nodes. TC has all of the property certificates of the platform, denoted asP={P1,…,Pn}. Let {PCR1,…,PCRm} denote all of the platform configuration information PCRs. We define the set C={C1,….,Cm} as follows.If the remote attestation ofPCRi is verified as in [3, 4], then Ci=1. Otherwise, Ci=0. The map between property certificates and corresponding platform configuration information is defined as follows:
(1)P=AC,A=(a11⋯a1m⋮⋱⋮an1⋯anm),
where aij is 0 or 1 and Pi=⋂aij=1Cj. If Pi=⋂aij=1Cj, then TC issues a property certificate Pi, which identifies a platform that has the property Pi. Otherwise, TC issues the property certificate which indicates that the platform does not have the property Pi.For example, if the computing nodeNinvolves the property certificate Pi, then computing nodeNrequires a series of remote attestations of {PCRj∣aij=1}. Then, TC issues property certificate Pi in accordance with the above-described method and sends property certificate Pi to TPMNsecurely.We simplify the process as follows.(1)
TPMN checks the current PCR to determine whether it needs to start the process of generating the property certificates. If the current PCR is not equal to the PCR used to generate the latest property certificate by TC, TPMNstart the process of generating the property certificates.(2)
TC sends the challengeNT PCRs toN.(3)
TPMN sends the result of the remote signature Sig{PCR,NT}Sk,PCR,SML to TC.(4)
TC uses PCR to generate the property certificates.


## 3. Anonymous Attestation Based on RSA

### 3.1. Attestation Execution

Before attestation, TPM generates a signature key(pk,sk);sk is stored by TPM and pk is registered by TC, so that TC stores all of the signature public keys of computing nodes in cloud computing. In the remote attestation, TC supports signature public keys required in the trusted ring signature. Let H:{0,1}*→{0,1}k be secure hash function. The process of remote attestation is as follows.LetA be user and letB be cloud computing node;B provides remote attestation forA, andA verifies the attestation.(1)
A sends request for remote attestation and NA∈{0,1}k toB.(2)
TPMB obtains t-1 valid signature public keys pk2,…,pkt from TC. We assume that TPMB has signature key (pk1,sk1).(3)
TPMB generates the signature of PL with pk2,…,pkt. Let D{data,K} denote decryption byK, and let E{data,K} denote encryption byK; TPMB chooses NB,r2,…,rt∈{0,1}k and generates the signature as follows:
(2)M=D{NB,pkA},ci=D{ri,pki}(2≤i≤t),c1=H(PL∥NA∥NB)-∑i=2tci,r1=E(c1,sk1).(4)
B sends pk1,…,pkt, r1,…,rt, M,PL toA.(5)
A verifies the signature as follows:
(3)NB=E{M,skA},∑i=1tD{ri,pki}=H(PL∣NA∥NB).(6)
A verifies the property certificate PL and sendsNBtoB.(7)
B verifiesNBto guarantee the success of the remote attestation.Remark 1.
Sincepk1,…,pkt are different from each other, then, we can choose suitable NB to overcome this aforementioned shortcoming, because the protocol has requirement that pk1,…,pkt have the same bits, for example, 2048 bits.


### 3.2. Correctness

In the signature scheme, the signing and verifying are consistent with each other as follows:(4)∑i=1tD{ri,pki}=D{r1,pk1}+∑i=2tD{ri,pki}=c1+∑i=2mci=H(PL∥NA∥NB).


### 3.3. Unconditional Anonymity

Ring signature scheme is characterized by anonymity. LetSig={r1,…,rm} be a valid ring signature for message m, and let Ui be a member of the ring. Then Ui can generate the ring signature. From the verification, we can obtain that the probability that the user distinguishes the signer is 1/t. So the scheme is unconditional anonymous.


### 3.4. Security Analysis

The security analysis is based on the Strong RSA Assumption. Strong RSA Assumption is a given RSA modulus, and a given random numberz<N. It is difficult to find r,y(r>1,y<N), satisfying yr=z.The proof of security can be simplified as the following theorem.Theorem 2.
Assume that the attacker F with the ability of adaptive chosen message and identity can break our scheme by a nonnegligible probabilityε within PPT time. Then, there exists an algorithm C, which can solve the problem of the Strong RSA Assumption by a nonnegligible probability ε′=O(ε) within PPT time, where O(ε) represents O(ε)≥kε, andkis a constant not dependent on ε.Proof.
We assume that C is a challenger. The target of C is to obtain a solution of the Strong RSA Assumption by F.(1)
Setup. C runs the setup algorithm. C maintainst signature public keys pk1,…,pkt. Let H1,H2 be two random oracles, and the construction of the machine H1,H2 is listed as follows. C sends {pk1,…,pkt,H1,H2} to the attacker F as public parameters.(2)
InquiringH1. C maintains a list H1L containing the array {NAi,hi}. C chooses qH2 random numbers h1,…,hqH1as answers. When F inquires H1-value of NAi, C recovers {NAi,hi} from H1L and sends hi to F.(3)
InquiringH2. C maintains a list of the array {NAi,Ri},Ri={r2,…,rt}. C chooses qH2 random numbers R1,…,RqH2as answers. When F inquires H2-value of NAi, C recovers {NAi,Ri} from H2L and sends Ri to F.(4)
Inquiring Signature. C maintains a list of the array {NAi,Ri′},Ri′={r1,…,rt}=r1∪Ri. When F inquires signature of NAi, C checks whether NAi is in H1L. Then, C recovers {NAi,Ri′} and sends Ri′ to F.
C simulates TPM, and the attacker F makes interaction with C. The output of C obeys the above strategy.
Then, F stops inquiring, and F generates a signatureR′ about NA (NA has never been asked) by simulating TPM, which meets Ver(NA,pk1,…,pkt,R′)=1. C recovers {NA,h} from H1L and recovers {NA,R} from H2L. Letting c=h-∑i=2tri, we have cpk=r1, which resolves the problem of Strong RSA Assumption.
It is easy to obtain that the probability that C successfully resolved the problem of Strong RSA Assumption isε′=O(ε). There is a question that c=h-∑i=2tri had been asked before the signature. However, by a simple analysis, we can obtain that the probability is 1/2k, which can be omitted. So the probability that C successfully resolves the problem of Strong RSA Assumption is also ε′=O(ε).


### 3.5. Efficiency

In our trusted ring signature scheme, there are three operations that are involved, such as nonsymmetric encryption, nonsymmetric decryption, and hash operations. LetE denote the nonsymmetric encryption operation, letD denote the nonasymmetric decryption operation, and letH denote hash operation. The efficiency of the signature is listed as follows.In the remote attestation, the computing node conducts nonsymmetric encryption once, nonsymmetric decryptiontmany times, and hash operation once. Then, the total amount of calculation is E+(t-1)D+H, see Table 1.Table 1
The efficiency of the signature.
E
D
H
Amount of calculation of the computing node
1
t
-
1
1
Amount of calculation of the user
0
t
1Since the hash operation can be omitted with respect to the nonsymmetric operation, the amount of calculation of computing node can be simply represented by the nonsymmetric encryptionE. By calculation, the total amount of calculation is approximately S=(1+4t/3n)E.


## 3.1. Attestation Execution

Before attestation, TPM generates a signature key(pk,sk);sk is stored by TPM and pk is registered by TC, so that TC stores all of the signature public keys of computing nodes in cloud computing. In the remote attestation, TC supports signature public keys required in the trusted ring signature. Let H:{0,1}*→{0,1}k be secure hash function. The process of remote attestation is as follows.LetA be user and letB be cloud computing node;B provides remote attestation forA, andA verifies the attestation.(1)
A sends request for remote attestation and NA∈{0,1}k toB.(2)
TPMB obtains t-1 valid signature public keys pk2,…,pkt from TC. We assume that TPMB has signature key (pk1,sk1).(3)
TPMB generates the signature of PL with pk2,…,pkt. Let D{data,K} denote decryption byK, and let E{data,K} denote encryption byK; TPMB chooses NB,r2,…,rt∈{0,1}k and generates the signature as follows:
(2)M=D{NB,pkA},ci=D{ri,pki}(2≤i≤t),c1=H(PL∥NA∥NB)-∑i=2tci,r1=E(c1,sk1).(4)
B sends pk1,…,pkt, r1,…,rt, M,PL toA.(5)
A verifies the signature as follows:
(3)NB=E{M,skA},∑i=1tD{ri,pki}=H(PL∣NA∥NB).(6)
A verifies the property certificate PL and sendsNBtoB.(7)
B verifiesNBto guarantee the success of the remote attestation.Remark 1.
Sincepk1,…,pkt are different from each other, then, we can choose suitable NB to overcome this aforementioned shortcoming, because the protocol has requirement that pk1,…,pkt have the same bits, for example, 2048 bits.


## 3.2. Correctness

In the signature scheme, the signing and verifying are consistent with each other as follows:(4)∑i=1tD{ri,pki}=D{r1,pk1}+∑i=2tD{ri,pki}=c1+∑i=2mci=H(PL∥NA∥NB).


## 3.3. Unconditional Anonymity

Ring signature scheme is characterized by anonymity. LetSig={r1,…,rm} be a valid ring signature for message m, and let Ui be a member of the ring. Then Ui can generate the ring signature. From the verification, we can obtain that the probability that the user distinguishes the signer is 1/t. So the scheme is unconditional anonymous.


## 3.4. Security Analysis

The security analysis is based on the Strong RSA Assumption. Strong RSA Assumption is a given RSA modulus, and a given random numberz<N. It is difficult to find r,y(r>1,y<N), satisfying yr=z.The proof of security can be simplified as the following theorem.Theorem 2.
Assume that the attacker F with the ability of adaptive chosen message and identity can break our scheme by a nonnegligible probabilityε within PPT time. Then, there exists an algorithm C, which can solve the problem of the Strong RSA Assumption by a nonnegligible probability ε′=O(ε) within PPT time, where O(ε) represents O(ε)≥kε, andkis a constant not dependent on ε.Proof.
We assume that C is a challenger. The target of C is to obtain a solution of the Strong RSA Assumption by F.(1)
Setup. C runs the setup algorithm. C maintainst signature public keys pk1,…,pkt. Let H1,H2 be two random oracles, and the construction of the machine H1,H2 is listed as follows. C sends {pk1,…,pkt,H1,H2} to the attacker F as public parameters.(2)
InquiringH1. C maintains a list H1L containing the array {NAi,hi}. C chooses qH2 random numbers h1,…,hqH1as answers. When F inquires H1-value of NAi, C recovers {NAi,hi} from H1L and sends hi to F.(3)
InquiringH2. C maintains a list of the array {NAi,Ri},Ri={r2,…,rt}. C chooses qH2 random numbers R1,…,RqH2as answers. When F inquires H2-value of NAi, C recovers {NAi,Ri} from H2L and sends Ri to F.(4)
Inquiring Signature. C maintains a list of the array {NAi,Ri′},Ri′={r1,…,rt}=r1∪Ri. When F inquires signature of NAi, C checks whether NAi is in H1L. Then, C recovers {NAi,Ri′} and sends Ri′ to F.
C simulates TPM, and the attacker F makes interaction with C. The output of C obeys the above strategy.
Then, F stops inquiring, and F generates a signatureR′ about NA (NA has never been asked) by simulating TPM, which meets Ver(NA,pk1,…,pkt,R′)=1. C recovers {NA,h} from H1L and recovers {NA,R} from H2L. Letting c=h-∑i=2tri, we have cpk=r1, which resolves the problem of Strong RSA Assumption.
It is easy to obtain that the probability that C successfully resolved the problem of Strong RSA Assumption isε′=O(ε). There is a question that c=h-∑i=2tri had been asked before the signature. However, by a simple analysis, we can obtain that the probability is 1/2k, which can be omitted. So the probability that C successfully resolves the problem of Strong RSA Assumption is also ε′=O(ε).


## 3.5. Efficiency

In our trusted ring signature scheme, there are three operations that are involved, such as nonsymmetric encryption, nonsymmetric decryption, and hash operations. LetE denote the nonsymmetric encryption operation, letD denote the nonasymmetric decryption operation, and letH denote hash operation. The efficiency of the signature is listed as follows.In the remote attestation, the computing node conducts nonsymmetric encryption once, nonsymmetric decryptiontmany times, and hash operation once. Then, the total amount of calculation is E+(t-1)D+H, see Table 1.Table 1
The efficiency of the signature.
E
D
H
Amount of calculation of the computing node
1
t
-
1
1
Amount of calculation of the user
0
t
1Since the hash operation can be omitted with respect to the nonsymmetric operation, the amount of calculation of computing node can be simply represented by the nonsymmetric encryptionE. By calculation, the total amount of calculation is approximately S=(1+4t/3n)E.


## 4. Anonymous Attestation Based on ECC

### 4.1. Attestation Execution

LetG1,G2 be defined as multiplicative group whose order isp, and g is the generator of G1. Bilinear map is G1×G1→G2, where e(g,g)=I. Let x1,…,xn be TPM signature private keys and let gx1,…,gxn be the corresponding TPM signature public keys.LetA be user and letB be cloud computing node;B provides remote attestation forA, andA verifies the attestation.(1)
A sends request for remote attestation and NA∈Zq* toB.(2)
TPMB obtains t-1 valid signature public keys pk2,…,pkt from TC. We assume that TPMB has signature key (pk1,sk1).(3)
TPMB generates the signature of PL with pk2,…,pkt. TPMB chooses r2,…,rt∈Zq* and generates the signature as follows:
(5)P=H(PL∥NA),si=gri(2≤i≤t),s1=1x1(P-∑i=2tpkiri).(4)
B sends pk1,…,pkt, s1,…,st, PL toA.(5)
A verifies the signature as follows:
(6)e(P,g)=∏i=1te(pki,si).(6)
A verifies the property certificate PL.This anonymous attestation is based on Boneh’s ring signature scheme [20]. We obtain the analysis of the scheme as follows.


### 4.2. Correctness

In the signature scheme, the signing and verifying are consistent with each other as follows:(7)∏i=1te(pki,si)=e(pk1,s1)∏i=2te(pki,si)=e(g,P-∑i=2tgxiri)∏i=2te(g,gxiri)=e(P,g).


### 4.3. Unconditional Anonymity

Similar with anonymous attestation based on ECC, we can easily obtain that the probability that the user distinguishes the signer is1/t. So the scheme is unconditional anonymous.


### 4.4. Security Analysis

The security analysis is based on the CDHI problem. CDHI problem is a givengx(x is unknown). It is difficult to calculate g1/x. Similar to Theorem 2, we can obtain the following theorem.Theorem 3.
Assume that the attacker F with the ability of adaptive chosen message and identity can break our scheme by a nonnegligible probabilityε within PPT time. Then, there exists an algorithm C, which can solve the problem of the CDHI problem by a nonnegligible probability ε′=O(ε) within PPT time, where O(ε) represents O(ε)≥kε,andk is a constant not dependent on ε.


### 4.5. Efficiency

In the remote attestation, the computing node conducts ECC2t-1times and hash operation once. Then, the total amount of calculation is T=(2t-1)E~+H, where E~ is the ECC encryption.


## 4.1. Attestation Execution

LetG1,G2 be defined as multiplicative group whose order isp, and g is the generator of G1. Bilinear map is G1×G1→G2, where e(g,g)=I. Let x1,…,xn be TPM signature private keys and let gx1,…,gxn be the corresponding TPM signature public keys.LetA be user and letB be cloud computing node;B provides remote attestation forA, andA verifies the attestation.(1)
A sends request for remote attestation and NA∈Zq* toB.(2)
TPMB obtains t-1 valid signature public keys pk2,…,pkt from TC. We assume that TPMB has signature key (pk1,sk1).(3)
TPMB generates the signature of PL with pk2,…,pkt. TPMB chooses r2,…,rt∈Zq* and generates the signature as follows:
(5)P=H(PL∥NA),si=gri(2≤i≤t),s1=1x1(P-∑i=2tpkiri).(4)
B sends pk1,…,pkt, s1,…,st, PL toA.(5)
A verifies the signature as follows:
(6)e(P,g)=∏i=1te(pki,si).(6)
A verifies the property certificate PL.This anonymous attestation is based on Boneh’s ring signature scheme [20]. We obtain the analysis of the scheme as follows.


## 4.2. Correctness

In the signature scheme, the signing and verifying are consistent with each other as follows:(7)∏i=1te(pki,si)=e(pk1,s1)∏i=2te(pki,si)=e(g,P-∑i=2tgxiri)∏i=2te(g,gxiri)=e(P,g).


## 4.3. Unconditional Anonymity

Similar with anonymous attestation based on ECC, we can easily obtain that the probability that the user distinguishes the signer is1/t. So the scheme is unconditional anonymous.


## 4.4. Security Analysis

The security analysis is based on the CDHI problem. CDHI problem is a givengx(x is unknown). It is difficult to calculate g1/x. Similar to Theorem 2, we can obtain the following theorem.Theorem 3.
Assume that the attacker F with the ability of adaptive chosen message and identity can break our scheme by a nonnegligible probabilityε within PPT time. Then, there exists an algorithm C, which can solve the problem of the CDHI problem by a nonnegligible probability ε′=O(ε) within PPT time, where O(ε) represents O(ε)≥kε,andk is a constant not dependent on ε.


## 4.5. Efficiency

In the remote attestation, the computing node conducts ECC2t-1times and hash operation once. Then, the total amount of calculation is T=(2t-1)E~+H, where E~ is the ECC encryption.


## 5. Formalized Proof of the Protocol

Here, we give the key exchange process of the protocol. LetKTC_B be the shared key between TC and TPMB, and let KTC_A be the shared key between TC andA; the target of this section is to obtain the shared key KAB betweenA and TPMB. The detailed process is listed as follows:
(8)A⟶CM,CM⟶B:A,NA,B⟶TC:A,B,NB,TC⟶B:{{NA,KAB,CM}KTC_ANB,KAB,A,nnnnnnnnnnn{NA,KAB,CM}KTC_A}KTC_B,B⟶A:{NA,KAB,CM}KTC_A{N}KAB,B⟶CM,CM⟶A:{N+1}KAB.To guarantee the anonymity ofB, the shared key KAB is actually a shared key between CM andA.A does not know thatB is the signer.Here, we use the Ban Logic [21] to obtain the formalized proof of the protocol.Detailed description of the protocol is the following:(9)TC⟶B:{NB,A↔KABBnnnnnnnn{NA,A↔KABB}KTC_A}KTC_B,(10)B⟶A:{NA,A↔KABB}TC_A,{N,A↔KABB}KAB,(11)A⟶B:{N,(A↔KABB)}KAB.Assumption is as follows:(12)A|≡A↔KTC_ATC,(13)B|≡B↔KTC_BTC,(14)TC|≡A↔KTC_ATC,(15)TC|≡B↔KTC_BTC,(16)TC|≡A↔KABB.The credibility of TC is given as follows:(17)A|≡(TC∣≡A↔KABB),(18)B|≡(TC∣≡A↔KABB),(19)A|≡(TC⟹#(A↔KABB)),(20)B|≡(TC⟹#(A↔KABB)).Freshness of random numbers is given as follows:(21)A|≡#(NA),(22)B|≡#(NB),(23)B|≡#(N).Target of the protocol is the following:(24)A|≡A↔KABB,(25)B|≡A↔KABB,(26)A|≡B|≡A↔KABB,(27)B|≡A|≡A↔KABB.Some rules of the Ban Logic applied in this paper are listed as follows:(28)P|≡Q↔KP,P⊲{X}KP|≡Q~X,(29)P|≡#(X),P|≡Q|~XP|≡Q|≡X,(30)P|≡Q|⟹P,P|≡Q|≡XP|≡X,(31)P|≡X,P|≡YP|≡(X,Y),(32)P|≡(X,Y)P|≡X,(33)P|≡Q|≡(X,Y)P|≡Q|≡X,(34)P|≡Q|~(X,Y)P|≡Q|~X,(35)P⊲(X,Y)P⊲X,(36)P|≡Q↔KP,P⊲{X}KP⊲X,(37)P|≡#(X)P|≡#(X,Y).Proof.
From (9), we have
(38)B⊲{(NB,A↔KABB),nnnn{NA,A↔KABB}KTC_A}KTC_B.
From (13) and (27), we obtain
(39)B|≡TC~(NB,A↔KABB),B|≡TC~{NA,A↔KABB}KTC_A.
It follows from (22) and (29) that
(40)B|≡TC|≡(NB,A↔KABB),B|≡TC|≡{NA,A↔KABB}KTC_A.
By (22) and (33), we obtain
(41)B|≡TC|≡A↔KABB,B|≡#(A↔KABB).
By (18), (20), and (30), we have
(42)B|≡A↔KABB.
Then, (25) holds true.
It follows from (10) that
(43)A⊲{NA,A↔KABB}KTCA,(44)A⊲{N,A↔KABB}KAB.
By (13) and (27), we have
(45)A|≡TC~{NA,A↔KABB}.
It follows from (21) and (29) that
(46)A|≡TC|≡{NA,A↔KABB}.
By (18), (20), and (30), we obtain
(47)A|≡TC|≡A↔KABB,(48)B|≡#(A↔KABB).
By (17), (19), and (30), we have
(49)A|≡A↔KABB.
Then, (24) holds true.
With (44) and (49), we have
(50)A|≡B~{N,A↔KABB}.
It follows from (48) that
(51)A|≡B|≡{N,A↔KABB}.
Then,
(52)A|≡B|≡A↔KABB.
Then, (26) holds true.
From (10), we have
(53)B⊲{N,A↔KABB}.
By (27) and (42), we obtain
(54)B|≡A~{N,A↔KABB}.
Then, we have
(55)B|≡A|≡A↔KABB.


## 6. Scenario Comparison

Compared with anonymous attestation based on ECC, whose amount of calculation isT=(2t-1)E~+H, then we have
(56)TS=tE~(1+4t/3n)E=3nE~4E×2-(1/t)3n/4t+1.Then,lim⁡t→∞⁡T/S=3nE~/2E. So it means that if S>T, then E~<2E/3n which is hard to meet, since modern commercial ECC computing cannot have both a stronger security than RSA-2048 and a less calculation satisfying E~<2E/3n. So the anonymous attestation based on RSA has advantages with the growth of the ring numbers.


## 7. Conclusion

In this paper, we studied the anonymous remote attestation based on property certificate. We obtained property certificates by matrix replacement algorithm from platform configuration information and designed a trusted ring signature based on RSA Strong Assumption. By an analysis, the scheme is effective to resolve the security of cloud computing nodes. By simulation, we obtained the computational efficiency of the scheme. We also expand the protocol to the anonymous attestation based on ECC and give the scenario comparison between two schemes. However, in this paper, we only use the operation and deduce the property value, which has some limitations. So it is the next work to expand the scheme and make it more applicable.



---

*Source: 687158-2014-03-25.xml*