What is the name of this public key encryption cryptosystem? I have been trying to find the name of a public key encryption cryptosystem that I learnt as an introduction to cryptography some years ago but the only scheme I could find was something similar but not the same called &quot;Learning with errors&quot;. The scheme I am trying to find the name of works as follows:
Let $q$ be the private key where $q$ is a large prime.
Make a large list of $n$ items with each item being $q * z_n$ where $z_n$ is a different large and random prime number for each position in the list.
So $z_1$ may be $q*a$ and $z_2$ may be $q*b$ where $a,b$ are different primes.
Make this list the public key.
The sender will be sent the public key by the recipient and the sender will encrypt his message $m$ by first taking a $ ^nC_r $ set from the public key list where $r$ is a random number and $1 &lt; r &lt; n$.
Then they sum all the values in this $ ^nC_r $ set and add $m$ to this sum to get the encrypted message $t$.
Note: $m$ must be $ &lt; q $ (we assume it is known that $q$ has some minimum value).
The encrypted value is sent to the recipient and to decrypt it they do $\frac{t}{q}$ to get $m$.
Maybe I miss something, but after some quick thoughts about that algorithm, I think it is not secure. Therefore it may not be used and be more like an example for teaching (with no name).
The problem with the algorithm is that you can derive the secret key q from the public key. When you have two integers a and b, where both are a multiple of q (like all q*z_i in your case), then a - b is also a multiple of q, that is much smaller.
So the private key q can be reconstructed within a fraction of a second for primes with few thousand bits. All you have to do it to take two q*z_i from the public key and compute the greatest (only) common divisor.