On the distribution of Diffie-Hellman triples with sparse exponents

John B. Friedlander; Igor E. Shparlinsk

doi:10.1137/S0895480199361740

On the distribution of Diffie-Hellman triples with sparse exponents

John B. Friedlander^*, Igor E. Shparlinsk

^*Corresponding author for this work

Department of Computing

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

2 Downloads (Pure)

Abstract

Let g be a primitive root modulo a (n + 1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie-Hellman triples (g^{cursive Greek chi}, g^y, g^{cursive Greek chiy}) as the exponents cursive Greek chi and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that k ≥ 0.35n. Such "sparse" exponents are of interest because for these the computation of g^{cursive Greek chi}, g^y, g^{cursive Greek chiy} is faster than for arbitrary cursive Greek chi and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [Israel J. Math, 120 (2000), pp. 23-46], and the authors.

Original language	English
Pages (from-to)	162-169
Number of pages	8
Journal	SIAM Journal on Discrete Mathematics
Volume	14
Issue number	2
DOIs	https://doi.org/10.1137/S0895480199361740
Publication status	Published - Feb 2001

Bibliographical note

Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see http://www.siam.org/.

Access to Document

10.1137/S0895480199361740

Publisher version (open access).pdfFinal published version, 136 KB

Link to publication in Scopus

Fingerprint Dive into the research topics of 'On the distribution of Diffie-Hellman triples with sparse exponents'. Together they form a unique fingerprint.

Cite this

@article{4758cc1ed6a54c22a98ca465a48c738e,

title = "On the distribution of Diffie-Hellman triples with sparse exponents",

abstract = "Let g be a primitive root modulo a (n + 1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie-Hellman triples (gcursive Greek chi, gy, gcursive Greek chiy) as the exponents cursive Greek chi and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that k ≥ 0.35n. Such {"}sparse{"} exponents are of interest because for these the computation of gcursive Greek chi, gy, gcursive Greek chiy is faster than for arbitrary cursive Greek chi and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [Israel J. Math, 120 (2000), pp. 23-46], and the authors.",

author = "Friedlander, {John B.} and Shparlinsk, {Igor E.}",

note = "Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see http://www.siam.org/.",

year = "2001",

month = feb,

doi = "10.1137/S0895480199361740",

language = "English",

volume = "14",

pages = "162--169",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - On the distribution of Diffie-Hellman triples with sparse exponents

AU - Friedlander, John B.

AU - Shparlinsk, Igor E.

N1 - Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see http://www.siam.org/.

PY - 2001/2

Y1 - 2001/2

N2 - Let g be a primitive root modulo a (n + 1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie-Hellman triples (gcursive Greek chi, gy, gcursive Greek chiy) as the exponents cursive Greek chi and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that k ≥ 0.35n. Such "sparse" exponents are of interest because for these the computation of gcursive Greek chi, gy, gcursive Greek chiy is faster than for arbitrary cursive Greek chi and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [Israel J. Math, 120 (2000), pp. 23-46], and the authors.

AB - Let g be a primitive root modulo a (n + 1)-bit prime p. In this paper we prove the uniformity of distribution of the Diffie-Hellman triples (gcursive Greek chi, gy, gcursive Greek chiy) as the exponents cursive Greek chi and y run through the set of n-bit integers with precisely k nonzero bits in their bit representation provided that k ≥ 0.35n. Such "sparse" exponents are of interest because for these the computation of gcursive Greek chi, gy, gcursive Greek chiy is faster than for arbitrary cursive Greek chi and y. In the latter case, that is, for arbitrary exponents, similar (albeit stronger) uniformity of distribution results have recently been obtained by R. Canetti, M. Larsen, D. Lieman, S. Konyagin [Israel J. Math, 120 (2000), pp. 23-46], and the authors.

UR - http://www.scopus.com/inward/record.url?scp=0000124225&partnerID=8YFLogxK

U2 - 10.1137/S0895480199361740

DO - 10.1137/S0895480199361740

M3 - Article

AN - SCOPUS:0000124225

VL - 14

SP - 162

EP - 169

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -