On the distribution of the Diffie-Hellman pairs
type: Item
instance of: scholarly article
title: On the distribution of the Diffie-Hellman pairs
zbMATH Open document ID: 1003.11059
author: Igor E. Shparlinski
published in: Finite Fields and their Applications
publication date: 2002-08-15T00:00:00Z
review text: 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.
reviewed by: Dingyi Pei
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1781821
zbMATH Keywords: Diffie-Hellman cryptosystem
zbMATH Keywords: uniform distribution
zbMATH Keywords: exponential sums
MaRDI profile type: Publication
full work available at URL: ffta.2000.0321
OpenAlex ID: W2050905931
cites work: Q4228459
cites work: Q4452561
cites work: A Simple Unpredictable Pseudo-Random Number Generator
cites work: Q4249640
cites work: On the statistical properties of Diffie-Hellman distributions
cites work: On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples
cites work: Q4208589
cites work: Sequences, discrepancies and applications
cites work: Q4330627
cites work: On the distribution of the power generator
cites work: Q4945398
cites work: New bounds for Gauss sums derived from KTH powers, and for Heilbronn's exponential sum
cites work: Efficient cryptographic schemes provably as secure as subset sum
cites work: Q4264395
cites work: ON THE DISTRIBUTION OF DIGITS IN PERIODIC FRACTIONS
cites work: Q4003239
cites work: Q3974094
cites work: Q4871218
cites work: Q4718481
cites work: Number-theoretic constructions of efficient pseudo-random functions
cites work: Synthesizers and their application to the parallel construction of pseudo-random functions
cites work: Q4941845
cites work: Quasi-Monte Carlo methods and pseudo-random numbers
cites work: Q4003879
cites work: Number theoretic methods in cryptography. Complexity lower bounds
cites work: On the Naor-Reingold pseudo-random function from elliptic curves
cites work: On the uniformity of distribution of the Naor-Reingold pseudo-random function
cites work: On the uniformity of distribution of the RSA pairs
cites work: On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves.
cites work: Q4839149
DOI: 10.1006/FFTA.2000.0321
description: scientific article; zbMATH DE number 1781821