Anonymous transactions based on distributed processing

• US 20030048906A1
• Filed: 05/10/2002
• Published: 03/13/2003
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: HTC Corporation
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Knapp, Verna E., Vora, Poorvi L.
• Granted Patent: US 7,187,772 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: G06Q 20/00 Payment architectures, schemes or protocols apparatus for performing or posting payment transactions G07F7/08, G07F19/00; electronic cash registers G07G1/12
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: G06Q 20/385 using an alias or single-use codes
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

An entity that desires to engage in anonymous transactions first generates a transaction identification that does not uniquely identify the entity. Additionally, the entity splits an entity identification uniquely associated with the entity into a plurality of secret shares and thereafter sends the transaction identification and the plurality of secret shares to a plurality of shareholders. Subsequently, anonymous transactions on behalf of the entity may be directly conducted by the shareholders based in part upon the plurality of secret shares. In one embodiment of the present invention, the entity identification comprises a public key uniquely assigned to the entity.

Claims

1. A method for an entity to support anonymous transactions, the method comprising:

generating a transaction identification that does not uniquely identify the entity;

splitting an entity identification uniquely associated with the entity into a plurality of secret shares; and

sending the transaction identification and the plurality of secret shares to a plurality of shareholders.

2. The method of claim 1, further comprising:

splitting an encryption key associated with the entity into a plurality of entity encryption key shares; and

sending the plurality of entity encryption key shares to the plurality of shareholders.

3. The method of claim 2, wherein the entity identification and the encryption key are the same.

4. The method of claim 3, wherein the entity identification is a public key uniquely associated with the entity.

5. The method of claim 2, wherein an encryption scheme in which the encryption key is used has a property that encrypted data resulting from encryption of data based on the encryption key is equivalent to a product of encrypted data portions based on the plurality of entity encryption key shares, wherein each encrypted data portion results from encryption of the data based on one of the plurality of entity encryption key shares.

6. The method of claim 1, wherein the entity identification is a linear combination of the plurality of entity identification secret shares.

7. The method of claim 1, further comprising:

sending an acquisition request and the transaction identification to at least one shareholder of the plurality of shareholders.

8. The method of claim 7, further comprising:

sending payment information and the transaction identification to the at least one shareholder.

9. The method of claim 1, further comprising:

sending a recommendation request and the plurality of secret shares to corresponding ones of the plurality of shareholders.

10. The method of claim 1, further comprising:

sending a voucher verification request and the plurality of secret shares to corresponding ones of the plurality of shareholders.

11. A method for an entity to support anonymous acquisitions, the method comprising:

generating a transaction identification that does not uniquely identify the entity;

distributing a public key, in the form of secret shares, and the transaction identification to a plurality of shareholders;

sending an acquisition request regarding goods to be acquired and the transaction identification to at least one shareholder of the plurality of shareholders;

receiving, based on the transaction identification, encrypted information from at least one shareholder of the plurality of shareholders, wherein the encrypted information comprises information regarding the goods and is encrypted, at least in part, by the plurality of shareholders based on each of the secret shares; and

decrypting the encrypted information based on the public key.

12. The method of claim 11, wherein the encrypted information is progressively encrypted by the plurality of shareholders based on each of the secret shares.

13. The method of claim 11, wherein receiving the encrypted information further comprises receiving, from at least one shareholder of the plurality of shareholders, encrypted information portions, wherein each encrypted information portion results from encryption of the information regarding the goods based on at least one of the secret shares, the method further comprising:

calculating the product of the encrypted information portions to provide the encrypted information.

14. The method of claim 11, further comprising, prior to receiving the encrypted information:

receiving a challenge request from a shareholder of the plurality of shareholders, the challenge request comprising encrypted challenge data;

decrypting the encrypted challenge data based on the public key to provide decrypted challenge data; and

sending the decrypted challenge data to the shareholder.

15. The method of claim 11, wherein the encrypted information comprises the goods.

16. The method of claim 11, wherein the encrypted information comprises an encryption key needed to access the goods.

17. The method of claim 11, further comprising:

sending payment information and the transaction identification to the at least one shareholder.

18. The method of claim 11, further comprising:

receiving, responsive to the acquisition request, recommendations from the at least one shareholder.

19. The method of claim 11, further comprising:

