Improvements and Planned Modifications for LESS

228 views

Skip to first unread message

Edoardo Persichetti

unread,

Jun 16, 2024, 4:22:52 AMJun 16

to pqc-forum, LESS Team

Dear all

I am writing this email on behalf of the LESS team in preparation for Round 2. We are very excited to share with you our recent work on Canonical Forms, which can be found at

https://eprint.iacr.org/2023/1533

Thanks to canonical forms, we are able to reduce the LESS signature size to 2.4KB and below; such sizes are near-optimal, in the sense that they closely approach the theoretical lower bound for signatures following this construction methodology. Furthermore, we show in the paper that there is no security loss when using LESS with this new formulation, thanks to reductions in both ways. Finally, as the cost of computing canonical forms is essentially the same as that of a Gaussian elimination (which is already required as part of the systematic form computation), there is no significant computational overhead involved.

The paper gives an accurate idea of what LESS would look like in Round 2. We stress that canonical forms only affect how the commitments are prepared and verified, and no further changes are necessary; thus, our work can be smoothly embedded into the Round 1 submission. We of course intend to keep working on a number of other aspects; for instance, as small implementation changes will need to be made, we plan to use this opportunity to refine our reference code, by incorporating recent improved techniques for GGM trees, revamping our verification algorithm, and so on.

We would like to thank the community for your support, and look forward to the next Round!