Exchanging a secret over an unreliable network

Details Exchanging a secret over an unreliable network Exchanging a secret over an unreliable network

1999-01-08

2001-01-30

Peeso, Thomas R. (Department: 2767)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Having particular address related cryptography

C713S178000, C713S152000, C713S152000, C380S036000, C380S029000, C380S274000

Reexamination Certificate

active

06182214

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to communication networks, and, more particularly, to exchanging a secret over an unreliable network.
BACKGROUND OF THE INVENTION
In today's information age, communication networks are becoming ever more pervasive as more and more communication consumers utilize on-line services to access information over the communication network. With this increased use of communication networks comes a need for security, and specifically for ensuring that the information is accessed by only those communication consumers that are authorized to do so.
One problem in many communication networks is that any information transmitted across the network is susceptible to interception by unintended and unauthorized entities. Therefore, encryption is often used to prevent those unintended and unauthorized entities from deciphering the intercepted information. Typically, the information is encrypted using symmetric key cryptography, in which a transmitting device (referred to hereinafter as the “server”) and an intended receiving device (referred to hereinafter as the “client”) share a secret encryption key that is used by the server to encrypt the information and by the client to decrypt the information.
Before symmetric key cryptography can be used to provide secure communication over the communication network, it is necessary for both the sever and the client to possess the shared secret encryption key. One way to distribute the secret encryption key to both the server and the client is to manually enter the secret encryption key into both the server and the client. Unfortunately, a manual key distribution scheme is typically impractical because the server and the client are usually in remote locations. Also, the manual key distribution scheme is generally too time-consuming to be useful for on-line transactions. Furthermore, the manual key distribution scheme is typically considered to be insecure because the secret encryption key is necessarily disclosed to a third party.
A more common way to distribute the secret encryption key to both the server and the client is through a key exchange mechanism performed by the server and the client. The key exchange mechanism permits the server and the client to exchange the secret encryption key over the communication network without any third party intervention, and without compromising the secret encryption key. A commonly used key exchange mechanism requires the server to randomly select the secret encryption key and transmit the secret encryption key to the client using a key exchange protocol. It is important for the key exchange mechanism to work even when communication over the communication network is unreliable. Thus, the key exchange mechanism must work even when there is no guarantee that all messages transmitted by the server will reach the client.
Of course, the secret encryption key is only one type of information that needs to be exchanged between the server and the client. Other types of information, for example, status and control information, may also need to be exchanged between the server and the client. Again, it is important for any such information (referred to hereinafter generically as a “secret,” although the information may be secret or non-secret information) to be successfully exchanged even when communication over the communication network is unreliable.
Thus, a need has remained for a technique for exchanging a secret over an unreliable communication network.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, threshold cryptography (secret sharing) is used for exchanging a secret between a server and a client over an unreliable communication 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.
In accordance with another aspect of the invention, threshold cryptography (secret sharing) is used for encryption key exchange between a server and a client over an unreliable communication network. Specifically, a secret encryption key K 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 encryption key K. 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 encryption key using the threshold encryption scheme.
In accordance with yet another aspect of the invention, threshold cryptography (secret sharing) is used for encryption key exchange between a multicast server and a multicast client over multicast communication network, and specifically over a multicast communication network utilizing a layered reliable multicast scheme. Specifically, a secret encryption key K 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 encryption key K. The N shares are spread over a number of layers of a layered reliable multicast transmission, with the assumption that some number of the layers 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 encryption key using the threshold encryption scheme.
In a typical embodiment, the shares are encrypted prior to transmission by the server and decrypted by the client prior to reconstructing the secret. The shares may be encrypted using any number of encryption algorithms, typically using as the encryption key either a master key or a prior secret encryption key.


REFERENCES:
patent: 5659615 (1997-08-01), Dillon
patent: 5748736 (1998-05-01), Mittra
“Applied Cryptography,” 1996, John Wiley & Sons, New York, XP002137412, pp. 71-73 and pp. 528-531.
Schneier, Bruce, “Applied Cryptography, Second Edition, Protocols, Algorithms, and Source Code in C”, pp. 71-73 and pp. 528-531.
Ballardie, Tony, et al, “Core Based Trees (CBT), An Architecture for Scalable Inter-Domain Multicast Routing”, pp. 85-95.
McCanne, Steven, et al, “Receiver-driven Layered Multicast”, pp. 117-130.

Affiliated with

Also associated with

Rating

Exchanging a secret over an unreliable network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Exchanging a secret over an unreliable network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exchanging a secret over an unreliable network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2491189