sending, to the plurality of shareholders, a voucher verification request regarding at least one usage right and the secret shares, wherein each shareholder of the plurality of shareholders has previously associated at least one usage right corresponding to the entity with the secret share maintained by the shareholder; and

receiving, from at least one shareholder of the plurality of shareholders, a message indicating that at least some of the at least one usage right is available to the entity.

20. A method for an entity to obtain recommendations, the method comprising:

sending, to a plurality of shareholders, a recommendation request and secret shares previously sent by the entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one activity corresponding to the entity with a secret share maintained by the shareholder; and

receiving, from at least one shareholder of the plurality of shareholders, at least one recommendation responsive to the recommendation request.

21. The method of claim 20, further comprising, prior to receiving the at least one recommendation:

receiving a challenge request from a shareholder of the plurality of shareholders, the challenge request comprising encrypted challenge data;

decrypting the encrypted challenge data to provide decrypted challenge data; and

sending the decrypted challenge data to the shareholder.

22. A method for an entity to verify availability of usage rights, the method comprising:

sending, to a plurality of shareholders, a voucher verification request regarding at least one usage right and secret shares previously sent by the entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one usage right corresponding to the entity with a secret share maintained by the shareholder; and

receiving, from at least one shareholder of the plurality of shareholders, a message indicating that the at least one usage right is available to the entity.

23. The method of claim 22, further comprising, prior to receiving the message:

receiving a challenge request from a shareholder of the plurality of shareholders, the challenge request comprising encrypted challenge data;

decrypting the encrypted challenge data to provide decrypted challenge data; and

sending the decrypted challenge data to the shareholder.

24. A method for a shareholder of a plurality of shareholders, in communication with an entity, to support anonymous transactions, the method comprising:

receiving a secret share and a transaction identification from the entity, wherein the secret share is one of a plurality of secret shares representative of an entity identification corresponding to the entity, and wherein the transaction identification does not uniquely identify the entity; and

associatively storing the secret share and the transaction identification.

25. The method of claim 24, further comprising:

receiving an entity encryption key share from the entity, wherein the entity encryption key share is one of a plurality of entity encryption key shares representative of an encryption key associated with the entity; and

associatively storing the entity encryption key share with the secret share and the transaction identification.

26. The method of claim 24, wherein the entity identification comprises a public key uniquely associated with the entity.

27. The method of claim 24, further comprising:

receiving the transaction identification and an acquisition request regarding goods from the entity;

receiving, based on the acquisition request and the transaction identification, information regarding the goods; and

encrypting the information regarding the goods based on the secret share to provide an encrypted information portion.

28. The method of claim 27, further comprising:

sending the encrypted information portion to the entity.

29. The method of claim 27, further comprising:

receiving information based on at least one other encrypted information portion from another shareholder of the plurality of shareholders; and

combining the encrypted information portion with the information based on the at least one other encrypted information portion to provide an updated encrypted information portion.

30. The method of claim 29, further comprising:

sending the updated encrypted information portion to yet another shareholder of the plurality of shareholders when the shareholder is not a last shareholder of the plurality of shareholders.

31. The method of claim 29, further comprising:

sending the updated encrypted information portion to the entity when the shareholder is a last shareholder of the plurality of shareholders.

32. The method of claim 27, further comprising:

receiving payment information and the transaction identification from the entity.

33. The method of claim 24, further comprising:

receiving a recommendation request and the secret share from the entity, wherein the shareholder has previously associated at least one activity corresponding to the entity with the secret share; and

determining, based on the recommendation request, the at least one activity.

34. The method of claim 33, further comprising:

sending the at least one activity to another shareholder of the plurality of shareholders.

35. The method of claim 33, further comprising:

sending the at least one activity to the entity.

36. The method of claim 33, further comprising:

receiving, from another shareholder of the plurality of shareholders, at least one additional activity;

determining common activities between the at least one activity and the at least one additional activity; and

when the shareholder is not a last shareholder of the plurality of shareholders, sending the common activities to yet another shareholder.

37. The method of claim 33, further comprising:

receiving, from another shareholder of the plurality of shareholders, at least one additional activity;

determining common activities between the at least one activity and the at least one additional activity;

when the shareholder is a last shareholder of the plurality of shareholders, generating a set of recommendations based on the common activities; and

providing the set of recommendations to the entity.

