Malleable pseudonym certificate system and method

• US 20070143608A1
• Filed: 09/20/2006
• Published: 06/21/2007
• Est. Priority Date: 09/21/2005
• Status: Active Application

• Current Assignee: NEC China Co Ltd (NEC Corporation)
• Original Assignee: NEC China Co Ltd (NEC Corporation)
• Inventors: Fujita, Tomoyuki, Zeng, Ke, Hsueh, Min-Yu
• Application Number:
  US11/523,597
• Publication Number:
  US 20070143608A1
• Time in Patent Office: Days
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• 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/3255 using group based signatures, e.g. ring or threshold signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

The invention provides a malleable pseudonym certificate system and method for a communication network. According to one embodiment of the invention, a user acquires a root proof from a trusted entity, generates one or more pseudonym certificates based on the root proof, and sends anonymous public keys each equipped with one pseudonym certificate to verifiers. Through use of the pseudonym certificate, the verifier believes that the user'"'"'s anonymous public key is certified by the trusted entity. The pseudonym certificate contains no information by which the verifier can figure out the real identity of the user. With the malleable pseudonym certificate system, the trusted entity needs only certify once for the user'"'"'s root public key. The user can generate by him or herself mass anonymous public keys where each anonymous public key is equipped with a distinct pseudonym certificate.

Claims

1. A computing apparatus for a user to certify a data in a communication network, said networking including a trusted entity and at least one verifier, said computing apparatus comprising:

a root proof unit, operatively coupled to said network, said root proof unit being adapted to receive a root proof from said trusted entity;

a pseudonym certificate generating unit, operatively coupled to said root proof unit, said pseudonym certificate generating unit being adapted to generate at least one pseudonym certificate based on said root proof; and

a transmission unit, operatively coupled to said pseudonym certification generating unit, said transmission unit being adapted to transmit said user'"'"'s data, coupled with said pseudonym certificate, to said communication network.

2. The computing apparatus of claim 1, wherein said pseudonym certificate is generated such that it contains no information by which said verifier can figure out the real identity of said user.

3. The computing apparatus of claim 1, wherein said user'"'"'s data contains a public key of said user.

4. The computing apparatus of claim 3, wherein said public key contained in said user'"'"'s data is an incomparable public key.

5. The computing apparatus of claim 3, wherein

said public key contained in said user'"'"'s data is an anonymous public key, and said computing apparatus further comprises an anonymous public key generating unit, operatively coupled to said transmission unit, said anonymous public key generating unit being adapted to generate a plurality of anonymous public keys of said user, said plurality of anonymous public keys being corresponding to a private key of said user.

6. The computing apparatus of claim 5, wherein said anonymous public key generating unit generates said plurality of anonymous public keys from said private key and a generator, said private key and said generator being from a predetermined group.

7. The computing apparatus of claim 1, wherein said root proof is a root certificate issued to said user by said trusted entity.

8. The computing apparatus of claim 1, wherein said root proof is a group private key of said user, and wherein said pseudonym certificate is a group signature of said user'"'"'s data.

9. The computing apparatus of claim 1, further comprising a root proof requesting unit, operatively coupled to said network, said root proof requesting unit being adapted to generate a request for said root proof and transmit said request to said trusted entity.

10. The computing apparatus of claim 1, further comprising a proving unit, operatively coupled to said network, the proving unit being adapted to perform knowledge proof with said trusted entity or said verifier.

11. A method for a user to certify a data in a communication network, said networking including a trusted entity and at least one verifier, said method comprising:

receiving a root proof from said trusted entity;

generating at least one pseudonym certificate based on said root proof; and

transmitting said user'"'"'s data coupled with one pseudonym certificate to one verifier.

12. The method of claim 11, wherein said pseudonym certificate is generated such that it contains no information by which said verifier can figure out the real identity of said user.

13. The method of claim 11, wherein said user'"'"'s data contains a public key of said user.

14. The method of claim 13, wherein said public key contained in said user'"'"'s data is an incomparable public key.

15. The method of claim 13, wherein

