User access to a unique data subset of a database

• US 7,047,422 B2
• Filed: 11/05/2004
• Issued: 05/16/2006
• Est. Priority Date: 08/13/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Benaloh, Josh D.
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): Nobahar, Abdulhakim
• Application Number:
  US10/983,039
• Publication Number:
  US 20050065889A1
• Time in Patent Office: 557 Days
• Field of Search: 713/156, 713/163, 713/168, 713/193, 380/30, 380/262
• US Class Current: 713/193
• CPC Class Codes: G06F 21/1011 to devices
• CPC Class Codes: G06F 21/107 License processing; Key processing
• CPC Class Codes: G06F 21/16 Program or content traceability, e.g. by watermarking
• CPC Class Codes: G06F 2211/007 Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: G11B 20/00086 Circuits for prevention of unauthorised reproduction or copying, e.g. piracy indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: G11B 20/00507 wherein consecutive physical data units of the record carrier are encrypted with separate encryption keys, e.g. the key changes on a cluster or sector basis
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure

Abstract

Described herein is one or more implementations for allowing a user access to a unique data subset of a database.

Claims

1. A method for allowing a user access to a unique data subset of a database, the method comprising:

partitioning the database into segments;

associating a prime number with each segment in the database to derive a prime set;

deriving an integer modulus;

choosing a random value;

assigning a segment key to each segment in the database, each segment key being a function of the prime set, the random value and the integer modulus;

encrypting each segment with the associated segment key to derive an encrypted database;

identifying prime numbers associated with the segments in the unique data subset as a prime subset;

identifying prime numbers in the prime set that are not included in the prime subset as a complement prime subset;

raising the random value to a power, modulo the modulus, of the product of all primes in the complement prime subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

2. The method as recited in claim 1, further comprising transmitting the encrypted database, the integer modulus and the compressed key to the user.

3. The method as recited in claim 1, further comprising:

encrypting the compressed key; and

transmitting the encrypted compressed key to the first user.

4. The method as recited in claim 1, wherein deriving the integer modulus further comprises:

selecting two prime numbers; and

deriving the integer modulus by deriving the product of the two prime numbers.

5. The method as recited in claim 1, wherein deriving the integer modulus further comprises:

selecting three or more prime numbers; and

deriving the integer modulus by deriving the product of the prime numbers.

6. The method as recited in claim 1, wherein deriving the integer modulus further comprises:

selecting two or more composite numbers; and

deriving the integer modulus by deriving the product of the two or more composite numbers.

7. The method as recited in claim 1, wherein deriving the integer modulus further comprises arbitrarily selecting an integer modulus.

8. The method as recited in claim 1, wherein the choosing a random value further comprises choosing a positive random integer that is less than the modulus.

9. The method as recited in claim 1, wherein the choosing a random value further comprises choosing a random value so that the random value does not have any factors in common with the modulus integer.

10. The method as recited in claim 1, wherein the assigning a segment key further comprises, for each segment, raising the random value to the power, modulo the integer modulus, of the product of all prime numbers in the prime set except for the prime number associated with the segment.

11. The method as recited in claim 1, further comprising applying a fixed determination function to a preliminary encryption key prior to using the segment key to encrypt the segment.

12. The method as recited in claim 11, wherein the fixed determination function comprises a hash.

13. The method as recited in claim 1, wherein the user can derive a segment key from the compressed key by raising the compressed key, modulo the integer modulus, to the power of the product of all primes in the prime subset except for the prime number associated with the segment.

14. The method as recited in claim 1, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

15. The method as recited in claim 1, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

16. The method as recited in claim 1, further comprising assigning an index ordinal to each data segment and referring to a data segment by the index ordinal assigned to the data segment.

17. One or more computer-readable media having computer-executable instructions thereon that, when executed by a computer, perform acts for allowing a user access to a unique data subset of a database, the acts comprising:

partitioning the database into segments;

associating a prime number with each segment in the database to derive a prime set;

deriving an integer modulus;

choosing a random value;

assigning a segment key to each segment in the database, each segment key being a function of the prime set, the random value and the integer modulus;

