Cryptographic authentication and/or establishment of shared cryptographic keys, including, but not limited to, password authenticated key exchange (pake)

Abstract

A server () uses a password (π) to construct a multiplicative group (Z*) with a (hidden) smooth order subgroup (<x'>), where the group order (P) depends on the password. The client () 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) for data whose position in a database () is defined by the password. The client provides () 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.