said public key contained in said user'"'"'s data is an anonymous public key, and the method further comprises generating a plurality of anonymous public keys by said user, said plurality of anonymous public keys being corresponding to a private key of said user.

16. The method of claim 15, wherein said plurality of anonymous public keys are generated from said private key and a generator, said private key and said generator being from a predetermined group.

17. The method of claim 11, wherein said root proof is a root certificate issued to said user by said trusted entity.

18. The method of claim 11, wherein said root proof is a group private key of said user, and wherein said pseudonym certificate is a group signature of said user'"'"'s data.

19. The method of claim 11, further comprising generating a request for said root proof and transmitting said request to said trusted entity.

20. The method of claim 11, further comprising performing knowledge proof with said trusted entity or said verifier.

21. An apparatus for managing certificates in a communication network, said networking

including at least one user and at least one verifier, said apparatus comprising:

a system parameter computing unit being adapted to compute system parameters;

a parameter publishing unit, operatively coupled to said system parameter computing unit, said parameter publishing unit being adapted to publish shared system parameters which are to be shared by said user and verifier;

a root proof request receiving unit, operatively coupled to said network, said root proof request receiving unit being adapted to receive a root proof request from said user; and

a root proof generating unit, operatively coupled to said root proof request receiving unit and said system parameter computing unit, said root proof generating unit being adapted to generate a root proof for said user in response to said root proof request, said root proof being used for the user to generate a plurality of pseudonym certificates.

22. The apparatus of claim 21, wherein said root proof is a root certificate issued to a public key of said user.

23. The apparatus of claim 21, wherein said root proof is a root certificate issued to a root anonymous public key of said user.

24. The apparatus of claim 21, wherein said root proof is a group private key issued to said user.

25. The apparatus of claim 21, further comprising an examining unit, operatively coupled to said root proof generating unit, said examining unit is adapted to perform identification examination on said root proof request.

26. The apparatus of claim 21, further comprising an tracing unit, operatively coupled to said network, said tracing unit is adapted to trace the identity of the owner of a pseudonym certificate received from said verifier based on said root proof.

27. A method for managing certificates in a communication network, said networking including at least one user and at least one verifier, said method comprising:

computing system parameters;

publishing shared system parameters, which are to be shared by said user and verifier;

receiving a root proof request from said user; and

generating a root proof for said user in response to said root proof request, said root proof being used for the user to generate a plurality of pseudonym certificates.

28. The method of claim 27, wherein said generating a root proof comprises generating a root certificate issued to a public key of said user.

29. The method of claim 27, wherein said generating a root proof comprises generating a root certificate issued to a root anonymous public key of said user.

30. The method of claim 27, wherein said generating a root proof comprises generating a group private key issued to said user.

31. The method of claim 27, further comprising performing identification examination on said root proof request after receiving said root proof request.

32. The method of claim 27, further comprising tracing the identity of the owner of a pseudonym certificate received from said verifier based on said root proof.

33. A malleable pseudonym certificate system for a user in a communication network, said networking including a trusted entity, said system comprising:

a root proof unit, operatively coupled to said network, said root proof unit being adapted to receive a root proof from said trusted entity;

a pseudonym certification generating unit, operatively coupled to said root proof unit, said pseudonym certification generating unit being adapted to generate at least one pseudonym certificate based on said root proof;

a transmission unit, operatively coupled to said pseudonym certification generating unit, said transmission unit being adapted to transmit said user'"'"'s data, coupled with said pseudonym certificate, to said communication network; and

a verifier unit, operatively coupled to said communication network, said verifier unit being adapted to verify said user'"'"'s data by the pseudonym certificate received.

34. The system of claim 33, wherein said pseudonym certificate is generated such that it contains no information by which the verifier unit can figure out the real identity of said user.

35. The system of claim 33, wherein said user'"'"'s data contains a public key of said user.

36. The system of claim 35, wherein said public key contained in said user'"'"'s data is an incomparable public key.

37. The system of claim 35, wherein