encrypting each segment with the associated segment key to derive an encrypted database;

identifying prime numbers associated with the segments in the unique data subset as a prime subset;

identifying prime numbers in the prime set that are not included in the prime subset as a complement prime subset;

raising the random value to the power, modulo the modulus, of the product of all primes in the complement prime subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

18. One or more media as recited in claim 17, further comprising transmitting the encrypted database, the integer modulus and the compressed key to the user.

19. One or more media as recited in claim 17, further comprising:

encrypting the compressed key; and

transmitting the encrypted compressed key to the first user.

20. One or more media as recited in claim 17, wherein deriving the integer modulus further comprises:

selecting two prime numbers; and

deriving the integer modulus by deriving the product of the two prime numbers.

21. One or more media as recited in claim 17, wherein deriving the integer modulus further comprises:

selecting three or more prime numbers; and

deriving the integer modulus by deriving the product of the prime numbers.

22. One or more media as recited in claim 17, wherein deriving the integer modulus further comprises:

selecting two or more composite numbers; and

deriving the integer modulus by deriving the product of the two or more composite numbers.

23. One or more media as recited in claim 17, wherein deriving the integer modulus further comprises arbitrarily selecting an integer modulus.

24. One or more media as recited in claim 17, wherein the choosing a random value further comprises choosing a positive random integer that is less than the modulus.

25. One or more media as recited in claim 17, wherein the choosing a random value further comprises choosing a random value so that the random value does not have any factors in common with the modulus integer.

26. One or more media as recited in claim 17, wherein the assigning a segment key further comprises, for each segment, raising the random value to the power, modulo the integer modulus, of the product of all prime numbers in the prime set except for the prime number associated with the segment.

27. One or more media as recited in claim 17, further comprising applying a fixed determination function to a preliminary encryption key prior to using the segment key to encrypt the segment.

28. One or more media as recited in claim 17, wherein the user can derive a segment key from the compressed key by raising the compressed key, modulo the integer modulus, to the power of the product of all primes in the prime subset except for the prime number associated with the segment.

29. One or more media as recited in claim 17, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

30. One or more media as recited in claim 17, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

31. One or more media as recited in claim 17, further comprising assigning an index ordinal to each data segment and referring to a data segment by the index ordinal assigned to the data segment.

32. A system for allowing a user access to a unique data subset of a database, the system comprising means for performing functions comprising:

partitioning the database into segments;

associating a prime number with each segment in the database to derive a prime set;

deriving an integer modulus;

choosing a random value;

assigning a segment key to each segment in the database, each segment key being a function of the prime set, the random value and the integer modulus;

encrypting each segment with the associated segment key to derive an encrypted database;

identifying prime numbers associated with the segments in the unique data subset as a prime subset;

identifying prime numbers in the prime set that are not included in the prime subset as a complement prime subset;

raising the random value to the power, modulo the modulus, of the product of all primes in the complement prime subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

33. A system as recited in claim 32, further comprising transmitting the encrypted database, the integer modulus and the compressed key to the user.

34. A system as recited in claim 32, further comprising:

encrypting the compressed key; and

transmitting the encrypted compressed key to the first user.

35. A system as recited in claim 32, wherein deriving the integer modulus further comprises:

selecting two prime numbers; and

deriving the integer modulus by deriving the product of the two prime numbers.

36. A system as recited in claim 32, wherein deriving the integer modulus further comprises:

selecting three or more prime numbers; and

deriving the integer modulus by deriving the product of the prime numbers.

37. A system as recited in claim 32, wherein deriving the integer modulus further comprises:

selecting two or more composite numbers; and

deriving the integer modulus by deriving the product of the two or more composite numbers.

38. A system as recited in claim 32, wherein deriving the integer modulus further comprises arbitrarily selecting an integer modulus.

39. A system as recited in claim 32, wherein the choosing a random value further comprises choosing a positive random integer that is less than the modulus.

40. A system as recited in claim 32, wherein the choosing a random value further comprises choosing a random value so that the random value does not have any factors in common with the modulus integer.

