OFFICIAL COMMENT: LAKE
Perlner, Ray (Fed)
Dear all.
I would like to report that the submission document for LAKE and LOCKER *underestimates* the complexity of a key recovery attack used to set the parameters. This attack is called the structural attack in the parameter tables and is discussed in section 5.2 of both documents. In particular the document says “[The dual code] contains q^n codewords of the same support, so the complexity of the algorithm is divided by q^n.” This does not follow, since the attack being evaluated involves guessing a space containing the support, not guessing the codeword. A guess will therefore find all the codewords or none of them. This structure can be exploited to speed up the attack but the speed up is actually closer to q^(m/4) for LAKE and LOCKER parameters. I have confirmed this observation with the submitters, and they point out that the correct analysis was given by Gaborit, Ruatta, Schrek, and Zemor, “New Results for Rank-Based Cryptography” Africacrypt 2014. It seems that those looking to improve on the best known key recovery attack for LAKE and LOCKER can now target n-m/4 bits of security more than is claimed by their round 1 submission documents.
We also discussed minors modeling type attacks, concluding that, while previous published analysis of the difficulty of applying minors modeling to the rank syndrome decoding problem was overly pessimistic, such attacks still do not affect the claimed security of the published parameters of LAKE, LOCKER, Ouroboros-R, or RQC. It should be noted here that the analysis is slightly tricky. When conceived of as a MinRank problem over GF2, we have m(n+1) matrices of dimension m x 2n and are looking for a linear combination of rank r. Applying minors modeling results in a system of degree r+1 equations over mn variables. However, Unlike the minors modeling instances typically seen in systems like HFE and Rainbow, the number of linearly independent minors is less than the number of degree r+1 monomials. The system therefore needs to be solved at a higher degree. This complication, which I hadn’t initially noticed, transforms an attack that might have dropped LAKE3 from security strength 5 to security strength 4 (given optimistic assumptions regarding the linear algebra constant and the effective difficulty of high memory attacks) into one which leaves LAKE3 fairly comfortably at security strength 5, barring any additional attacks I don’t know about.
Thanks to the submitters for their responsiveness.
Ray Perlner
David Jao
Hi Ray,
As I understand, this underestimate applies only to the "structural attack" of Section 5.2 and not the "generic attack" of Section 5.1. In cases where the generic attack is faster than the structural attack (or where the generic attack becomes faster than the structural attack after correcting for the aforementioned underestimate), the speed of the generic attack becomes the new security target. Please confirm.
-David
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.
Perlner, Ray (Fed)
Yes. That is correct. The underestimate affects the “structural attack” which is a key recovery attack. It does not affect the “generic attack” which is a message recovery attack. If you’re just looking for the best overall attack, the “generic” attack may indeed be or become the limiting attack.
That said, a message recovery attack can’t in general be converted into a key recovery attack, so key recovery attacks that improve on the “structural attack,” even if they are more expensive than the “generic attack” may still be of some interest. Of course, it’s worth looking into any attack that demonstrates a new or different technique, even if it doesn’t turn out to be the best for any particular goal.