3
$\begingroup$

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)]$?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

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.