**Key agreement: security / division**

*Daniel R. L. Brown*

**Abstract: **Some key agreement schemes, such as Diffie--Hellman key agreement, reduce to Rabi--Sherman 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 non-interactive 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 Rabi--Sherman key agreement is instantiated as Diffie--Hellman key agreement: its multiplication amounts to modular exponentiation; its division amounts to the discrete logarithm problem; the wedge operation amounts to the computational Diffie--Hellman problem.

Ring theory is well-developed and implies efficient division algorithms in some specific rings, such as matrix rings over fields. Semigroup theory, though less widely-known, also implies efficient division in specific semigroups, such as group-like semigroups.

The rarity of key agreement schemes with well-established 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 well-known 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.

**Category / Keywords: **public-key cryptography / public-key cryptograpy, key exchange, key management, key agreement, semigroup, division, wedge, non-interactive key exchange, Diffie--Hellman

**Date: **received 31 Aug 2021, last revised 10 Sep 2021

**Contact author: **danibrown at blackberry com

**Available format(s): **PDF | BibTeX Citation

**Note: **Updates over previous version: cited Hrubes and Wigderson for matrix inversion over a skew field.

**Version: **20210910:210013 (All versions of this report)

**Short URL: **ia.cr/2021/1112

[ Cryptology ePrint archive ]