Ntt Docomo, Inc.

Philip Mackenzie

Zulfikar Ramzan

Craig B Gentry

A server () uses a password (&#x3c0;) to construct a multiplicative group (Z*) with a (hidden) smooth order subgroup (&#x3c;x'&#x3e;), 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&#x2032;) 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.

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

A protocol for closing all active communication links between one device () and one or more other devices in a group provides that the first device sets up the group by generating an input to a predefined function (e.g. one-way function) according to some random distribution, computing the output of the one-way function, and sharing the output value with all other devices in the group. Then to close all communication links, the first device broadcasts the stored input to all other devices in the group. The other devices may check that the one-way function applied to this input results in the shared output value, and if so, close the communication link.

Changing states of communication links in computer networks in an authenticated manner

Using a password (&#x3c0;), a client (C) computes part (H(&#x3c;C,&#x3c0;&#x3e;) of the password verification information of a server (S), and together they use this information to authenticate each other and establish a cryptographic key (K'), possibly using a method resilient to offline dictionary attacks. Then over a secure channel based on that cryptographic key, the server sends an encryption (EE&#x3e;(sk)) of a signing key (sk) to a signature scheme for which the server know a verification key (pk). The encryption is possibly non-malleable and/or includes a decryptable portion (E&#x3c;&#x3e;(sk)) and a verification portion (H(sk)) used to verify the decrypted value obtained by decrypting the decryptable portion. The signing key is based on the password and unknown to the server. The client obtains the signing key using the password, signs a message, and returns the signature to the server. The server verifies this signature using the verification key, hence getting additional proof that the client has knowledge of the password. The client and the server generate a shared secret key (K&#x2033;), more secure than the password, for subsequent communication.

Cryptographic authentication, and/or establishment of shared cryptographic keys, using a signing key encrypted with a non-one-time-pad encryption, including (but not limited to) techniques with improved security against malleability attacks

Growing community of inventors

San Jose, CA, United States of America

Philip Mackenzie