Is there a formal definition for a protocol that expands keys that are pre-shared among 2 or more parties?
How about an informal definition?


Alice and Bob pre-share a $n$-bit string $k$. After running algorithm $\Pi$ Alice and Bob have a common ($n$+$q$)-bit string $k'$, where $q>0$. In addition Eve learns nothing about $k$ or $k'$. Eve is an an eavesdropper on the channel between Alice and Bob with unlimited computational power. i.e. If $P_x$ are the odds of Eve learning $x$ then $P_k\le \frac{1}{2^n}$ and $P_{k'}\le \frac{1}{2^{n}}$.

  • $\begingroup$ If Eve learns $k$, then she automatically learns $k'$ through $\Pi$, but your formulae seem to imply that $P_{k'} < P_k$. Are you perhaps looking for [en.wikipedia.org/wiki/Key_schedule](a key schedule), or rather [en.wikipedia.org/wiki/Key_stretching](key stretching)? $\endgroup$ Jun 11, 2017 at 15:12
  • $\begingroup$ @RubenDeSmet: That is true. I changed the bound for $P_{k'}$ I was looking at the wikipedia pages but none gave a definition of what it meant for a key expansion algorithm to be secure. For example would Alice and Bob seeding an agreed upon PRNG with $k$ and retrieving $n+q$ bits constitute as an information-theoretically secure key expansion? $\endgroup$
    – edggy
    Jun 11, 2017 at 15:33
  • 1
    $\begingroup$ This sounds more like a KBKDF (key based key derivation function) to me than key stretching or key schedule. Basically you team the input secret with a label and output size and then generate a key that is derived from the input key material $k$. An example is HKDF (with somebody posting the SHAKE equivalent in a minute or so :) ) $\endgroup$
    – Maarten Bodewes
    Jun 11, 2017 at 15:35
  • $\begingroup$ @MaartenBodewes: There are plenty of examples, but I can't find a definition. $\endgroup$
    – edggy
    Jun 11, 2017 at 15:51

1 Answer 1


NIST SP-800 108 seems to have a semi-formal definition in chapter 5.0:

Section 1:

A key derivation function iterates a pseudorandom function (ed: PRF) $n$ times and concatenates the outputs until $L$ bits of keying material are generated, where $n = ⎡L/h⎤$.

Section 2:

For each of the iterations of the PRF, the key derivation key $K_I$ is used as the key, and the input data consists of an iteration variable and a string of fixed input data.

But I must admit that this seems more a description of the inner workings of the described KDF's than a formal definition of one, if such a thing exists.

As about any KDF actually works this way it remains to be seen if this isn't enough of a formal description.

The original HKDF paper has this more formal definition:

Definition 5: A key derivation function (KDF) accepts as input four arguments:

  • a value $\sigma$ sampled from a source of keying material (Def. 6),
  • a length value $l$,

and two additional arguments,

  • a salt value $r$ defined over a set of possible salt values
  • and a context variable $c$,

both of which are optional, i.e., can be set to the null string or to a constant. The KDF output is a string of $l$ bits.

  • $\begingroup$ The original HKDF paper also should have plenty of definitions. eprint.iacr.org/2010/264 $\endgroup$
    – SEJPM
    Jun 11, 2017 at 16:02
  • $\begingroup$ I don't think this is what I'm looking for. I am looking for a multi-party (2) protocol in which a pre-shared is elongated securely. So far this looks like a one-party protocol. There is no mention of an eavesdropper or communication. $\endgroup$
    – edggy
    Jun 11, 2017 at 16:08
  • $\begingroup$ You mean something like a ratchet? I think there are several ways of doing so, so that may mean more than one definition I suppose... One thing you can do is to pick a KDF and then include a counter in the label. As long as the counters are kept in sync this can create any amount of key material. $\endgroup$
    – Maarten Bodewes
    Jun 11, 2017 at 16:12
  • $\begingroup$ As long as the key derivation is deterministic (which it is), you can run it at both sides and get the same extended key. That's probably not what you're after though. $\endgroup$ Jun 11, 2017 at 16:14
  • $\begingroup$ @edggy What you want is either a KBKDF as Maarten has it explained here or a pre-shared key authenticated key exchange (where you derive new keys using your old symmetric ones). Expansion of key material as a multi-party protocol doesn't make much practical sense and is usually actually a composition of the above named primitives. $\endgroup$
    – SEJPM
    Jun 11, 2017 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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