A new logarithmic-size signature scheme LS-LSAG

This innovative scheme is detailed in a draft available at https://eprint.iacr.org/2024/921, inviting the community for comments and discussion. The design of LS-LSAG enables it to act as a direct replacement for the traditionally known linear-size LSAG/CLSAG signatures, offering significant improvements particularly in terms of size efficiency. One of the noteworthy features of LS-LSAG is its compatibility with full-chain Curve Trees, suggesting a seamless substitution not only for LS-LSAG itself but also for LSAG/CLSAG by incorporating an additional curve with specific attributes.

Delving into technical specifics, LS-LSAG is constructed using systems of equations similar to those found in LSAG/CLSAG. However, it diverges by employing an inner-product argument rather than sequential challenges, which is instrumental in reducing the signature size from linear to logarithmic. Such a reduction does not compromise compatibility; LS-LSAG maintains the same key image as LSAG, ensuring a smooth transition between the two signature schemes. Furthermore, LS-LSAG distinguishes itself by being a log-size linkable ring signature that operates without trusted setup within a pairings-free prime-order group of elliptic curve (EC) points, based on the Discrete Logarithm (DL) assumption. The unforgeability of LS-LSAG is substantiated through reliance on the DL principle and the collision resistance of standard hash-to-curve functions. A comprehensive proof sketch outlining these security assurances is included in the draft, providing a foundation for its reliability and potential adoption in cryptographic applications.