Method, apparatus, and program product for enabling access to flexibly redacted content

• US 7,865,742 B2
• Filed: 12/15/2006
• Issued: 01/04/2011
• Est. Priority Date: 07/12/2006
• Status: Expired due to Fees

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica N., Golle, Philippe Jean-Paul
• Primary Examiner(s): Ustaris; Joseph G
• Assistant Examiner(s): RICHARDS, KEVIN T
• Application Number:
  US11/611,845
• Publication Number:
  US 20080016341A1
• Time in Patent Office: 1,481 Days
• Field of Search: 705/76, 713/67, 380/44
• US Class Current: 713/193
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06Q 20/3821 Electronic credentials
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• 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

Abstract

A capability key is generated that provides access to sensitive information within a selectively encrypted data unit created from an unencrypted data unit. A user specifies access rights as a monotone boolean relationship between a selection of a list of attributes related to the unencrypted data unit. This relationship is used to compute a key descriptor. Next one or more shares of a master secret is generated responsive to the monotone boolean relationship and a random number. Next a unique capability key is computed from one or more cryptosystem parameters, the one or more shares and the random number. The unique capability key and the key descriptor together enable decryption of sensitive information within a selectively encrypted data unit created from an unencrypted data unit. Finally, the unique capability key and the key descriptor are provided to allow decryption of sensitive information within the selectively encrypted data unit.

Claims

1. A computer controlled method for generating one or more capability keys related to an unencrypted data unit comprising:

selecting one or more attributes from a list of attributes related to said unencrypted data unit;

using a computer, computing a key descriptor responsive to a selection of one or more access rights capable of being represented by a monotone boolean relationship between said one or more attributes;

generating one or more random numbers;

generating one or more shares responsive to said monotone boolean relationship and responsive to a master secret;

generating a unique capability key responsive to one or more cryptosystem parameters, said one or more shares and said one or more random numbers, wherein said unique capability key and said key descriptor together enable decryption of sensitive information within a selectively encrypted data unit created from the unencrypted data unit; and

providing said unique capability key and said key descriptor

wherein at least one of said one or more access rights is specified as a threshold relationship of said one or more attributes from a subset of said one or more attributes;

wherein the generating said one or more shares further comprises selecting a random polynomial of degree I−

1 responsive to said master secret wherein said one or more shares can be represented as one or more respective points on said random polynomial;

wherein the threshold relationship is operative to reduce the number of shares and number of auxiliary values; and

wherein I is the number of attributes in the threshold relationship.

2. The computer controlled method of claim 1, wherein generating said one or more shares comprises generating said one or more shares of said master secret responsive to said monotone boolean relationship.

3. The computer controlled method of claim 1, wherein generating said one or more shares comprises generating said one or more shares responsive to said monotone boolean relationship and a polynomial responsive to said master secret.

4. The computer controlled method of claim 3, wherein said polynomial is responsive to a number of possible users and a number of possible user revocations.

5. The computer controlled method of claim 1, wherein generating said one or more shares is further responsive to a specified user.

6. The computer controlled method of claim 1, wherein generating said unique capability key is also responsive to an access key and wherein the method further comprises preparing said access key and a protection key for delivery to a trusted third party.

7. The computer controlled method of claim 1, wherein said unencrypted data unit is one of a collection of data units, and said list of attributes is related to said collection of data units.

8. The computer controlled method of claim 1, wherein said one or more attributes categorize one or more of a group consisting of personally identifiable data, one or more restricted numbers, one or more restricted topics, one or more metadata values, one or more text characteristics, one or more identified ranges of restricted data, or one or more restricted images.

9. The computer controlled method of claim 1, further comprising generating a second unique capability key;

and providing said second unique capability key.

10. An apparatus comprising:

a central processing unit (CPU),

a memory coupled to said CPU,

an attribute logic configured to select one or more attributes from a list of attributes related to said unencrypted data unit;

a key descriptor generation logic configured to compute a key descriptor responsive to a selection of one or more access rights capable of being represented by a monotone boolean relationship between said one or more attributes;

a random number generator configured to generate one or more random numbers;

a share generation logic configured to generate one or more shares responsive to said monotone boolean relationship and responsive to a master secret;

