Schnorr

You are currently browsing articles tagged Schnorr.

Bitcoin – ECDSA signature

December 24, 2018 in Bitcoin | No comments

Download pdf here: Bitcoin ECDSA

1. Introduction

Simply stated, a bitcoin transaction is a transfer of spending control between different parties over a pre-specified amount of satoshis. A satoshi is the smallest fraction of a bitcoin and is equivalent to BTC $10^{-8}.$ In order to successfuly complete said transfer, the sender must demonstrate that she is the rightful owner of the satoshis she wishes to spend. Such a proof is imperative as it allows the different nodes on the network to reach an agreement regarding the validity of the transaction and as a result, facilitate its inclusion in the blockchain.

At the time of writing, bitcoin’s proof of ownership is encapsulated in a particular type of digital signature known as the Elliptic Curve Digital Signature Algorithm (ECDSA). It is a variant of the Digital Signature Algorithm (DSA) that relies on Elliptic Curve Cryptography (ECC).

In the first section, we introduce the DSA scheme, prove its correctness, and discuss some of its security properties. In particular, we point out that as of the time of writing, and despite its prevalence in various cryptographic settings, we do not know of any valid security proof of DSA in the random oracle (RO) model. However, we highlight that slight variations of it can be proven to be secure.

In the second section, we introduce the ECDSA scheme and prove its correctness. Later on, we present a python-based implementation to further elucidate its building blocks. We also describe how an ECDSA signature gets typically encoded within a bitcoin transaction. Finally, we highlight some of the scheme’s potential shortcomings including the absence to-date of a security proof in the RO model, its susceptibility to being malleable, and its non-linear design that hinders an efficient implementation of multisignature transactions.

Read the rest of this entry »

Tags: dsa, ecdsa, malleability, Schnorr, Security

Herranz & Saèz Generic Ring Signature

April 16, 2018 in Monero | No comments

Download pdf here: Herranz & Saèz Generic Ring Signature

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: anonymity, Crypto, Privacy, ring signature, Schnorr

Pointcheval and Stern Generic Signature

April 8, 2018 in Monero | No comments

Download pdf here: Pointcheval and Stern Generic Signature

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}}$ .