0
$\begingroup$

Given prime $p$, generator $g$ of $\mathbb Z_p^*$ and $h_1,h_2,h_3\in\mathbb Z_p^*$ is $$\log_ph_3=(\log_ph_1)(\log_ph_2)$$ where at every $i\in\{1,2,3\}\mbox{ }g^{\log_ph_i}\equiv h_i\bmod p$ holds?

Is the above problem in $\mathsf{NP}\cap\mathsf{coNP}$ where the witness does not reveal information about discrete log of $h_1$ and $h_2$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The question is of the form: "(given foo) is bar (where qux) holds?" . That's grammatically incorrect. And if we replace "is" with "does", the proposition is trivially false. Something must be missing. Please edit the question. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @frgieu: I think that the parsing is [I present the following decision problem:] (given foo) (is bar?) (where qux holds) $\endgroup$ Commented yesterday

1 Answer 1

Reset to default
1
$\begingroup$

The concept of not revealing information about the discrete logarithms is a little fuzzy as the verification of the witness provides information.

However, if I understand the spirit of your question, here is a construction that works in some instances. If we present an elliptic curve $E$ mod $p$ with embedding degree 1 (see section 6 of Koblitz and Menezes) and points $G_1$, $G_2$, $H_1$, $H_2$ and $H_3$ such that $e(G_1,G_2)=g$, $e(H_1,G_2)=h_1$, and $e(G_1,H_2)=h_2$, then these data act as witness to the statement and can be validated by the computation $$h_3\stackrel{?}{=}e(H_1,H_2).$$

ETA 20252611: In response to questions below:

  • the embedding degree needs to be 1 because $h_1$, $h_2$, $h_3$ lie in $\mathbb F_p$ and not $\mathbb F_{p^k}$ for some larger $k$
  • the witness consists of related pre-images of the elements of $\mathbb F_p$ under $e$. I am not sure what the phrase "using dh as witness" means.
  • if decisional Diffie-Hellman is equivalent to the computation of discrete logarithms, then a small number of witnesses to statements of the form under consideration would allow the computation of discrete logarithms. If this is true one could say that such a witness could provide "some" information about some discrete logarithm, but without further description of the equivalence of the problems, one cannot say which discrete logarithms we are getting information about.
Improve this answer
$\endgroup$
6
  • $\begingroup$ sorry I was thinking something in reverse. We know the problem is equivalent to ddh. DDH is in NP because of discrete logarithms. Is there another reason for DDH in NP? $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @Turbo ... and my answer gives an example that acts as a NP/co-NP witness without discrete logarithms. The certificate is $E$, $G_1$, $G_2$, $H_1$, H_2$. Under the usual hardness assumptions, none of these provide discrete logarithm information. $\endgroup$ Commented yesterday
  • $\begingroup$ Let me look carefully in few hours. $\endgroup$ Commented yesterday
  • $\begingroup$ Quickly embedding degree needs to be $1$? $\endgroup$ Commented yesterday
  • $\begingroup$ It appears you are using dh as witness.. but if dh=dlog we do not have the witness we need? $\endgroup$ Commented yesterday

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.