The security of DDH with multiple instances?

filter hash

12/23/22, 12:53 PM

Let $G$ be a finite group of prime order $p$, and $g$ a generator of $G$. The standard DDH is hard to distinguish two distributions $$ \{ (g, g^a, g^b, g^{ab}) : a, b \leftarrow \mathbb{Z}_p\} \text{ and } \{ (g, g^a,g^{b}, g^r) : a, r \leftarrow \mathbb{Z}_p\}. $$

Is still secure DDH with multiple instances? That is, is hard to distinguish two following distributions? $$ \{ (g, g^a, g^{b_i}, g^{ab_i}) : a, b_i \leftarrow \mathbb{Z}_p\} \text{ and } \{ (g, g^a,g^{b_i}, g^r) : a, r_i \leftarrow \mathbb{Z}_p\}. $$ We also suppose that the cardinality of the set, $|\{b_i\}|$, is much smaller than $p$ to avoid easy cases.

1 + 3

security-definition

hardness-assumptions

filter hash

12/23/22, 1:07 PM

Is it naturally true due to the self-reducibility of DDH?

Geoffroy Couteau

12/23/22, 2:05 PM

Is this homework? If it is, you should clarify it.

filter hash

12/23/22, 2:26 PM

@GeoffroyCouteau No. Not homework. just curious things

Score:4

Crypto

Yehuda Lindell

12/24/22, 10:49 AM

This can be solved via a standard hybrid argument. I won't give you all the details. However, note that given a single tuple $(g,h_1,h_2,h_3)$ you can generate a tuple of the form $(g,g^a,g^{b_i},g^{ab_i})$ by choosing $b_i$ and forming $(g,h_1,g^{b_i},h_1^{b_i})$ and you can generate a tuple of the form $(g,g^a,g^{b_i},g^r)$ by choosing $b_i$ and forming $(g,h_1,g^{b_i},g^r)$. This suffices for building hybrid distributions as needed for a hybrid argument.

0 + 1

filter hash

12/24/22, 1:59 PM

Thank you for your hopeful comments!