Polynomial representations of the Diffie-Hellman mapping

Edwin El Mahassni; Igor Shparlinski

Polynomial representations of the Diffie-Hellman mapping

Edwin El Mahassni^*, Igor Shparlinski

^*Corresponding author for this work

School of Computing

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

16 Citations (Scopus)

Abstract

We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (g^x,g^y) → g^xy, where g is a primitive root of a finite field double-struck F sign_q of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.

Original language	English
Pages (from-to)	467-473
Number of pages	7
Journal	Bulletin of the Australian Mathematical Society
Volume	63
Issue number	3
Publication status	Published - Jun 2001

Cite this

@article{eb4786499deb4fba89f6dfa75afa786b,

title = "Polynomial representations of the Diffie-Hellman mapping",

abstract = "We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (gx,gy) → gxy, where g is a primitive root of a finite field double-struck F signq of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.",

author = "\{El Mahassni\}, Edwin and Igor Shparlinski",

year = "2001",

month = jun,

language = "English",

volume = "63",

pages = "467--473",

journal = "Bulletin of the Australian Mathematical Society",

issn = "0004-9727",

publisher = "Cambridge University Press (CUP)",

number = "3",

}

TY - JOUR

T1 - Polynomial representations of the Diffie-Hellman mapping

AU - El Mahassni, Edwin

AU - Shparlinski, Igor

PY - 2001/6

Y1 - 2001/6

N2 - We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (gx,gy) → gxy, where g is a primitive root of a finite field double-struck F signq of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.

AB - We obtain lower bounds on the degrees of polynomials representing the Diffie-Hellman mapping (gx,gy) → gxy, where g is a primitive root of a finite field double-struck F signq of q elements. These bounds are exponential in terms of log q. In particular, these results can be used to obtain lower bounds on the parallel arithmetic complexity of breaking the Diffie-Hellman cryptosystem. The method is based on bounds of numbers of solutions of some polynomial equations.

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

M3 - Article

AN - SCOPUS:0012482609

SN - 0004-9727

VL - 63

SP - 467

EP - 473

JO - Bulletin of the Australian Mathematical Society

JF - Bulletin of the Australian Mathematical Society

IS - 3

ER -

Polynomial representations of the Diffie-Hellman mapping

Abstract

Other files and links

Fingerprint

Cite this