Skip to content
Home » Full Security Analysis

Full Security Analysis

We shall give a proof for our one-time ring signature scheme.

These are the properties to be established:

  • Linkability. Given all the secret keys {xi}ni=1 for a set S it is impossible to produce n + 1 valid signatures σ1, σ2, . . . , σn+1, such that all of them pass the LNK phase (i.e. with n+1 different key images Ii). This property implies the double spending protection in Dynex.
  • Exculpability. Given set S, at most n−1 corresponding private keys xi (excluding i = j) and the image Ij of the keys xj it is impossible to produce a valid signature σ with Ij. This property implies theft protection in the context of Dynex.
  • Unforgeability. Given only a public keys set S it is impossible to produce a valid signature σ.
  • Anonymity. Given a signature σ and the corresponding set S it is impossible to determine the secret index j of the signer with a probability p > n1 .

Linkability

Theorem 1. Our one-time ring signature scheme is linkable under the random oracle model. Proof. Suppose an adversary can produce n + 1 valid signatures σi with key images Ii = Ij for any i,j ∈ [1…n]. Since #S = n, at least one Ii = xiHp(Pi) for every i. Consider the corresponding signature σ = (I, c1, . . . , cn, r1, . . . , rn). VER(σ) = “true”, this means that

The first two equalities imply

where logA B informally denotes the discrete logarithm of B to the base A.
We note that i : xi = logHp(Pi) I implies that all ci’s are uniquely determined. The third equality forces the adversary to find a pre-image of Hs to succeed in the attack, an event whose probability is considered to be negligible.

Exculpability

Theorem 2. Our one-time ring signature scheme is exculpable under the discrete logarithm assumption in the random oracle model.

Proof. Suppose an adversary can produce a valid signature σ = (I,c1,…,cn,r1,…,rn) with I =xjHP(Pj)withgiven{xi |i=1,…,j−1,j+1,…,n}. Then,wecanconstructanalgorithm A which solves the discrete logarithm problem in E(Fq).

Suppose inst = (G,P) ∈ E(Fq) is a given instance of the DLP and the goal is to get s, such that P = sG. Using the standard technique, A simulates the random and signing oracles and makes the adversary produce two valid signatures with Pj = P in the set S:

σ = (I,c1,…,cn,r1,…,rn) and σ′ = (I,c′1,…,c′n,r1′ ,…,rn′ ).

Since I = xjHp(Pj) in both signatures we compute xj = logHp(Pj) I = (r j − r j′) / (c′j−cj) mod l

A outputs xj because Lj =rjG+cjPj =rj′G+c′jPj andPj=P.

Unforgeability

Unforgeability is just an implication of both linkability and excul- pability.

Theorem 3. If a one-time ring signature scheme is linkable and exculpable, then it is unforgeable.

Proof. Suppose an adversary can forge a signature for a given set S: σ0 = (I0,…). Consider all valid signatures (produced by the honest signers) for the same message m and the set S: σ1, σ2, . . . , σn. There are two possible cases:

1. I0 ∈ {Ii}ni=1. Which contradicts exculpability.

2. I0 Ii}ni=1. Which contradicts linkability.

Anonymity

Theorem 4. Our one-time ring signature scheme is anonymous under the decisional Diffie- Hellman assumption in the random oracle model.

Proof. Suppose an adversary can determine the secret index j of the Signer with a probability p = n1 + ε. Then, we can construct algorithm A which solves the decisional Diffie-Hellman problem in E(Fq) with the probability 12 + 2ε .

Let inst = (G1,G2,Q1,Q2) ∈ E(Fq) be the instance of DDH and the goal to determine if logG1 Q1 = logG2 Q2. A feeds the adversary with valid signature σ0 = (I,…), where Pj = xjG1 = Q1 and I = Q2 and simulates oracle Hp, returning G2 for query Hp(Pj).

The adversary returns k as his guess for the index i: I = xiHP (Pi). If k = j, then A returns 1 (for “yes”) otherwise a random r ∈ {1, 0}. The probability of the right choice is com- puted as in [24]: 12 +Pr(1 | inst ∈ DDH)−Pr(1 | inst ∈/ DDH) = 12 +Pr(k = j | inst ∈ DDH)+ Pr(k = j | inst ∈ DDH)·Pr(r = 1)−Pr(k = j | inst ∈/ DDH)−Pr(k = j | inst ∈/ DDH)·Pr(r = 0) = (1/2) +(1/n) +ε+( (n−1)/n−ε)·(1/2) − (1/n) − (n−1)/n ·1/2 =1/2 +ε/2

In fact, the result should be reduced by the probability of collision in Hs, but this value is considered to be negligible.

Notes on the hash function Hp

We defined Hp as deterministic hash function E(Fq) → E(Fq). None of the proofs demands Hp to be an ideal cryptographic hash function. It’s main purpose is to get a pseudo-random base for image key I = xHp(xG) in some determined way.

With fixed base (I = xG2) the following scenario is possible:

1. Alice sends two standard transactions to Bob, generating one-time tx-keys: P2 = Hs(r1A)G+ B and P1 = Hs(r2A)G + B.

2. Bob recovers corresponding one-time private tx-keys x1 and x2 and spends the outputs with valid signatures and images keys I1 = x1G2 and I2 = x2G2.

3. Now Alice can link these signatures, checking the equality I1−I2 =? (Hs(r1A)−Hs(r2A))G2.

The problem is that Alice knows the linear correlation between public keys P1 and P2 and in case of fixed base G2 she also gets the same correlation between key images I1 and I2. Replacing G2 with Hp(xG2), which does not preserve linearity, fixes that flaw.

Reference: “Crypto Note v 2.0”; unknown author under the pseudonym Nicolas van Saberhagen; 2013