41. A system as recited in claim 32, wherein the assigning a segment key further comprises, for each segment, raising the random value to the power, modulo the integer modulus, of the product of all prime numbers in the prime set except for the prime number associated with the segment.

42. A system as recited in claim 32, further comprising applying a fixed determination function to a preliminary encryption prior to using the segment key to encrypt the segment.

43. A system as recited in claim 32, wherein the user can derive a segment key from the compressed key by raising the compressed key, modulo the integer modulus, to the power of the product of all primes in the prime subset except for the prime number associated with the segment.

44. A system as recited in claim 32, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

45. A system as recited in claim 32, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

46. A system as recited in claim 32, further comprising assigning an index ordinal to each data segment and referring to a data segment by the index ordinal assigned to the data segment.

47. A method for allowing a user access to a unique data subset of a database, the method comprising:

partitioning the database into segments;

associating an ordinal with each segment in the database to derive an ordinal set;

deriving an integer modulus;

choosing a random value;

assigning a segment key to each segment in the database, each segment key being a function of the ordinal set, the random value and the integer modulus;

encrypting each segment with the associated segment key to derive an encrypted database;

identifying ordinals associated with the segments in the unique data subset as an ordinal subset;

identifying ordinals in the ordinal set that are not included in the ordinal subset as a complement ordinal subset;

raising the random value to the power, modulo the modulus, of the product of all ordinals in the complement ordinal subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

48. The method as recited in claim 47, further comprising transmitting the encrypted database, the integer modulus and the compressed key to the user.

49. The method as recited in claim 47, further comprising:

encrypting the compressed key; and

transmitting the encrypted compressed key to the first user.

50. The method as recited in claim 47, wherein deriving the integer modulus further comprises:

selecting two prime numbers; and

deriving the integer modulus by deriving the product of the two prime numbers.

51. The method as recited in claim 47, wherein deriving the integer modulus further comprises:

selecting three or more prime numbers; and

deriving the integer modulus by deriving the product of the prime numbers.

52. The method as recited in claim 47, wherein deriving the integer modulus further comprises:

selecting two or more composite numbers; and

deriving the integer modulus by deriving the product of the two or more composite numbers.

53. The method as recited in claim 47, wherein deriving the integer modulus further comprises arbitrarily selecting an integer modulus.

54. The method as recited in claim 47, wherein the assigning a segment key further comprises, for each segment, raising the random value to the power, modulo the integer modulus, of the product of all ordinals in the ordinal set except for the ordinal associated with the segment.

55. The method as recited in claim 47, further comprising applying a fixed determination function to a preliminary encryption prior to using the segment key to encrypt the segment.

56. The method as recited in claim 55, wherein the fixed determination function comprises a hash.

57. The method as recited in claim 47, wherein the user can derive a segment key from the compressed key by raising the compressed key, modulo the integer modulus, to the power of the product of all ordinals in the ordinal subset except for the ordinal associated with the segment.

58. The method as recited in claim 47, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

59. The method as recited in claim 47, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

60. One or more computer-readable media having computer-executable instructions that, when executed by a computer, perform acts for allowing a user access to a unique data subset of a database, the acts comprising:

partitioning the database into segments;

associating an ordinal with each segment in the database to derive an ordinal set;

deriving an integer modulus;

choosing a random value;

assigning a segment key to each segment in the database, each segment key being a function of the ordinal set, the random value and the integer modulus;

encrypting each segment with the associated segment key to derive an encrypted database;

identifying ordinals associated with the segments in the unique data subset as an ordinal subset;

identifying ordinals in the ordinal set that are not included in the ordinal subset as a complement ordinal subset;

raising the random value to the power, modulo the modulus, of the product of all ordinals in the complement ordinal subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

61. One or more media as recited in claim 60, further comprising transmitting the encrypted database, the integer modulus and the compressed key to the user.

62. One or more media as recited in claim 60, further comprising:

encrypting the compressed key; and

transmitting the encrypted compressed key to the first user.

63. One or more media as recited in claim 60, wherein deriving the integer modulus further comprises:

selecting two prime numbers; and

