A new logarithmic-size signature scheme LS-LSAG

[Ed Hughes]

Hello all,

I'd like to propose an idea of a simple logarithmic-size ring signature scheme 

which can be used in the blockchain and related applications. The signature is 

called LS-LSAG, a draft of it is available at https://eprint.iacr.org/2024/921 

In making this announcement I'd like to ask the community to comment on 

the idea if anyone is interested.

LS-LSAG has such a design so that it can drop-in replace the well-known linear-size

LSAG/CLSAG signature. Also, it looks compatible with the full-chain Curve Trees, 

which in turn can drop-in replace both LS-LSAG and LSAG/CLSAG at the price of

using one more curve with specific properties.

In more detail, LS-LSAG is built up of almost the same systems of equations as

LSAG/CLSAG. However, it makes a call to the inner-product argument instead of 

doing the sequential challenges. This results in the size reduction from linear to logarithmic and in the compatibility with LSAG/CLSAG. Particularly, LS-LSAG and 

LSAG has the same key image.

Formally, LS-LSAG is a log-size linkable ring signature without trusted setup in a 

pairings-free prime-order group of EC points under the DL assumption. 

Unforgeability of LS-LSAG follows from the DL and collision-resistance of the 

standard hash-to-curve function, the draft contains a detailed proof sketch of this.