Efficient distribution of computation in key agreement
First Claim
1. A method of participating in communication with a client, the method comprising:
- using a processor to perform acts comprising;
receiving, at a server, a first public key from a client;
choosing a first value;
encrypting said first value with said first public key of said client to produce an encrypted value;
using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature;
sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and
engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value,wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise;
creating an n-bit fifth value that is derived from said fourth value;
encoding said n-bit fifth value in an m-bit encoding in which no more than k bits are set to one, wherein k<
n<
m;
wherein at least one of said one or more signatures is calculated using said m-bit encoding.
2 Assignments
0 Petitions
Accused Products
Abstract
In Transport Layer Security (TLS) or other communication protocols, the load on the server may be lowered by reducing the number of expensive decryption operations that the server has to perform. When a client contacts a server, the client sends the server the client'"'"'s public key. The server chooses a secret value, encrypts the value with the client'"'"'s public key, and sends the encrypted value to the client. When the client decrypts the secret, the server and client share a secret value, which may be used to derive an encryption key for further messages. In many key agreement schemes, the client chooses and encrypts the secret value, and the server recovers the value with an expensive decryption operation. By instead having the server choose the value and send it to the client, an expensive decryption operation is redistributed from the server to the client, thereby freeing server resources.
-
Citations
18 Claims
-
1. A method of participating in communication with a client, the method comprising:
-
using a processor to perform acts comprising; receiving, at a server, a first public key from a client; choosing a first value; encrypting said first value with said first public key of said client to produce an encrypted value; using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature; sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value, wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise; creating an n-bit fifth value that is derived from said fourth value; encoding said n-bit fifth value in an m-bit encoding in which no more than k bits are set to one, wherein k<
n<
m;wherein at least one of said one or more signatures is calculated using said m-bit encoding. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method of participating in communication with a client, the method comprising:
-
using a processor to perform acts comprising; receiving, at a server, a first public key from a client; choosing a first value; encrypting said first value with said first public key of said client to produce an encrypted value; using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature; sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value, wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits that are set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise; creating an n-bit fifth value that is derived from the data to be signed, wherein the data to be signed comprises, or is derived from, said encrypted value; dividing said n-bit fifth value into d segments of b bits each; creating an m-bit encoding that comprises d blocks each of which has 2b bits; and for each of the d blocks in the m-bit encoding, setting exactly one of the bits in the block to one based on a corresponding b-bit segment in the n-bit fifth value, wherein at least one of said one or more signatures is calculated on said m-bit encoding. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. One or more computer-readable memories that store executable instructions to participate in communication with a client, executable instructions, when executed by a computer, causing the computer to perform acts comprising:
-
receiving, at a server, a first public key from a client; choosing a first value; encrypting said first value with said first public key of said client to produce an encrypted value; using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature; sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value, wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise; creating an n-bit fifth value that is derived from said fourth value; encoding said n-bit fifth value in an m-bit encoding in which no more than k bits are set to one, wherein k<
n<
m;wherein at least one of said one or more signatures is calculated using said m-bit encoding. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification