Signature

You are currently browsing articles tagged Signature.

Pointcheval and Stern Generic Signature

April 8, 2018 in Monero | No comments

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

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