# Boneh DDH Paper - Sampling Integers in Random Reduction

I've been reading Dan Boneh's DDH paper, in particular section 3.1 which covers DDH randomized reduction.

The first two sentences of theorem 3.1 state: Let $$\Bbb G = \{G_p\}$$ be a family of finite cyclic groups of prime order. Let $$s(p)$$ be an efficiently computable function such that $$|G_p| \leq s(p)$$ for all $$p$$.

If I understand this correctly, for a given group in practice we can set $$s(p) = p$$ if we know the order of the group.

In section 3.1, he describes a statistical experiment in which you can construct a DDH triplet or a random triplet from an existing DDH or random triplet respectively by sampling integers $$u_1, u_2, v$$ from the range $$[1, s(p)^2]$$ and following the formula given.

I am struggling to understand the purpose of sampling in the range $$[1, s(p)^2]$$. Why not just sample from $$[1, s(p)]$$?

Here's a simpler game. There is an unknown modulus $$m$$, for which you know an upper bound $$M \ge m$$. You must devise a strategy for sampling an integer $$x$$ such that $$y = x \bmod m$$ is close to uniform in $$\mathbb{Z}_m$$.

Does it work to choose $$x$$ uniformly in $$\mathbb{Z}_M$$? No, consider the case of $$M= 1.5m+1$$.

$$\begin{array}{c|cccccccc} x & 0 & 1 & 2 & \cdots & m-1 & m & m+1 & \cdots & M-1 \\ \hline y = x \bmod m & 0 & 1 & 2 & \cdots & m-1 & 0 & 1 & \cdots & m/2 \end{array}$$ In this diagram, each column is chosen with equal probability. The output value $$y$$ is highly non-uniform in $$\mathbb{Z}_m$$. In fact, you can easily distinguish $$y$$ from uniform by the simple distinguisher "is $$y < m/2$$?" The distinguisher says yes with probability 2/3 with this example, but only probability 1/2 for the uniform distribution (on $$\mathbb{Z}_m$$).

How does this work in the general case? Each $$y$$ has either $$\lceil M/m \rceil$$ or $$\lfloor M/m \rfloor$$ values of $$x$$ that map to it. (In this example, each $$y$$ had either 1 or 2 values of $$x$$ that map to it.) More precisely, exactly $$r = (M \bmod m)$$ of the $$y$$'s will have the higher number of associated $$x$$ values. So the distinguisher "is $$y \le r$$?" will be the optimal distinguisher and you can easily compute its advantage as: $$(M \bmod m) \left( \frac{\lceil M/m \rceil}{M} - \frac{1}{m} \right)$$

We can upper-bound this advantage as follows: $$\le (M \bmod m) \left( \frac{\lceil M/m \rceil}{M} - \frac{ \lfloor M/m \rfloor }{M}\right) \le \frac{M \bmod m}{M} < \frac{m}{M}$$

Now, what if we used a bound $$M$$ such that $$M > m^2$$ (not just $$M>m$$) and we are sure that $$m$$ is exponentially large in the security parameter? Then the statistical distance from uniform would be bounded by $$m/M < 1/m$$, which is negligible.

In other words, sampling from $$\mathbb{Z}_M$$, where $$M > m^2$$, results in a value whose residue mod $$m$$ is close to uniform.

Connection to the DDH reduction algorithm: The reduction algorithm takes as input a triple of elements whose discrete logs are $$(a,b,c)$$. It outputs a triple whose discrete logs are $$(av+u_1, b+u_2, cv+bu_1+avu_2+u_1u_2)$$. We want to say the following:

• if $$c \ne ab$$ (i.e., the input is not a DH triple), then the output is statistically close to uniform over all triples --- i.e, the output discrete logs are close to uniform in $$(\mathbb{Z}_p)^3$$.
• if $$c=ab$$, then the output is statistically close to uniform over the set of DH triples --- i.e., the discrete logs of the first two outputs are uniform in $$(\mathbb{Z}_p)^2$$ and the discrete log of the third output is the product of the first two.

Arithmetic on these discrete logs happens naturally mod $$p$$, by the actions of the group. If you don't know $$p$$ then you must choose $$v, u_1, u_2$$ over the integers (e.g., in $$\mathbb{Z}_M$$ for some bound $$M$$) and argue that you still get a result that is close to uniform mod $$p$$.

You will soon find yourself in a situation like above, where if your choice of $$M$$ is bad then the result has high statistical distance from uniform. That's why you will need to choose a bound $$M$$ that is larger than $$p^2$$. Since $$p$$ is exponentially large in the security parameter, this gets you negligibly close to uniform in the result.

Note: it would also work to say $$M > p 2^\kappa$$ where $$\kappa$$ is the security parameter. Then you would conveniently bound the statistical distance by $$1/2^\kappa$$. I agree that $$M>p^2$$ is a little sneaky because one factor of $$p$$ is plays the role of a bound on $$p$$, and the other factor of $$p$$ plays the role of a bound on $$2^\kappa$$.