Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM

[Perlner, Ray A. (Fed)]

Dear Enhanced pqsigRM team and community,

 

We have observed a number of weaknesses in the public key of pqsigRM that we believe will lead to a practical full key recovery attack. Most notably, there are a significant number of weight-8 codewords in the dual of the hull of the public key for pqsigRM, which can be used to recover sets of 4 columns in the public key corresponding to columns with the same index mod 2048 in the private key. From this, an additional observation concerning weight 128 codewords in the hull of the public key, and the known attacks of Minder Shokrollahi 2007, Chizov Borodin 2013, we expect that we can practically recover an equivalent private key that is structurally identical to the pqsigRM private key. More details about the attack and what we have experimentally confirmed so far are in the attached slides. (We ultimately plan to finish implementing our attack and publish on eprint.)

 

This attack differs from the previous attack announced on this forum by Debris-Alazard, Loisel, and Vasseur in that our attack does not require access to signatures produced by the honest signer, and therefore cannot be avoided via rejection sampling or other modifications to the signing procedure. We further note that our attack demonstrates that the modifications Enhanced pqsigRM makes to the underlying Reed-Muller code not only are ineffective at hiding the private code’s structure, but in fact make that structure significantly easier to detect.

 

Cheers,

 

Ray Perlner on behalf of

Pierre Briaud,
Maxime Bros,
Ray Perlner,
Daniel Smith-Tone