Key Agreement

Asymmetric Version

What is a key agreement system?

• Simplified: ``two-pass'', secure against passive observer, two participants

• Five sets:
  • $\mathcal {R}$_A = the set of Alice's possible private secrets
  • $\mathcal {U}$_A = the set of Alice's possible public transmissions
  • $\mathcal {R}$_B = the set of Bob's possible private secrets
  • $\mathcal {U}$_B = the set of Bob's possible public transmissions
  • $\mathcal {K}$ = the set of possible keys

• ``One-way'' functions:
  • f_A : $\mathcal {R}$_A$\to$$\mathcal {U}$_A, bijective
  • f_B : $\mathcal {R}$_B$\to$$\mathcal {U}$_B, bijective
  • g_A : $\mathcal {R}$_A×$\mathcal {U}$_B$\to$$\mathcal {K}$
  • g_B : $\mathcal {R}$_B×$\mathcal {U}$_A$\to$$\mathcal {K}$
  • g_A(a, f_B(b)) = g_B(b, f_A(a)) for all a in $\mathcal {R}$_A, b in $\mathcal {R}$_B

Protocol

• Alice picks a in $\mathcal {R}$_A, sends Bob $\alpha$ = f_A(a)
• Bob picks b in $\mathcal {R}$_B, sends Alice $\beta$ = f_B(b)
• Alice computes k = g_A(a,$\beta$)
• Bob computes k = g_B(b,$\alpha$)

Computational Requirements

1. ``Easy'' to find r in $\mathcal {R}$_A (respectively $\mathcal {R}$_B) and compute u = f_A(r) (respectively u = f_B(r)) given r

2. ``Easy'' to compute k = g_A(r, u) (respectively k = g_B(r, u)) given r and u

3. ``Hard'' to compute r = f_A^-1(u) (respectively r = f_B^-1(u)) given only u

4. ``Hard'' to compute k = g_A(f_A^-1($\alpha$),$\beta$) = g_B(f_B^-1($\beta$),$\alpha$) given only $\alpha$ and $\beta$

Symmetric version

What is a symmetric key agreement system?

• More simplified: symmetric, ``two-pass'', secure against passive observer, two participants

• Three sets:
  • $\mathcal {R}$ = the set of possible private secrets
  • $\mathcal {U}$ = the set of possible public transmissions
  • $\mathcal {K}$ = the set of possible keys

• ``One-way'' functions:
  • f : $\mathcal {R}$$\to$$\mathcal {U}$, bijective
  • g : $\mathcal {R}$×$\mathcal {U}$$\to$$\mathcal {K}$
  • g(a, f (b)) = g(b, f (a)) for all a, b in $\mathcal {R}$

Protocol

• Alice picks a in $\mathcal {R}$, sends Bob $\alpha$ = f (a)
• Bob picks b in $\mathcal {R}$, sends Alice $\beta$ = f (b)
• Alice computes k = g(a,$\beta$)
• Bob computes k = g(b,$\alpha$)

Computational Requirements

1. ``Easy'' to find r in $\mathcal {R}$ and compute u = f (r) given r

2. ``Easy'' to compute k = g(r, u) given r and u

3. ``Hard'' to compute f^-1(r) given only u

4. ``Hard'' to compute k = g(f^-1($\alpha$),$\beta$) = g(f^-1($\beta$),$\alpha$) given only $\alpha$ and $\beta$

About this document ...

Key Agreement

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.57)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -link 0 -split +0 -html_version 3.2,math key-agreement.tex

The translation was initiated by Joshua R Holden on 2004-04-25