Subject: [pqc-forum] OFFICIAL COMMENT: RaCoSS From: "D. J. Bernstein" Reply-To: authorcontact-racoss@box.cr.yp.to Date: 23 Dec 2017 14:26:19 -0000 To: pqc-comments@nist.gov Cc: pqc-forum@list.nist.gov Message-ID: <20171223142619.3438.qmail@cr.yp.to> Dear designers, dear all, The RaCoSS design specifies an upper bound for the weight of z. The designers want to ensure that all properly generated signatures are valid. They chose to use the Chernoff bound to compute a bound on the weight of z. We point out that the Chernoff bound is a very weak bound: for the parameters suggested here the 2400-bit vector z is accepted if it has weight no larger than 1564, which means that more than half of the bits of z are allowed to be 1. For comparison, the z in the first KAT has weight 275. This illustrates that a better analysis would lead to better bounds while keeping a negligible probability of failure. The designers could further tighten the bound and push a check whether (z,c) verifies into the signature generation. The algorithm could iterate over different choices of y to find one satisfying the bound. For the given parameters this will not stop the attack laid out in our previous message. Any reasonable choice of bound that will not require too many iterations of choosing y will allow the attacker's z to pass and the attacker similarly has the freedom to change y and on top of that to change the subset of columns in H1. The bounds will become worse with larger weights in c, but those are necessary to avoid preimage attacks on the hash functions. Maybe there are some very large choices of n and k for which one can achieve a separation of the weight of the attacker's z and the legitimately computed values, but we see no chance for the given n and k. Regards Andreas, Dan, Lorenz, and Tanja ----------- Andreas Huelsing, Daniel J. Bernstein, Lorenz Panny, Tanja Lange -- 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+unsubscribe@list.nist.gov. Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.