2
$\begingroup$

In the Kyber paper in section 3 about the Kyber IND-CPA Encryption there is a proof by sequence of games containing three games. I understand that in the first game hop the M-LWE advantage is used to bound the advantage of distinguishing the games. The second hop (from $G_1$ to $G_2$) exchanges two elements ($\boldsymbol{u}', v'$) in the protocol at the same time with essentially the same reasoning.

A similar proof based on R-LWE instead of M-LWE can be seen in the paper by Bos et al. in section 3.

Why is this done in one hop instead of two distinct ones and would it be valid to do it in two hops, i.e exchange one element first and the second one in a second hop?

$\endgroup$

1 Answer 1

2
$\begingroup$

I'm answering my own question here, because i finally found the answer and want to preserve it for future reference.

The Bos et al. paper states it more clearly. The define the R-LWE problem as a problem on $m$ independent samples, either from the uniform distribution over the ring, or from the R-LWE Distribution where the secret $s$ is common to all the samples. With this assumption, we can clearly do the game hop with two simultaneously exchanged parameters (here $m=2$). I am assuming the definition for M-LWE is similar.

Regarding validity of splitting the game hop into two: That may be possible, but is not obvious, i.e. I was not able to write down the reduction.

$\endgroup$

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.