# Key exchange without an underlying semigroup

I am wondering whether there is a general reformulation of perfect forward secrecy for 2 party key exchange in 2 messages using semigroups. I am looking for references, which would discuss such approach. I am trying to prove my probably misguided intuition, which tells me that every 2 party key exchange requires an underlying semigroup wrong, but so far I failed. The intuition is that if we want to work in 2 messages:

send message from A to B, B derives final key and sends a message from B to A and A derives the same final key we need a relationship like this.

We need a triple of operations (opAinit,opB,opAfin) such that opAinit : seed1 -> (shareA,msg1), opB : seed2 -> msg1 -> (msg2,key), opAfin : shareA -> msg2 -> key and the following to holdopAfin (fst (opAinit(seed1)),fst(opbres)) = opB (snd(opbres)), where opbres=opB(seed2,snd(opAinit(seed1)). Can this always be turned into an underlying semigroup? I am thinking that it should be possible to glue the different operations and domains/codomains into a semigroup action somehow.

• "I am trying to prove my probably misguided intuition, which tells me that every 2 party key exchange requires an underlying semigroup wrong, but so far I failed"; actually, that is believed to be false; there are a number of non-group-based key exchanges known, for example, based on lattices or isogenies. They are currently of special interest as potentially quantum resistant; see the KEMs listed in the NIST page csrc.nist.gov/Projects/Post-Quantum-Cryptography/… – poncho May 26 '19 at 19:06
• If I understand correctly that would apply only to abelian semi-groups, the KEMs on that list could be turned into non-abelian semi-group in some way and still be quantum resistant. – user69465 May 26 '19 at 19:14
• If you had a way of turning (say) NewHope into a semigroup, well, that'd be nontrivial... – poncho May 26 '19 at 19:24

Can this always be turned into an underlying semigroup? I am thinking that it should be possible to glue the different operations and domains/codomains into a semigroup action somehow.

It wouldn't appear so, as there's no reason to expect to be able to perform any operations other than the ones listed in the protocol; in particular, one wouldn't expect to be able to concatenate operations as would be expected in a semigroup.

For example, here's a simple way to turn a public key encryption method (e.g. RSA) into a key exchange method:

• Alice generates a public/private key pair $$pub_A, priv_A$$, and also selects a random nonce $$n_A$$; she sends $$pub_A$$ and $$n_A$$ to Bob

• Bob selects a random nonce $$n_B$$; he encrypts it with $$pub_A$$, and sends $$Enc_{pub_A}(n_B)$$ to Alice

• Alice uses $$priv_A$$ to decrypt the ciphertext to recover $$n_B$$

• Then, both Alice and Bob compute $$h( n_A, n_B )$$ to obtain the shared secret.

In this case, the private values are $$priv_A$$ and $$n_B$$; the messages that are exchanged are the values $$pub_A, n_A$$, and $$Enc_{Pub_A}(n_B)$$. It is not at all clear how someone could define an operator that would take an unrelated message/private value pair (e.g. $$priv_A$$ and $$Enc_{Pub_C}(n_D)$$, you can consider all four possible pairs), and combine them into a meaningful value.