Short exponent diffie-hellman problems

Takeshi Koshiba; Kaoru Kurosawa

doi:10.1007/978-3-540-24632-9_13

Short exponent diffie-hellman problems

Takeshi Koshiba^*, Kaoru Kurosawa

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter

15 Citations (Scopus)

Abstract

In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Feng Bao, Robert Deng, Jianying Zhou
Publisher	Springer Verlag
Pages	173-186
Number of pages	14
ISBN (Print)	3540210180, 9783540210184
DOIs	https://doi.org/10.1007/978-3-540-24632-9_13
Publication status	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2947
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-24632-9_13

Cite this

Koshiba, T., & Kurosawa, K. (2004). Short exponent diffie-hellman problems. In F. Bao, R. Deng, & J. Zhou (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 173-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2947). Springer Verlag. https://doi.org/10.1007/978-3-540-24632-9_13

Short exponent diffie-hellman problems. / Koshiba, Takeshi; Kurosawa, Kaoru.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Feng Bao; Robert Deng; Jianying Zhou. Springer Verlag, 2004. p. 173-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2947).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Koshiba, T & Kurosawa, K 2004, Short exponent diffie-hellman problems. in F Bao, R Deng & J Zhou (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2947, Springer Verlag, pp. 173-186. https://doi.org/10.1007/978-3-540-24632-9_13

Koshiba T, Kurosawa K. Short exponent diffie-hellman problems. In Bao F, Deng R, Zhou J, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 173-186. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24632-9_13

Koshiba, Takeshi ; Kurosawa, Kaoru. / Short exponent diffie-hellman problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Feng Bao ; Robert Deng ; Jianying Zhou. Springer Verlag, 2004. pp. 173-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{e0bf3a12b08048c38426c8810e5cfbd6,

title = "Short exponent diffie-hellman problems",

abstract = "In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.",

author = "Takeshi Koshiba and Kaoru Kurosawa",

year = "2004",

doi = "10.1007/978-3-540-24632-9_13",

language = "English",

isbn = "3540210180",

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

publisher = "Springer Verlag",

pages = "173--186",

editor = "Feng Bao and Robert Deng and Jianying Zhou",

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

}

TY - CHAP

T1 - Short exponent diffie-hellman problems

AU - Koshiba, Takeshi

AU - Kurosawa, Kaoru

PY - 2004

Y1 - 2004

N2 - In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.

AB - In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.

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

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

U2 - 10.1007/978-3-540-24632-9_13

DO - 10.1007/978-3-540-24632-9_13

M3 - Chapter

AN - SCOPUS:35048903103

SN - 3540210180

SN - 9783540210184

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

SP - 173

EP - 186

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

A2 - Bao, Feng

A2 - Deng, Robert

A2 - Zhou, Jianying

PB - Springer Verlag

ER -

Short exponent diffie-hellman problems

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this