Lucent Technologies Inc.

Alcatel Lucent

Certco, Inc.

Cqrcert, LLC

Philip Douglas MacKenzie

Marcel Mordechay Yung

Yair Frankel

Michael Kendrick Reiter

Bjorn Markus Jakobsson

Sarvar M Patel

Eric Henry Grosse

Victor Vladimir Boyko

Ram Swaminathan

Techniques for an efficient and provably secure protocol by which two parties, each holding a share of a Cramer-Shoup private key, can jointly decrypt a ciphertext, but such that neither party can decrypt a ciphertext alone. In an illustrative embodiment, the secure protocol may use homomorphic encryptions of partial Cramer-Shoup decryption subcomputations, and three-move &#x3a3;-protocols for proving consistency.

Methods and apparatus for providing secure two-party public key cryptosystem

Improved cryptographic techniques are provided by which a device that performs private key operations (e.g., signatures and/or decryptions), and whose private key operations are protected by a password, is immunized against offline dictionary attacks in case of capture by forcing the device to confirm a password guess with a designated entity or party in order to perform a private key operation, and by which the initiating device may dynamically delegate the password-checking function (i.e., confirmation of the password guess) from the originally designated entity or party to another designated entity or party.

Methods and apparatus for delegation of cryptographic servers for capture-resilient devices

The invention provides for robust efficient distributed generation of RSA keys. An efficient protocol is one which is independent of the primality test 'circuit size', while a robust protocol allows correct completion even in the presence of a minority of arbitrarily misbehaving malicious parties. The disclosed protocol is secure against any minority of malicious parties (which is optimal). The disclosed method is useful in establishing sensitive distributed cryptographic function sharing services (certification authorities, signature schemes with distributed trust, and key escrow authorities), as well as other applications besides RSA (namely: composite ElGamal, identification schemes, simultaneous bit exchange, etc.). The disclosed method can be combined with proactive function sharing techniques to establish the first efficient, optimal-resilience, robust and proactively-secure RSA-based distributed trust services where the key is never entrusted to a single entity (i.e., distributed trust totally 'from scratch'). The disclosed method involves new efficient &#x201c;robustness assurance techniques&#x201d; which guarantee &#x201c;correct computations&#x201d; by mutually distrusting parties with malicious minority.

Robust efficient distributed RSA-key generation

Techniques are provided by which a device that performs private key operations (e.g., signatures or decryptions) in networked applications, and whose local private key is activated with, for example, a password or PIN, can be immunized to offline dictionary attacks in case the device is captured. The techniques do not assume tamper resistance of the device, but rather exploit the networked nature of the device, in that the device's private key operations are performed using a simple interaction with a remote server. This server, however, is untrusted, i.e., its compromise does not reduce the security of the device's private key unless the device is also captured, and need not have a prior relationship with the device. Techniques are also provided for supporting key disabling, by which the rightful owner of a stolen device can disable the device's private key even if the attacker already knows the user's password.

Methods and apparatus for providing networked cryptographic devices resilient to capture

A secure protocol is provided which uses a Diffie-Hellman type shared secret, but modified such that the two parties may authenticate each other using a shared password. In accordance with the invention, a party generates the Diffie-Hellman value gand combines it with a function of at least the password using a group operation, wherein any portion of a result associated with the function that is outside the group is randomized. The resulting value is transmitted to the other party. The group operation is defined for the particular group being used. Every group has a group operation and a corresponding inverse group operation. Upon receipt of the value, the other party performs the inverse group operation on the received value and the function of at least the password, and removes the randomization of any portion of the result associated with the function that is outside the group, to extract gsuch that the other party may then generate the shared secret gusing its knowledge of y.

Methods and apparatus for providing efficient password-authenticated key exchange

A method for distributing a password amongst a plurality of servers for subsequent use in a provably secure multi-server threshold password authentication process. A client, having a password to be authenticated by a plurality of servers, generates an encryption of a function of the password. Then, this encryption is provided to each of the servers for use in subsequent password authentication. In accordance with one illustrative embodiment of the invention, the encryption is of an ElGamal ciphertext of the function g, where &#x3c0;is password and g is the generator used to generate the cryptographic keys used for communication between the client and the plurality of servers.

Method and apparatus for distributing shares of a password for use in multi-server password authentication

Secure communication protocols are disclosed in which two parties generate a shared secret which may be used as a secure session key for communication between the parties. The protocols are based on Diffie-Hellman type key exchange in which a Diffie-Hellman value is combined with a function of at least a password using the group operation such that the Diffie-Hellman value may be extracted by the other party using the inverse group operation and knowledge of the password. In one embodiment, each of the parties explicitly authenticates the other party, while in another embodiment, the parties utilize implicit authentication relying on the generation of an appropriate secret session key to provide the implicit authentication. Typically, the parties will be a client computer and a server computer. In accordance with other embodiments of the invention, in order to protect against a security compromise at the server, the server is not in possession of the password, but instead is provided with, and stores, a so-called password verifier which is a function of the password and where the password itself cannot be determined from the value of the password verifier.

Secure mutual network authentication and key exchange protocol

A password-only mutual network authentication protocol and key exchange protocol using a public key encryption scheme in which a server generates a public key/secret key pair and transmits the public key to a client. The client determines whether the public key was chosen in an acceptable manner, and if so, continues with the protocol. Otherwise, the client rejects authentication. If the protocol is continued, in one embodiment the client generates a parameterp as a function of the public key and a password (or, in an alternate embodiment, as a function of the public key and a function of a password). If the public key space mapping function F applied to p, F (p), is an element of the public key message space, then the protocol continues. If F (p) is not an element of the public key message space, then the client determines to reject authentication, but continues with the protocol so that the server does not gain any information about the password. If the client determines to reject authentication, it will terminate the protocol at a later step at which time the termination of the protocol cannot leak any sensitive information. If both the client and the server accept authentication, then session keys are generated for subsequent secure communication between the client and server. Specific embodiments are disclosed in which RSA is used as the public key encryption scheme.

Secure mutual network authentication protocol

The invention provides for robust efficient distributed generation of RSA keys. An efficient protocol is one which is independent of the primality test &ldquo;circuit size&rdquo;, while a robust protocol allows correct completion even in the presence of a minority of arbitrarily misbehaving malicious parties. The disclosed protocol is secure against any minority of malicious parties (which is optimal). The disclosed method is useful in establishing sensitive distributed cryptographic function sharing services (certification authorities, signature schemes with distributed trust, and key escrow authorities), as well as other applications besides RSA (namely: composite ElGamal, identification schemes, simultaneous bit exchange, etc.). The disclosed method can be combined with proactive function sharing techniques to establish the first efficient, optimal-resilience, robust and proactively-secure RSA-based distributed trust services where the key is never entrusted to a single entity (i.e., distributed trust totally &ldquo;from scratch&rdquo;). The disclosed method involves new efficient &ldquo;robustness assurance techniques&rdquo; which guarantee &ldquo;correct computations&rdquo; by mutually distrusting parties with malicious minority.

Growing community of inventors

Maplewood, NJ, United States of America

Philip Douglas MacKenzie