38. The method of claim 24, further comprising:

receiving a voucher verification request regarding at least one requested usage right and the secret share from the entity, wherein the shareholder has previously associated at least one usage right corresponding to the entity with the secret share; and

determining, based on the voucher verification request, the at least one usage right.

39. The method of claim 38, further comprising:

sending the at least one usage right to another shareholder of the plurality of shareholders.

40. The method of claim 38, further comprising:

sending the at least one usage right to the entity.

41. The method of claim 38, further comprising:

receiving, from another shareholder of the plurality of shareholders, at least one additional usage right;

determining common usage rights between the at least one usage right and the at least one additional usage right; and

when the shareholder is not a last shareholder of the plurality of shareholders, sending the common usage rights to yet another shareholder.

42. The method of claim 38, further comprising:

receiving, from another shareholder of the plurality of shareholders, at least one additional usage right;

determining common usage rights between the at least one usage right and the at least one additional usage right;

when the shareholder is a last shareholder of the plurality of shareholders, determining whether the at least one requested usage right matches the common usage rights; and

sending a message indicating the availability of the at least one requested usage right to the entity when the at least one requested usage right matches the common usage rights.

43. An apparatus for supporting anonymous transactions by an entity comprising:

means for generating a transaction identification that does not uniquely identify the entity;

means for splitting an entity identification uniquely associated with the entity into a plurality of secret shares; and

means, coupled to the means for generating and the means for splitting, for sending the transaction identification and the plurality of secret shares to a plurality of shareholders.

44. The apparatus of claim 43, further comprising:

means, coupled to the means for sending, for splitting an encryption key associated with the entity into a plurality of entity encryption key shares,

wherein the means for sending further function to send the plurality of entity encryption key shares to the plurality of shareholders.

45. The apparatus of claim 44, wherein the entity identification and the encryption key are the same, and wherein the means for splitting the entity identification comprise the means for splitting the encryption key.

46. The apparatus of claim 45, wherein the entity identification is a public key uniquely associated with the entity.

47. The apparatus of claim 43, further comprising:

means for sending an acquisition request and the transaction identification to at least one shareholder of the plurality of shareholders.

48. The apparatus of claim 47, wherein the means for sending the acquisition request further function to send payment information and the transaction identification to the at least one shareholder.

49. The apparatus of claim 43, further comprising:

means for sending a recommendation request and the plurality of secret shares to corresponding ones of the plurality of shareholders.

50. The method of claim 43, further comprising:

means for sending a voucher verification request and the plurality of secret shares to corresponding ones of the plurality of shareholders.

51. An apparatus for supporting anonymous acquisitions by an entity comprising:

means for generating a transaction identification that does not uniquely identify the entity;

means, coupled to the means for generating, for distributing a public key, in the form of secret shares, and the transaction identification to a plurality of shareholders;

means, coupled to the means for generating, for sending an acquisition request regarding goods to be acquired and the transaction identification to at least one shareholder of the plurality of shareholders;

means for receiving, based on the transaction identification, encrypted information from at least one shareholder of the plurality of shareholders, wherein the encrypted information comprises information regarding the goods and is encrypted, at least in part, by the plurality of shareholders based on each of the secret shares; and

means, coupled to the means for receiving, for decrypting the encrypted information based on the public key.

52. The apparatus of claim 51, wherein the means for receiving further function to receive, from at least one shareholder of the plurality of shareholders, encrypted information portions, wherein each encrypted information portion results from encryption of the information regarding the goods based on at least one of the secret shares, and wherein the apparatus further comprises:

means, coupled to the means for receiving, for calculating the product of the encrypted information portions to provide the encrypted information.

53. The apparatus of claim 51, further comprising:

means for receiving, prior to receiving the encrypted information, a challenge request from a shareholder of the plurality of shareholders, the challenge request comprising encrypted challenge data;

means, coupled to the means for receiving the challenge request, for decrypting the encrypted challenge data based on the public key to provide decrypted challenge data; and

means, coupled to the means for decrypting, for sending the decrypted challenge data to the shareholder.

54. The apparatus of claim 51, wherein the means for sending the acquisition request further function to send payment information and the transaction identification to the at least one shareholder.

55. The apparatus of claim 51, further comprising:

