# US 7,613,302 B2 · Systems and methods for compression of key sets having multiple keys

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,613,302 B2
- Document ID: US7613302B2
- Status: Granted
- Kind: B2
- Application number: 11/016,458
- Filed: 2004-12-17
- Published: 2005-06-02
- Granted: 2009-11-03
- Earliest claimed: 1999-08-13
- Assignees: Microsoft Corporation
- Inventors: Josh D. Benaloh
- Web page: https://patentgrep.com/patent/US7613302B2

## CPC

- G06Q 20/3829: {involving key management}
- 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)}
- G11B 20/0021: {involving encryption or decryption of contents recorded on or reproduced from a record carrier}
- 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}
- H04L 9/0836: {using tree structure or hierarchical structure}
- G06F 21/1011: {to devices}
- G06F 21/107: {License processing; Key processing}
- G06F 21/16: Program or content traceability, e.g. by watermarking
- G06F 2211/007: Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
- G06F 2221/2107: File encryption
- H04L 2209/60: Digital content management, e.g. content distribution
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems, methods and modulated data signals are described herein that provide an efficient way to derive a single key from which a user can extract virtually any number of data encryption keys. A database is logically divided into segments and a small prime number is associated with each segment. An encryption key is derived for each segment in the database and a key set is determined for distributing a data subset to a user. Each segment is encrypted with the corresponding encryption key. A single key is derived using the prime numbers associated with the data segments and the single key, the encrypted database, and a small amount of public information is provided to the user. The user utilizes this information to extract the encryption key set from the single key. One implementation utilizes a tree structure to significantly reduce the number of modular exponentiations that must be calculated when extracting the encryption keys. This, in turn, dramatically decreases the processing overhead that must be allocated to the processing associated with deriving the encryption keys.

## Claims

### Claim 1

One or more computer-readable media having computer-executable instructions that, when executed by a computer, perform acts for distributing a first data subset of a database to a first user and a second data subset of a database to a second user, the first user being excluded from accessing the second data subset and the second user being excluded from accessing the first data subset, the acts comprising:
logically dividing the database into multiple segments, the first user being entitled to a plurality of segments that make up the first data subset, the second user being entitled to a plurality of segments that make up the second data subset;
encrypting each segment of the database to derive an encrypted database;
deriving a first key from which the first user can derive a set of segment keys, each segment key being uniquely associated with one segment in the first data subset;
deriving a second key from which the second user can derive a set of segment keys, each segment key being uniquely associated with one segment in the second data subset;
distributing the encrypted database and the first key to the first user;
distributing the encrypted database and the second key to the second user;
deriving a first key further comprises:
determining a first complement prime set that includes prime numbers that are not associated with any segments in the first data subset; and
raising a random value, modulo the modulus, to a power of a product of the first complement prime set;
deriving the second key further comprises:
determining a second complement prime set that includes prime numbers that are not associated with any segments in the second data subset; and
raising a random value, modulo the modulus, to a power of a product of the second complement prime set; and
wherein the first user can gain access to the first data subset from the first key but cannot access any segment that is not included in the first data subset, and the second user can gain access to the second data subset from the second key but cannot access any segment that is not included in the second data subset.

### Claim 2 (depends on 1)

One or more media as recited in claim 1, further comprising creating an index to the database segments, the index comprising a series of ordinals, each ordinal corresponding to one segment in the database.

### Claim 3 (depends on 1)

One or more media as recited in claim 1, further comprising applying a fixed deterministic function to each segment key prior to using the segment key to encrypt the segment associated with the segment key.

### Claim 4

A method for decrypting a data subset of an encrypted database that is logically divided into multiple segments, each segment being encrypted with a unique segment key, the method comprising:
extracting a key set from a single key, each key in the key set being uniquely associated with one segment of the data subset of the database; and
decrypting each segment of the data subset with a segment key from the key set;
wherein extracting the key set further comprises:
identifying a prime subset that includes one prime number for each segment of the data subset, one prime number being uniquely associated with one segment of the data subset;
identifying an integer modulus;
for each segment in the data subset, determining a segment key for the segment by raising the single key, modulo the modulus, to a power of a product of all primes in the prime subset except the prime number that is uniquely associated with the segment.

### Claim 5 (depends on 4)

A method as recited in claim 4, wherein the segment key for each segment is a preliminary segment key, and wherein the method further comprises, for each segment, applying a fixed deterministic function to the preliminary segment key to derive the segment key.

### Claim 6

A method for distributing a first data subset of a database to a first user and a second data subset of a database to a second user, the first user being excluded from accessing the second data subset and the second user being excluded from accessing the first data subset, the method comprising:
logically dividing the database into multiple segments, the first user being entitled to a plurality of segments that make up the first data subset, the second user being entitled to a plurality of segments that make up the second data subset;
encrypting each segment of the database to derive an encrypted database;
deriving a first key from which the first user can derive a set of segment keys, each segment key being uniquely associated with one segment in the first data subset;
deriving a second key from which the second user can derive a set of segment keys, each segment key being uniquely associated with one segment in the second data subset;
distributing the encrypted database and the first key to the first user;
distributing the encrypted database and the second key to the second user;
deriving a first key further comprises:
determining a first complement prime set that includes prime numbers that are not associated with any segments in the first data subset; and
raising a random value, modulo the modulus, to a power of a product of the first complement prime set;
deriving the second key further comprises:
determining a second complement prime set that includes prime numbers that are not associated with any segments in the second data subset; and
raising a random value, modulo the modulus, to a power of a product of the second complement prime set; and
wherein the first user can gain access to the first data subset from the first key but cannot access any segment that is not included in the first data subset, and the second user can gain access to the second data subset from the second key but cannot access any segment that is not included in the second data subset.

### Claim 7 (depends on 6)

A method as recited in claim 6, further comprising creating an index to the database segments, the index comprising a series of ordinals, each ordinal corresponding to one segment in the database.

### Claim 8 (depends on 6)

A method as recited in claim 6, further comprising applying a fixed deterministic function to each segment key prior to using the segment key to encrypt the segment associated with the segment key.