Title

Variations of Diffie-Hellman problem

Publication Type

Conference Proceeding Article

Publication Date

10-2003

Abstract

This paper studies various computational and decisional Diffie-Hellman problems by providing reductions among them in the high granularity setting. We show that all three variations of computational Diffie-Hellman problem: square Diffie-Hellman problem, inverse Diffie-Hellman problem and divisible Diffie-Hellman problem, are equivalent with optimal reduction. Also, we are considering variations of the decisional Diffie-Hellman problem in single sample and polynomial samples settings, and we are able to show that all variations are equivalent except for the argument DDH ⇐ SDDH. We are not able to prove or disprove this statement, thus leave an interesting open problem. Keywords: Diffie-Hellman problem, Square Diffie-Hellman problem, Inverse Diffie-Hellman problem, Divisible Diffie-Hellman problem

Discipline

Information Security

Research Areas

Intelligent Systems and Decision Analytics

Publication

Information and Communications Security: 5th International Conference, ICICS 2003, Huhehaote, China, October 10-13

Volume

2836

First Page

301

Last Page

312

ISBN

9783540399278

Identifier

10.1007/978-3-540-39927-8_28

Publisher

Springer Verlag

City or Country

Huhehaote, China

Additional URL

http://dx.doi.org/10.1007/978-3-540-39927-8_28