On the distribution of the Diffie-Hellman pairs (Q1609391): Difference between revisions

Let \(F_{p}\) be a prime field of \(p\) elements and \(g\) be an element of \(F_{p}\) with multiplicative order \(t\) modulo \(p\). The security of the Diffie-Hellman scheme is based on the complexity of solving \(x\) mod \(t\) given \(g^{x}\bmod p\). In this paper the author proves that for any \(\varepsilon > 0\) and \(t\geq p^{1/3+\varepsilon}\), the distrubition of the Diffie-Hellman pairs \((x, g^{x})\) is close to uniform in the Cartesian product \(Z_{t}\times F_{p}\) where \(x\) runs through \(Z_{t}\), or the all \(k\)-sums \(x=a_{i_{1}}+\cdots +a_{i_{k}},\) \(1\leq i_{1}< \cdots <i_{k}\leq n\) where \(a_{1}, \cdots,a_{n} \in Z_{t}\) are selected at random. Some very recent bounds of character sums are used in the proof.