# Creating a secure key

Imagine that your lecturer and the undergraduate office have conducted a key exchange protocol after which both of them hold the string $X$. Yet, it is possible that a curious student sitting next to the lecturer in the bus may have gained some information $E$ about $X$. (Un)fortunately, the student eavesdropper Eve has gained only $1000$ bits of information $E$ about $X$ from the quick glance. If $X$ contains 1 million bits and was chosen randomly beforehand, describe how the lecturer and the undergraduate office can produce a fully secure key $K$ from $X$ to encrypt the final exam for electronic transmission, such that student eavesdropper Eve knows essentially nothing about the key $K$.

-
Is this homework? The answer is to hash $X$, but I'll let you figure out the reasoning yourself. Note that if Eve truly only learned the individual values of 1000 of the million bits you can just hash 1256 bits to get a 256-bit security level, by the pigeonhole principle. –  orlp Nov 22 '13 at 8:54
@nightcracker : $\:$ Could your suggestion be shown to be secure in the plain model? $\hspace{1.4 in}$ –  Ricky Demer Nov 22 '13 at 9:53
@nightcracker I would guess you need a KBKDF here (e.g. HKDF or one of the NIST SP 800-108 algorithms). It's what's they are there for. Hashes may not be secure enough (in principle, I would think that just using SHA-2 would be secure enough in practice). –  owlstead Nov 22 '13 at 10:33
Probably, what is wanted is an argument that extracts a key $K$ from $X$ that Eve has no information about. If you just need a reasonable key size (say 256 bits), there's no need to use hash functions. Hint: partition and xor. –  K.G. Nov 22 '13 at 10:52
HKDF (with SHA-2 as underlying hash) is the cleanest solution IMO. But a plain SHA-2 hash to extract the entropy would be perfectly fine. // In theory there are some provably secure constructions, in practice SHA-2 I'd prefer a proper hash like SHA-2 over all of them. –  CodesInChaos Nov 22 '13 at 10:56

The basic problem is to establish a shared key between Lecturer and undergraduate office securely. In the original Diffie-Hellman key-exchange protocol, Alice and Bob use the $g^{ab}$ as their session key. This basic DH protocol is based on CDH assumption, but CDH assumption alone can not ensure that we can use all the bits of $g^{ab}$ securely, it can only make sure that we can obtain a hard core bit which is unpredictable. So the straight idea is to run the protocol $k-times$ to get secure $k$ bits. But it's undesirable and inefficient. So, in order to make the weak bits of $g^{ab}$ as strong as others, usually we hash the shared value to get the final session key.
The slightly less straight but still provably secure-if-CDH-is-hard idea is to run the protocol $\:\Theta(k/(\log(k)))\:$ times and obtain logarithmically many hard-core bits, as described on page 32 of this paper. $\hspace{1.06 in}$ –  Ricky Demer Nov 23 '13 at 2:05