1
$\begingroup$

in learning with error encryption scheme (e.g. in Kyber scheme). there are two vectors: $u = r^t A + e_2$ and $v= r^t * pk + e_3 + \lfloor \frac{q}{2}\rceil m$ such that $pk = As +e_1$.

my question is does the encryption still secure if we omit $e_3$ so $v = r^t * pk + \lfloor \frac{q}{2}\rceil m $.

as far as I know (and my current level of understanding) the answer is yes since the underlying problem is (Mod/Ring/Primal) LWE problem.

$\endgroup$

1 Answer 1

2
$\begingroup$

No, it is no longer secure. Kyber is an instantiation of a cryptosystem called "LPR Encryption". Its public key is an LWE encryption of zero $(A, As + e_1)$. Encryption proceeds by computing

  1. $u = r^tA + e_2$ (so $u^t = A^t r + e_2^t$), an LWE encryption of zero under the matrix $A^t$ (which is clearly correlated with $A$), and then
  2. $v = r^t (As + e_1) + (q/2)m + e_3$, an LWE encryption of zero using the random pad $(As + e_1)$.

To argue security, you first

  1. Argue under the LWE assumption that $As + e_1$ is pseudorandom, i.e. you can replace it with a uniformly random string.

  2. Argue that $v$ is now of the form $\langle r,pk\rangle + (q/2)m+e_3$, i.e. is an LWE encryption of $m$. You further need to argue that releasing $(rA^t + e_2)$ does not hurt security, but ignore this for now (it isn't needed to show the insecurity of your proposal).

Under your modification, this second step would no longer work, as $\langle r, pk\rangle + (q/2)m$ is not an LWE encryption (and is instead a "noiseless LWE encryption"). Noiseless LWE encryptions are known to be susceptible to simple attacks, say using Gaussian elimination. So one could attack your cryptosystem by viewing ($pk, r^tpk + (q/2)m)$ as a noiseless LWE encryption of $m$, and running standard attacks in this setting.


The way I reached the above attack was simple --- look at the proof, see what step no longer works, and see if you can attack it. I would highly encourage you to think through things in this way, rather than simply "It uses LWE so it's secure", as reasoning such as that is nearly never sound in cryptography.

$\endgroup$
6
  • $\begingroup$ in the second step why $\langle r,u\rangle + (q/2)m+e_3$ and not $\langle r,pk\rangle + (q/2)m+e_3 $ ? $u\not= pk$ another question can we think $(q/2)m)$ as a noise and r as a secret? so Gaussian Elimination will not work (in fact, this is why I did argued with "it uses LWE so its secure") Thanks Mr. Mark $\endgroup$
    – Don Freecs
    Oct 5, 2022 at 0:13
  • 1
    $\begingroup$ 1. Oops, that's a typo. 2. No, you cannot think of $(q/2)m$ as noise. In the IND-CPA security game, it is assumed the attacker gets control over what $m$ is, so they can always remove it before mounting the Gaussian elimination attack. $\endgroup$
    – Mark Schultz-Wu
    Oct 5, 2022 at 4:09
  • $\begingroup$ thanks, it is clear thanks a lot, $\endgroup$
    – Don Freecs
    Oct 5, 2022 at 10:34
  • $\begingroup$ Who downvoted this answer? $\endgroup$
    – kelalaka
    Oct 7, 2022 at 11:49
  • 1
    $\begingroup$ @DonFreecs, down or upvote cannot be changed after 6 minutes. The only possible way is after the answer is edited (even one may invisibly use comments for that...), I did some minor editings.. $\endgroup$
    – kelalaka
    Nov 3, 2022 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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