OFFICIAL COMMENT: CRYSTALS-KYBER
222 views
Skip to first unread message
Jan-Pieter D'Anvers
Jan 17, 2018, 7:26:40 AM1/17/18
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Dear all,
In the security proof of the IND-CPA security of Kyber [1] the values
u'=A^T r+e_1 and v'= t^T r + e_2 in game G1, are substituted with
uniform random values in game G2. The values (A,u) and (t,v') in game G1
are considered as samples from a Module-LWE distribution. In the
definition of Module-LWE (section 2.3 of [1]) you state that the samples
of a_i (in this case A and t), are sampled from a uniform distribution.
However, after compressing and decompressing t, its coefficients are not
uniformly distributed in Z_q, and therefore it is not an MLWE sample. So
I'm wondering how you arrive at the statement that |Pr[b=b′ in game
G1]−|Pr[b=b′in game G2]| ≤ Adv^mlwe_{k+1,k,mu}(B), since the last sample
(t,v') does not seem to be a valid Module-LWE sample.
If proving this step would be a problem, you could add a small error to
t after decompression, to make its coefficients uniformly distributed in
Z_q. Of course, this would result in a (slightly) bigger error and a
(small) increase in computational complexity.
Regards,
Jan-Pieter D'Anvers
[1] Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim
Lyubashevsky, John M. Schanck, Peter Schwabe, and Damien Stehlé.
Crystals – Kyber: a cca-secure module-lattice-based kem. Cryptology
ePrint Archive, Report 2017/634, 2017. http://eprint.iacr.org/2017/634
In the security proof of the IND-CPA security of Kyber [1] the values
u'=A^T r+e_1 and v'= t^T r + e_2 in game G1, are substituted with
uniform random values in game G2. The values (A,u) and (t,v') in game G1
are considered as samples from a Module-LWE distribution. In the
definition of Module-LWE (section 2.3 of [1]) you state that the samples
of a_i (in this case A and t), are sampled from a uniform distribution.
However, after compressing and decompressing t, its coefficients are not
uniformly distributed in Z_q, and therefore it is not an MLWE sample. So
I'm wondering how you arrive at the statement that |Pr[b=b′ in game
G1]−|Pr[b=b′in game G2]| ≤ Adv^mlwe_{k+1,k,mu}(B), since the last sample
(t,v') does not seem to be a valid Module-LWE sample.
If proving this step would be a problem, you could add a small error to
t after decompression, to make its coefficients uniformly distributed in
Z_q. Of course, this would result in a (slightly) bigger error and a
(small) increase in computational complexity.
Regards,
Jan-Pieter D'Anvers
[1] Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim
Lyubashevsky, John M. Schanck, Peter Schwabe, and Damien Stehlé.
Crystals – Kyber: a cca-secure module-lattice-based kem. Cryptology
ePrint Archive, Report 2017/634, 2017. http://eprint.iacr.org/2017/634
Peter Schwabe
Apr 10, 2018, 1:27:06 PM4/10/18
to Jan-Pieter D'Anvers, pqc-co...@nist.gov, pqc-...@list.nist.gov, aut...@pq-crystals.org
Jan-Pieter D'Anvers <janpiete...@esat.kuleuven.be> wrote:
> Dear all,
Dear Jan-Pieter, dear all,
> In the security proof of the IND-CPA security of Kyber [1] the values
> u'=A^T r+e_1 and v'= t^T r + e_2 in game G1, are substituted with uniform
> random values in game G2. The values (A,u) and (t,v') in game G1 are
> considered as samples from a Module-LWE distribution. In the definition of
> Module-LWE (section 2.3 of [1]) you state that the samples of a_i (in this
> case A and t), are sampled from a uniform distribution. However, after
> compressing and decompressing t, its coefficients are not uniformly
> distributed in Z_q, and therefore it is not an MLWE sample. So I'm wondering
> how you arrive at the statement that |Pr[b=b′ in game G1]−|Pr[b=b′in game
> G2]| ≤ Adv^mlwe_{k+1,k,mu}(B), since the last sample (t,v') does not seem to
> be a valid Module-LWE sample.
First of all, sorry for replying so late and thank you for pointing this
out. You are absolutely right. We agree that re-randomization after
decompression of the public key would make sure that the proof goes
through. However, not re-randomizing does not create an actual security
problem, so we decided not to update the definition of Kyber. We discuss
this in more detail in the conference paper, which is now available from
https://pq-crystals.org/kyber/resources.shtml
All the best,
The Kyber team
> Dear all,
Dear Jan-Pieter, dear all,
> In the security proof of the IND-CPA security of Kyber [1] the values
> u'=A^T r+e_1 and v'= t^T r + e_2 in game G1, are substituted with uniform
> random values in game G2. The values (A,u) and (t,v') in game G1 are
> considered as samples from a Module-LWE distribution. In the definition of
> Module-LWE (section 2.3 of [1]) you state that the samples of a_i (in this
> case A and t), are sampled from a uniform distribution. However, after
> compressing and decompressing t, its coefficients are not uniformly
> distributed in Z_q, and therefore it is not an MLWE sample. So I'm wondering
> how you arrive at the statement that |Pr[b=b′ in game G1]−|Pr[b=b′in game
> G2]| ≤ Adv^mlwe_{k+1,k,mu}(B), since the last sample (t,v') does not seem to
> be a valid Module-LWE sample.
out. You are absolutely right. We agree that re-randomization after
decompression of the public key would make sure that the proof goes
through. However, not re-randomizing does not create an actual security
problem, so we decided not to update the definition of Kyber. We discuss
this in more detail in the conference paper, which is now available from
https://pq-crystals.org/kyber/resources.shtml
All the best,
The Kyber team
Reply all
Reply to author
Forward
0 new messages