Non-interactive and Reusable Non-malleable Commitment Schemes

I Common reference string model

In cryptography, the common reference string (CRS) model captures the assumption that a trusted setup in which all involved parties get access to the same string crs taken from some distribution D exists. Schemes proven secure in the CRS model are secure given that the setup was performed correctly. The common reference string model is a generalization of the common random string model, in which D is the uniform distribution of bit strings. As stated in, the CRS model is equivalent to the reference string model and the public parameters model.

II Framework

Honest Sender Commitment

We introduce the notion of honest sender commitments. This covers a special type of commitment scheme with a weak binding property, it is not a real commitment scheme. When speaking of an honest sender commitment scheme, we do not require the commitment scheme to be binding. Instead, we only demand that it is binding whenever a commitment has been formed by an honest sender, i.e., when it has been formed according to the protocol.

\(\Sigma\)-protocol for the Signature Scheme

A Σ-protocol for relation R is a special type of a 3-move honest verifier zero-knowledge proof. It is a protocol for two parties, the prover \(P\) and the verifier \(V\) . \(P\) gets as input \((x, w) ∈ R\), \(V\) gets as input \(x\), and the goal is for \(P\) to convince \(V\) that he knows \(w\) such that \((x, w) ∈ R\), without revealing information about \(w\). We require that it be done using a protocol of the following form: \(P\) first computes and sends a message a to \(V\) . Then \(V\) returns a random challenge \(m\) of length \(k\) bits and \(P\) sends a response \(z\) to \(V\) . Finally, \(V\) outputs accept or reject. Besides the protocol being of this form,

• Completeness:

If \((x, w) ∈ R\), then the verifier accepts with overwhelming probability.

• Special soundness:

There exists an algorithm, which given \(x\), and two accepting conversations \((a, m, z)\) and \((a, m' , z')\), where \(m \neq m'\) , outputs \(w\) such that \((x, w) ∈ R\).

• Special honest verifier zero-knowledge:

There exists an algorithm, the honest verifier simulator S, which given instance x (where there exists w such that \((x, w) ∈ R)\) and any challenge m generates \((a, m, z) ← S(x, m)\) such that \((x, a, m, z)\) is computationally indistinguishable from a successful conversation where m occurs as challenge.

Message Authentication Code

A message authentication code is used for checking the integrity of messages. It consists of an algorithm MAC that takes as input an authentication key \(ak\) and some message. On basis of this one can compute a message authentication code \(mac\). Given a message and a mac for this message, anybody who knows \(ak\) can check whether they fit together. However, without ak it is hard to compute correct message authentication codes.

In our case, we need to authenticate the initial message of the Σ-protocol for the signature scheme. If we assume such an initial message has at most length k’ , then we can do all operations in \(GF(2k' )\). We pick at random two elements \(r_1 , r_2 ∈ GF(2k' )\). The authentication key will be \(ak = (r_1 , r_2)\). When given \(a\) we then compute \(mac = r_1 a + r_2\) . Clearly, anybody knowing ak can verify this. However, without ak, one only has a negligible chance of computing such a message authentication code correctly.

III Commitment

To commit to a message \(m ∈ M_pk\) we choose at random a randomizer \(r\). We give \(m, r\) as input to commit \(pk\) . The resulting output is \((c, d) = commit_{pk} (m; r)\), where \(c\) belongs to \(C_{pk}\) , while \(d\) is the decommitment information needed to open the commitment. Typically \(d = (m, r)\).

To open a message the sender sends \(d\) to the receiver. The receiver computes decommit \(pk (c, d)\). When the commitment is constructed as above the output of this computation is m. If something is wrong, \(e.g., c \notin C_pk\) or \(d\) is not a valid opening of the commitment; the output of the decommitment algorithm is \(\bot\).

Equivocable Commitment

Equivocable commitment schemes are a special type of commitment schemes where we can generate the public key in a special way getting some equivo- cation information about the public key. This extra information, the equivo- cation key, allows us to violate the binding property. With it we are able to generate commitments that we can open as containing any message we wish, without the adversary being able to notice the deceit.

Non-malleable Commitment

Non-malleability is a security notion concerned with man-in-the-middle at- tacks. With respect to commitments, the intuition is that the execution of some commitment protocols should not affect the execution of other commit- ment protocols. We capture this in a notion of non-malleability where the adversary does not get an advantage from having access to the execution of commitment protocols compared with the case where the adversary has no such access. In the latter case, we simply let the adversary specify the mes- sages rather than first forming commitments and then opening them later on.

III A Non-malleable Commitment Scheme

Key Generation:

We choose a key \(pk\) for a statistically hiding honest sender commitment scheme. Then we generate a public key \(vk\) for the signature scheme. We select a universal one-way hash function \(h : C_{pk} \rightarrow A_{vk}\).

The signature scheme must be known message attack secure with the message distribution given as hashes of honest sender commitments with side information that is openings of the honest sender commit- ments.

The public key is

\[PK = (pk, vk, h)\]

---

from klefki.types.algebra.concrete import EllipticCurveCyclicSubgroupSecp256k1 as ECC
from klefki.types.algebra.concrete import EllipticCurveGroupSecp256k1 as Cruve
from klefki.types.algebra.concrete import FiniteFieldCyclicSecp256k1 as CF
from klefki.types.algebra.concrete import FiniteFieldSecp256k1 as F
from klefki.types.algebra.utils import randfield
from klefki.bitcoin.address import gen_address
from klefki.utils import to_sha256int

pk = randfield(CF)
vk = CF(to_sha256int(str(pk.value)))
h = gen_address
PK = (pk, vk, h)

Commitment:

To commit to a \(k\)-bit message m we choose a key \(ak\) for the message authentication scheme. We set \((c, d) = HScommit_{pk}(ak)\), and compute \(α = h(c)\). Now we simulate a proof of knowledge of a signature on \(\alpha\) with challenge \(m\). We set \((a, m, z) = S((vk, α), m)\). Finally, we compute \(mac = MAC_{ak} (a)\).

The commitment to \(m\) is \(C = (c, a, mac)\), while the decommitment information is \(D = (m, d, z)\).

from klefki.zkp.pedersen import com as commit
from klefki.zkp.pedersen import PedersonCommitment
from functools import partial

G = ECC.G
H = G ** CF(to_sha256int("hello NIRNCS"))
#com = partial(commit, H=H, G=G)
ak = randfield(CF)
com = PedersonCommitment(H, G, pk, ak)

\((𝑐,𝑑)=𝐻𝑆𝑐𝑜𝑚𝑚𝑖𝑡𝑝𝑘(𝑎𝑘)\)

c, d = com.C, com.D
#c, d = (G ** pk, G ** ak), (pk, ak)

\(α=ℎ(𝑐)\)

alpha = CF(to_sha256int(gen_address(c)))

Now we simulate a proof of knowledge of a signature on 𝛼 with challenge 𝑚

m = randfield(CF)
S = PedersonCommitment(G, H, vk, alpha)
r1 = randfield(CF)
r2 = randfield(CF)
a = S.commit(r1, r2)
z = S.challenge(m)
S.proof()
(a, m, z)

(EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::65305324377188005782377700178028737401788663470526826050130238405561434306803, FiniteFieldSecp256k1::51756740416389774025916908316567670088786641308875261052677258404830697308940),
 FiniteFieldCyclicSecp256k1::56646854059851268980329769907295932795576099875142914434658624564702613382143,
 (FiniteFieldCyclicSecp256k1::109522999716473413521340105218466435927129271893586930248571930167452858230042,
  FiniteFieldCyclicSecp256k1::21392565710504642859385122496656030560953184631209595551121610056043363985695))

