As I know DDH assumption and bilinear pairings are contradictory, but I see this in a paper, RingCT 2.0.
How could this be ok? Linkable ring signature will be attacked by bilinear pairings.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
For the following explanation, let $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. It depends on the setting you are using whether DDH can hold or not. In the symmetric setting ($\mathbb{G}_1 = \mathbb{G}_2$, i.e., Type 1 pairings) the pairing serves as a DDH oracle for both, $\mathbb{G}_1$ and $\mathbb{G}_2$ and DDH can neither hold in $\mathbb{G}_1$ nor in $\mathbb{G}_2$. In the asymmetric setting, we distinguish two different settings, i.e., Type 2 and Type 3. The important difference in this context is that in the Type 2 setting there exists an isomorphism $\psi: \mathbb{G}_2 \to \mathbb{G}_1$ while such an isomorphism is unknown for the Type 3 setting. Now, in the Type 2 setting, the pairing together with the isomorphism serves as a DDH oracle for $\mathbb{G}_2$, while DDH is assumed to hold in $\mathbb{G}_1$. Finally, in the Type 3 setting, DDH is assumed to hold in both $\mathbb{G}_1$ and $\mathbb{G}_2$.
The particular combination you are asking about is in the Type 1 setting, so DDH can not hold for both source groups of the pairing.
Additional note: In the paper you are citing, actually a group (i.e., $\mathbb{G}_q$) which is independent of the pairing groups is used. In such a setting DDH can of course also hold in $\mathbb{G}_q$. However, using an independent group also means that the order of this group is different to the order of the pairing groups, which makes ZK consistency proofs between elements of the different groups - as required in this paper - quite complicated. I can not find anything in the paper which would address this issue.
-
2
-
$\begingroup$ Right, but typically this assumption is not very useful in protocol design as it only involves elements of the target group. Typically, when using pairing groups, elements from the source groups are involved to actually profit from the pairing. To keep my answer simple, I have thus omitted to mention it. Are you aware of any use of DDH in $\mathbb{G}_T$ (I have seen bilinear DDH being used, but never DDH in $\mathbb{G}_T$)? $\endgroup$ – dade Feb 5 '18 at 6:29
-
2$\begingroup$ No, I can't think of an instance where DDH in the target group is actually used. $\endgroup$ – Maeher Feb 5 '18 at 6:54
$\begingroup$
$\endgroup$
There are some groups that have pairings; DDH does not hold in those groups.
But there are also groups in which DDH is believed to hold; of course it means that those groups do not have (known) pairings.
-
-
$\begingroup$ I have to object. It is not true that groups where DDH is believed to hold do not have known pairings. This is only true for the symmetric setting. See my answer below for an explanation of the different settings. $\endgroup$ – dade Feb 5 '18 at 6:32
-
$\begingroup$ @dade The question is in the symmetric setting. $\endgroup$ – fkraiem Feb 5 '18 at 7:15
-
2$\begingroup$ @fkraiem Yes the question is. My point is that your answer is not. This is very misleading - especially in the context of this question, which also asks "How could this be ok?". For example, you say "There are some groups that have pairings; DDH does not hold in those groups.", which is not true without making the Type 1 setting explicit. Further, you also say that groups where DDH is believed to be hard do not have (known) pairings, which is also not true (Type 2 and Type 3 setting). So your answer suggests that there is no possible pairing setting where DDH holds in the source groups $\endgroup$ – dade Feb 5 '18 at 8:03
