LSAG

You are currently browsing articles tagged LSAG.

MLSAG Signature Scheme

May 7, 2018 in Monero | No comments

Download pdf here: MLSAG Signature Scheme

1. Introduction

Monero stands out from other cryptocurrencies in its ability to hide the signer, conceal the transaction amount, and protect the identity of the recepient. Parts 1, 2, 3, 4, 5, and 6 helped us build the foundation to better understand and appreciate the security properties of ring signatures (albeit in the RO model). This part (introduction to MLSAG), as well as part 8 and part 9 will focus on Monero’s privacy in so far as the signer’s identity and the transaction amount are concerned. Part 10 will introduce stealth addresses as a mechanism to protect the identity of the fund’s recipient.

In order to describe how a Monero transaction hides both the signer’s identity and the amount of the transaction, we introduce 2 additional concepts:

  1. A generalization of the LSAG signature (introduced in part 6) to allow each member of the ring to have a key-pair vector [(pk_1,sk_1),.,(pk_n,sk_n)] instead of only one pair (pk,sk).
  2. A particular map known as the Pedersen Commitment that will be used to hide transaction amounts while allowing the network to check that input and output amounts always balance out.

Recall that by proving that a digital signature scheme was unforgeable, one gets the assurance that only the signing algorithm {\Sigma} associated with a given ring member can produce a valid signature (i.e., verified by \mathcal{V}). Any other procedure that bypasses {\Sigma} will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of \mathcal{V}:

  • In a “non-ring” setting, the verification is done using a particular public key pk_{\pi}. The validation of a given signature proves that the signer of the message (in this case user \pi) knows the secret key sk_{\pi} associated with pk_{\pi}. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair (pk_{\pi},sk_{\pi}) signed the message.
  • In a ring setting, the verification is conducted using a public key vector L \equiv [pk_1,...,pk_{\pi},...,pk_n] known as a ring. This vector is used to conceal the identity of the signer. The validation of a given signature proves that the the signer of the message (in this case user \pi) knows the secret key associated with one of the public keys in L. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair (pk_{\pi},sk_{\pi}) signed the message, for some index 1 \leq \pi \leq n that no one other then the actual signer knows.

  • The ring setting can be generalized further by allowing each ring member i, 1 \leq i \leq n to have a key-pair vector of length m, given by [(pk_{i}^1, sk_{i}^1),...,(pk_{i}^m, sk_{i}^m)], as opposed to a unique key pair (pk_i, sk_i). In this setting, the verification is conducted using a public key matrix

        \[PK= \begin{bmatrix} pk_1^1 & ... & pk_{\pi}^1 & ... & pk_n^1 \\ ... & ... & ... & ... & ...\\ pk_1^m & ... & pk_{\pi}^m & ... & pk_n^m \\ \end{bmatrix} \]

    The validation of the signature proves that the signer knows the secret key associated with each one of its public keys. In other terms, there exists a column in PK (say column 1 \leq \pi \leq n) such that the signer knows the secret key associated with each public key appearing in that column. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair vector [(pk_{\pi}^1,sk_{\pi}^1),...,(pk_{\pi}^m,sk_{\pi}^m)] signed the message, for some index 1 \leq \pi \leq n (that no one other then the actual signer knows).

Read the rest of this entry »

Tags: , , , , ,

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.

Read the rest of this entry »

Tags: , , , , , ,