Method and apparatus for performing multi-server threshold password-authenticated key exchange

• US 20030221102A1
• Filed: 05/24/2002
• Published: 11/27/2003
• Est. Priority Date: 05/24/2002
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Shrimpton, Thomas E., Jakobsson, Bjorn Markus, MacKenzie, Philip D.
• Application Number:
  US10/154,663
• Publication Number:
  US 20030221102A1
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• 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/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A provably secure multi-server threshold password-authenticated key exchange system and method. Initially, an encryption of a function of a client'"'"'s password is provided to each of a plurality of servers. The client later can authenticate the password (i.e., login) by generating an encryption based on the password which is nonetheless mathematically independent of the value of the password. Then, this encryption, along with a “proof” that the encryption was, in fact, generated based on the password, is provided to each of the servers for verification. Thus, it can be shown that the protocol is provably secure. The password authentication protocol advantageously incorporates a thresholding scheme such that the compromise of fewer than a given threshold number of the servers neither compromises the security of the system nor inhibits the proper operation of the password authentication process.

Claims

1. A method for performing password authentication between a client and a plurality of servers, the client having a password to be authenticated by 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 using the public key, wherein the generation of the encryption is based on the password, but wherein the generated encryption is mathematically independent of the password; and

communicating the generated encryption to the plurality of servers.

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

3. The method of claim 1 wherein said encryption is a representation of a predetermined plaintext message.

4. The method of claim 3 wherein said predetermined plaintext message is “

1”

.

5. The method of claim 1 wherein said encryption is generated with use of a password removal transform.

6. The method of claim 5 further comprising the steps of:

generating a proof that said encryption has been generated with use of a password removal transform;

communicating said proof to said plurality of servers.

7. The method of claim 6 wherein said proof comprises a non-interactive zero knowledge proof.

8. The method of claim 1 wherein said plurality of servers consists of n servers, and wherein said step of communicating the generated encryption communicates said generated encryption to a number k of servers, where k<

n, said k servers being sufficient to authenticate said password.

9. A method for performing password authentication between a client and a plurality of servers, the client having a password to be authenticated by 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 one of said servers and comprising the steps of:

receiving from said client an encryption using the public key, wherein the encryption has been generated based on the password, but wherein the generated encryption is mathematically independent of said password; and

verifying that said encryption has been generated based on the password.

10. The method of claim 9 wherein said encryption is a representation of a predetermined plaintext message.

11. The method of claim 9 wherein said encryption has been generated with use of a password removal transform, the method further comprising the step of receiving from said client a proof that said encryption has been generated with use of said password removal transform, and wherein said step of verifying that said encryption has been generated based on the password comprises verifying said proof that said encryption has been generated with use of said password removal transform.

12. The method of claim 11 wherein said proof comprises a non-interactive zero knowledge proof.

13. The method of claim 11 wherein said step of verifying that said encryption has been generated based on the password further comprises verifying that said encryption is a representation of a predetermined plaintext message.

14. The method of claim 13 wherein the predetermined plaintext message is “

1”

.

15. The method of claim 9 wherein said step of verifying that said encryption has been generated based on the password is based on password authentication information received from one or more servers other than the server performing the method.

16. The method of claim 15 wherein said plurality of servers consists of n servers, and wherein said step of verifying that said encryption has been generated based on the password is based on password authentication information received from a number k−

1 of the servers other than the server performing the method, where k<

n.

17. A method for performing password authentication between a client and a plurality of servers, the client having a password to be authenticated by 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 using the public key, wherein the generation of the encryption is based on the password; and

communicating the generated encryption to the plurality of servers, wherein said plurality of servers consists of n servers, and wherein said step of communicating the generated encryption communicates said generated encryption to a number k of servers, where k<

n, said k servers being sufficient to authenticate said password.

18. The method of claim 17 wherein the generated encryption is mathematically independent of the password and wherein said encryption is generated based on an ElGamal ciphertext encryption of a function of said password.

19. The method of claim 17 wherein the generated encryption is mathematically independent of the password and wherein said encryption is a representation of a predetermined plaintext message.

20. The method of claim 19 wherein said predetermined plaintext message is “

1”

.

21. The method of claim 17 wherein the generated encryption is mathematically independent of the password and wherein said encryption is generated with use of a password removal transform.

22. The method of claim 21 further comprising the steps of:

generating a proof that said encryption has been generated with use of a password removal transform;

communicating said proof to said plurality of servers.

23. The method of claim 22 wherein said proof comprises a non-interactive zero knowledge proof.

24. A method for performing password authentication between a client and a plurality of servers, the client having a password to be authenticated by 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 one of said servers and comprising the steps of:

receiving from said client an encryption using the public key, wherein the encryption has been generated based on the password; and

verifying that said encryption has been generated based on the password, wherein said plurality of servers consists of n servers, and wherein said step of verifying that said encryption has been generated based on the password is based on password authentication information received from a number k−

1 of the servers other than the server performing the method, where k<

n.

25. The method of claim 24 wherein the generated encryption is mathematically independent of said password and wherein said encryption is a representation of a predetermined plaintext message.

26. The method of claim 24 wherein the generated encryption is mathematically independent of said password and wherein said encryption has been generated with use of a password removal transform, the method further comprising the step of receiving from said client a proof that said encryption has been generated with use of said password removal transform, and wherein said step of verifying that said encryption has been generated based on the password comprises verifying said proof that said encryption has been generated with use of said password removal transform.

27. The method of claim 26 wherein said proof comprises a non-interactive zero knowledge proof.

28. The method of claim 26 wherein said step of verifying that said encryption has been generated based on the password further comprises verifying that said encryption is a representation of a predetermined plaintext message.

29. The method of claim 28 wherein the predetermined plaintext message is “

1”

.

30. The method of claim 24 wherein said step of verifying that said encryption has been generated based on the password is based on password authentication information received from one or more servers other than the server performing the method.