Anonymous transactions based on distributed processing

• US 7,187,772 B2
• Filed: 05/10/2002
• Issued: 03/06/2007
• 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.
• Primary Examiner(s): Song; Hosuk
• Application Number:
  US10/143,081
• Publication Number:
  US 20030048906A1
• Time in Patent Office: 1,761 Days
• Field of Search: 380277-285, 705/74, 713/163, 713/171, 713175-176
• 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

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.

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 1, wherein the entity identification is a linear combination of the plurality of entity identification secret shares.

6. 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.

7. The method of claim 6, further comprising:

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

8. 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.

9. 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.

10. 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,

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.

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

12. The method of claim 10, wherein the encrypted information comprises the goods.

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

14. The method of claim 10, further comprising:

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

15. The method of claim 10, further comprising:

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

16. A method for an entity to support anonymous acquisitions, 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

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.

17. A method for an entity to support anonymous acquisitions, 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;

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.

18. 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;

associatively storing the secret share and the transaction identification;

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

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.

19. The method of claim 18, 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.

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

21. The method of claim 18, further comprising:

sending the encrypted information portion to the entity.

22. The method of claim 18, 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.

23. The method of claim 18, further comprising:

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

24. The method of claim 18, further comprising:

receiving payment information and the transaction identification from the entity.

25. The method of claim 18, 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.

26. The method of claim 25, further comprising:

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

27. The method of claim 25, further comprising:

sending the at least one activity to the entity.

28. The method of claim 18, 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.

29. The method of claim 28, further comprising:

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

30. The method of claim 28, further comprising:

sending the at least one usage right to the entity.

31. A method for a shareholder of a plurality of shareholders, in communication with an entity, to support anonymous transactions, 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;

associatively storing the secret share and the transaction identification;

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;

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.

32. A method for a shareholder of a plurality of shareholders, in communication with an entity, to support anonymous transactions, 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;

associatively storing the secret share and the transaction identification;

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;

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.

33. A method for a shareholder of a plurality of shareholders, in communication with an entity, to support anonymous transactions, 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;

associatively storing the secret share and the transaction identification;

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;

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.

34. A method for a shareholder of a plurality of shareholders, in communication with an entity, to support anonymous transactions, 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;

associatively storing the secret share and the transaction identification;

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;

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.

35. 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,

wherein the entity identification and the encryption key are the same, and wherein the means for splitting the entity identification comprise the means for spitting the encryption key.

36. The apparatus of claim 35, 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.

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

38. The apparatus of claim 35, further comprising:

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

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

40. The apparatus of claim 35, further comprising:

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

41. The method of claim 35, further comprising:

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

42. 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; and

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,

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.

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

44. 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; and

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,

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.

45. 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; and

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.

46. 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;

means, coupled to the means for receiving, for associatively storing the secret share and the transaction identifications;

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;

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

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; and

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.

47. The apparatus of claim 46, 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.

48. The apparatus of claim 46, further comprising:

means for sending the encrypted information portion to the entity.

49. The apparatus of claim 46, 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.

50. The apparatus of claim 46, further comprising:

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

51. The apparatus of claim 46, 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.

52. The apparatus of claim 51, further comprising:

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

53. The apparatus of claim 51, further comprising:

sending the at least one activity to the entity.

54. The apparatus of claim 51, 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.

55. The apparatus of claim 46, 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.

56. The apparatus of claim 55, further comprising:

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

57. The apparatus of claim 55, further comprising:

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

58. The apparatus of claim 55, 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.

59. 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;

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;

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.

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;

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

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;

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.