For a given ring size , Cryptonote’s original scheme (as introduced in part 5), generates signatures of the form consisting of arguments. It turns out that a more efficient scheme initially introduce in  and later adapted by Adam Back in  can achieve the same security properties as Cryptonote’s with arguments instead (a reduction factor that tends to 2 as tends to ). The scheme introduced in  is known as Linkable Spontaneous Anonymous Group signature or LSAG signature scheme for short. In part 7 of this series, we will see how  generalizes the LSAG construct to build the foundation of Monero’s current ringCT signature scheme.
2. The LSAG scheme
The LSAG signature introduced in  is built on a group of prime order and generator . Moreover, it uses 2 statistically independent ROs:
In what follows we introduce a slightly modified LSAG scheme that will allow an easier comparison to Cryptonote’s original scheme. We carry forward all the notation used in the Cryptonote scheme to the current LSAG definition. In particular, we let be a large finite group generated by the same elliptic curve introduced in part 5 (refer to the post entitled Elliptic Curve Groups for an introduction to this topic). We also consider the same base point . Recall that the base point is chosen in such a way to ensure that it has a large prime order All arithmetic is done in the subgroup of the elliptic curve group As a matter of convention, we write