Method and apparatus for authenticating users of a communication system to each other

• US 5,202,921 A
• Filed: 04/01/1991
• Issued: 04/13/1993
• Est. Priority Date: 04/01/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Herzberg, Amir, Yung, Marcel M., Kutten, Shay
• Primary Examiner(s): Swann, Tod R.
• Application Number:
  US07/678,474
• Time in Patent Office: 743 Days
• Field of Search: 380/21, 380/23, 380/24, 380/25, 380/28
• US Class Current: 713/162
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
• CPC Class Codes: H04L 9/3273 for mutual authentication network architectures or network communication protocols for achieving mutual authentication in a packet data network H04L63/0869

Abstract

Method and apparatus for authenticating users (entities) of a computer network based on the entity'"'"'s identification is described. Keys for each party of a potential session are derived by projections stored at each party'"'"'s location. The projections are based on a partially computed function which can be in encryption by some key of the user identification or a multivariable polynomial or other function which is partially evaluated for one user'"'"'s identification. Each user evaluates his projection with the other user/party'"'"'s identification. The evaluated quantities are compared using a validation routine. The method requires only one basic piece of information, the projection to be distributed to each user, and does not need specific keys for specific users (or other users'"'"' information stored in one user'"'"'s memory or global network). The method enables adding users to the system directory in a flexible way, without having to notify users of the addition. The method applies to communication heirarchies and inter-domain communication, as well.

Claims

1. In a communication system having a plurality of parties, a method for each party to authenticate another party comprising:

generating a system function in at least two variables, said function two variables representing the identity of first and second parties;

transferring to each of the parties a projection of said function solved for a respective party'"'"'s identity;

evaluating at said first party'"'"'s location said projection with the identity of said second party to obtain a validation number, when said first party needs to authenticate said second party;

evaluating at said second party'"'"'s location said second projection with the identity of said first party;

comparing at each party'"'"'s location the evaluated projections, and determining based on said comparison the authenticity of each party.

2. The method of authenticating of claim 1 wherein said function is a polynomial having an order greater than the number of system parties preventing said parties as a group from deriving said polynomial, or its projections outside said group.

3. The method according to claim 2 wherein said polynomial is selected so that each pair of parties produces a common evaluation of their projections.

4. The method of claim 1 wherein said function is a polynomial having a degree greater than the number of potential malicious parties.

5. The method according to claim 1 wherein each party receives a projection which is based upon an identity of said party and a parameter related to said party.

6. A method for giving each subsystem of an interconnected network the authority to issue information to parties of interconnected subsystems which permit said parties to authenticate each other, comprising:

providing a polynomial having a plurality of variables at a central authority;

providing to each subsystem a projection of said polynomial evaluated for one of said variables, said one variable representing an identifier for said subsystem;

providing from each subsystem to each party connected to a subsystem a projection of said subsystem further evaluated for another of said variables representing said connected party'"'"'s identification;

evaluating remaining variables of said further evaluated projection with another party'"'"'s identification when said another party attempts to initiate a session with said party, whereby a completely evaluated projection results defining a key; and

,

validating said key with a second key at said another party'"'"'s location.

7. The method of claim 6 wherein said second key at said another party'"'"'s location is generated by evaluating a projection received by said another party with respect to a second variable representing said first party identification.

8. The method of claim 7 wherein said first and second parties are connected to different subsystems, each of said parties further evaluating a respective projection using for an additional variable the identity of the other party'"'"'s subsystem.

9. In a communication system interconnecting groups of parties providing intercommunication between parties of different groups, a method for authorizing parties of one group to communicate with parties of another group comprising:

generating for each group independent multivariable functions, two of said variables representing the identity of parties which are to be interconnected;

forwarding to each party of said groups projections of said functions which are partially evaluated for a party'"'"'s identity, whereby each party has a projection representing each group;

evaluating at a party'"'"'s location of a first group desiring to communicate with a party of a second group, said second group'"'"'s projection using the identity of said second group'"'"'s party;

evaluating at a second party'"'"'s location of the second group said second group projection using the identity of said first group first party; and

,

validating the results of said first and second parties'"'"' evaluations.

10. A method for authenticating parties of one class connected by a communication network to parties of a second class comprising:

computing a set of keys which may be used to encrypt data, and projections of said keys based on each party'"'"'s name;

distributing to said first class of said parties a subset of said keys;

distributing said projections of said keys to said second class of parties evaluated for said parties'"'"' names;

encrypting by a party of said first class a value of the name of a party of said second class from each key of said subset associated with said party of said first class, and combining the encryptions;

combining said projections of said keys for a party of said second class, using said first class party'"'"'s identity to generate a key;

validating the combined encryption of said keys of said party of said first class with the key resulting from the combined values of the projections of said party of said second class.

11. A method for authentication according to claim 10 wherein each party of said first class each receive a different subset of keys.

12. A method for authentication according to claim 10, wherein said party of said second class identifies which of said party'"'"'s projections of said second class relate to keys possessed by said party of said first class.

13. The method according to claim 10 wherein said parties of said second class receive said projections further encrypted by a party'"'"'s password.

14. The method according to claim 10 wherein said validation results when said first and second party'"'"'s evaluations are the same.

15. A system for authenticating parties of a common communication network comprising:

a central administrator for selecting a multivariable function, at least two of said variables representing the identity of parties to a communication session;

a first memory at a network node connected to a first party for storing a projection of said function partially evaluated for said party'"'"'s identification;

a second memory at a network node connected to a second party of a communication session, storing a projection of said function evaluated for said second party'"'"'s identification;

means at said first node for evaluating a respective stored projection using the identity of said second party, whereby a first validation quantity is produced;

means at said second node for evaluating said projection of said second party using the identity of said first party, whereby a second validation quantity is produced; and

,

means for validating said first and second validation quantities, whereby the authority of said parties is verified.

16. The system of claim 15, wherein said means for validating said first and second quantities determines whether or not said quantities are equal.

17. The system of claim 16 wherein said user terminals combine said calculated set of keys, and said server encrypts with its keys said user terminals identification, and combines the result to derive a single common key known to both user terminal and server.

18. The system for authenticating a party according to claim 16, wherein said user terminal receives said projections password encrypted.

19. A system for authenticating parties connected to a server comprising:

a plurality of servers, each connected to receive a set of keys from a central administrator;

a plurality of sets of user terminals, each set of user terminals being connected to communicate with a respective plurality of servers;

a central administrator for supplying to each server a different set of keys for authenticating said connected user terminals, and for sending projections of said keys based on an identity associated with said user terminal to each user terminal, whereby each user terminal has a set of projections of a connected server'"'"'s keys, permitting said user terminal to calculate a set of keys common to said connected server, identifying said user terminal as authorized to communicate with said server.

20. The system for authenticating a party according to claim 19 wherein said user receives said projections on a smart card which is read by said terminal.