Patent ID: 7756269

Claim:
A method for efficiently generating, using a processor, two private keys and a public key for a ring-based cryptosystem, comprising: the processor selecting a primary vector from a primary ring R XOR , wherein the primary ring R XOR has elements from the set of N-dimensional vectors with integer coefficients Z N and is distinguished by the operations: ( f + g ) ⁡ [ i ] = f ⁡ [ i ] + g ⁡ [ i ] , and ( f · g ) ⁡ [ i ] = ∑ j = 0 , … , N - 1 ⁢ ( f ⁡ [ j ] ⁢ g ⁡ [ i ⊗ j ] ) , for ⁢ ⁢ 0 ≤ i ≤ N - 1 ; ⁢ where f is an element of the primary ring R XOR , g is an element of the primary ring R XOR , and ⊕ represents an exclusive OR operation between the i and j values; the processor computing a transform of the primary vector; the processor computing a first private key from a secondary ring R XOR,q , wherein R XOR,q comprises the elements of R XOR reduced modulo q, and the first private key is computed using the multiplicative inverse reduced modulo q of each component of the transformed primary vector; the processor computing a second private key from a secondary ring R XOR,p , wherein R XOR,p comprises the elements of R XOR reduced modulo p, and the second private key is computed using the multiplicative inverse reduced modulo p of each component of the transformed primary vector, and q and p are co-prime integer values; and the processor using the first private key to generate a public key, wherein the public key is for encrypting a message and the second private key is used for decrypting the message.