Direct anonymous attestation scheme with outsourcing capability

• US 8,145,897 B2
• Filed: 09/29/2008
• Issued: 03/27/2012
• Est. Priority Date: 09/29/2008
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernie, Li, Jiangtao
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US12/286,303
• Publication Number:
  US 20100082973A1
• Time in Patent Office: 1,275 Days
• Field of Search: 713/155, 713/176, 713/180, 726/5, 380/277, 380/283
• 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 first portion of a signature for use in authentication by an encryption device, the encryption device requesting a host computer to generate a second portion of the signature while maintaining privacy of the first and second portion of the signature, the first portion of the signature including a private membership key; and

receiving at the encryption device the second portion of the signature from the host computer including a private membership exponent.

2. The method of claim 1, further comprising:

the encryption device determining a base (B) where B=H₃(bsn_v) and

the encryption device determining a pseudonym (K) where K=B^f, wherein bsn_v comprises a basename value, f comprises the private membership exponent and H( ) is a hashing function.

3. The method of claim 2, wherein the generating the first portion of the signature at the encryption device further comprises:

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

f (mod p), wherein H_x is received from the host computer, nd is a random 80 bit integer, m is a message, rf and f are random numbers in [0, p−

1], and p is a prime order of a bilinear group.

4. The method of claim 3, wherein the generating the second portion of the signature at the host computer comprises:

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

determining commitment values of the signature.

5. The method of claim 4, wherein determining random values used to determine commitment values of the signature comprises the host computer selecting values a, b randomly from [0, p−

1] and

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

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

h₂^b.

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

the host computer determining;

(1) d=x·

a mod p;

(2) e=x·

b mod p;

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

1];

the host 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₄).

7. The method of claim 6, wherein the generating the second portion of the signature at the host computer comprises the host 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).

8. The method of claim 7, wherein the generating the second portion of the signature at the host computer comprises the host 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 encryption device to the host computer.

9. The method of claim 8, wherein the encryption device requesting the host computer to generate the second portion of the signature while maintaining privacy of the first portion of the private membership key comprises:

the encryption device transmitting (A, x, y) to the host computer, while keeping f secret.

10. The method of claim 1, wherein the encryption device comprises a trusted platform module and the host computer is communicatively coupled to the encryption device.

11. A method comprising:

requesting, by a first computer, admission to a group from an issuer computer while maintaining privacy of a first portion of a private membership key by transmitting a commitment of the first portion to the issuer computer;

receiving a second portion of the private membership key from the issuer computer;

receiving a value;

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

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

12. The method of claim 11, wherein the first portion comprises a private membership exponent.

13. The method of claim 12, 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.

14. The method of claim 13, wherein the private membership key comprises A, x, y, f where A, x and y are values computed by the issuer computer and f is a random number from [0, p−

1].

15. The method of claim 11, further comprising:

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

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

16. A method comprising:

receiving a signature for authentication from a first computer at a second computer, the signature including a first portion of a private key of the first computer wherein the private key comprises (A, x, y, f) and wherein the first portion comprises the value A where A x and are values computed by an issuer computer and f is a random number from [0, p−

1] and p is a prime order of a bilinear group; and

verifying the signature.

17. The method of claim 16, wherein the verifying comprises:

receiving the 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₂)^sx·

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,

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

f (mod p) wherein H_x is received from the host computer, nd is a random 80 bit integer, m is a message, rf and f are random numbers in [0, p−

1], and p is a prime order of a bilinear group.

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

generating a first portion of a signature for use in authentication by an encryption device, the encryption device requesting a host computer to generate a second portion of the signature while maintaining privacy of the first and second portion of the signature, the first portion of the signature including a private membership key; and

receiving at the encryption device the second portion of the signature from the host computer including a private membership exponent.

19. The article of manufacture of claim 18, wherein the encryption device is a trusted platform module and the host computer is communicatively coupled to the encryption device.

20. A system comprising:

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

the TPM is to generate a first portion of a signature for use in authentication by the TPM, the TPM requesting a host computer to generate a second portion of the signature while maintaining privacy of the first and second portion of the signature, the first portion of the signature including a private membership key, and the TPM to receive the second portion of the signature from the host computer including a private membership exponent.

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

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

23. The system of claim 22, further comprising an issuer, wherein:

the issuer is to determine whether the prover platform is capable of joining the 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 the group and to determine whether the signature from the prover platform is valid both comprise performance of a revocation check over a same elliptic curve group.