Dynamic anonymous password-authenticated key exchange (APAKE)

Patent metadata

Field	Value
Publication number	US-11070366-B2
Application number	US-201916239564-A
Country	US
Kind code	B2
Filing date	Jan 4, 2019
Priority date	May 8, 2018
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A method for anonymous authentication and key establishment based on passwords (APAKE), includes instantiating, by the server, an OPRF scheme and a symmetric encryption scheme; engaging in, by the client and the server, an OPRFEvaluate protocol so that the client learns a decryption key associated with its password while the server learns nothing; securely transferring, by the server, a nonce and a symmetric encryption key to the client if the client holds a valid password; sending, by the client, its nonce encrypted under the symmetric encryption key; using, by the server, the symmetric encryption key to decipher ciphertext received by virtue of the sending, by the client, its nonce encrypted under the symmetric encryption key and to recover the client's nonce; and computing, by the server and the client, a compute key based on the client's nonce and the server's nonce.

First claim

What is claimed is:

1. A method for anonymous password-authenticated key exchange (APAKE), wherein a server holds a set of valid passwords and a client holds a client password from the set of valid passwords, the method comprising:
defining, by the server, public parameters and a master key;
transmitting, by the server to the client, the public parameters;
engaging, by the server, in an interactive protocol with the client, wherein the interactive protocol involves the public parameters, the master key, and the client password, wherein the interactive protocol enables the client to derive a decryption key associated with the client password, wherein the interactive protocol does not allow the server to identify the client password and does not allow the client to determine the master key or to learn any information on the set of valid passwords;
securely transferring, by the server to the client, an encrypted server nonce and an encrypted symmetric encryption key, wherein the decryption key derived by the client enables the client to decrypt the server nonce and the symmetric encryption key;
receiving, by the server from the client, ciphertext including a client nonce encrypted with the symmetric encryption key;
deciphering, by the server by using the symmetric encryption key, ciphertext received from the client to recover the client nonce; and
computing a common key, which is shared between client and server, based on the client nonce and the server nonce.

2. The method according to claim 1 , wherein the interactive protocol is an oblivious pseudo-random function (OPRF).

3. The method according to claim 2 , wherein the public parameters are generated by a randomized algorithm that partially defines the OPRF.

4. The method according to claim 1 , wherein the symmetric encryption key is derived from a symmetric encryption scheme defined by a triplet of algorithms.

5. The method according to claim 4 , wherein the triplet of algorithms includes:
a first algorithm that is a randomized algorithm that outputs the symmetric encryption key,
a second algorithm that is a randomized algorithm that outputs, based on the symmetric encryption key and the client nonce, the ciphertext, and
a third algorithm that is a deterministic algorithm that outputs, based on the symmetric encryption key and the ciphertext, the client nonce.

6. The method according to claim 1 , wherein the server computes, for each password in the set of valid passwords, a corresponding password tag by using the master key.

7. The method according to claim 6 , wherein the server maps each password tag to the symmetric encryption key using a cryptographic hash function to provide, for each password in the set of valid passwords, a password key.

8. The method according to claim 7 , wherein the server encrypts the server nonce and the symmetric encryption key with each password key to generate, for each password in the set of valid passwords, a ciphertext.

9. The method according to claim 8 , wherein the server initializes an empty associative array, stores the ciphertexts in the array, and sends the array to the client.

10. The method according to claim 9 , wherein the decryption key derived by the client enables the client to decrypt the server nonce and the symmetric encryption key from an index in the array sent by the server.

11. The method according to claim 1 , wherein the interactive protocol is an oblivious programmable pseudo-random function (OPPRF).

12. A non-transitory computer readable medium having stored thereon instructions for performing a method for anonymous password-authenticated key exchange (APAKE), wherein a server holds a set of valid passwords and a client holds a client password from the set of valid passwords, the method comprising:
defining, by the server, public parameters and a master key;
transmitting, by the server to the client, the public parameters;
engaging, by the server, in an interactive protocol with the client, wherein the interactive protocol involves the public parameters, the master key, and the client password, wherein the interactive protocol enables the client to derive a decryption key associated with the client password, wherein the interactive protocol does not allow the server to identify the client password and does not allow the client to determine the master key;
securely transferring, by the server to the client, an encrypted server nonce and an encrypted symmetric encryption key, wherein the decryption key derived by the client enables the client to decrypt the server nonce and the symmetric encryption key;
receiving, by the server from the client, ciphertext including a client nonce encrypted with the symmetric encryption key;
deciphering, by the server by using the symmetric encryption key, ciphertext received from the client to recover the client nonce; and
computing a common key, which is shared between client and server, based on the client nonce and the server nonce.

13. The non-transitory computer readable medium according to claim 12 , wherein the interactive protocol is an oblivious pseudo-random function (OPRF).

14. The non-transitory computer readable medium according to claim 13 , wherein the public parameters are generated by a randomized algorithm that partially defines the OPRF.

15. A server for performing anonymous password-authenticated key exchange (APAKE), the server having access to a memory configured to store a set of valid passwords, the server comprising one or more processors, which alone or in combination, provide for execution of a method comprising:
defining public parameters and a master key;
transmitting, to a client storing a password from the set of valid passwords, the public parameters;
engaging in an interactive protocol with the client, wherein the interactive protocol involves the public parameters, the master key, and a client password, wherein the interactive protocol enables the client to derive a decryption key associated with the client password, wherein the interactive protocol does not allow the server to identify the client password and does not allow the client to determine the master key or any other information about the set of valid passwords;
securely transferring, to the client, an encrypted server nonce and an encrypted symmetric encryption key, wherein the decryption key derived by the client enables the client to decrypt the server nonce and the symmetric encryption key;
receiving, from the client, ciphertext including a client nonce encrypted with the symmetric encryption key;
deciphering, by using the symmetric encryption key, ciphertext received from the client to recover the client nonce; and
computing a common key, which is shared between client and server, based on the client nonce and the server nonce.

Assignees

• NEC Laboratories Europe GmbH
• Nec Corp

Inventors

• Soriente Claudio
• Gonzalez Vasco Maria Isabel
• Perez Del Pozo Angel Luis

Classifications

• H04L63/061

  for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838) · CPC title

• H04L63/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 title

• H04L2209/50

  Oblivious transfer · CPC title

• H04L63/0421 Primary

  Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer · CPC title

• H04L9/0838 Primary

  Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these (network architectures or network communication protocols for key exchange in a packet data network H04L63/061) · CPC title