means for sending a voucher verification request regarding at least one usage right and the secret shares to the plurality of shareholders, wherein each shareholder of the plurality of shareholders has previously associated at least one usage right corresponding to the entity with the secret share maintained by the shareholder; and

means for receiving, from at least one shareholder of the plurality of shareholders, a message indicating that at least some of the at least one usage right is available to the entity.

56. An apparatus for an entity to obtain recommendations comprising:

means for sending, to a plurality of shareholders, a recommendation request and secret shares previously sent by the entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one activity corresponding to the entity with a secret share maintained by the shareholder; and

means for receiving, from at least one shareholder of the plurality of shareholders, at least one recommendation responsive to the recommendation request.

57. The apparatus of claim 56, further comprising:

means for receiving a challenge request from a shareholder of the plurality of shareholders prior to receiving the at least one recommendation, the challenge request comprising encrypted challenge data;

means, coupled to the means for receiving the challenge request, for decrypting the encrypted challenge data to provide decrypted challenge data; and

means, coupled to the means for decrypting, for sending the decrypted challenge data to the shareholder.

58. An apparatus for an entity to verify availability of usage rights comprising:

means for sending, to a plurality of shareholders, a voucher verification request regarding at least one usage right and secret shares previously sent by the entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one usage right corresponding to the entity with a secret share maintained by the shareholder; and

means for receiving, from at least one shareholder of the plurality of shareholders, a message indicating that the at least one usage right is available to the entity.

59. The apparatus of claim 58, further comprising:

means for receiving a challenge request from a shareholder of the plurality of shareholders prior to receiving the message, the challenge request comprising encrypted challenge data;

means, coupled to the means for receiving the challenge request, for decrypting the encrypted challenge data to provide decrypted challenge data; and

means, coupled to the means for decrypting, for sending the decrypted challenge data to the shareholder.

60. An apparatus by which a shareholder of a plurality of shareholders can supporting anonymous transactions by an entity, wherein the shareholder is in communication with the entity, comprising:

means for receiving a secret share and a transaction identification from the entity, wherein the secret share is one of a plurality of secret shares representative of an entity identification corresponding to the entity, and wherein the transaction identification does not uniquely identify the entity; and

means, coupled to the means for receiving, for associatively storing the secret share and the transaction identification.

61. The apparatus of claim 60, further comprising:

means for receiving an entity encryption key share from the entity, wherein the entity encryption key share is one of a plurality of entity encryption key shares representative of an encryption key associated with the entity; and

means for associatively storing the entity encryption key share with the secret share and the transaction identification.

62. The apparatus of claim 60, further comprising:

means for receiving the transaction identification and an acquisition request regarding goods from the entity;

means for receiving information regarding the goods, wherein the information regarding the goods is provided based on the acquisition request and the transaction identification; and

means for encrypting the information regarding the goods based on the secret share to provide an encrypted information portion.

63. The apparatus of claim 62, further comprising:

means for sending the encrypted information portion to the entity.

64. The apparatus of claim 62, further comprising:

means for receiving, from another shareholder of the plurality of shareholders, information based on at least one other encrypted information portion; and

means for combining the encrypted information portion with the information based on the at least one other encrypted information portion to provide an updated encrypted information portion.

65. The apparatus of claim 64, further comprising:

means for sending the updated encrypted information portion to yet another shareholder of the plurality of shareholders when the shareholder is not a last shareholder of the plurality of shareholders.

66. The apparatus of claim 64, further comprising:

means for sending the updated encrypted information portion to the entity when the shareholder is a last shareholder of the plurality of shareholders.

67. The apparatus of claim 62, further comprising:

means for receiving payment information and the transaction identification from the entity.

68. The apparatus of claim 60, further comprising:

means for receiving a recommendation request and the secret share from the entity, wherein the shareholder has previously associated at least one activity corresponding to the entity with the secret share; and

means for determining, based on the recommendation request, the at least one activity.

69. The apparatus of claim 68, further comprising:

means for sending the at least one activity to another shareholder of the plurality of shareholders.

70. The apparatus of claim 68, further comprising:

sending the at least one activity to the entity.

71. The apparatus of claim 68, further comprising:

means for receiving, from another shareholder of the plurality of shareholders, at least one additional activity;

means for determining common activities between the at least one activity and the at least one additional activity; and

