You are currently browsing the archive for the Monero category.

Download pdf here: Ring Signature Schemes

1. Introduction

This is a brief article that introduces the concept of a ring signature. In parts 4, 5, 6, and 7 we will look at specific instances of ring signature schemes — including those used in earlier and more recent versions of the Monero project — and analyze their security properties.

In 1991, Chaum and Van Heyst introduced a new class of signature schemes known as group signatures[2]. The core of the model consisted of a trusted entity known as the group manager that clusters a subset of users together into a group. The group manager provides each member of the group with a separate private key. The ingenuity of this structure lies in the fact that any member can sign messages in an anonymous fashion. This means that anybody who can access the signature, can also verify that it was created by one of the group members without knowing who specifically. The only entity that can identify the real signer is the trusted group manager. In group signature schemes, the anonymity of signers comes at the expense of relinquishing power to the group manager. Indeed, the trusted group manager is the only entity that:

  • Decides who joins the group.
  • Decides which member(s) get(s) banned from the group.
  • Chooses the private key allocated to each member of the group.
  • Identifies the real signer whenever a message is signed.

This setting works best if the group members agreed to cooperate beforehand . The group manager can then serve as the enforcer of this cooperation, revoking the membership of anyone trying to game the system.

The anonymity of group signatures paved the way to another class of signer-ambiguous shemes known as ring signature schemes. The expression ring signature was first coined by Rivest, Shamir, and Tauman[3]. Note that schemes fitting the definition of a ring signature have been proposed way before the publication of this paper. In a ring signature, there does not exist a pre-defined group of users. As a consequence, there does not exist any omnipotent group manager. Instead, the actual signer defines a set of members of her choosing before she signs a message. This set is known as a ring. The only constraint is that the ring must include the actual signer. The signer creates a signature using her private key and all the other ring members’ public keys. The ring can be arbitrary without the need to inform selected members of their participation — (all that is needed is access to their public keys which is usually common knowledge). The reason behind adopting the ring terminology is that “rings are geometric regions with uniform periphery and no center”[3].

Read the rest of this entry »

Tags: , , , ,

1. Introduction

In the next few parts of this series, we look at various signature schemes and prove their security in the RO model. This part is dedicated to the analysis of Pointcheval and Stern Generic Signature Scheme of which the Schnorr scheme is an example. The generic scheme is built around a single (sk,pk) pair. Later parts of this series will focus on ring signature schemes. Ring signatures embed the actual signer in a ring of other possible signers to hide her identity. We will discuss them in parts 3, 4, 5, 6, and 7.

2. Pointcheval and Stern generic signature scheme

For a given message m, our generic scheme creates a signature \sigma(m) \equiv (r,h,\alpha) where r is a random element chosen from a pre-defined set, h = \mathcal{H}(m,r) (i.e., RO output on query (m,r)), and \alpha is fully determined by m, r, and h. By design, we require that the probability of selecting any particular r be upper-bounded by \frac{1}{2^{k-1}} for a given security parameter k.

Schnorr’s signature scheme is an example that fits this generic model. To see why, recall that \Sigma_{Schnorr} chooses a random commitment k \in \mathbb{Z}^{*}_{q} where q is a pre-defined prime number. It then assigns r \equiv g^{k} where g denotes a chosen generator of \mathbb{Z}^{*}_{q}. Afterwards, h is set to \mathcal{H}(m,r). Finally, \alpha is calculated as k-hx where x denotes the signer’s private key. Note that r can be any element of \mathbb{Z}^{*}_{q} and so the probability that it takes on a specific value is equal to \frac{1}{q-1}. By design, we choose the security parameter k \leq log_{2}(q). This choice of k guarantees that the aforementioned probability is upper-bounded by \frac{1}{2^{k}-1} \leq \frac{1}{2^{k-1}}.

Read the rest of this entry »

Tags: , , , , ,

1. Introduction

We divide this post into 6 sections. Section 2 is a qualitative description of digital signature schemes. Section 3 motivates the introduction of hash functions along with some of their desired properties. Section 4 describes a hypothetical ideal random function known as a Random Oracle. Section 5 briefly introduces the notion of Probabilistic Turing Machines that will be needed when studying the security of digital signature schemes. Sections 6 and 7 describe 2 pillars introduced by Poitncheval & Stern to prove the resilience of some digital signature schemes against a forgery attack in the Random Oracle model. In particular, Setion 6 describes a reduction model to facilitate the security analysis of signature schemes. Section 7 states and proves an important lemma known as the splitting lemma.

There is one caveat: I assume that the reader is familiar with basic probability theory, modulo arithmetic, as well as some group theoretic concepts including the notions of cyclic groups and finite fields. A concise introduction to group and field theory can be found in this post. For a more detailed treatment, the reader can refer to e.g., [3].

Read the rest of this entry »

Tags: , , , , , , , , , ,

Newer entries »