Method and apparatus for encrypting data

• US 7,263,191 B2
• Filed: 10/11/2002
• Issued: 08/28/2007
• Est. Priority Date: 10/15/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Harrison, Keith Alexander, Chen, Liqun
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): Wyszynski, Aubrey H
• Application Number:
  US10/270,040
• Publication Number:
  US 20030091192A1
• Time in Patent Office: 1,782 Days
• Field of Search: 380/265, 380/278, 380/44
• US Class Current: 380/265
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 63/0457 wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A method for encrypting data comprising dividing a first data set into a second data set and a third data set; deriving a first value using the second data set as an input into a polynomial equation; deriving a second value using the third data set as an input into the polynomial equation; deriving a first encryption key associated with a first party; deriving a second encryption key associated with a second party; encrypting the first value with the first encryption key; encrypting the second value with the second encryption key.

Claims

1. A method for encrypting first data such that the participation of t out of n trusted authorities is required to decrypt the encrypted first data, the method comprising executing instructions on a computer apparatus for:

dividing the first data into t elements where t>

1;

setting the value of each coefficient of a polynomial in x of order (t−

1) in dependence on a respective one of said elements;

deriving n share values by evaluating said polynomial for n different values of x where n≧

t;

encrypting each share value using as encryption parameters both public data of a respective trust authority and a key string that serves, in relation to that trust authority, as a public key of an intended recipients;

providing the encrypted shares, and the values of x used in deriving the shares, to said intended recipient;

providing to the intended recipient, from each of t said trust authorities, a private key corresponding to the said public key of the intended recipient in respect of that trust authority;

using the private keys to decrypt t encrypted shares;

using the decrypted shares to recover the coefficients of said polynomial; and

combining the polynomial coefficients to recover the first data.

2. A method according to claim 1, further comprising providing the encrypted shares to said intended recipient for decryption and recovery of the first data.

3. A method according to claim 1, wherein the size of the elements is the same.

4. A method according to claim 1, wherein the elements have values that are random and independent.

5. A method according to claim 1, wherein the public keys of the intended recipient specify conditions to be checked by the trust authorities, a said trust authority only providing the intended recipient with a said private key after checking that the condition specified in the corresponding public key has been met.

6. A method according to claim 1, wherein for 0<

j<

t, the j^th order coefficient of the polynomial, is formed by combining a respective one of said elements with a hash of the (j−

1)^th order coefficient.

7. Computer apparatus for encrypting first data such that the participation of t out of n trusted authorities is required to decrypt the encrypted first data, the apparatus comprising:

a processor arranged to divide the first data into t elements where t>

1 , set the value of each coefficient of a polynomial in x of order (t−

1) in dependence on a respective one of said elements, derive n share values by evaluating said polynomial for n different values of x where n≧

t, and encrypt each share value using as encryption parameters both public data of a respective trust authority and a key string that serves, in relation to that trust authority, as a public key of an intended recipient; and

communication means for providing the encrypted shares to a third parry for decryption and recovery of the first data.

8. Apparatus according to claim 7, wherein the size of the elements is the same.

9. Apparatus according to claim 7, wherein the elements have values that are random and independent.