Round 1 (Additional Signatures) OFFICIAL COMMENT: MEDS

[Youming Qiao]

Dear all,
 
We would like to report that we devise a new algorithm for matrix code equivalence, available at https://eprint.iacr.org/2024/368. This algorithm then has the following implication to MEDS parameters (table taken from the paper):

We have timely communicated this with the MEDS team. 

Best regards,

Anand Kumar Narayanan, Youming Qiao, and Gang Tang

[simona s]

Dear all,

The MEDS team would like to thank  Anand, Youming and Gang for showing interest in our scheme MEDS and the clever observation leading to reducing the security level of the Round 1 MEDS parameters.
We acknowledge that the new non-trivial invariant found by them indeed exists for the matrix codes used in MEDS. In order to be secure against this attack we need to increase the parameters of MEDS. We will soon publish the updated parameters.

Note that using a new optimization technique that we have developed for MEDS, even with the required increase of parameters due to the above algorithm, we can still maintain and even improve upon the signature sizes of our current set of parameters for all three security levels. Our optimization technique which was sketched in Section 8 of our specs will soon be made public.

All the best,

The MEDS team

--
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9dc9f126-7871-4aa9-b093-1728a90aae8an%40list.nist.gov.

[simona s]

Dear all,

The MEDS team would like to share the new parameters for all security levels of the MEDS signature scheme. 

The parameters were already announced last month at the 5th NIST PQC Standardization Conference (April 10-12, 2024).

set	q	n	m	k	s	t	w	pk	sig (seed tree)	sig (no seed tree)	signing (ms)	verif (ms)
level1	4093	26	25	25	2	144	48	21595	5456	5200	494	485
level3	4093	35	34	34	2	208	75	55520	10786	10906	2324	2333
level5	4093	45	44	44	2	272	103	122000	21052	19068	8203	9194

The reparametrization is a result of the recent attack by Anand Kumar Narayanan, Youming Qiao, and Gang Tang 

available at https://eprint.iacr.org/2024/368, and to be presented soon at EUROCRYPT. 

The concrete new parameters are also tuned to take advantage of a new signature size optimization technique we 

developed recently (to be presented at PQCrypto). For more details of the optimization, check out our preprint at 

https://eprint.iacr.org/2024/495. 

The benefit from the optimization is that we substantially improve the signature size for approximately the same 

public key size. As a result, even with the increase of parameters due to the recent attack, we still achieve significantly 

smaller signatures than in the initial submission. Furthermore, the signature size scales much better now.

The downside is, as can be seen from the table, the increase in signing and verification time. We are currently 

working on techniques to reduce these numbers.

All the best, 

The MEDS team