METHOD AND SYSTEM FOR CALCULATIONS ON ENCRYPTED DATA

• US 20140321644A1
• Filed: 04/29/2013
• Published: 10/30/2014
• Est. Priority Date: 04/29/2013
• Status: Abandoned Application

• Current Assignee: Her Majesty The Queen In Right of Canada As Represented By The Minister of National Defence
• Original Assignee: Her Majesty The Queen In Right of Canada As Represented By The Minister of National Defence
• Inventors: Lemieux, Stephane R.
• Application Number:
  US13/872,507
• Publication Number:
  US 20140321644A1
• Time in Patent Office: Days
• US Class Current: 380/46
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0827 involving distinctive intermediate devices or communication paths network architectures or network communication protocols using different networks H04L63/18

Abstract

A method and device for generating a communal decryption key among participants to permit sharing of sensitive data, the method at a current participant includes generating a secret value; adding the generated secret value to an in progress key to create a modified in progress key; and forwarding the modified in progress key to a subsequent participant in accordance with a predetermined ordering of participants, over a predetermined number of rounds. Further a method for sharing of sensitive data among participants, the method at a current participant includes constructing an exponent by combining a secret value of the current participant and the sensitive data; creating an encrypted value using the constructed exponent; publishing the encrypted value; finding a product of encrypted values of all participants; and decrypting the product of encrypted values using a communal decryption key, wherein the communal decryption key includes secret values of all the participants.

Claims

1. A method at a computing device for generating a communal decryption key among at least three participants to permit sharing of sensitive data, the method comprising:

at a current participant;

generating a secret value;

adding the generated secret value to an in progress key to create a modified in progress key; and

forwarding the modified in progress key to a subsequent participant in accordance with a predetermined ordering of participants; and

wherein said communal decryption key is derived upon performing said generating, adding and forwarding over a predetermined number of rounds.

2. The method of claim 1, wherein the in progress key is received from a preceding participant.

3. The method of claim 1 wherein if the in progress key is not received from a preceding participant, the in progress key is a large randomly generated number H.

4. The method of claim 3 wherein upon the completion of said predetermined number of rounds the large randomly generated number is removed from a received modified in progress key.

5. The method of claim 1, wherein the secret value is a vector.

6. The method of claim 1, wherein the secret value and the large randomly generated number are elements of multiplicative group G of integers modulo a prime number p.

7. The method of claim 1, wherein an encryption key for one of said participants is computed by exponentiation using the sum of the secret values generated by the one of said participants over the number of rounds.

8. The method of claim 7, wherein a base value for said exponentiation is a hash function H(t).

9. The method of claim 7, wherein a base value for said exponentiation is a primitive root g of multiplicative group G of integers modulo the prime p.

10. The method of claim 1, wherein the predetermined ordering of participants ensures that the current participant receives or sends to every other participant at least once during said predetermined number of rounds.

11. A method at a computing device for sharing of sensitive data among at least three participants, the method comprising:

at a current participant;

constructing an exponent by mathematically combining a secret value of the current participant and the sensitive data;

creating an encrypted value using the constructed exponent;

publishing the encrypted value;

finding a product of encrypted values of all said participants; and

decrypting the product of encrypted values using a communal decryption key,

wherein the communal decryption key includes secret values of all said participants.

12. The method of claim 11, further comprising, at the current participant

generating an element z of the secret value d;

adding the generated element of the secret value to an in progress key IPK to create a modified in progress key; and

forwarding the modified in progress key to a subsequent participant in accordance with a predetermined ordering of participants; and

wherein said communal decryption key is derived upon performing said generating, adding and forwarding over a predetermined number of rounds.

13. The method of claim 11, wherein the secret value of the current participant is derived from a trusted third party.

14. The method of claim 11, wherein the secret value of the current participant is a vector.

15. The method of claim 11, wherein a base value for said exponent is a hash function H(t).

16. The method of claim 11, wherein a base value for said exponent is a primitive root g of multiplicative group G of integers modulo a prime p.

17. The method of claim 11, wherein decrypting the product of encrypted values produces a sum of the sensitive data of all said participants.

18. The method of claim 11, wherein decrypting the product of encrypted values produces a product of the sensitive data of all said participants.

19. The method of claim 11, wherein the creating the encrypted value includes two rounds, wherein in a first round a first prime is encrypted if the current participant has data to send and second prime is encrypted if the current participant has no data to send;

and

wherein in a second round the data is encrypted if the first prime was encrypted in the first round and a null value is encrypted if the second prime was encrypted.

20. The method of claim 11, further comprising, at said current participant:

receiving a value m that is infeasible to factor;

using the value m as a modulo for the constructing of the exponent;

deriving a verification key by exponentiation using the secret value modulo m; and

publishing the verification key.

21. The method of claim 11, wherein multiple rounds of said constructing, creating, publishing, finding and decrypting are performed.