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 significantly increase his success probability of finding 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 first 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 defined 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

\begin{align} M &= g^{m0}h^{r0}\\ &=g^{m0}h^{r+(m-m_0)x^{-1}}\\ &=g^{m_0}h^rg^{m-m_0}\\ &=g^mh^r \end{align}

---

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

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

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

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

---

Formally, we define 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:

\[\begin{split}\text{on input $(comm, 1^n)$ the simulator $Sim $ outouts a tuple:}\\ (\omega_\sigma, \omega_{msg}, \omega_{rnd, R^*}, \omega_{out, sim}) \leftarrow Sim(com, 1^n)\\ \text{such that given $\omega_{out, sim}$ and the message $m_n$ the simulator returns}\\ (\omega_{rnd, S},\omega_{out, S}, \omega_{out, R^*}) = Sim(decom, 1^n, m_n, \omega_{out, sim})\\ \text{with the property that $(\omega_{\sigma}, \omega_{msg}, \omega_{rnd, S}, \omega_{rnd, R^*}, \omega_{out, S}, \omega_{out, R^*})$ is indistinguishable from}\\ view_{S(comm, m_n), R*(comm), \tau ^{1^n}}\end{split}\]

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 identifier as input besides the message, typically this is a random bit string. Specifically, we assume that there is an efficiently 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 identifier :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 definitions 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

\[\begin{split}M = (g_1^{id}g_2 )^m h^r\\ g := g_1^{id} g_2\\ h:= g^x\end{split}\]

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

---

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

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

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\).

G = G1** id * G2

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

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:

\[\begin{split}\text{on input $(comm, 1^n, id_0)$ where $id_0 \leftarrow ID_n$ the simulator Sim outputs a tubple}\\ (\omega_\sigma, \omega_{msg}, id_0, \omega_{out, sim}) \leftarrow Sim(com, 1^n ,id_0)\\ \text{such that given $\omega_{out, sim}, id_0$, and the message $m_n$ the simulator returns}\\ \text{with the property that $(\omega_{sigma}, \omega_{msg}, id_0, \omega_{rnd, S}, \omega_{out,S})$ is indistinguishable from $view_{S{com, m_n, R*(com), \tau(1^n)}}$}\end{split}\]

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:

\[M:=(g^{id}g')^m h^r\]

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 identifier \(id ∈ Z_q\), the simulator selects \(x ∈ Z_q\) and computes:

\[g'=g^{-id}h^x\]

\begin{align} M &= (g^{id}g')^m h^r \\ &= (g^{id}g^{-id}h^x)^mh^r\\ &=h^{mx}h^r\\ &=h^{mx+r} \end{align}

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

---

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

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

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

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

r_ = m*x - m_*x + r

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

True

Ref

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