Crypto

You are currently browsing articles tagged Crypto.

Herranz & Saèz Generic Ring Signature

April 16, 2018 in Monero | No comments

1. Introduction

In the next 4 parts of this series, we look at various ring signature schemes and prove their security in the RO model. This part is dedicated to the analysis of a generic class of ring signature schemes introduced in [1] and inspired by [2]. We also introduce a specific instance of the generic scheme which is itself a generalization of the non-interactive Schnorr signature.

2. Herranz & Saèz generic scheme

The scheme is built on a security parameter k, which by design corresponds to the length in bits of the output of the random oracle \mathcal{H}. Given a message m and a ring L \equiv \{{A_1,...,A_n \}} of n members, the signing algorithm \Sigma outputs a signature \sigma(m,L) \equiv (r_1,...,r_n,h_1,...,h_n,\delta) where:

  • The r_i‘s are pairwise-different random elements chosen from a pre-defined large set. The term pairwise-different means that \forall i,j \in \{{1,...,n\}}, (i \neq j) \Rightarrow (r_i \neq r_j).
  • \forall i \in \{{1,...,n\}}, h_i = \mathcal{H}(m,r_i). That means that h_i is the RO’s output on query (m,r_i).
  • \delta is fully determined by m, r_i, and h_i, for all i \in \{{1,...,n\}}.

By design, we require that the probability of selecting any particular r_i be upper-bounded by \frac{1}{2^{k-1}}. For example, consider the finite field \mathbb{Z}_{q} over a large prime q \geq 2^k. The probability of choosing a particular value for r_i in the mutiplicative cyclic group \mathbb{Z}^{*}_q is equal to \frac{1}{q-1} (assuming a uniform distribution over \mathbb{Z}^{*}_q). Clearly, this is less than or equal to \frac{1}{2^k-1} < \frac{1}{2^{k-1}}.

Read the rest of this entry »

Tags: , , , ,

Digital Signature and Other Prerequisites

April 5, 2018 in Bitcoin, Monero, Prerequisites | No comments

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: , , , , , , , , , ,