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 -&gt; (shareA,msg1), opB : seed2 -&gt; msg1 -&gt; (msg2,key), opAfin : shareA -&gt; msg2 -&gt; 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.
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.