0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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/… $\endgroup$ – poncho May 26 at 19:06
  • $\begingroup$ 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. $\endgroup$ – user69465 May 26 at 19:14
  • $\begingroup$ If you had a way of turning (say) NewHope into a semigroup, well, that'd be nontrivial... $\endgroup$ – poncho May 26 at 19:24
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.