I am trying to understand how to apply a multi-trapdoor commitment described by Gennaro and what makes them secure against a concurrent MiM attack.

There are two ways to construct a multi-trapdoor commitment scheme: one based on the strong RSA assumption and one based on the Strong Diffie-Hellman assumption.

For the purpose of this question let's use the latter:

Let ${G}$ be a cyclic group of prime order ${q}$ generated by ${g}$. We assume that ${G}$ is a group such that deciding Diffie-Hellman triplets is easy. More formally we assume the existence of an efficient algorithm $DDHTest$ which on input a tripled ${(g^a, g^b, g^c)}$ of elements in ${G}$ outputs ${1}$ if and only if, ${c=ab \: mod \: q}$.

The master key generation algorithm selects a random ${x \in Z_q}$ which will be the master trapdoor. The master public key $PK$ will be the pair ${g,h}$ where ${h = g^x}$ in $G$. Each commitment in the family will be identified by a specific public key $pk$ which is simply an element ${e \in Z_q}$. The specific trapdoor $tk$ of this scheme is the value ${f_e}$ in $G$ such that ${f_e^{x+e} = g}$.

To commit to a message ${a \in Z_q}$ with public key ${pk = e}$, the sender runs Pedersen's commitment with bases ${g, h_e}$ where ${h_e = g^e * h}$. I.e., it selects a random ${r \in Z_q}$ and computes ${A = g^a h_e^r}$. The commitment to $a$ is the value $A$.

To open a commitment, the sender reveals ${a}$ and ${F = g^r}$, The receiver accepts the opening if ${DDHTest(F, h*g^e, A * g^{-a}) = 1}$

According to Gennaro, we can use the described multi-trapdoor commitment to achieve a non-malleable trapdoor commitment secure under concurrent MiM attack. The intuitive description of a non-malleable commitment given in section 3.1 is as follows:

The adversary, after seeing a tuple of commitments produced by honest parties, outputs his own tuple of committed values. At this point, the honest parties de-commit their values and now the adversary tries to decommit his values in a way that his messages are related to the honest parties’ ones. Intuitively, we say that a commitment scheme is non-malleable if the adversary fails at this game.

The way a non-malleable commitment scheme is constructed is as follows:

Key Generation: The public key of the non-malleable scheme includes three elements: (i) the master public key $PK$ for a multi-trapdoor commitment scheme; (ii) the description of a one- time signature scheme; (iii) a collision-resistant hash function $H$ from the set of verification keys $vk$ of the one-time signature scheme, to the set of public keys $pk$ in the multi-trapdoor commitment scheme determined by the master public key $PK$. The trapdoor of the scheme is $TK$ the master trapdoor of the multi-trapdoor family.

Commitment Algorithm: To commit to a message $M$, the sender chooses a key pair ${(sk,vk)}$ for a one-time signature scheme and computes ${pk= H(vk)}$. Then the sender computes ${[C(M),D(M)] = Com(PK,pk,M,r)}$ where $r $ is chosen at random (as prescribed by the definition of $Com$). The commitment string is ${vk,C(M)}$. To decommit the sender reveals ${M,D(M)}$ and $sig$, where $sig$ is the one-time signature on ${C(M)}$.

Verification Algorithm: On input a commitment ${vk, C}$ , the receiver accepts the decommitment ${M,D,sig}$ if after computing ${pk = H(vk)}$, it holds that ${Ver(PK,pk,M,C,D) = 1}$ and the signature is valid.

The crucial trick here is the fact that the verification key $vk$ is used to determine the value $pk$ used in the commitment scheme.

There are a few things I do not understand here:

  1. In Gennaro's publication, it's assumed that the master trapdoor key $PK$ is shared between the parties in a common reference string along with the multi-trapdoor commitment scheme. My question is: can't the $PK$ be generated and sent to the committing party by the verifier? Since $x$ is kept private and the verifier is the party most interested in the security of the scheme, this seems like a valid approach for me,

  2. Do we have to use a one-time signature scheme like the Lamport signature? Can't we just use e.g. ECDSA signature and generate different $(sk, vk)$ for each commitment and never reuse the same key?

  3. Why is this scheme any better in terms of security against MiM attacks than the standard computationally binding Pedersen scheme? Is it because a computationally unbounded sender can change commitment in Pedersen and here not?

  • $\begingroup$ In the first scheme, how can u open the commitment with master trapdoor x? $\endgroup$
    – Fiono
    Jun 9, 2019 at 14:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.