On the distribution of Diffie-Hellman triples with sparse exponents (Q2706197)

Let \(p\) be an \((n+1)\)-bit prime and \(g\) be a primitive root modulo \(p\). In [\textit{R. Canetti, J. B. Friedlander} and \textit{I. E. Shparlinski}, J. Lond. Math. Soc. (2) 59, 799-812 (1999; Zbl 0935.11028)] and [\textit{R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman} and \textit{I. E. Shparlinski}, Isr. J. Math. 120, Pt. A, 23-46 (2000; Zbl 0997.11066)] it has been shown that the Diffie-Hellman triples \((g^x,g^y,g^{xy})\) are uniformly distributed when \(x\) and \(y\) run through the full range \(0,1,\ldots,p-2\). NEWLINENEWLINENEWLINEIn the situation when \(x\) and \(y\) have only a small number of nonzero bits the computation of \(g^x,g^y,g^{xy}\) is faster than for arbitrary \(x\) and \(y\). The paper under review deals with the triples \((g^x,g^y,g^{xy})\) when \(x\) and \(y\) run through all \(n\)-bit integers with precisely \(k\) nonzero bits provided \(k\geq 0.35 n\). The authors prove that these triples are uniformly distributed, as well. The results are based on new bounds on the exponential sums NEWLINE\[NEWLINES_k(a,b,c)=\sum_{x,y} \exp(2\pi \text{ i} (ag^x+bg^y+cg^{xy})/p),NEWLINE\]NEWLINE where \(x\) and \(y\) run through all \(n\)-bit integers with precisely \(k\) nonzero bits.