# Discrete-Logarithm-Based Trapdoor Commitment Schemes¶

## I Introduction¶

Trapdoors in commitment protocols have already been considered and constructed in the past; they are also called **equivocable commitment schemes** or **chameleon blobs** in the literature.

### Commitment¶

Instructively, one can describe a commitment scheme with a lockable steely box. In the so-called commitment phase, one party, the sender, puts a message into a box, locks the box and gives it to the other party, the receiver. On one hand, the receiver cannot open the box to learn the message, and on the other side, the sender cannot change the message anymore.

### non-malleable commitments¶

a commitment scheme is non-malleable if giving the adversary the original commitment of the honest party does not signiﬁcantly increase his success probability of ﬁnding a commitment of a related message (e.g., a higher bid), compared to the case that the adversary does not have access to the honest party’s commitment at all.

### trapdoors commitment¶

These are commitment schemes for which knowledge of a special information, the trapdoor, allows to overcome the binding property and to open a commitment ambiguously.

Ambiguous decommitments are only possible given this special information; without, a commitment is still solidly binding.

**E.g.**

On the bid auction case:

the adversary ﬁrst sees the commitment of the other sender and is supposed to output his commitment to a higher bid afterwards.

Assume that the honest sender’s commitment contains a trapdoor but the adversary’s commitment does not. Then, on one hand, the honest party’s bid can still be altered by the trapdoor property in principle, even after the adversary has submitted his value. On the other hand, the adversary’s commitment does not have a trapdoor and his value thenceforth is pinned down due to the binding property.

## II Notation¶

### Turing Machine¶

Let A be a probabilistic algorithm, or more formally, a Turing machine with a random tape. We say that A is polynomial-time if there exists a polynomial \(p(n)\) such that A takes at most \(p(n)\) steps on inputs of length \(n\).

Algorithm A runs in expected polynomial-time if A is polynomial-time on the average, the expectation taken over the internal random coins.

For a **deterministic algorithm** \(A\) let **a = A(x)** be the output a of A on input x.

If A is a **probabilistic algorithm** then we denote by **A(x)** the random variable that describes the output of A on input x.

The probability space is deﬁned by the internal coin tosses of A. In this case, we write \([A(x)]\) for the support of A on input x.

By \(a\leftarrow A(x)\) we denote the process of sampling an output a of A on input x.

\(A(x, r)\) is the output of algorithm \(A\) on input \(x\) with random bits \(r\)

### circuit¶

A polynomial-size circuit family is a sequence \(C=(C_n)_{n\in \mathbb{N}}\) of circuits \(C_n\) with the property that the total number of gates of \(C_n\), including the input gates, is polynomially bounded in \(n\).

## III Trapdoor Commitment Schemes¶

The discrete-logarithm scheme includes a trapdoor.

Let the simulator pick \(p, q\) and \(g\) as the trusted party, and let it generate \(h = g^x \mod p\) for random \(x \in Z_q\) . The simulator publishes these values.

Basically, the value x, or more q precisely, the inverse \(x^{-1}\) in, is the trapdoor. because if the simulator commits \(q\) on behalf of the sender to some message \(m_0\) by sending \(M = g^{m_0}h^{r_0}\) for random \(r_0 \in Z_q\), then the simulator can open this commitment with any message \(m \in Z_q\) by computing \(r := r_0 - (m - m_0)x^{−1}\). In this case

```
[1]:
```

```
from klefki.types.algebra.concrete import (
EllipticCurveGroupSecp256k1 as ECG,
EllipticCurveCyclicSubgroupSecp256k1 as CG,
FiniteFieldSecp256k1 as F,
FiniteFieldCyclicSecp256k1 as CF
)
import random
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
def random_cf() -> CF: return CF(random.randint(1, N) % F.P)
G = CG.G
x = random_cf()
H = G^x
```

```
[2]:
```

```
m0 , r0 = random_cf(), random_cf()
M = G**m0 * H**r0
```

```
[3]:
```

```
m = random_cf()
r = r0 - (m - m0) * ~x
```

```
[4]:
```

```
assert M == G**m0 * H**r0 == G**m0 * H**(r+((m-m0)*~x)) == G**m * H**r
```

Formally, we deﬁne all values necessary to adapt the decommitment as the trapdoor, i.e., here \((x, m_0 , r_0)\) form the trapdoor.

**Definition Trapdoor Commit Scheme**

Let \((S, R, T)\) be an M-commitment scheme.

Then the scheme is called a **trapdoor M-commitment scheme** if for any probailistic polynormil-time algorithm \(R^*\) there exists an expected polynomial-time algorithm \(Sim\) such that for any sequence \(m_n; n\in \mathbb{N}\) of message \(m_n \in M_n\) the following holds:

We say that the trapdoor scheme is:

perfectly simulative if the distributions are identical,

statistically simulative if the random variables are statistically close,

computationally simulative if the random variables are computationally indistinguishable.