deriving the integer modulus by deriving the product of the two prime numbers.

64. One or more media as recited in claim 60, wherein deriving the integer modulus further comprises:

selecting three or more prime numbers; and

deriving the integer modulus by deriving the product of the prime numbers.

65. One or more media as recited in claim 60, wherein deriving the integer modulus further comprises:

selecting two or more composite numbers; and

deriving the integer modulus by deriving the product of the two or more composite numbers.

66. One or more media as recited in claim 60, wherein deriving the integer modulus further comprises arbitrarily selecting an integer modulus.

67. One or more media as recited in claim 60, wherein the assigning a segment key further comprises, for each segment, raising the random value to the power, modulo the integer modulus, of the product of all ordinals in the ordinal set except for the ordinal associated with the segment.

68. One or more media as recited in claim 60, further comprising applying a fixed determination function to a preliminary encryption prior to using the segment key to encrypt the segment.

69. One or more media as recited in claim 68, wherein the fixed determination function comprises a hash.

70. One or more media as recited in claim 60, wherein the user can derive a segment key from the compressed key by raising the compressed key, modulo the integer modulus, to the power of the product of all ordinals in the ordinal subset except for the ordinal associated with the segment.

71. One or more media as recited in claim 60, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

72. One or more media as recited in claim 60, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

73. A system for allowing a user access to a unique data subset of a database, the system comprising:

a partitioning means for partitioning the database into segments;

an association means for associating an ordinal with each segment in the database to derive an ordinal set;

a derivation means for deriving an integer modulus;

a selection means for choosing a random value;

an assignment means for assigning a segment key to each segment in the database, each segment key being a function of the ordinal set, the random value and the integer modulus;

an encryption means for encrypting each segment with the associated segment key to derive an encrypted database;

an identification means for identifying ordinals associated with the segments in the unique data subset as an ordinal subset;

another identification means for identifying ordinals in the ordinal set that are not included in the ordinal subset as a complement ordinal subset;

a raising means for raising the random value to the power, modulo the modulus, of the product of all ordinals in the complement ordinal subset to generate a compressed key; and

wherein the user can derive each segment key associated with the data subset from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

74. The system as recited in claim 73, further comprising transmission means for transmitting the encrypted database, the integer modulus and the compressed key to the user.

75. The system as recited in claim 73, further comprising:

another encryption means for encrypting the compressed key; and

a transmission means for transmitting the encrypted compressed key to the first user.

76. The system as recited in claim 73, wherein the unique data set is a first unique data set, and wherein a second user receives the database segments and has access to a second unique data subset but is unable to access the first unique data subset.

77. The system as recited in claim 73, wherein the user cannot use the compressed key or any segment key to access a segment that is not included in the unique data subset.

78. A method for allowing a user access to a unique data subset of a database, the method comprising:

partitioning the database into segments;

associating a prime number, pi, with each segment, Si, in the database to derive a prime set, P;

deriving an integer modulus, N, as the product of two large prime numbers;

choosing a random value, x;

assigning a segment key, ki, to each segment of the database, each segment key being a function of P, x and N;

encrypting each segment, S1, with the associated segment key, k1;

identifying the prime numbers associated with the segments in the unique data subset as a prime subset, Ps;

identifying the prime numbers in the prime set that are not included in the prime subset as a complement prime subset, Pc;

generating a compressed key with the following equation;

CK=xIIPc mod N; and

wherein the user can derive each segment key from the compressed key and decrypt each segment of the unique data subset to access the unique data subset.

79. The method as recited in claim 78, further comprising transmitting the compressed key, CK, to the user.

80. The method as recited in claim 78, wherein the choosing a random value, x, further comprises choosing a random value, x, such that 1<

x<

(N−

1).

81. The method as recited in claim 78, wherein assigning a segment key, ki, to each segment of the database further comprises, for each segment, Si, calculation a corresponding segment key, ki, by solving:

ki=xIIP/pi mod N.

82. The method as recited in claim 78, wherein the user can derive a segment key, Ki, from the compressed key, CK, by solving:

Ki=CKIIP/pi mod N.