Efficient distribution of computation in key agreement

One or more computer-readable storage media that store executable instructions that, when executed by a computer, cause the computer to perform acts comprising:

• determining that a public key of a client is to be sent to a server in connection with a key agreement to be performed between said client and said server;
• sending, to said server, said public key of said client and a request to use a cipher suite in which said server encrypts a value with said public key of said client;
• receiving, from said server, said value encrypted by said public key;
• decrypting said value with a private key of said client that corresponds to said public key;
• and
• engaging in encrypted communications with said server using a secret key that comprises, or is derived from, said value.

A server for engaging in communication with a client, the server comprising:

• a processor;
• a data remembrance component;
• server software that comprises a plurality of cipher suites, said cipher suites comprising:
• a first cipher suite that implements a first key agreement protocol in which said server uses said server's private key to decrypt an encrypted value received from said client;
• and
• a second cipher suite that implements a second key agreement protocol in which said server chooses a value and encrypts said value with said client's public key, wherein said server receives, from said client, a public key and a list of cipher suites that said client supports, said list comprising said second cipher suite, wherein said server chooses said value, encrypts said value with the public key received from said client, signs, with said server's private key, a message that comprises, or is derived from, (a) the encrypted value, and (b) data received from said client, to create a signature, and sends the encrypted value and said signature to said client.