a key generation logic configured to generate a unique capability key responsive to one or more cryptosystem parameters, said one or more shares and said one or more random numbers, wherein said unique capability key and said key descriptor together enable decryption of sensitive information within a selectively encrypted data unit created from the unencrypted data unit; and

a provision logic configured to provide said unique capability key and said key descriptor

wherein at least one of said one or more access rights is specified as a threshold relationship of said one or more attributes from a subset of said one or more attributes;

wherein the generating said one or more shares further comprises selecting a random polynomial of degree I−

1 responsive to said master secret wherein said one or more shares can be represented as one or more respective points on said random polynomial;

wherein the threshold relationship is operative to reduce the number of shares and number of auxiliary values; and

wherein I is the number of attributes in the threshold relationship.

11. The apparatus of claim 10, wherein the share generation logic is configured to generate said one or more shares of said master secret responsive to said monotone boolean relationship.

12. The apparatus of claim 10, wherein the share generation logic is configured to generate said monotone boolean relationship and a polynomial responsive to said master secret.

13. The apparatus of claim 12, wherein said polynomial is responsive to a number of possible users and a number of possible user revocations.

14. The apparatus of claim 10, wherein the share generation logic is further responsive to a specified user.

15. The apparatus of claim 10, wherein the key generation logic is also responsive to an access key and further comprises a key preparation logic configured to prepare said access key and a protection key for delivery to a trusted third party.

16. The apparatus of claim 10, wherein said unencrypted data unit is one of a collection of data units, and said list of attributes is related to said collection of data units.

17. The apparatus of claim 10, wherein said one or more attributes categorize one or more of a group consisting of personally identifiable data, one or more restricted numbers, one or more restricted topics, one or more metadata values, one or more text characteristics, one or more identified ranges of restricted data, or one or more restricted images.

18. A computer program product comprising:

a non-transitory computer-usable data carder providing instructions that, when executed by a computer, cause said computer to perform a method to generate one or more capability keys related to an unencrypted data unit, said method comprising;

selecting one or more attributes from a list of attributes related to said unencrypted data unit;

computing a key descriptor responsive to a selection of one or more access rights capable of being represented by a monotone boolean relationship between said one or more attributes;

generating one or more random numbers;

generating one or more shares responsive to said monotone boolean relationship and responsive to a master secret;

generating a unique capability key responsive to one or more cryptosystem parameters, said one or more shares and said one or more random numbers, wherein said unique capability key and said key descriptor together enable decryption of sensitive information within a selectively encrypted data unit created from the unencrypted data unit; and

providing said unique capability key and said key descriptor

wherein at least one of said one or more access rights is specified as a threshold relationship of said one or more attributes from a subset of said one or more attributes;

wherein the generating said one or more shares further comprises selecting a random polynomial of degree I−

1 responsive to said master secret wherein said one or more shares can be represented as one or more respective points on said random polynomial;

wherein the threshold relationship is operative to reduce the number of shares and number of auxiliary values; and

wherein I is the number of attributes in the threshold relationship.

19. The computer program product of claim 18, wherein generating said one or more shares comprises generating said one or more shares of said master secret responsive to said monotone boolean relationship.

20. The computer program product of claim 18, wherein generating said one or more shares comprises generating said one or more shares responsive to said monotone boolean relationship and a polynomial responsive to said master secret.

21. The computer program product of claim 20, wherein said polynomial is responsive to a number of possible users and a number of possible user revocations.

22. The computer program product of claim 18, wherein generating said one or more shares is further responsive to a specified user.

23. The computer program product of claim 18, wherein generating said unique capability key is also responsive to an access key and wherein the product further comprises preparing said access key and a protection key for delivery to a trusted third party.

24. The computer program product of claim 18, wherein said unencrypted data unit is one of a collection of data units, and said list of attributes is related to said collection of data units.

25. The computer program product of claim 18, wherein said one or more attributes categorize one or more of a group consisting of personally identifiable data, one or more restricted numbers, one or more restricted topics, one or more metadata values, one or more text characteristics, one or more identified ranges of restricted data or one or more restricted images.

26. The computer program product of claim 18, further comprising generating a second unique capability key;

and providing said second unique capability key.