means for sending the common activities to yet another shareholder when the shareholder is not a last shareholder of the plurality of shareholders.

72. The apparatus of claim 68, further comprising:

means for receiving, from another shareholder of the plurality of shareholders, at least one additional activity;

means for determining common activities between the at least one activity and the at least one additional activity;

means for generating a set of recommendations based on the common activities when the shareholder is a last shareholder of the plurality of shareholders; and

means for providing the set of recommendations to the entity.

73. The apparatus of claim 60, further comprising:

means for receiving a voucher verification request regarding at least one requested usage right and the secret share from the entity, wherein the shareholder has previously associated at least one usage right corresponding to the entity with the secret share; and

means for determining, based on the voucher verification request, the at least one usage right.

74. The apparatus of claim 73, further comprising:

means for sending the at least one usage right to another shareholder of the plurality of shareholders.

75. The apparatus of claim 73, further comprising:

means for sending the at least one usage right to the entity.

76. The apparatus of claim 73, further comprising:

means for receiving, from another shareholder of the plurality of shareholders, at least one additional usage right;

means for determining common usage rights between the at least one usage right and the at least one additional usage right; and

means for sending the common usage rights to yet another shareholder when the shareholder is not a last shareholder of the plurality of shareholders.

77. The apparatus of claim 73, further comprising:

means for receiving, from another shareholder of the plurality of shareholders, at least one additional usage right;

means for determining common usage rights between the at least one usage right and the at least one additional usage right;

means for determining whether the at least one requested usage right matches the common usage rights when the shareholder is a last shareholder of the plurality of shareholders; and

means for sending a message indicating the availability of the at least one requested usage right to the entity when the at least one requested usage right matches the common usage rights.

78. A system for supporting anonymous transactions, the system comprising:

a computer-implemented entity that generates a transaction identification that does not uniquely identify the entity, and that splits an entity identification uniquely associated with the entity into a plurality of secret shares; and

a plurality of computer-implemented shareholders that each receive the transaction identification and a corresponding one of the plurality of secret shares from entity and that associatively store the transaction identification and the corresponding one of the plurality of secret shares.

79. The system of claim 78, wherein the entity identification is a public key uniquely associated with the entity.

80. A computer-readable medium having stored thereon computer-executable instructions for performing steps of:

generating a transaction identification that does not uniquely identify an entity;

splitting an entity identification uniquely associated with the entity into a plurality of secret shares; and

sending the transaction identification and the plurality of secret shares to a plurality of shareholders.

81. A computer-readable medium having stored thereon computer-executable instructions for performing steps of:

generating a transaction identification that does not uniquely identify an entity;

distributing a public key, in the form of secret shares, and the transaction identification to a plurality of shareholders;

sending an acquisition request regarding goods to be acquired and the transaction identification to at least one shareholder of the plurality of shareholders;

receiving, based on the transaction identification, encrypted information from at least one shareholder of the plurality of shareholders, wherein the encrypted information comprises information regarding the goods and is encrypted, at least in part, by the plurality of shareholders based on each of the secret shares; and

decrypting the encrypted information based on the public key.

82. A computer-readable medium having stored thereon computer-executable instructions for performing steps of:

sending, to a plurality of shareholders, a recommendation request and secret shares previously sent by an entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one activity corresponding to the entity with a secret share maintained by the shareholder; and

receiving, from at least one shareholder of the plurality of shareholders, at least one recommendation responsive to the recommendation request.

83. A computer-readable medium having stored thereon computer-executable instructions for performing steps of:

sending, to a plurality of shareholders, a voucher verification request regarding at least one usage right and secret shares previously sent by an entity to corresponding ones of the plurality of shareholders, wherein the secret shares are representative of an entity identification corresponding to the entity, and wherein each shareholder of the plurality of shareholders has previously associated at least one usage right corresponding to the entity with a secret share maintained by the shareholder; and

receiving, from at least one shareholder of the plurality of shareholders, a message indicating that the at least one usage right is available to the entity.

84. A computer-readable medium having stored thereon computer-executable instructions for performing steps of:

receiving a secret share and a transaction identification from an entity, wherein the secret share is one of a plurality of secret shares representative of an entity identification corresponding to the entity, and wherein the transaction identification does not uniquely identify the entity; and

associatively storing the secret share and the transaction identification.