Single-round password-based key exchange protocols

• US 8,681,986 B2
• Filed: 05/25/2011
• Issued: 03/25/2014
• Est. Priority Date: 05/25/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jutla, Charanjit Singh, Roy, Arnab
• Primary Examiner(s): Zecher, Cordelia
• Assistant Examiner(s): DOAN, TRANG T
• Application Number:
  US13/115,720
• Publication Number:
  US 20120300930A1
• Time in Patent Office: 1,035 Days
• Field of Search: None
• US Class Current: 380/262
• 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/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A method for initializing encrypted communications using a common reference string and a shared password, includes determining a secret key of a peer using a first message, a second message and the common reference string, wherein the first message and the second message each comprise a tuple of elements of a cyclic group G of prime order p, a blinding encryption of the shared password, and a hash projection key.

Claims

1. A method for initializing encrypted communications using a common reference string and a shared password comprising:

determining a generalized Diffie-Hellman tuple;

generating a one-time simulation-sound zero-knowledge proof proving a consistency of the generalized Diffie-Hellman tuple; and

encrypting a message according to the generalized Diffie-Hellman tuple, the common reference string, and the shared password, wherein the method is performed by a processor,

wherein the common reference string comprises elements g, A and K selected from a cyclic group G, and wherein the generalized Diffie-Hellman tuple comprises elements S and S′

in the cyclic group G, the elements S and S′

are obtained by picking a random integer x, and the element S is determined by exponentiating the element g to the power of the random integer x, and the element S′

is obtained by exponentiating the element A to the power of the random integer x, and

wherein the steps of determining, generating, and encrypting are performed using one or more computer systems.

2. A method for conducting encrypted communication using a common reference string and a shared password comprising:

determining, using one or more computer systems, a secret key using a first message sent to a peer, a second message received from the peer and the common reference string, wherein the first message and the second message each comprise a generalized Diffie-Hellman tuple of elements of a cyclic group G of prime order p, a blinding encryption of the shared password, and a hash projection key,

wherein the common reference string comprises elements g, A, B, K and K1 selected from the cyclic group G, and wherein the generalized Diffie-Hellman tuple comprises elements S, T, and U in the cyclic group G, the elements S, T, and U are obtained by picking random integers x and y, the element S is determined by exponentiating the element g to the power of the random integer x, the element T is determined by exponentiating the element A to the power of the random integer y, and the element U is determined by exponentiating the element B to the power of the random integer x plus the random integer y.

3. The method of claim 2, further comprising decoding by a processor a payload using a decoded form of the secret key.

4. The method of claim 2, further comprising encrypting a payload using a symmetric-key encryption scheme and the secret key.

5. The method of claim 2, wherein the first message and the second message each further comprise a one-time simulation-sound zero-knowledge proof.

6. The method of claim 5, further comprising proving consistency of the tuple by the processor according to a symmetric external Diffie-Hellman assumption.

7. The method of claim 5, further comprising proving consistency of the tuple by the processor according to a decisional linear assumption.

8. A computer program product for initializing encrypted communications using a common reference string and a shared password, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to determine a secret key of a peer using a first message, a second message and the common reference string, wherein the first message and the second message each comprise a generalized Diffie-Hellman tuple of elements of a cyclic group G of prime order p, a blinding encryption of the shared password, and a hash projection key,

wherein the common reference string comprises elements g, A and K selected from the cyclic group G, and wherein the generalized Diffie-Hellman tuple comprises elements S and S′

in the cyclic group G, the elements S and S′

are obtained by picking a random integer x, and the element S is determined by exponentiating the element g to the power of the random integer x, and the element S′

is obtained by exponentiating the element A to the power of the random integer x.

9. The computer program product of claim 8, wherein the first message and the second message each further comprise a one-time simulation-sound zero-knowledge proof.

10. The computer program product of claim 9, further comprising proving consistency of the tuple according to a symmetric external Diffie-Hellman assumption.

11. The computer program product of claim 9, further comprising proving consistency of the tuple according to a decisional linear assumption.

12. A computer program product for initializing encrypted communications using a common reference string and a shared password, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to send a first message to a peer;

computer readable program code configured to receive a second message from the peer; and

computer readable program code configured to determine a secret key of the peer using the first message, the second message and the common reference string, wherein the first message and the second message each comprise a generalized Diffie-Hellman tuple, a blinding encryption of the shared password, a hash projection key, and a one-time simulation-sound zero-knowledge proof proving consistency of the generalized Diffie-Hellman tuple,

wherein the common reference string comprises elements g, A and K selected from a cyclic group G, and wherein the generalized Diffie-Hellman tuple comprises elements S and S′

in the cyclic group G, the computer readable program code comprising;

computer readable program code configured to obtain the elements S and S′

by picking a random integer x, and determining the element S by exponentiating the element g to the power of the random integer x; and

computer readable program code configured to obtain the element S′

by exponentiating the element A to the power of the random integer x.

13. The computer program product of claim 12, further comprising computer readable program code configured to obtain the hash projection key by picking two or more random integers, and determining the hash projection key using the two or more random integers and the elements g, A and K.

14. The computer program product of claim 12, further comprising computer readable program code configured to obtain the encryption of the shared password by exponentiating the element K to the power of the random integer x and multiplying a result with the shared password in the cyclic group G.

15. The computer program product of claim 12, further comprising computer readable program code configured to obtain the encryption of the shared password by exponentiating the element K to the power of the random integer x, and exponentiating by a function determined from the hash projection key and a pre-determined protocol session identifier, and multiplying a result with the shared password in the cyclic group G.

16. A computer program product for initializing encrypted communications using a common reference string and a shared password, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to send a first message to a peer;

computer readable program code configured to receive a second message from the peer; and

computer readable program code configured to determine a secret key of the peer using the first message, the second message and the common reference string, wherein the first message and the second message each comprise a generalized Diffie-Hellman tuple, a blinding encryption of the shared password, a hash projection key, and a one-time simulation-sound zero-knowledge proof proving consistency of the generalized Diffie-Hellman tuple,

wherein the common reference string comprises elements g, A, B, K and K1 selected from a cyclic group G, and wherein the generalized Diffie-Hellman tuple comprises elements S, T and U in the cyclic group G, the computer readable program code comprising;

comprising computer readable program code configured to obtain the elements S, T, and U by picking random integers x and y, comprising, determining the element S by exponentiating the g to a power of the random integer x, determining the element T by exponentiating the element A to a power of the random integer y, and determining the element U by exponentiating the element B to a power of the random integer x plus the random integer y.

17. The computer program product of claim 16, further comprising computer readable program code configured to obtain the hash projection key using the random integers x and y in the cyclic group G and the elements g, A, B, K1, and K2.

18. The computer program product of claim 16, further comprising computer readable program code configured to obtain the encryption of the shared password is obtained by exponentiating the element K1 to a power of the random integer x, and exponentiating the element K2 to a power of the random integer y, multiplying the random integers x and y, and multiplying a result with the shared password.

19. The computer program product of claim 16, further comprising computer readable program code configured to obtain the encryption of the shared password by exponentiating the element K1 to a power of the random integer x, and exponentiating the element K2 to a power of the random integer y, multiplying the random integers x and y, raising a result to a power of a function determined from the hash projection key, and multiplying a result with the shared password.