We call the Simulator’s output \(\omega_{out, sim}\) a trapdoor.

## IV Identity-Based Trapdoor Commitments¶

An identity-based commitment takes an aditional identiﬁer as input besides the message, typically this is a random bit string. Speciﬁcally, we assume that there is an eﬃciently samplable sequence \(ID=(ID_n);n \in \mathbb{N}\) of random variables \(ID_n\) over \(s(n)\)-bit strings. For pa- rameter n we let the sender use some of the random bits for the commitment to sample an identiﬁer :math:`id_n leftarrow ID_nB, and let the sender append this sample `id_n$ to the commitment in clear.

We remark that the commitment itself may also depend on \(id_n\). Then the deﬁnitions of statistically-binding and statistically-secret commit- ment schemes carry over to such **identity-based (ID, M)-commitment schemes**.

we return to the commitment scheme based on the discrete-logarithm problem. the trusted party announces three gener ators \(g_1 , g_2\) and \(h\). A sender with identity \(id ∈ {0, 1} s ⊆ Z_q\), computes his commitment to \(m ∈ Z_q\) by

and sends \((id, M)\) to the receiver.

```
[11]:
```

```
from klefki.types.algebra.concrete import (
EllipticCurveGroupSecp256k1 as ECG,
EllipticCurveCyclicSubgroupSecp256k1 as CG,
FiniteFieldSecp256k1 as F,
FiniteFieldCyclicSecp256k1 as CF
)
from klefki.types.algebra.utils import randfield
from klefki.utils import to_sha256int
G1 = ECG.lift_x(randfield(F))
G2 = ECG.lift_x(randfield(F))
G3 = ECG.lift_x(randfield(F))
x = randfield(CF)
id = randfield(CF)
H = (G1** id * G2) ** x
```

```
[12]:
```

```
m = CF(to_sha256int("hello world"))
r = randfield(CF)
```

```
[13]:
```

```
M = (G1**id * G2) ** m * H ** r
```

Instructively, the identity determines the generator \(g := g_1^{id} g_2\) and the parties run the well-known protocol on the generators \(g\) and \(h\).

```
[14]:
```

```
G = G1** id * G2
```

```
[15]:
```

```
m1 = CF(to_sha256int("hello trapdoor"))
r1 = r - (m1 - m) * ~x
```

```
[16]:
```

```
assert M == G**m * H**r == G**m1 * H**r1
```

**Definition Non-Interactive Identity-Based Trapdoor Commitment Scheme**

Let \((S, R, T )\) be a non-interactive identity-based **(ID, M)-commitment scheme**. The scheme is called an **identity-based trapdoor (ID, M)-commitment scheme** if there ex- ists an expected polynomial-time algorithm \(Sim\) such that for any sequence \((m_n); n∈N\) of messages \(m_n ∈ M_n\) the following holds:

We say that the trapdoor scheme is

perfectly simulative if the distributions are identical,

statistically simulative if the random variables are statistically close,

computationally simulative if the random variables are computationally indistinguishable.

We call the simulator’s output \(\omega_{out,Sim}\) together with \(id_0\) a trapdoor.

For the discrete-logarithm setting the public parameters consist of a group \(G_q ⊆ \mathbb{Z}_p\) of prime order \(q\) generated by some \(g\) and of two further generators \(g' , h\) of \(G_q\) . To commit to \(m ∈ \mathbb{Z}_q\) with \(id ∈ {0, 1}^s ⊆ \mathbb{Z}_q\) the sender picks \(r ∈ \mathbb{Z}_q\) and computes:

and sends M together with id to the receiver.

To set up the identity-based trapdoor the simulator picks \(G_q ⊆ Z\) and \(g , h\) at random. Given the special identiﬁer \(id ∈ Z_q\), the simulator selects \(x ∈ Z_q\) and computes:

Let \(r'=m'x-mx\)

```
[45]:
```

```
from klefki.types.algebra.concrete import (
EllipticCurveGroupSecp256k1 as ECG,
EllipticCurveCyclicSubgroupSecp256k1 as CG,
FiniteFieldSecp256k1 as F,
FiniteFieldCyclicSecp256k1 as CF
)
from klefki.types.algebra.utils import randfield
from klefki.utils import to_sha256int
G = CG.G
H = ECG.lift_x(randfield(F))
x = randfield(CF)
id = randfield(CF)
G_ = G**(-id) * H ** x
```

```
[46]:
```

```
m = CF(to_sha256int("hello world"))
```

```
[47]:
```

```
m_ = CF(to_sha256int("hello trapdoor"))
```

```
[55]:
```

```
M = (G**id * G_) ** m * (H ** r)
```

```
[58]:
```

```
r_ = m*x - m_*x + r
```

```
[59]:
```

```
M == H ** (m*x + r)
```

```
[59]:
```

```
True
```

## Ref¶

Fischlin, Marc. (2001). Trapdoor Commitment Schemes and Their Applications.