Method and apparatus for distributing shares of a password for use in multi-server password authentication

• US 20030229788A1
• Filed: 05/24/2002
• Published: 12/11/2003
• Est. Priority Date: 05/24/2002
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Jakobsson, Bjorn Markus, MacKenzie, Philip D.
• Granted Patent: US 7,073,068 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083

Abstract

A method for distributing a password amongst a plurality of servers for subsequent use in a provably secure multi-server threshold password authentication process. A client, having a password to be authenticated by a plurality of servers, generates an encryption of a function of the password. Then, this encryption is provided to each of the servers for use in subsequent password authentication. In accordance with one illustrative embodiment of the invention, the encryption is of an ElGamal ciphertext of the function g^(π_C)−1, where π_C is password and g is the generator used to generate the cryptographic keys used for communication between the client and the plurality of servers.

Claims

1. A method for providing information representative of a password from a client to a plurality of servers, the method performed in preparation for subsequent password authentication of the password by one or more of the plurality of servers, each of the plurality of servers having a share of a secret key, the secret key having a public key associated therewith, the method performed by the client and comprising the steps of:

generating an encryption of a function of the password, the encryption based on the public key; and

communicating the encryption to each server in said plurality of servers for use in said subsequent password authentication.

2. The method of claim 1 wherein the encryption is based on an ElGamal ciphertext of a function of the password.

3. The method of claim 2 wherein the function is g^(π

^_C)−

where π

_C is the password and g is a cryptographic key generator, the cryptographic key generator g having been used to generate cryptographic keys provided for communication between the client and the plurality of servers.

4. The method of claim 3 wherein the encryption comprises the tuple (y^α

g<sup>(π

_C)−

1</sup>,g^α

) where y is the public key and α

is a randomly chosen value.

5. The method of claim 2 wherein the function is the identity function and the encryption is based on an ElGamal ciphertext of the password itself.

6. A method for storing information representative of a password, the method performed in preparation for subsequent password authentication between a client and a plurality of servers, each of the plurality of servers having a share of a secret key, the secret key having a public key associated therewith, the method performed by one of said servers and comprising the steps of:

receiving from said client an encryption of a function of the password, the encryption based on the public key; and

storing said encryption for use in said subsequent password authentication.

7. The method of claim 6 wherein the encryption is based on an ElGamal ciphertext of a function of the password.

8. The method of claim 7 wherein the function is g^(π

<sup>_C)−

1</sup>, where π

_C is the password and g is a cryptographic key generator, the cryptographic key generator g having been used to generate cryptographic keys provided for communication between the client and the plurality of servers.

9. The method of claim 8 wherein the encryption comprises the tuple (y^α

g<sup>(π

_C)−

1</sup>,g^α

), where y is the public key and α

is a randomly chosen value.

10. The method of claim 6 wherein the function is the identity function and the encryption is based on an ElGamal ciphertext of the password itself.