0
$\begingroup$

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 "Learning with errors". 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 < r < 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 $ < 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$.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oh yeh good point you could take the two $q*z_n$ that are closest to each other in size and then you would be left with $q(z_x - z_y) =$ much smaller number to factor. So maybe I am thinking about the learning with errors after all as described in a simple format here: asecuritysite.com/encryption/lwe as the addition of the random error e would solve this problem? For some reason the site linked uses the same e for each item in the list so you would just get $(qi + e) - (qj +e) = (i - j)q$ but maybe using a different error e for each item in the list would work? $\endgroup$
    – Tristan
    May 16, 2021 at 23:52
  • $\begingroup$ Edit: and then I guess instead of adding message $m$ I would have to make each e even and send 1 bit at a time so that I would not need to know which values of e were used in the $^nC_r$ sum in order to decrypt? $\endgroup$
    – Tristan
    May 17, 2021 at 0:10
  • 1
    $\begingroup$ I think it's OK that it's the same e. When it is different, decryption would become difficult. Spontaneously I would say, that you have to transmit the number (call it k) of values you chose from the key list with the encrypted message. Everything else can stay the same, the receiver can subtract e*k an processed normally. This will weaken the strength a bit, but not much. I have no proof, I just don't see a weakness at first glance $\endgroup$
    – jjj
    May 17, 2021 at 0:32
  • $\begingroup$ Yeh I see what you mean. This is my first time taking a proper look at crypto algorithms apart from what I seemed to remember from the method I described that I read somewhere a while back (thanks for pointing out the problem with it :) at least I can forget about that method now haha) so I will take a further dive into this Learning with errors as it seems more friendly than RSA and I may just ask a new titled question about the LWE method on stack exchange if I don't figure anything out. $\endgroup$
    – Tristan
    May 17, 2021 at 1:03
  • $\begingroup$ I checkd and it you should NOT use the SAME e. By subtracting the values you can get rid of it an have the same situation as before, where you can just calculate the gcd! $\endgroup$
    – jjj
    May 18, 2021 at 11:32
3
$\begingroup$

You are describing what you might call an "exact GCD" scheme. It is insecure (as discussed in the comments), and I believe the suggested modification to make it secure (add a single error $e$ to all samples) is insecure as well (take 4 coordinates, subtract pairs of them to get $q(a_0-a_1)$, $q(a_2-a_3)$, and then take GCDs. It seems quite likely you will recover $q$).

There exist secure versions of this, which are normally called "approximate GCD"-based cryptography. This should be seen as a (simplified) variant of lattice-based cryptography, so the fact that in searching you found "Learning with Errors"-based things should not be surprising. I don't know if there are any metrics that AGCD schemes outperform lattice-based schemes, but as they are quite simple they are good to learn with (it seems plausible they might replace/augment RSA as the "first asymmetric scheme" taught to students --- from your post it is even plausible this happened to you).

Anyway, an explicit public-key encryption scheme from AGCD is described here. This particular paradigm (encrypting by taking a subset-sum of the public key) is itself quite popular as well, for example one can build lattice-based PKE from it as well (although there exist more efficient constructions). Anyway, the secure AGCD scheme is broken into three parts.

  1. KeyGen: Generate a bunch of noisy AGCD samples of the form $(a_i, b_i :=qa_i + 2r_i)$ for $i\in[n]$ (the $r_i$ is the noise, and is required). The secret key is $q$

  2. Enc: To encrypt $m\in\{0,1\}$, select some random subset $S\subseteq \{0,1\}^n$, and output $c = m +\sum_{i\in S}b_i = m + q\sum_{i\in S}a_i + 2\sum_{i\in S}r_i$

  3. Dec: Compute $(c\bmod q)\bmod 2$

To see that this is correct, note that $c\bmod q = m + 2\sum_{i\in S}r_i\bmod q$, so provided $2\sum_{i\in S}r_i < q$ the first modular reduction will not overflow. Then $m + 2\sum_{i\in S}r_i \bmod 2 \equiv m$, yielding correct decryption.

There are some parameters to tune ($r_i$'s must not be too small, or it will be insecure. They must not be too large, or it will be incorrect), but setting secure parameters has always been one of the unfortunate annoyances of lattice-based cryptography compared to other techniques (there are just more possible parameters you have to set, and some parameters have to satisfy certain relationships).

Improve this answer
$\endgroup$
3
  • $\begingroup$ So just to confirm you are saying that for large prime private key $q$ you make the public key list of $n$ items by making each item doing $f(q)$ where $f(x) = x * RAN() + ERR()$ where $RAN()$ gives a large random number and $ERR()$ gives a large even number that is $< q$. Then to encrypt single bit $m$ we take the random $^nC_r$ set, sum them and add $m$ to get encrypted message $e$. Then to decrypt we do $e$ mod $q$ and if the result is even then $m$ was $0$ and if odd then $m$ was $1$? This would be secure? I took a look at the site you sent and it suggested it would not be CCA secure. $\endgroup$
    – Tristan
    May 17, 2021 at 12:53
  • $\begingroup$ @Tristan it is like in your original question. But by adding the error, it q can't be derived from the key anymore. The r_i must sum to less than q to ensure that c mod q just leaves the encrypted message plus the summed error. Because the summed error is even, you know if the message was a 0 or a 1. I think it is secure. $\endgroup$
    – jjj
    May 18, 2021 at 10:28
  • $\begingroup$ @tristan if you want CCA security, you typically build a CPA secure scheme and then apply some generic transform (for example, to build a CCA secure KEM one often applies the FO transform to a CPA secure public key encryption scheme). $\endgroup$
    – Mark
    May 18, 2021 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.