Let $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ be yclic group of the same order and $ e: \mathbb{G}_1 \times \mathbb{G}_2\rightarrow \mathbb{G}_T$, such that $u\in \mathbb{G}_1, g \in \mathbb{G}_2, a,b,r \in \mathbb{Z}$.

Question 1: is the following equation correct? Is there any situation under which it might be correct? If not why?

$e(u^a,\frac {u^b}{u^a} g)=e(u^b,g)$

Scenario: assume we have two parties: $A$ and $B$, where $A$ has two messages $m, m'$ and $B$ has a message $m$. $A$ commitments to a message $m$ as: $(r.u^m)^a$, and B commitments the same message as $(r.u^m)^b$. They send their commitments to a server. It's clear that if $A$ gives $g^{\frac{1}{a}}$ to $B$, $B$ can compute $w=g^{\frac {b}{a}}$, and send it to the server to let the server check whether two messages $m$ for different parties are equal: $e((r.u^m)^a,g^{\frac {b}{a}})=e((r.u^m)^b,g)$

Question 2: Given $g^{\frac{1}{a}}$ can B generate $w'$ to convince the server that it has commited to $m'$ rather than $m$?

All operation are $\bmod p$ where $p$ is a large prime number.


If you define $u$ as element of $G_1$, then you can't just use it in $G_2$ (in the first equation), like you did in your equation. Besides, you missed to state, if $u$ and $g$ are generators of those groups. The following holds:

$$e(u^a,g^{\frac{b}{a}}) = e(u,g)^b = e(u^b,g)$$

Anyway, you didn't do that in the actual question, where I don't really see the connection to your construction. Btw, how do A and B know that they are using the same value $r$? And then: How can the server relate anything $B$ sends to $m'$, if the server has no knowledge of $m'$ or a commitment to $m'$? So no, he can't. Because $m'$ is not used in your construction at all.

The question now is: What is your actual goal? Should the server just be able to make sure, A and B committed to the same value? And A and B have to interact to generate the witness for that? You don't need pairings for that.

edit: Maybe even Alice could cheat in the system, by not sending $g^a$ to Bob, but something else. What happens then? Well, if the server check returns true, the "commited" messages are not equal. Too many things that can go wrong, especially with that $r$, which doesn't make sense.

  • $\begingroup$ Can you give me a clue what you mean by " the commited messages are not equal ", please. $\endgroup$ – user153465 Apr 27 '15 at 19:17
  • $\begingroup$ Why would the server change anything? From what you describe, A and B are the ones committing values, and the server is the one verifying that the commitment matches to the value (which is revealed later - if we are still talking about commitment schemes). About the interaction part: I can't give an concrete example, but Alice could send something else other than $g^{1/a}$, and then the pairing equation would be true for messages, where the commitments of A and B are not equal. In order to do that, Alice would know what B was going to commit, and adapt accordingly. $\endgroup$ – tylo Apr 28 '15 at 12:32
  • $\begingroup$ you are absolutely right. In "my scenario" $A$ is semi_honest, but $B$ is malicious, in the sense that given $g^a$ it may try to modify it and fool the server that it has some other message than what it has already commited to (e.g. $m'$) . Why does it matter? Becasue it may guess that $m'$ is in A's outsourced values and try to get confirmation from the server. This is the "main" reason that the above so called protocol is designed. So the server can detect it if $B$ asks something beyond its outsouced commited values. $\endgroup$ – user153465 Apr 28 '15 at 13:38
  • $\begingroup$ We also have $g^{a}$ that is given to $B$ by $A$. If $B$ modifies it honestly (i.e. it generates $g^{\frac{b}{a}}$) , it could give a mapping from its own outsouced commited value to $A$'s. I need to mention that in the comment (not in the question) I mistakenly used $g^{\frac{1}{a}}$ instead of $g^a$. $\endgroup$ – user153465 Apr 28 '15 at 13:38
  • $\begingroup$ Thus after some computation $B$ gets access to $m$. It sends $(r.u^m)^b$ and $g^{\frac{a}{b}}$ to the server. The server first checks whether $B$ has commited to this value then it uses $g^{\frac{a}{b}}$ to map $B$'s commited value to $A$. And this ensures it that $m$ belongs to both $A$ and $B$ outsourced values. $\endgroup$ – user153465 Apr 28 '15 at 13:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.