Patent ID: 8331568

Claim:
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.