Paper 2021/1112
Key agreement: security / division
Daniel R. L. Brown
Abstract
Some key agreement schemes, such as DiffieHellman key agreement, reduce to RabiSherman key agreement, in which Alice sends $ab$ to Charlie, Charlie sends $bc$ to Alice, they agree on key $a(bc) = (ab)c$, where multiplicative notation here indicates some specialized associative binary operation. All noninteractive key agreement schemes, where each peer independently determines a single delivery to the other, reduce to this case, because the ability to agree implies the existence of an associative operation. By extending the associative operation’s domain, the key agreement scheme can be enveloped into a mathematical ring, such that all cryptographic values are ring elements, and all key agreement computations are ring multiplications. (A smaller envelope, a semigroup instead of a ring, is also possible.) Security relies on the difficulty of division: here, meaning an operator $/$ such that $((ab)/b)b = ab$. Security also relies on the difficulty of the less familiar wedge operation $[ab, b, bc] \mapsto abc$. When RabiSherman key agreement is instantiated as DiffieHellman key agreement: its multiplication amounts to modular exponentiation; its division amounts to the discrete logarithm problem; the wedge operation amounts to the computational DiffieHellman problem. Ring theory is welldeveloped and implies efficient division algorithms in some specific rings, such as matrix rings over fields. Semigroup theory, though less widelyknown, also implies efficient division in specific semigroups, such as grouplike semigroups. The rarity of key agreement schemes with wellestablished security suggests that easy multiplication with difficult division (and wedges) is elusive. Reduction of key agreement to ring or semigroup multiplication is not a panacea for cryptanalysis. Nonetheless, novel proposals for key agreement perhaps ought to run the gauntlet of a checklist for vulnerability to wellknown division strategies that generalize across several forms of multiplication. Ambitiously applying this process of elimination to a plethora of diverse rings or semigroups might also, if only by a fluke, leave standing a few promising schemes, which might then deserve a more focused cryptanalysis.
Note: Updates over previous version: cited 2 new papers about discrete logarithms in semigroups. Banin and Tsaban reduce semigroup discrete logs to group discrete logs. Childs and Ivanyos find quantum algorithms for semigroup discrete logs. Neither paper significantly impacts the way that semigroups are used in this report, since it is multiplication in the semigroup, not exponentiation in the semigroup, which this semigroup focuses. So, division not logarithm is the main attack strategies. In special cases, discrete logarithms can be used to divide, so this report therefore cites these two papers on semigroup discrete logarithms.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 publickey cryptograpykey exchangekey managementkey agreementsemigroupdivisionwedgenoninteractive key exchangeDiffieHellman
 Contact author(s)
 danibrown @ blackberry com
 History
 20220516: last of 2 revisions
 20210903: received
 See all versions
 Short URL
 https://ia.cr/2021/1112
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1112, author = {Daniel R. L. Brown}, title = {Key agreement: security / division}, howpublished = {Cryptology ePrint Archive, Paper 2021/1112}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1112}}, url = {https://eprint.iacr.org/2021/1112} }