Communication complexity and fourier coefficients of the Diffie-Hellman key

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

5 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationLATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings
EditorsGaston Gonnet, Daniel Panario, Alfredo Viola
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages259-268
Number of pages10
Volume1776 LNCS
ISBN (Print)3540673067, 9783540673064
DOIs
Publication statusPublished - 2000
Event4th Latin American Symposium on Theoretical Informatics, LATIN 2000 - Punta del Este, Uruguay
Duration: 10 Apr 200014 Apr 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1776 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other4th Latin American Symposium on Theoretical Informatics, LATIN 2000
CountryUruguay
CityPunta del Este
Period10/04/0014/04/00

Fingerprint

Dive into the research topics of 'Communication complexity and fourier coefficients of the Diffie-Hellman key'. Together they form a unique fingerprint.

Cite this