1
$\begingroup$

I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group generator): Given the input tuple $(g, g^{\alpha_1}, g^{\alpha_2}, g^{y}, g^{z})$ where $z \in \{y \alpha_1, y \alpha_2\}$, the desired output is $g^{\alpha_i}$ (or simply $i$) such that $z = y\alpha_i$.

If it is not known, I would appreciate any suggestions for a reduction based proof.

Improve this question
$\endgroup$
1
  • $\begingroup$ This is tightly equivalent to DDH. $\endgroup$
    – Gee Law
    Commented Sep 18, 2020 at 4:20

1 Answer 1

Reset to default
1
$\begingroup$

The two given tuples are computationally indistinguishable. Here's a proof

Let tuples $T_1=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_1y})$ and $T_2=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_2y})$

Lets take a tuple $T_3=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^r)$ where $r \overset{$}\leftarrow \mathcal{R}$. That is, for the purpose of the proof we generate a tuple with the last element being a random element of the group.

It's easy to see that $T_1 \approx T_3$ ($\approx$: notation for compuational indistinguishability) because of DDH assumption. Same way, $T_2 \approx T_3$ as well. Since we know that computational indistinguishability is transitive, that means $T_1 \approx T_2$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ One may want to note when reading this answer that computational indistinguishability is in general only transitive for a constant number of hops. $\endgroup$
    – SEJPM
    Commented Sep 18, 2020 at 9:02
  • $\begingroup$ @SEJPM: Could you explain why? I always thought it also worked for poly-many hops (this is how, for example, the hybrid argument works). The discussion in this lecture note also seems to agree. $\endgroup$
    – ckamath
    Commented Sep 18, 2020 at 15:07
  • 1
    $\begingroup$ @Occams_Trimmer It only works for poly-many hops if all the hops can be bound by the same negligble function. An example for a family of functions where each is negligible but the sum isn't is: $\varepsilon_i(n)=\begin{cases}1&i\geq n\\0&\text{else}\end{cases}$. Obviously each is individually neglgigble but if you consider $$p(n)=\sum^n_i \varepsilon_i(n)$$ it is obviously constantly $1$ and thus not negligible. Though also note that most proofs where an author errornously assumed that poly-many hops can be done can usually be fixed. $\endgroup$
    – SEJPM
    Commented Sep 18, 2020 at 18:55
  • $\begingroup$ In the non-uniform model, the assumptions (finitely many) allow transitivity to go through for poly-many hops. In the uniform model, a strict proof is written as a probabilistic reduction and "poly-many hops" do not exist in the proof and are a pedagody device. Usually the proof can be uniform (i.e., written as probabilistic reduction) and it's routine to use "poly-many hops" exposition (or perhaps the authors don't care about uniform security). $\endgroup$
    – Gee Law
    Commented Sep 21, 2020 at 5:51

Your Answer

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

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