Finally, we compute 𝑚𝑎𝑐=𝑀𝐴𝐶𝑎𝑘(𝑎).

# Finally, we compute 𝑚𝑎𝑐=𝑀𝐴𝐶𝑎𝑘(𝑎).

import hmac
from klefki.bitcoin.public import encode_pubkey
from klefki.utils import int_to_byte
mac = hmac.new(str(ak.value).encode(), encode_pubkey(a).encode()).hexdigest()

C = (c, a, mac)
D = (m, d , z)

Decommitment:

We open the honest sender commitment to get the authentication key. We compute \(\alpha\) as above. We verify the message authentication code. Finally, we verify the proof. If everything goes well we output \(m\). Otherwise, we output \(⊥\).

For the Pedersen Example, we got:

\[\begin{split}Z = u, v\\ u = pk.m + ak\\ v = ak.m + \alpha\end{split}\]

alpha = CF(to_sha256int(gen_address(c)))

S1 = PedersonCommitment(G, H, vk, alpha)

r1 = randfield(CF)
r2 = randfield(CF)

S.commit(r1, r2)
S.challenge(m)
assert S.proof()

mac == hmac.new(str(d[1].value).encode(), encode_pubkey(a).encode()).hexdigest()

True

Implementation in Klefki

from klefki.zkp.gorth03 import NMCommitment, keygen
G = ECC.G
H = Cruve.lift_x(CF(to_sha256int("hello NIRNCS")))


key = keygen(CF)


com = NMCommitment(G, H, key)

pk, vk, h = key

c = com.commit(CF(to_sha256int("hello klefki")), ak)

com.open() == CF(to_sha256int("hello klefki"))

True

Ref:

• 1. Damg˚ard, J. Groth. Non-interactive and reusable non-malleable commitment schemes. Proc. of 35 th ACM Symp. on Theory of Computing (STOC’03), pp.426- 437, 2003.

• Common reference string model https://en.wikipedia.org/wiki/Common_reference_string_model