Exchanging a secret over an unreliable network
First Claim
1. A method for transmitting a secret to a client over an unreliable communication network, the method comprising the steps of:
- dividing the secret into a predetermined number N shares using a threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme; and
transmitting to the client a plurality of messages including at least one share in each of said plurality of messages.
12 Assignments
0 Petitions
Accused Products
Abstract
Threshold cryptography (secret sharing) is used for exchanging a secret between a server and a client over an unreliable network. Specifically, a secret is computationally divided into N shares using a threshold encryption scheme such that any M of the shares (M less than or equal to N) can be used to reconstruct the secret. The N shares are spread over a number of transmitted messages, with the assumption that some number of the messages including a total of at least M shares will be received by the client. Upon receiving at least M shares, the client uses the at least M shares to reconstruct the secret using the threshold encryption scheme.
233 Citations
42 Claims
-
1. A method for transmitting a secret to a client over an unreliable communication network, the method comprising the steps of:
-
dividing the secret into a predetermined number N shares using a threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme; and
transmitting to the client a plurality of messages including at least one share in each of said plurality of messages. - View Dependent Claims (2, 3, 4, 5, 6, 13, 14)
dividing the secret into the N shares; and
transmitting at least one share in each of a plurality of layers of a layered reliable multicast transmission.
-
-
3. The method of claim 2 wherein the layered reliable multicast transmission comprises at least N layers and wherein the method comprises the steps of:
-
dividing the secret encryption key into the N shares; and
transmitting a different one of the N shares in each of N layers of the layered reliable multicast transmission.
-
-
4. The method of claim 2 further comprising the step of encrypting each of the N shares prior to transmitting.
-
5. The method of claim 4 wherein the step of encrypting each of the N shares comprises encrypting each of the N shares using a master key.
-
6. The method of claim 4 wherein the step of encrypting each of the N shares comprises encrypting each of the N shares using a prior secret encryption key.
-
13. The apparatus of claim 1 comprising:
-
means for dividing the secret into the N shares; and
means for transmitting a plurality of messages to the client including at least one share in each of said plurality of messages.
-
-
14. The apparatus of claim 13 further comprising means for encrypting each of the N shares prior to transmitting.
-
7. An apparatus for transmitting a secret to a client over an unreliable communication network, the apparatus comprising:
-
a threshold encryptor operably coupled to divide the secret into a predetermined number N shares using a predetermined threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme; and
transmitting logic operably coupled to transmit a plurality of messages to the client including at least one share in each of said plurality of messages. - View Dependent Claims (8, 9, 10, 11, 12)
the threshold encryptor operably coupled to divide the secret encryption key into the N shares; and
a layered reliable multicast transmitter responsive to the threshold encryptor and operably coupled to transmit at least one share in each of a plurality of layers of a layered reliable multicast transmission.
-
-
9. The apparatus of claim 8 wherein the layered reliable multicast transmission comprises at least N layers and wherein the layered reliable multicast transmitter is operably coupled to transmit a different one of the N shares in each of N layers of the layered reliable multicast transmission.
-
10. The apparatus of claim 8 further comprising a data encryptor operably coupled between the threshold encryptor and the layered reliable multicast transmitter, the data encryptor operably coupled to encrypt each of the shares and provide encrypted shares to the layered reliable multicast transmitter.
-
11. The apparatus of claim 10 wherein the data encryptor encrypts each of the N shares using a master key.
-
12. The apparatus of claim 10 wherein the data encryptor encrypts each of the N shares using a prior secret encryption key.
-
15. A program product comprising a computer readable medium having embodied therein a computer readable program for transmitting a secret to a client over an unreliable communication network, the computer readable program comprising:
-
threshold encryption logic programmed to divide the secret into a predetermined number N shares using a predetermined threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme; and
transmitting logic programmed to transmit a plurality of messages to the client including at least one share in each of said plurality of messages. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22)
the threshold encryption logic programmed to divide the secret encryption key into the N shares; and
layered reliable multicast transmitter logic programmed to transmit at least one share in each of a plurality of layers of a layered reliable multicast transmission.
-
-
17. The program product of claim 16 wherein the layered reliable multicast transmission comprises at least N layers and wherein the layered reliable multicast transmitter logic is programmed to transmit a different one of the N shares in each of N layers of the layered reliable multicast transmission.
-
18. The program product of claim 16 further comprising data encryption logic operably coupled between the threshold encryption logic and the layered reliable multicast transmitter logic and programmed to encrypt each of the shares and provide encrypted shares to the layered reliable multicast transmitter logic.
-
19. The program product of claim 18 wherein the data encryption logic is programmed to encrypt each of the N shares using a master key.
-
20. The program product of claim 18 wherein the data encryption logic is programmed to encrypt each of the N shares using a prior secret encryption key.
-
21. The program product of claim 15 comprising:
-
computer readable program code means for dividing the secret into the N shares; and
computer readable program code means for transmitting a plurality of messages to the client including at least one share in each of said plurality of messages.
-
-
22. The program product of claim 21 further comprising computer readable program code means for encrypting each of the N shares prior to transmitting.
-
23. A method for receiving a secret over an unreliable communication network, the method comprising the steps of:
-
receiving a plurality of messages including in each message at least one share of the secret generated by a threshold encryption scheme; and
reconstructing the secret using at least a predetermined minimum number M shares. - View Dependent Claims (24, 25, 26, 27)
receiving a plurality of layers of a layered reliable multicast transmission including in each layer at least one share of the secret generated by a threshold encryption scheme; and
reconstructing the secret using the at least M shares.
-
-
25. The method of claim 23 wherein each share is encrypted and wherein the method further comprises the step of decrypting each share prior to reconstructing the secret.
-
26. The method of claim 25 wherein the step of decrypting each share comprises decrypting each share using a master key.
-
27. The method of claim 25 wherein the step of decrypting each share comprises decrypting each share using a prior secret encryption key.
-
28. An apparatus for receiving a secret encryption key over an unreliable communication network, the apparatus comprising:
-
receiving logic operably coupled to receive a plurality of messages including in each message at least one share of the secret generated by a threshold encryption scheme; and
a threshold decryptor operably coupled to reconstruct the secret using at least a predetermined minimum number M shares. - View Dependent Claims (29, 30, 31, 32)
a layered reliable multicast receiver operably coupled to receive a plurality of layers of a layered reliable multicast transmission including in each layer at least one share of the secret generated by the threshold encryption scheme; and
the threshold decryptor operably coupled to reconstruct the secret using the at least M shares.
-
-
30. The apparatus of claim 28 wherein each share is encrypted and wherein the apparatus further comprises a data decryptor operably coupled to decrypt the shares received by the layered reliable multicast receiver and provide the decrypted shares to the threshold decryptor.
-
31. The apparatus of claim 30 wherein the data decryptor is operably coupled to decrypt each share using a master key.
-
32. The apparatus of claim 30 wherein the data decryptor is operably coupled to decrypt each share using a prior secret encryption key.
-
33. A program product comprising a computer readable medium having embodied therein a computer readable program for receiving a secret over an unreliable communication network, the computer readable program comprising:
-
receiving logic programmed to receive a plurality of messages including in each message at least one share of the secret generated by a threshold encryption scheme; and
threshold decryption logic programmed to reconstruct the secret using at least a predetermined minimum number M shares. - View Dependent Claims (34, 35, 36, 37)
layered reliable multicast receiver logic programmed to receive a plurality of layers of a layered reliable multicast transmission including in each layer at least one share of the secret generated by the threshold encryption scheme; and
the threshold decryption logic programmed to reconstruct the secret using the at least M shares.
-
-
35. The program product of claim 33 wherein each share is encrypted and wherein the program product further comprises data decryption logic programmed to decrypt the shares received by the layered reliable multicast receiver logic and provide the decrypted shares to the threshold decryption logic.
-
36. The program product of claim 35 wherein the data decryption logic is programmed to decrypt each share using a master key.
-
37. The program product of claim 35 wherein the data decryption logic is programmed to decrypt each share using a prior secret encryption key.
-
38. A method of exchanging a secret between a server and a client over an unreliable communication network, the method comprising the steps of:
-
dividing, by the server, the secret into a predetermined number N shares using a threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme;
transmitting, by the server to the client, a first number of messages including at least one share in each of said first number of messages;
receiving, by the client, a second number of messages including at least one share in each of said second number of messages; and
reconstructing, by the client, the secret using at least a predetermined minimum number M shares. - View Dependent Claims (39, 40)
dividing, by the server, the secret into the N shares;
encrypting, by the server, each of the N shares;
transmitting, by the server to the client, a first number of messages including at least one encrypted share in each of said first number of messages;
receiving, by the client, a second number of messages including at least one encrypted share in each of said second number of messages;
decrypting, by the client, each of the encrypted shares received by the client; and
reconstructing, by the client, the secret using the at least M shares.
-
-
40. The method of claim 38 wherein the unreliable communication network comprises a layered reliable multicast network and wherein the method comprises the steps of:
-
dividing, by the server, the secret into the N shares;
transmitting, by the server to the client, at least one share in each of a first number of layers of a layered reliable multicast transmission;
receiving, by the client, a second number of layers of the layered reliable multicast transmission including at least one share in each of said second number of layers; and
reconstructing, by the client, the secret using the at least M shares.
-
-
41. A system for exchanging a secret over an unreliable communication network, the system comprising a server in communication with at least one client over the unreliable communication network, wherein:
-
the server is operably coupled to divide the secret into a predetermined number N shares using a threshold encryption scheme such that at least a predetermined minimum number M shares, but no more than the predetermined number N shares, are needed to reconstruct the secret using the threshold encryption scheme and transmit a first number of messages to the client including at least one share in each of said first number of messages; and
the client is operably coupled to receive a second number of messages including at least one share in each of said second number of messages and reconstruct the secret using at least a predetermined minimum number M shares. - View Dependent Claims (42)
the server is operably coupled to divide the secret into the N shares, encrypt each of the shares, and transmit a first number of messages to the client including at least one encrypted share in each of said first number of messages; and
the client is operably coupled to receive a second number of messages including at least one encrypted share in each of said second number of messages, decrypt each of the received shares, and reconstruct the secret using the at least M shares.
-
Specification