3
$\begingroup$

When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then:

Given $P, zP \in G_1$ and $Q, zQ \in G_2$, compute $z$.

I haven't found this problem in the literature anywhere, so I am not aware of any name of it. It clearly implies the discrete logarithm problems in $G_1$ and $G_2$, but those two do not seem to imply this problem on their own or combined. On the other hand, it is implied by the co-CDH* as well as the q-SDH assumptions - but those are stronger than I need.

I'm wondering the following two things:

  1. Has this problem appeared anywhere in the literature?
  2. Is it implied by any other common assumptions?

It seems very natural to assume the hardness of this problem in a Type 3 cryptographic scheme. Usually the point of working with a Type 3 pairing is exactly to have such a tuple, and use the pairing to decide if the fourth element indeed equals $zQ$ or some other element. So if this problem is not hard and $z$ is private, then you're in trouble.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Usually the point of working with a Type 3 pairing is exactly to have such a tuple, and use the pairing to decide if the fourth element indeed equals $zQ$ or some other element. So if this problem is not hard and $z$ is private, then you're in trouble.

From your explanation, I don't think you require a Discrete Log-like assumption. You are saying that the pairing is used to check if some element is indeed $zQ$ or some random value. This seem to imply that $P$, $zP$, and $Q$ are known to an adversary, and you want to ensure that an adversary cannot produce a value that passes the check you make with the pairing.

Assuming I understood this right, then this seems to be a fit for the Computational co-Diffie Hellman problem (co-CDH): given $P$, $zP \in G_1$, and $Q \in G_2$, the co-CDH problem is to output is $zQ \in G_2$. This output is what you are checking with the pairing, so it seems to me that the co-CDH problem is what you are looking for.

In this case, a Discrete Log-like assumption may be overkill, since an adversary wouldn't need to find $z$. It suffices to compute $zQ$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. Actually, in my case additional elements of the form $R, zR \in G_2$ are around as well, so it would have to be the co-CDH* assumption that I mentioned (since it allows for such extra elements). But for separate reasons I may be able to get away with assuming only the difficulty of the problem of my question. Since that problem is weaker than co-CDH*, that would be preferable, so I am still interested in the problem. $\endgroup$
    – miramo
    Dec 16, 2015 at 13:08
  • $\begingroup$ I see, but usually, you don't choose the weakest assumption (otherwise, all crypto protocols would be based on the DL problem), so I think you should go with the co-CDH* problem. $\endgroup$
    – cygnusv
    Dec 16, 2015 at 16:02
  • 2
    $\begingroup$ Okay, either I misunderstand everything or we are talking on different wavelengths. As I understand it, all crypto protocols are based on the DL problem, because (for example) if you assume CDH, then you also assume DL because if DL is easy then CDH is too. So assuming CDH excludes more adversaries, while only assuming DL and not CDH excludes less adversaries. That is why it is preferable to assume only DL and not also CDH - or, in the case of my question, only the mentioned problem and not also co-CDH*. $\endgroup$
    – miramo
    Dec 16, 2015 at 21:46
  • $\begingroup$ You are right in that the CDH assumption implies the DL assumption. The thing is that CDH does not "exclude more adversaries" (following your terminology), but quite the opposite. Since DL is more difficult, you could say that there are less adversaries capable of solving DL than those capable of solving CDH (which is easier than DL). $\endgroup$
    – cygnusv
    Dec 17, 2015 at 7:45
  • $\begingroup$ Exactly. So by assuming DL, you are saying "I do not believe that efficient DL-solving algorithms exist", but since solving DL is so difficult, you are denying the existence of less algorithms than you would if you were to assume CDH - so assuming only DL and not also CDH is preferable. $\endgroup$
    – miramo
    Dec 17, 2015 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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