University of Oulu

Partala, J. (2017). Algebraic generalization of Diffie–Hellman key exchange. Journal of Mathematical Cryptology, 12(1), pp. 1-21. Retrieved 11 Apr. 2019, from doi:10.1515/jmc-2017-0015

Algebraic generalization of Diffie–Hellman key exchange

Saved in:
Author: Partala, Juha1
Organizations: 1Physiological Signal Analysis Team, Center for Machine Vision and Signal Analysis, University of Oulu, Oulu, Finland
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.5 MB)
Persistent link:
Language: English
Published: De Gruyter, 2018
Publish Date: 2019-04-11


The Diffie–Hellman key exchange scheme is one of the earliest and most widely used public-key primitives. Its underlying algebraic structure is a cyclic group and its security is based on the discrete logarithm problem (DLP). The DLP can be solved in polynomial time for any cyclic group in the quantum computation model. Therefore, new key exchange schemes have been sought to prepare for the time when quantum computing becomes a reality. Algebraically, these schemes need to provide some sort of commutativity to enable Alice and Bob to derive a common key on a public channel while keeping it computationally difficult for the adversary to deduce the derived key. We suggest an algebraically generalized Diffie–Hellman scheme (AGDH) that, in general, enables the application of any algebra as the platform for key exchange. We formulate the underlying computational problems in the framework of average-case complexity and show that the scheme is secure if the problem of computing images under an unknown homomorphism is infeasible. We also show that a symmetric encryption scheme possessing homomorphic properties over some algebraic operation can be turned into a public-key primitive with the AGDH, provided that the operation is complex enough. In addition, we present a brief survey on the algebraic properties of existing key exchange schemes and identify the source of commutativity and the family of underlying algebraic structures for each scheme.

see all

Series: Journal of mathematical cryptology
ISSN: 1862-2976
ISSN-E: 1862-2984
ISSN-L: 1862-2976
Volume: 12
Issue: 1
Pages: 1 - 21
DOI: 10.1515/jmc-2017-0015
Type of Publication: A1 Journal article – refereed
Field of Science: 113 Computer and information sciences
213 Electronic, automation and communications engineering, electronics
217 Medical engineering
Copyright information: © 2018 Walter de Gruyter GmbH, Berlin/Boston.