Group

You are currently browsing articles tagged Group.

LSAG Signature Scheme

April 26, 2018 in Monero | No comments

Download pdf here: LSAG Signature Scheme

1. Introduction

For a given ring size $n$ , Cryptonote’s original scheme (as introduced in part 5), generates signatures of the form $(I, c_1,..,c_n,r_1,..,r_n)$ consisting of $(2n+1)$ arguments. It turns out that a more efficient scheme initially introduce in [3] and later adapted by Adam Back in [1] can achieve the same security properties as Cryptonote’s with $(n+2)$ arguments instead (a reduction factor that tends to 2 as $n$ tends to $\infty$ ). The scheme introduced in [3] is known as Linkable Spontaneous Anonymous Group signature or LSAG signature scheme for short. In part 7 of this series, we will see how [4] generalizes the LSAG construct to build the foundation of Monero’s current ringCT signature scheme.

2. The LSAG scheme

The LSAG signature introduced in [3] is built on a group $E$ of prime order $q$ and generator $G$ . Moreover, it uses 2 statistically independent ROs:

$\mathcal{H}_1: \{{0,1\}^*} \longrightarrow \mathbb{F}_q$
$\mathcal{H}_2: \{{0,1\}^*} \longrightarrow E$

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 $E$ 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 $G$ . Recall that the base point is chosen in such a way to ensure that it has a large prime order $l < q.$ All arithmetic is done in the subgroup $\{{G\}}$ of the elliptic curve group $E.$ As a matter of convention, we write $\{{G\}^{*}} \equiv \{{G\}} - e.$