Direct anonymous attestation scheme with outsourcing capability

• US 20100082973A1
• Filed: 09/29/2008
• Published: 04/01/2010
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernie, Li, Jiangtao
• Granted Patent: US 8,145,897 B2
• Time in Patent Office: Days
• US Class Current: 713/155
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A Direct Anonymous Attestation (DAA) scheme using elliptic curve cryptography (ECC) and bilinear maps. A trusted platform module (TPM) may maintain privacy of a portion of a private membership key from an issuer while joining a group. Moreover, the TPM can outsource most of the computation involved in generating a signature to a host computer.

Claims

1. A method comprising:

generating a portion of a signature at a first computer;

the first computer requesting a second computer to generate a second portion of the signature while maintaining privacy of the portion of the private membership key; and

generating the second portion of the signature at the second computer.

2. The method of claim 1, wherein the portion of the private membership key comprises a private membership exponent.

3. The method of claim 1, wherein the generating a portion of a signature at a first computer comprises:

determining a base and a pseudonym at the first computer.

4. The method of claim 3, wherein the determining a base and a pseudonym at the first computer comprises:

the first computer determining B=H₃(bsn_v) and

the first computer determining K=B^f, wherein bsn_v comprises a basename value and f comprises the private membership exponent.

5. The method of claim 1, wherein the generating a portion of a signature at a first computer comprises the first computer determining:

c=H(H_x, nd, m) and sf=rf+c·

f mod p, wherein H_x are determined by the second computer.

6. The method of claim 1, wherein the generating the second portion of the signature at the second computer comprises:

determining random values used to determine commitment values of the signature; and

determining commitment values of the signature.

7. The method of claim 6, wherein

determining random values used to determine commitment values of the signature comprises the second computer selecting values a, b randomly from [0, p−

1] and

determining commitment values of the signature comprises the second computer determining T₁=A·

h₂^a and T₂=h₁^a·

h₂^b.

8. The method of claim 1, wherein the generating the second portion of the signature at the second computer comprises:

the second computer determining;

(1) d=x·

a mod p;

(2) e=x·

b mod p;

the second computer randomly picking six integers rx, ry, ra, rb, rd, re from [0, p−

1];

the second computer determining;

(1) R₁=h₁^ra·

h₂^rb;

(2) R₂=h₁^rd·

h₂^re·

T₂<sup>−

rx</sup>;

(3) R₄=e(T₁, g₂)<sup>−

rx</sup>·

e(Rd, g₂)·

e(h₂, g₂)^ry+rd·

e(h₂, w)^ra; and

(4) H_x=H(p, g₁, g₂, g₃, h₁, h₂, w, B, K, T₁, T₂, R₁, R₂, R₃, R₄).

9. The method of claim 1, wherein the generating the second portion of the signature at the second computer comprises the second computer determining:

(1) sx=rx+c·

x (mod p),

(2) sy=ry+c·

y (mod p),

(3) sa=ra+c·

a (mod p),

(4) sb=rb+c·

b (mod p),

(5) sd=rd+c·

d (mod p), and

(6) se=re+c·

e (mod p).

10. The method of claim 1, wherein the generating the second portion of the signature at the second computer comprises the second computer setting the signature as:

σ

=(B, K, T₁, T₂, c, nd, sx, sy, sf, sa, sb, sd, se), wherein B, K, c, nd, and sf are transmitted by the first computer to the second computer.

11. The method of claim 1, wherein the first computer requesting a second computer to generate a second portion of the signature while maintaining privacy of the portion of the private membership key comprises:

the first computer transmitting (A, x, y) to the second computer, while keeping f secret.

12. The method of claim 1, wherein the first computer comprises a trusted platform module and the second computer comprises a host computer communicatively coupled to the first computer.

13. A method comprising:

requesting admission to a group while maintaining privacy of a first portion of a private membership key.

14. The method of claim 13, wherein the first portion comprises a private membership exponent.

15. The method of claim 14, wherein the private membership exponent is selected at random from [0, p−

1], where p is a prime order of a bilinear group associated with the group.

16. The method of claim 13, wherein the requesting admission comprises:

transmitting a commitment of the first portion.

17. The method of claim 13, further comprising:

receiving a second portion of the private membership key;

receiving a value;

determining a third portion of the private membership key from the value; and

storing the first, second, and third portions of the private membership key.

18. The method of claim 13, wherein the private membership key comprises A, x, y, f.

19. The method of claim 13, further comprising:

determining whether a first computer is capable of joining the group; and

determining whether a signature from the first computer is valid, wherein the determining whether a first computer is capable of joining a group and determining whether a signature from a first computer is valid both comprise performing a revocation check over the same elliptic curve group.

20. A method comprising:

generating a signature at a first computer;

transmitting the signature to a second computer while maintaining privacy of a first portion of a private key of the first computer; and

verifying the signature.

21. The method of claim 20, wherein the private key comprises (A, x, y, f) and wherein the first portion comprises the value A.

22. The method of claim 20, wherein the verifying comprises:

receiving a signature comprising (B, K, T₁, T₂, c, nd, sx, sy, sf, sa, sb, sd, se);

verifying that B, K are elements in a first bilinear group;

verifying that T₁, T₂ are elements in a second bilinear group;

verifying that sx, sy, sf, sa, sb, sd, se are integers between [0, p−

1];

determining R₁=h₁^sa·

h₂^sb·

T₂<sup>−

c</sup>;

determining R₂=h₁^sd·

h₂^se·

T₂<sup>−

sx</sup>;

determining R₃=B^sf·

K<sup>−

c</sup>;

determining R₄=e(T₁, g₂)<sup>−

sx</sup>·

e(h₁, g₂)^sf·

e(h₂, g₂)^sy+sd·

e(h₂, w)^sa·

(e(g₁, g₂)/e(T₁, w))^c;

verifying that c=H(H(p, g₁, g₂, g₃, h₁, h₂, w, B, K, T₁, T₂, R₁, R₂, R₃, R₄), nd, m); and

for each fi in the revocation list, checking that K≠

B^fi.

23. An article of manufacture including a machine readable medium having instructions stored thereon, which when executed cause a machine to:

generate a portion of a signature at a first computer; and

request a second computer to generate a second portion of the signature while maintaining privacy of a portion of the private membership key.

24. The article of manufacture of claim 23, wherein the portion of the private membership key comprises a private membership exponent.

25. The article of manufacture of claim 23, wherein the first computer comprises a trusted platform module and the second computer comprises a host computer communicatively coupled to the first computer.

26. A system comprising:

a prover platform coupled to the network, wherein the prover platform comprises a Trusted Platform Module (TPM) and a host computer, wherein;

the TPM is to generate a portion of a signature and

the TPM is to request the host computer to generate a second portion of the signature while maintaining privacy of a portion of the private membership key; and

a verifier coupled to a network, wherein the verifier is to verify the signature.

27. The system of claim 26, wherein the portion of the private membership key comprises a private membership exponent.

28. The system of claim 26, wherein the TPM is to request admission to a group while maintaining privacy of a private membership exponent.

29. The system of claim 26, wherein the verifier is to verify the signature from the prover platform while the prover platform maintains privacy of a second portion of the private membership key.

30. The system of claim 26, further comprising an issuer, wherein:

the issuer is to determine whether the prover platform is capable of joining a group and

the verifier is to determine whether the signature from the prover platform is valid, wherein to determine whether the prover platform is capable of joining a group and to determine whether a signature from the prover platform is valid both comprise performance of a revocation check over the same elliptic curve group.