Password-Based Authentication

• US 20170237725A1
• Filed: 02/12/2016
• Published: 08/17/2017
• Est. Priority Date: 02/12/2016
• Status: Active Grant

• Current Assignee: International Business Machines SA (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: CAMENISCH, Jan Leonhard, LEHMANN, Anja, NEVEN, Gregory
• Granted Patent: US 10,250,591 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A system has λ≧2 servers. At least each of a set of authentication servers stores a key-share sk_i of secret key sk, shared between q of the λ servers, of a key-pair (pk, sk). An access control server sends an authentication value to a subset of the authentication servers. The authentication value was formed using a predetermined function of a first ciphertext for a user ID and a second ciphertext produced by encrypting a password attempt under public key pk using a homomorphic encryption algorithm. The authentication value decrypts to a predetermined value if the password attempt equals the user password for that user ID. Each authentication server in the subset produces a decryption share dependent on the authentication value using the key-share sk_i. The access control server uses decryption shares to determine if the authentication value decrypts to the predetermined value, if so permitting access to a resource.

Claims

1. A method, comprising:

sending by an access control server an authentication value to at least a subset of a set of authentication servers, wherein the access control server is one of λ

≧

2 servers in a system and the set of authentication servers are others of the λ

≧

2 servers, wherein the access control server stores, for each of a plurality of user IDs, a first ciphertext which has been produced by encrypting a user password associated with a respective user ID under a public key pk using a homomorphic encryption algorithm, and wherein the sending is performed in response to receipt from a user computer of a user ID and the authentication value which was previously determined using a predetermined function of a first ciphertext for that user ID and a second ciphertext produced by encrypting a password attempt under the public key pk using a homomorphic encryption algorithm such that the authentication value decrypts to a predetermined value if the password attempt equals the user password for that user ID;

receiving, by the access control server and from each one of the authentication servers in the subset, a decryption share dependent on the authentication value and produced by a corresponding one of the authentication servers using a key-share sk_i thereof, wherein each authentication server stores a respective key-share sk_i of a secret key sk, shared between a plurality q of the λ

servers, of a cryptographic key-pair (pk, sk) where pk is the public key of the key-pair;

using by the access control server at least the decryption shares of the subset of the authentication servers to determine if the authentication value decrypts to the predetermined value, if so permitting access to the resource by the user computer.

2. The method of claim 1, wherein the predetermined function and the first and second ciphertexts are constructed such that the authentication value encrypts a quotient of the user password and the password attempt via the homomorphic encryption algorithm.

3. The method of claim 2;

wherein the predetermined value is 1.

4. The method of claim 3, wherein the authentication value comprises the predetermined function of the first and second ciphertexts blinded with a random exponent r.

5. The method of claim 3, wherein:

the method further comprises receiving by the access control server a blinded value from each of at least the subset of authentication servers, wherein a blinded value has been produced by a corresponding one of the subset of authentication servers by blinding the authentication value with a random exponent r_i;

sending by access control server received blinded values to each of the authentication servers so that each authentication server has blinded values from the subset of authentication servers, and wherein the decryption shares received by the access control server authentication server are produced by corresponding authentication servers by decrypting a randomized authentication value using the secret key-share sk_i thereof, wherein the randomized authentication value is produced by corresponding authentication servers by the combining the blinded values.

6. The method of claim 1, wherein λ

>

2 and the encryption algorithm is an encryption algorithm of a threshold encryption scheme requiring a plurality t<

q of the key-shares sk_i for decryption, and wherein sending further comprises sending by the access control server the authentication value to at least (t−

1) of the authentication servers and using further comprises using the decryption shares of t of the λ

servers to determine if the authentication value decrypts to the predetermined value.

7. The method of claim 6, wherein each of the λ

servers stores a respective key-share sk_i, and wherein the method further comprises producing by the access control server a decryption share and using the decryption share with the other decryption shares from the subset to determine if the authentication value decrypts to the predetermined value.

8. The method of claim 1, wherein the method further comprises verifying, in response to receipt with the authentication value of a cryptographic proof that the authentication value encrypts the second ciphertext and the first ciphertext for the user ID, by the access control server the proof before sending the authentication value to the authentication servers.

9. The method of claim 8, wherein:

the method further comprises sending by the access control server the cryptographic proof with the authentication value to the authentication servers; and

wherein each authentication server in the subset verifies the proof before producing the decryption share.

10. The method of claim 1, further comprising sending, in response to receipt from the user computer of the user ID, by the access control server the first ciphertext for that user ID to the user computer for production of the authentication value.

11. The method of claim 1, further comprising periodically refreshing, by each server which stores a key-share sk_i, a corresponding key-share sk_i.

12. A method, comprising:

receiving at an authentication server an authentication value from an access control server, wherein the authentication server is one of a set of authentication servers, the access control server is one of λ

≧

2 servers in a system and the set of authentication servers are others of the λ

≧

2 servers, wherein each authentication server stores a respective key-share sk_i of a secret key sk, shared between a plurality q of the λ

servers, of a cryptographic key-pair (pk, sk) where pk is a public key of the key-pair, wherein the authentication value was previously determined by a user computer using a predetermined function of a first ciphertext for a user ID and a second ciphertext produced by encrypting a password attempt under the public key pk using a homomorphic encryption algorithm such that the authentication value decrypts to a predetermined value if the password attempt equals the user password for that user ID;

producing, by the authentication server and in response to receipt of the authentication value, a decryption share dependent on the authentication value using the key-share sk_i for the authentication server; and

sending by the authentication server the produced decryption share to the access control server for use by the access control server to determine whether to permit access to a resource by the user computer.

13. The method of claim 12 wherein the predetermined function and the first and second ciphertexts are constructed such that the authentication value encrypts a quotient of the user password and the password attempt via the homomorphic encryption algorithm.

14. The method of claim 13, wherein the predetermined value is 1.

15. The method of claim 14, wherein the authentication value comprises the predetermined function of the first and second ciphertexts blinded with a random exponent r.

16. The method of claim 14, wherein:

the method further comprises;

producing, by the authentication server and in response to receipt of the authentication value, a blinded value by blinding the authentication value with a random exponent r_i;

sending by the authentication server the blinded value to the access control server;

receiving, by the authentication server and from the access control server, blinded values for the other authentication servers in a subset of the set of authentication servers; and

combining the blinded values to produce a randomized authentication value; and

producing the decryption share further comprises producing by the authentication server the decryption share by decrypting the randomized authentication value using the secret key-share sk_i for the authentication server.

17. The method of claim 14, wherein:

the authentication server stores the first ciphertext for the user ID;

the method further comprises;

receiving by the authentication server a cryptographic proof with the authentication value, wherein the cryptographic proof indicates that the authentication value encrypts the second ciphertext and the first ciphertext for the user ID; and

verifying by the authentication server the proof before producing the decryption share.

18. The method of claim 14, further comprising periodically refreshing by the authentication server the key-share sk_i.

19. A method, comprising:

in a user computer having previously produced a first ciphertext by encrypting a user password associated with a user ID under a public key pk using a homomorphic encryption algorithm and previously sent the first ciphertext to an access control server, producing a second ciphertext by encrypting a password input by a user having the user ID under the public key pk using the homomorphic encryption algorithm, wherein the access control server is part of a system shaving λ

≧

2 servers and comprising the access control server and a set of authentication servers, wherein at least each authentication server stores a respective key-share sk_i of a secret key sk, shared between a plurality q of the λ

servers, of a cryptographic key-pair (pk, sk) where pk is a public key of the key-pair;

producing by the user computer an authentication value comprising a predetermined function of the first ciphertext for that user ID and the second ciphertext such that the authentication value decrypts to a predetermined value if the password equals the user password for the user ID;

sending by the user computer the authentication value and the user ID to the access control server via a network; and

accessing or not accessing by the user computer a resource on the network based on response from the access control server.

20. The method of claim 19, further comprising requesting by the user computer the first ciphertext for the user ID from the access control server via the network, and producing the authentication value using the first ciphertext received from the access control server.

21. The method of claim 19, wherein the predetermined function and the first and second ciphertexts are constructed such that the authentication value encrypts a quotient of the user password and the password via the homomorphic encryption algorithm.

22. The method of claim 21 wherein the predetermined value is 1, the method further comprises producing at the user computer the authentication value by blinding the predetermined function of the first and second ciphertexts with a random exponent r, producing a cryptographic proof that the authentication value encrypts the second ciphertext and the first ciphertext for the user ID, and sending the cryptographic proof to the access control server.