Back to results
US 9,432,191 B2Granted
Public key encryption system based on the quadratic residuosity assumption
AssigneeThomson Licensing
InventorsDavide Alessio, Marc Joye
Life of this patent
Estimating the term…
Abstract
A public-key encryption system. Encryption of a k-bit plaintext m is performed by picking a random generating ciphertext and outputting the ciphertext. N is a non-prime integer (preferably the product of two primes p and q), y is an element in multiplicative group of integers modulo N, and k is an integer larger than 1, Decryption of ciphertext c using private key is performed by recovering such that holds and outputting plaintext m, wherein denotes the 2k-th power residue symbol modulo p, which is defined. Also provided are an encryption device and a decryption device. The encryption scheme provides better bandwidth than the Goldwasser-Micali encryption scheme.
Claims12
A device for encryption, the device comprising:
- a memory;
- at least one processor configured to:
- detect plain text having at least one bit;
- generate two random prime numbers that are not equal to each other;
- generate a public key comprising a multiple of a product of the two random prime numbers, an element of a multiplicative group of integers modulo the multiple, and an integer larger than 1;
- generate a random number from the multiplicative group of integers modulo the multiple;
- and
- generate a ciphertext based at least partially on the public key and a formula ymx2k, such that m is the plain text;
- x is the random number;
- y is the element of the multiplicative group of integers modulo the multiple;
- and k is the integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N.
8 more elements
A method for encryption, the method comprising:
- detecting, using at least one processor, plain text having at least one bit;
- generating, using the at least one processor, two random prime numbers that are not equal to each other;
- generating, using the at least one processor, a public key comprising a multiple of a product of the two random prime numbers, an element of a multiplicative group of integers modulo the multiple, and an integer larger than 1;
- generating, using the at least one processor, a random number from the multiplicative group of integers modulo the multiple;
- and
- setting, using the at least one processor, a ciphertext based at least partially on a formula ymx2k, such that m is the plain text;
- x is the random number;
- y is the element of the multiplicative group of integers modulo the multiple;
- and k is the integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N.
6 more elements
A device for decryption, the device comprising:
- a memory;
- at least one processor configured to:
- detect a ciphertext based at least partially on a random number from a multiplicative group of integers modulo a multiple of a product of two random prime numbers and a formula ymx2k, such that m is a plain text;
- x is the random number;
- y is an element of the multiplicative group of integers modulo the multiple;
- and k is an integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N;
- detect a private key equal to one of two random prime numbers whose product is equal to 1 (mod 2k) such that the product minus 1 is divisible by 2;
- and
- decrypt the ciphertext based at least partially on a 2k power residue symbol associated with the ciphertext and the private key and the element of the multiplicative group of integers modulo the multiple of the two random prime numbers.
6 more elements
A method of decryption, the method comprising:
- detecting, using at least one processor, a ciphertext based at least partially on a random number from a multiplicative group of integers modulo a multiple of a product of two random prime numbers and a formula ymx2k, such that m is a plain text;
- x is the random number;
- y is an element of the multiplicative group of integers modulo the multiple;
- and k is an integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N;
- detecting, using the at least one processor, a private key equal to one of two random prime numbers whose product is equal to 1 (mod 2k) such that the product minus 1 is divisible by 2;
- and
- decrypting, using the at least one processor, the ciphertext based at least partially on a 2k power residue symbol associated with the ciphertext and the private key and the element of the multiplicative group of integers modulo the multiple.
4 more elements
A non-transitory computer readable medium with instructions stored therein which upon execution instruct at least one processor to:
- detect plain text having at least one bit;
- generate two random prime numbers that are not equal to each other;
- generate a public key comprising a multiple of a product of the two random prime numbers, an element of a multiplicative group of integers modulo the multiple, and an integer larger than 1;
- generate a random number from the multiplicative group of integers modulo the multiple;
- and
- generate a ciphertext based at least partially on the public key and a formula ymx2k, such that m is the plain text;
- x is the random number;
- y is the element of the multiplicative group of integers modulo the multiple;
- and k is the integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N.
6 more elements
A non-transitory computer readable medium with instructions stored therein which upon execution instruct at least one processor to:
- detect a ciphertext based at least partially on a random number from a multiplicative group of integers modulo a multiple of a product of two random prime numbers and a formula ymx2k, such that m is a plain text;
- x is the random number;
- y is an element of the multiplicative group of integers modulo the multiple;
- and k is an integer larger than 1, in which yεJ2(N)\QR(N) such that N is the multiple, J2(N) is a set of integers associated with N whose Jacobi symbol is 1, and QR(N) is a subset of quadratic residues modulo N;
- detect a private key equal to one of two random prime numbers whose product is equal to 1 (mod 2k) such that the product minus 1 is divisible by 2;
- and
- decrypt the ciphertext based at least partially on a 2k power residue symbol associated with the ciphertext and the private key and the element of the multiplicative group of integers modulo the multiple.
4 more elements
Dependencies are inferred from the claim text.