# The security of DDH with multiple instances?

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.

• Is it naturally true due to the self-reducibility of DDH? Aug 23 at 13:07
• Is this homework? If it is, you should clarify it. Aug 23 at 14:05
• @GeoffroyCouteau No. Not homework. just curious things Aug 23 at 14:26

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.