Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1999-05-10
2004-08-17
Wright, Norman M. (Department: 2134)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C713S161000, C713S162000, C380S029000, C380S030000, C380S259000, C380S267000
Reexamination Certificate
active
06779111
ABSTRACT:
BACKGROUND
The present invention relates to communications networks and to security and encryption techniques. More particularly, the present invention relates to network architectures and methods for encrypting communications data messages between clients and servers.
Modern communications often require privacy, whether for transmission of financial information in the course of electronic commerce or for transmission of trade secrets and other important commercial information. One way to protect the privacy of communications is to encrypt them according to either a symmetric cryptosystem or an asymmetric cryptosystem.
In general, a symmetric cryptosystem is a set of instructions, implemented in either hardware, software or both that can convert plaintext (the unencrypted information) to ciphertext, or vice versa, in a variety of ways, using a specific key that is known to the users but is kept secret from others. An example of a symmetric cryptosystem is the Data Encryption Standard (DES), which is described in
Data Encryption Standard
, Federal Information Processing Standards Publication 46 (1977) (“FIPS PUB 46”, republished as FIPS PUB 46-1 (1988)) and
DES Modes of Operation
, FIPS PUB 81 (1980) that are available from the U.S. Department of Commerce.
An asymmetric encryption system typically employs two keys, one for encryption and one for decryption, where knowledge of one key (the public key) does not permit derivation of the second key (the private key). Various aspects of public-key cryptographic (PKC) systems are described in the literature, including R. L. Rivest et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”
Communications of the ACM
vol. 21, pp. 120-126 (February 1978); M. E. Hellman, “The Mathematics of Public-Key Cryptography”,
Scientific American
vol. 234, no. 8, pp. 146-152, 154-157 (August 1979); and W. Diffie, “The First Ten Years of Public-Key Cryptography”,
Proceedings of the IEEE
vol. 76, pp. 560-577 (May 1988).
For either a symmetric or PKC system, the security of a message is dependent to a great extent on the length of the key, as described in C. E. Shannon, “Communication Theory of Secrecy Systems”,
Bell System Technical Journal
vol. 28, pp. 656-715 (October 1949).
Many popular PKC systems use the fact that finding large prime numbers is computationally easy but factoring the products of two large prime numbers is computationally difficult. Thus, PKC permits the user's public key to be posted (e.g., in a directory or on a bulletin board), without compromising the user's private key. This public-key concept simplifies the key distribution process. Example PKC algorithms are the digital signature algorithm and secure hash algorithm (DSA/SHA) and RSA/MD5.
The RSA algorithm is described in the above-cited publication by R. L. Rivest et al. and is commonly used in a client-server processor architecture, such as that illustrated in
FIG. 1
, to encrypt a message M using the server's public key [e, n] resulting in ciphertext M′ as follows:
M′=M
e
mod n
This RSA encryption operation is computationally expensive for clients that currently have limited computing power, e.g., mobile phones and personal digital assistants (PDAs). As a result, the time needed for such a thin client to encrypt a message can be unacceptable.
In a client-proxy-server architecture such as that illustrated in
FIG. 2
, the client may be able to exploit the higher computational power of the proxy to off-load the expensive RSA encryption algorithm and reduce the client's response time. For one example, the client can simply pass the plaintext message M to the proxy, which in turn performs a full RSA encryption. For another, better example, the client can “lightly encrypt” the plaintext message M, forming a ciphertext m with an algorithm that is less computationally expensive than RSA, and then securely pass the “lightly encrypted” message m to the proxy, which in turn performs a full encryption, forming the ciphertext M′. (It will be appreciated that some form of authentication would typically be used between the client and the proxy.)
The problem with these examples is the absence of end-to-end, client-server security. Indeed, the client must trust the proxy because the proxy has easy access to the plaintext M. Applicants invention achieves end-to-end, client-server security at the same time as a computationally expensive encryption algorithm is off-loaded to an untrusted proxy, i.e., without revealing the plaintext to the proxy.
General aspects of the problem of computing with encrypted data are described in B. Schneier,
Applied Cryptography
2d ed., sections 4.8 and 23.6, pp. 85-86 and 540-541, John Wiley & Sons (1996). Also, the publication by Y. Desmedt et al., “Shared Generation of Authenticators and Signatures”,
Advances in Cryotology—Cryoto
'91, Lecture Notes in Computer Science, vol. 537, pp. 457-469, Springer-Verlag (1991) describes group signatures, which are schemes where a given number of individuals can collectively generate a single secure signature without interaction among the individuals and without revealing the secret key to any of them.
The Charon protocol, which is described in A. Fox et al., “Security on the Move: Indirect Authentication Using Kerberos”,
Proceedings Mobicom
96 (1996), provides indirect authentication using a trusted proxy for the Kerberos authentication protocol.
The Internet publication, M. Blaze et al., “Atomic Proxy Cryptography”,
www.research.att.com
, AT&T Labs—Research (Feb. 23, 1998), describes atomic proxy cryptography, in which an atomic proxy function with a proxy key converts ciphertext for a key k
1
into ciphertext for another key k
2
.
In J. Feigenbaum, “Encrypting Problem Instances, or, . . . Can You Take Advantage of Someone without Having to Trust Him”,
Advances in Coytology—Coyto
'85, Lecture Notes in Computer Science, vol. 218, pp. 477-488, Springer-Verlag (1986), a method for computing with encrypted data is described, where a party A lacks the computational power to perform a calculation and lets another untrusted party B with more computing power do a partial calculation. The result of this is further used by the original party A to compute the final result using a simpler operation.
U.S. Pat. No. 5,696,823 to Blaze describes a way to use an untrusted high-bandwidth device for block symmetric encryption on behalf of a secure low-bandwidth device. PKC is used for authentication or key exchange in the symmetric cryptographic protocols, not for information data encryption. The patent is directed to symmetric encryption, not the problem of public key encryption “on the fly”. Also, the host does not only act as a proxy; calculations made by the host must be performed if it should be possible to encrypt or decrypt a message, and the cleartext is located in the insecure device after decryption. Thus, the host is “untrusted” only with respect to the secret key, not with respect to the data to be encrypted.
None of these publications solves the problem addressed by Applicants' invention, which provides end-to-end, client-server security at the same time as a computationally expensive encryption algorithm is off-loaded to an untrusted proxy, i.e., without revealing the plaintext to the proxy.
SUMMARY
The present invention addresses certain shortcomings in the art by providing a network architecture and method for providing secure (e.g., encrypted) communications between a client and server that enables computationally expensive encryption calculations to be performed by a proxy server, rather than by the client. In other words, the methods of the present invention enable the client to delegate certain computationally expensive encryption calculations to the proxy server. Delegating these computations is particularly advantageous for “thin” clients (e.g., devices which are characterized by limited processing power, transmission bandwidth, and/or memory). Delegating these computations enables a thin client to utilize
Barriga Luis
Gehrmann Christian
Telefonaktiebolaget LM Ericsson (publ)
Wright Norman M.
LandOfFree
Indirect public-key encryption does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Indirect public-key encryption, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Indirect public-key encryption will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291610