Cryptographic authentication and/or establishment of shared cryptographic keys, including, but not limited to, password authenticated key exchange (PAKE)
First Claim
1. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems, the method comprising the first computer system performing the following operations;
(1) receiving data representing positive integer values N and x whose absolute values are greater than 1;
(2) generating data representing an integer e and an integer b, where b is coprime to N;
(3) generating data which define values y and z such that;
y is congruent to xe mod N; and
z is congruent to bP{overscore (π
)} mod N;
where;
P{overscore (π
)}=P/Pπ
, Pπ
is the product of one or more integers which form a proper subset θ
(π
) of a set PP of non-zero integers, the subset θ
(π
) being associated with the value π
; and
P is the product of all the integers in the set PP;
(4) sending the data which represent the values y and z to the second computer system without sending, to the second computer system, data which represent any one or more of the values e, b, Pπ
, P{overscore (π
)}.
2 Assignments
0 Petitions
Accused Products
Abstract
A server (120) uses a password (π) to construct a multiplicative group (ZN*) with a (hidden) smooth order subgroup (<x′>), where the group order (Pπ) depends on the password. The client (110) uses its knowledge of the password to generate a root extraction problem instance (z) in the group and to generate data (y) allowing the server to construct a discrete logarithm problem instance (y′) in the subgroup. The server uses its knowledge of the group order to solve the root extraction problem, and solves the discrete logarithm problem efficiently by leveraging the smoothness of the subgroup. A shared key (sk) can be computed as a function of the solutions to the discrete logarithm and root extraction problem instances. In some embodiments, in an oblivious transfer protocol, the server queries the client (at 230) for data whose position in a database (210) is defined by the password. The client provides (240) such data without knowing the data position associated with the server'"'"'s query. The client obtains the data position independently from the password. The data positions and/or the respective data are used for authentication and shared secret key generation. Other embodiments are also provided.
33 Citations
32 Claims
-
1. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems, the method comprising the first computer system performing the following operations;
(1) receiving data representing positive integer values N and x whose absolute values are greater than 1;
(2) generating data representing an integer e and an integer b, where b is coprime to N;
(3) generating data which define values y and z such that;
y is congruent to xe mod N; and
z is congruent to bP {overscore (π mod N;
)}
where;
P{overscore (π
)}=P/Pπ
,Pπ
is the product of one or more integers which form a proper subset θ
(π
) of a set PP of non-zero integers, the subset θ
(π
) being associated with the value π
; and
P is the product of all the integers in the set PP;
(4) sending the data which represent the values y and z to the second computer system without sending, to the second computer system, data which represent any one or more of the values e, b, Pπ
, P{overscore (π
)}. - View Dependent Claims (2, 3, 4, 5, 21, 22)
- to the other one of the first and second computer systems, the method comprising the first computer system performing the following operations;
-
6. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems, the method comprising the second computer system performing the following operations;
(1) generating data representing a composite integer N and an integer x;
(2) sending the data representing the values N and x to the first computer system and receiving in response data representing integer values y and z;
(3) generating data representing a value a congruent to a logarithm of y′
to base x′
modulo Pπ
, where;
x′ and
y′
are obtained form x and y; and
Pπ
is the product of one or more integers which form a subset θ
(π
) of a set PP of integers, the subset θ
(π
) being associated with the value π
;
(4) generating data representing a value b congruent to a value z1/P {overscore (π modulo N, where P{overscore (π
)}
)} is the product of the integers in PP−
θ
(π
);
(5) using the values a and b for proving said knowledge of the value π
. - View Dependent Claims (7, 8, 9, 10, 11, 23, 24)
- to the other one of the first and second computer systems, the method comprising the second computer system performing the following operations;
-
12. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems and/or for generating a cryptographic key to be shared by the first and second computer systems, the method comprising the first computer system performing the following operations in interacting with the second computer system;
determining data in a first position in the database, the first position being defined by the value π
;
executing a protocol in which the first computer system receives one or more queries for data in a database, the queries being for data in a second position in the database, the queries not informing the first computer system of the second position, wherein the first computer system provides the data in the second position to the second computer system;
verifying that the first position is the same as the second position, and/or sending a function of the first position to the second computer system to allow the second computer system to verify that the first position is the same as the second position, and/or generating said cryptographic key as a function of the first position. - View Dependent Claims (13, 14, 25, 26)
- to the other one of the first and second computer systems and/or for generating a cryptographic key to be shared by the first and second computer systems, the method comprising the first computer system performing the following operations in interacting with the second computer system;
-
15. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems, the method comprising the second computer system performing the following operations in interacting with the first computer system;
executing a protocol in which the second computer system sends one or more queries for data in a database, the queries being for data in a predefined position in the database, the predefined position being defined by the value π
, the queries not informing the first computer system of the predefined position, wherein the second computer system receives one or more responses to the queries from the first computer system;
verifying that the predefined position is the same as a first position determined by the first computer system from the value π
, and/or sending a function of the predefined position to the first computer system to allow the first computer system to verify that the first position is the same as the predefined position, and/or generating a cryptographic key as a function of the predefined position. - View Dependent Claims (27, 28)
- to the other one of the first and second computer systems, the method comprising the second computer system performing the following operations in interacting with the first computer system;
-
16. A computer-implemented cryptographic authentication method for at least one of first and second computer systems to prove knowledge of a predefined value π
- to the other one of the first and second computer systems and/or for generating a cryptographic key to be shared by the first and second computer systems, the method comprising the first computer system performing the following operations;
(1) receiving data representing a description of a group G;
(2) generating data representing an integer e and an element b of the group G;
(3) generating data which define values y and z such that;
y=xe; and
z=bP {overscore (π ;
)}
where P{overscore (π
)} is the product of one or more integers selected based on the value π
;
(4) sending the data which represent the values y and z to the second computer system for the second computer system to generate data representing values matching the values e and b;
(5) verifying that the values e and b match the values obtained by the second computer system, and/or providing data representing a predefined function of the values e and b to the second computer system to allow the second computer system to verify that the values e and b match the values obtained by the second computer system, and/or generating said cryptographic key from the values e and b. - View Dependent Claims (17, 29, 30)
- to the other one of the first and second computer systems and/or for generating a cryptographic key to be shared by the first and second computer systems, the method comprising the first computer system performing the following operations;
-
18. A computer-implemented cryptographic method establishing a secure communication between first and second computer systems based on a predefined security value π
- , the method comprising the second computer system performing the following operations;
(1) generating first data representing a description of a group G whose order has a predefined relationship to the value π
;
(2) sending the first data to the first computer system and receiving in response data representing elements y and z of the group G;
(3) generating data representing a value a defined by a discrete logarithm of y′
to base x′
, where y′ and
x′
are elements of a proper subgroup of G,y′
being a function of y;
(4) generating data representing a value z1/P {overscore (π , where P{overscore (π
)}
)} is the product of one or more integers selected based on the value π
;
(5) using the values a and b for at least of one of the first and second computer systems to prove knowledge of the value π
to the other one of the first and second computer systems, and/or for generating a cryptographic key. - View Dependent Claims (19, 20, 31, 32)
- , the method comprising the second computer system performing the following operations;
Specification