Public key distribution using an approximate linear function

Details Public key distribution using an approximate linear function Public key distribution using an approximate linear function

2005-01-04

2005-01-04

Morse, Gregory (Department: 2134)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

Reexamination Certificate

active

06839839

ABSTRACT:
A completely new and fast public key distribution algorithm is presented which uses only a modest number of weighted multi-precision integer additions (with small integer weights). In a method consistent with the present invention, a first entity determines a first value, x, and determines a weighted sum based on the first value and a first part of a public key corresponding to the second entity. The first entity transmits the weighted sum to the second entity and determines a first comparator based on the first value and a second part of a public key corresponding to the second entity. The second entity determines a second comparator representing an approximate version of the first comparator. Based on the first and second comparators, the first and second entities can agree on cryptographic key information. In one embodiment of the present invention, the first entity determines a first comparator based on a first approximately linear function, the first value, and a second part of a public key corresponding to the second entity, and the second entity determines a second comparator based on the second value and a second approximately linear function related to the first approximately linear function. In one embodiment of the present invention, the method of agreeing on cryptographic key information is based on an approximate linear function, i.e., a family of functions AL(*, w) such that AL(i+j, w)˜AL(i, w)+AL(j, w), where w parameterizes the family.

REFERENCES:
patent: 4218582 (1980-08-01), Hellman et al.
patent: 5297206 (1994-03-01), Orton
patent: 5338959 (1994-08-01), Kim et al.
patent: 5349228 (1994-09-01), Neudeck et al.
patent: 5602047 (1997-02-01), Tsai et al.
Ralph C. Merkle, “Public key distribution using approximately linear functions”, 1998, pp. 1-16.*
Merkle et al., “Hiding Information and Signatures in Trapdoor Knapsacks,” IEEE Transactions on Information Theory, IEEE Inc., vol. IT-24, No. 5, pps. 525-530 New York, Sep. 1978.
Lu et al., “A Conference Key Distribution System Based on the Lagrange Interpolating Polynominal” Networks: Evolution or Revolution? New Orleans, Mar. 27-31, 1988, Proceedings of the Annual Joint Conference of the Computer and Communications Societies, New York, IEEE, vol. Conf. 7, Mar. 27, 1988, pps. 1092-1094.
Leonard M. Adleman,On Breaking the Iterated Merkle-Hellman public-Key Cryptosystem, Advances in Cryptology Proceedings of Crypto 1982, Plenum Press 1983, pp. 303-308.
Ernest F. Brickell,Breaking Iterated Knapsacks, Advances in Cryptology Proceedings of Crypto 1984, Springer Verlag, 1985, pp. 342-358.

Affiliated with

Also associated with

Rating

Public key distribution using an approximate linear function does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Public key distribution using an approximate linear function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Public key distribution using an approximate linear function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3437583