Communication complexity and fourier coefficients of the Diffie-Hellman key

Igor E. Shparlinski

doi:10.1007/10719839_27

Communication complexity and fourier coefficients of the Diffie-Hellman key

Igor E. Shparlinski^*

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

6 Citations (Scopus)

Abstract

Let p be a prime and let g be a primitive root of the field IF_p of p elements. In the paper we show that the communication complexity of the last bit of the Diffie-Hellman key g^xy, is at least n/24 + o(n) where x and y are n-bit integers where n is defined by the inequalities 2ⁿ ≤ p ≤ 2ⁿ⁺¹ - 1. We also obtain a nontrivial upper bound on the Fourier coefficients of the last bit of g^xy. The results are based on some new bounds of exponential sums with g^xy.

Original language	English
Title of host publication	LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings
Editors	Gaston Gonnet, Daniel Panario, Alfredo Viola
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	259-268
Number of pages	10
Volume	1776 LNCS
ISBN (Print)	3540673067, 9783540673064
DOIs	https://doi.org/10.1007/10719839_27
Publication status	Published - 2000
Event	4th Latin American Symposium on Theoretical Informatics, LATIN 2000 - Punta del Este, Uruguay Duration: 10 Apr 2000 → 14 Apr 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1776 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	4th Latin American Symposium on Theoretical Informatics, LATIN 2000
Country/Territory	Uruguay
City	Punta del Este
Period	10/04/00 → 14/04/00

Access to Document

10.1007/10719839_27

Cite this

Shparlinski, I. E. (2000). Communication complexity and fourier coefficients of the Diffie-Hellman key. In G. Gonnet, D. Panario, & A. Viola (Eds.), LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings (Vol. 1776 LNCS, pp. 259-268). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1776 LNCS). Springer, Springer Nature. https://doi.org/10.1007/10719839_27

Shparlinski, Igor E. / Communication complexity and fourier coefficients of the Diffie-Hellman key. LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. editor / Gaston Gonnet ; Daniel Panario ; Alfredo Viola. Vol. 1776 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2000. pp. 259-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f30ee12a96064c1fa314e888bff5599e,

title = "Communication complexity and fourier coefficients of the Diffie-Hellman key",

abstract = "Let p be a prime and let g be a primitive root of the field IFp of p elements. In the paper we show that the communication complexity of the last bit of the Diffie-Hellman key gxy, is at least n/24 + o(n) where x and y are n-bit integers where n is defined by the inequalities 2n ≤ p ≤ 2n+1 - 1. We also obtain a nontrivial upper bound on the Fourier coefficients of the last bit of gxy. The results are based on some new bounds of exponential sums with gxy.",

author = "Shparlinski, \{Igor E.\}",

year = "2000",

doi = "10.1007/10719839\_27",

language = "English",

isbn = "3540673067",

volume = "1776 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "259--268",

editor = "Gaston Gonnet and Daniel Panario and Alfredo Viola",

booktitle = "LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings",

address = "United States",

note = "4th Latin American Symposium on Theoretical Informatics, LATIN 2000 ; Conference date: 10-04-2000 Through 14-04-2000",

}

Shparlinski, IE 2000, Communication complexity and fourier coefficients of the Diffie-Hellman key. in G Gonnet, D Panario & A Viola (eds), LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. vol. 1776 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1776 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 259-268, 4th Latin American Symposium on Theoretical Informatics, LATIN 2000, Punta del Este, Uruguay, 10/04/00. https://doi.org/10.1007/10719839_27

Communication complexity and fourier coefficients of the Diffie-Hellman key. / Shparlinski, Igor E.
LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. ed. / Gaston Gonnet; Daniel Panario; Alfredo Viola. Vol. 1776 LNCS Berlin; Heidelberg: Springer, Springer Nature, 2000. p. 259-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1776 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Communication complexity and fourier coefficients of the Diffie-Hellman key

AU - Shparlinski, Igor E.

PY - 2000

Y1 - 2000

N2 - Let p be a prime and let g be a primitive root of the field IFp of p elements. In the paper we show that the communication complexity of the last bit of the Diffie-Hellman key gxy, is at least n/24 + o(n) where x and y are n-bit integers where n is defined by the inequalities 2n ≤ p ≤ 2n+1 - 1. We also obtain a nontrivial upper bound on the Fourier coefficients of the last bit of gxy. The results are based on some new bounds of exponential sums with gxy.

AB - Let p be a prime and let g be a primitive root of the field IFp of p elements. In the paper we show that the communication complexity of the last bit of the Diffie-Hellman key gxy, is at least n/24 + o(n) where x and y are n-bit integers where n is defined by the inequalities 2n ≤ p ≤ 2n+1 - 1. We also obtain a nontrivial upper bound on the Fourier coefficients of the last bit of gxy. The results are based on some new bounds of exponential sums with gxy.

UR - https://www.scopus.com/pages/publications/84896692764

U2 - 10.1007/10719839_27

DO - 10.1007/10719839_27

M3 - Conference proceeding contribution

AN - SCOPUS:84896692764

SN - 3540673067

SN - 9783540673064

VL - 1776 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 259

EP - 268

BT - LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings

A2 - Gonnet, Gaston

A2 - Panario, Daniel

A2 - Viola, Alfredo

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 4th Latin American Symposium on Theoretical Informatics, LATIN 2000

Y2 - 10 April 2000 through 14 April 2000

ER -

Shparlinski IE. Communication complexity and fourier coefficients of the Diffie-Hellman key. In Gonnet G, Panario D, Viola A, editors, LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. Vol. 1776 LNCS. Berlin; Heidelberg: Springer, Springer Nature. 2000. p. 259-268. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/10719839_27

Communication complexity and fourier coefficients of the Diffie-Hellman key

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this