said public key contained in said user'"'"'s data is an anonymous public key, and the system further comprises an anonymous public key generating unit, operatively coupled to said transmission unit, said anonymous public key generating unit being adapted to generate a plurality of anonymous public keys of said user, said plurality of anonymous public keys being corresponding to a private key of said user.

38. The system of claim 37, wherein said anonymous public key generating unit generates said plurality of anonymous public keys from said private key and a generator, said private key and said generator being from a predetermined group.

39. The system of claim 33, wherein said root proof is a root certificate issued to said user by said trusted entity.

40. The system of claim 33, wherein said root proof is a group private key of said user, and wherein said pseudonym certificate is a group signature of said user'"'"'s data.

41. The system of claim 33, wherein said verifier unit comprises:

a verification module for performing verification on said pseudonym certificate and said user'"'"'s data.

42. The system of claim 41, wherein said verifier unit further comprises:

a memory couple to said verification module for storing the data that have been verified correctly; and

a comparison module operatively coupled to said memory and said verification module, said comparison module is adapted to compare the received user'"'"'s data with said stored data.

43. The system of claim 33, further comprising a tracing unit, operatively coupled to said verifier unit, said tracing unit is adapted to trace the identity of the owner of a pseudonym certificate received from said verifier unit based on said root proof.

44. A method of certifying a user'"'"'s data by a pseudonym certificate in a communication network, said networking including a trusted entity and at least one verifier, comprising:

issuing a root proof from said trusted entity to said user;

generating at least one pseudonym certificate based on said root proof by the user; and

transmitting said user'"'"'s data coupled with one pseudonym certificate to one verifier, said verifier verifying said user'"'"'s data by said pseudonym certificate.

45. The method of claim 44, wherein said pseudonym certificate is generated such that it contains no information by which said verifier can figure out the real identity of said user.

46. The method of claim 44, wherein said user'"'"'s data contains a public key of said user.

47. The method of claim 46, wherein said public key contained in said user'"'"'s data is an incomparable public key.

48. The method of claim 46, wherein

said public key contained in said user'"'"'s data is an anonymous public key, and the method further comprises generating a plurality of anonymous public keys by said user, said plurality of anonymous public keys being corresponding to a private key of said user.

49. The method of claim 48, wherein said plurality of anonymous public keys are generated from said private key and a generator, said private key and said generator being from a predetermined group.

50. The method of claim 44, wherein issuing a root proof comprises issuing a root certificate to a public key of said user.

51. The method of claim 44, wherein issuing a root proof comprises issuing a group private key to said user, and said generating at least one pseudonym certificate comprises generating a group signature of said user'"'"'s data.

52. The method of claim 44, wherein said verifier verifies said pseudonym certificate and said user'"'"'s data by performing knowledge proof with said user.

53. The method of claim 44, wherein said verifier verifies said pseudonym certificate and said user'"'"'s data by:

storing the data that have been verified correctly by said verifier;

comparing the user'"'"'s data received from said user with said stored data;

If said user'"'"'s data matches one of said stored data, performing knowledge proof concerning said user'"'"'s data with said user; and

If said user'"'"'s data does not match any one of said stored data, performing verification on said pseudonym certificate and said user'"'"'s data.

54. The method of claim 44, further comprising tracing by said trusted entity the identity of the owner of a pseudonym certificate received from said verifier based on said root proof.

55. A manufacturing article having a machine readable medium with instructions recorded thereon which, when executed by one or more processors, causes the processors to:

receive a root proof from a trusted entity;

generate at least one pseudonym certificates from said root proof; and

transmit a data, coupled with one of said pseudonym certificates, to a verifier.

56. The manufacturing article of claim 55, wherein said data is an anonymous public key.

57. A manufacturing article having a machine readable medium with instructions recorded thereon which, when executed by a processor, cause the processor to:

compute system parameters;

publish shared parameters, which are to be shared by all users of a network;

receive a root proof request from one of said users of the network; and

generate a root proof for said user, said root proof being used for said user to generate a plurality of pseudonym certificates.

58. The manufacturing article of claim 57, wherein said root proof is a root certificate for a root anonymous public key of said user.