0
$\begingroup$

Some questions I have ended up wondering about while reading through many of key-exchange protocols are:

  • Is there an intrinsic reason, why most key exchange protocols use group-based approaches apart from it being a well-studied area?
  • Given a key exchange protocol does there always need to be some group or a particular algebraic structure involved?
  • What about key-exchange with a requirement for perfect forward secrecy?
  • What would be the least constrained algebraic structure involved for a secure key exchange?
  • If not can you give some examples of perfect forward secure key exchange protocols not involving group operations?
$\endgroup$
  • 1
    $\begingroup$ What if the protocol uses rings or fields instead? Or is your question asking for a key-exchange protocol that uses less structure than a group (e.g. a monoid)? If so, it should specify that in the body of the question. $\endgroup$ – Ella Rose Oct 7 '18 at 3:33
  • $\begingroup$ Having easily computable is very important. Having Well defined and proved/studied hard problems are important. $\endgroup$ – kelalaka Oct 7 '18 at 6:29
4
$\begingroup$

Is there an intrinsic reason, why most key exchange protocols use group-based approaches apart from it being a well-studied area?

No. It just so happens that

  • Diffie-Hellman was first and heavily used multiplication modulo a prime, which was later generalized to groups. So groups are important for historic reasons.
  • Groups are easy to understand and "even the average software developer" can probably get a grasp of why this is secure somewhat quickly.
  • We know efficient ways to create groups which yield fast, small and secure key exchanges, so they are a natural choice.

Beyond that you can build a secure key exchange from any encryption scheme, including e.g. McEliece (by simply encryptingt the shared secret and sending it over).

Given a key exchange protocol does there always need to be some group or a particular algebraic structure involved?

In some sense yes. You can't avoid fields / groups because computer arithmetic fundamentally is working with these, so if you want to actually compute / execute the protcol you'll at some point involve fields and groups.

On a higher level, to agree on a secret over a public channel we need some structure that allows us to publicly show values and blocks passive adversaries from learning the corresponding secrets. Chances are you can always find a relevant mathematical concept / basic idea out of any key exchange. Additionally sometimes these protocols start from things we know how to quickly compute as honest users but know to be hard to break from other fields, so why make an effort to come up with something new (that may be broken in a few days - years) when you can build on a large amount of existing research?

What about key-exchange with a requirement for perfect forward secrecy?

Just about any protocol can be modified / extended to provide forward secrecy, so there's nothing special about this property and groups. It just so happens that with groups the property can be achieved somewhat cheaply.

What would be the least constrained algebraic structure involved for a secure key exchange?

On an abstract level probably the semi-group which is usually enough for the "group-based" key exchanges we are using, because these don't actually make use of the ability to invert every element nor do they make use of the availability of a neutral element.

Note though that not every semi-group (eg the natural numbers with addition) actually provide cryptographic security. If you are looking for examples of secure semi-group based key exchange look no further than standard ECDH and DH, which use $(E(\mathbb F_p),+_{\text{EC}})$ and $(\mathbb F_p^*,\cdot)$ as their semigroups.

If not can you give some examples of perfect forward secure key exchange protocols not involving group operations?

See above on avoiding groups and using McEliece. You get forward secrecy by throwing the encryption scheme's private / public key away after each key exchange.

$\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.