Cryptography

One obvious way to proceed is to extract a hardcore bit of $g^{\mathrm{xy}}$. For example, using the Goldreich-Levin method, they can find a hardcore bit $B$, and to derive a 128-bit key, they simply perform 128 Diffie-Hellman exchanges and extract $B(g^{\mathrm{xy}})$ each time. This is secure provided we assume no efficient Computational Diffie-Hellman algorithm exists, for then the adversary should not be able to distinguish between the distributions $\{g^x,g^y,B(g^{\mathrm{xy}}),x,y\leftarrow {\mathbb{Z}}_q\}$ and $\{g^x,g^y,r,x,y\leftarrow {\mathbb{Z}}_q,r\leftarrow \{\mathrm{0,1}\}\}$. More formally:

Theorem: If the CDH problem is $(t,\epsilon )$-hard then there is no $(t,\epsilon /128)$-distinguisher between

$$\{g^{x_1},...,g^{x^{128}},g^{y_1},...,g^{y_{128}},K=B(g^{x_1{y}_1})\mid \mid ...\mid \mid B(g^{x_{128}{y}_{128}}),\bar{x},\bar{y}\leftarrow {\mathbb{Z}}_q^{128}\}$$

and

$$\{g^{x_1},...,g^{x^{128}},g^{y_1},...,g^{y_{128}},K,\bar{x},\bar{y}\leftarrow {\mathbb{Z}}_q^{128},K\leftarrow \{\mathrm{0,1}{\}}^{128}\}$$

Sketch of proof: distinguisher $\Rightarrow$ predictor for $i$th bit $\Rightarrow$ predictor for $B(g^{\mathrm{xy}})$ given $g^x,g^y$ $\Rightarrow$ CDH algorithm.

However, this method is impractical as it requires one Diffie-Hellman exchange for each bit of the session key. Unfortunately, it is not known how to improve this method much without using a stronger assumption:

The $(t,\epsilon )$-Decisional Diffie-Hellman (DDH) assumption says that the distribution

$$\{g,g^a,g^b,g^c\mid a,b,c\leftarrow {\mathbb{Z}}_q\}$$

is $(t,\epsilon )$-indistinguishable from the distribution

$$\{g,g^a,g^b,g^{\mathrm{ab}}\mid a,b\leftarrow {\mathbb{Z}}_q\}$$

(In other words, given $g^a$ and $g^b$, $g^{ab}$ is indistinguishable from a random element, which implies that $\lfloor \lg q\rfloor$ bits of $g^{\mathrm{ab}}$ are simultanesouly secure given $g^a,g^b$.

Using this assumption allows a provably secure scheme for extracting a session key, via the left-over lemma.

Let $p$ be a 1024-bit prime, and let $q$ be a 255-bit prime such that $G$ is a subgroup of ${\mathbb{Z}}_p^{*}$ of order $q$, and let $g$ be a generator of $G$. Let $m=\lfloor \lg q\rfloor$, and suppose $\mid G\mid \approx 2^m$. Set $e=m/3$, and let $H=\{h_{\lambda }\mid \lambda \in \Lambda \}:{\mathbb{Z}}_p^{*}\to \{\mathrm{0,1}{\}}^{m-2e}=\{\mathrm{0,1}{\}}^{m/3}=\{\mathrm{0,1}{\}}^{85}$. be almost universal. Then consider the following key exchange protocol:

Alice picks $x\leftarrow {\mathbb{Z}}_q,{\lambda }_1\leftarrow \Lambda$ and sends $g^x,{\lambda }_1$ to Bob. Similarly, Bob picks $y\leftarrow {\mathbb{Z}}_q,{\lambda }_2\leftarrow \Lambda$ and sends $g^y,{\lambda }_2$ to Alice. They both compute the secret key $\mathrm{SK}=h_{{\lambda }_1\oplus {\lambda }_2}(g^{\mathrm{xy}})$.

Theorem: Assuming $(t,\epsilon )$-DDH on $G$, the distributions

$$\{g,g^x,g^y,{\lambda }_1,{\lambda }_2,\mathrm{SK}\mid x,y\leftarrow {\mathbb{Z}}_q,{\lambda }_1,{\lambda }_2\leftarrow \Lambda \}$$

and

$$\{g,g^x,g^y,{\lambda }_1,{\lambda }_2,R\mid x,y\leftarrow {\mathbb{Z}}_q,{\lambda }_1,{\lambda }_2\leftarrow \Lambda ,R\leftarrow \{\mathrm{0,1}{\}}^{m/3}\}$$

are $(t,\epsilon +1/2^{m/3})$-indistinguishable.

Proof: Suppose $A$ is a $(t,\epsilon +1/2^{m/3})$-distiguisher. Then we can construct a DDH-distiguisher $B$ as follows.

• $B$ is given a tuple $I=⟨g,g_1,g_2,g_3⟩\in G^4$.

• $B$ picks random ${\lambda }_1,{\lambda }_2\leftarrow \Lambda$, and computes $S=h_{{\lambda }_1\oplus {\lambda }_2}(g_3)$.

• $B$ gives the tuple $I\prime =⟨g_1,g_2,g_3,{\lambda }_1,{\lambda }_2,S⟩$ to $A$, and outputs the output of $A$.

We show that $B$ is a $(t,\epsilon )$-DDH algorithm. Note

$$\mid \mathrm{Pr}[B(I)\mid I-\mathrm{DDH}]-\mathrm{Pr}[B(I)\mid I-\mathrm{randg}3]\mid =\mid \mathrm{Pr}[A(I\prime )\mid I\prime -\mathrm{DDH}]-\mathrm{Pr}[A(I\prime )\mid I\prime -\mathrm{randg}3\mathrm{hash}]\ge \mid \mathrm{Pr}[A(I\prime )\mid I\prime -\mathrm{DDH}]-\mathrm{Pr}(A(I\prime )\mid I\prime -\mathrm{rand}01m3]\mid -\mid \mathrm{Pr}[A(I\prime )\mid I\prime -\mathrm{rand}01m3-\mathrm{Pr}[A(I\prime )\mid I\prime -\mathrm{randg}3\mathrm{hash}]\mid$$

where we have used the inequality $\mid A+B\mid \ge \mid A\mid -\mid B\mid$. Now the first term is at least $\epsilon +1/2^{m/3}$, while the second term is at most $1/2^{m/3}$ by the leftover lemma.

The leftover lemma shows how to extracts randomness from a "defective" random source.

Definition: Let

$$H=\{h_{\lambda }:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^l{\}}_{\lambda \in \Lambda }$$

$H$ is called a universal family of hash functions if for all $x\ne y\in \{\mathrm{0,1}{\}}^n$ we have

$${\mathrm{Pr}}_{h\leftarrow H}[h(x)=h(y)]=1/2^l$$

$H$ is almost universal if for all $x\ne y\in \{\mathrm{0,1}{\}}^n$ we have

$${\mathrm{Pr}}_{h\leftarrow H}[h(x)=h(y)]=1/2^l+1/2^n.$$

A set of all linear congruential generators (modulo some prime $p$) is an example of an almost universal family of hash functions.

Definition: Let $S$ be a finite set and $D,D\prime$ be distributions on $S$. For all $x\in S$, denote the probability of picking $x$ according to $D$ by $D(x)$, and for all $X\subseteq S$, define $D(X)={\sum }_{x\in X}D(x)$. Define the following:

• The collision probability of $D$ is $\mathrm{coll}(D)={\sum }_{x\in S}D(x{)}^2$.

• $D,D\prime$ are $\epsilon$-statistically indistinguishable if for all $X\subseteq S$, we have $\mid D(X)-D\prime (X)\mid <\epsilon$.

• $D$ is $\epsilon$-quasirandom if $D$ is $\epsilon$-statistically indistinguishable from the uniform distribution on $S$ (which we denote by $U(S)$. Hence for any subset $X\subseteq S$ we have $\mid D(X)-\mid X\mid /\mid S\mid \mid <\epsilon .$

Quasirandomness is useful. For suppose $D$ is $\epsilon$-quasirandom on $S$. Then for any algorithm $A$, we have

$$\mid {\mathrm{Pr}}_{x\leftarrow D}[A(x)\text{accepts}]-{\mathrm{Pr}}_{x\leftarrow U(S)}[A(x)\text{accepts}]\mid <\epsilon$$

Proof: Let $T\subseteq S$ be $T\{x\mid A(x)\}$. Then

$$\begin{array}{ccc}\mid {\mathrm{Pr}}_{x\leftarrow D}[A(x)]-{\mathrm{Pr}}_{x\leftarrow U(S)}[A(x)]\mid & =& \mid {\mathrm{Pr}}_{x\leftarrow D}[A(x)\mid x\in T]\mathrm{Pr}[x\in T]\\ & +& {\mathrm{Pr}}_{x\leftarrow D}[A(x)\mid x\notin T]\mathrm{Pr}[x\notin T]\\ & -& {\mathrm{Pr}}_{x\leftarrow U(S)}[A(x)\mid x\in T]\mathrm{Pr}[x\in T]\\ & -& {\mathrm{Pr}}_{x\leftarrow U(S)}[A(x)\mid x\notin T]\mathrm{Pr}[x\notin T]\mid \\ & =& \mid {\mathrm{Pr}}_{x\leftarrow D}[x\in T]-{\mathrm{Pr}}_{x\leftarrow U(S)}[x\in T]\mid \\ & =& \mid D(T)-U(T)\mid <\epsilon \end{array}$$

Leftover Lemma: Let $G\subseteq \{\mathrm{0,1}{\}}^n$, $\mid G\mid >2^l$. Let $e>0$ and let $H$ be an almost universal hash family from $\{\mathrm{0,1}{\}}^n$ to $\{\mathrm{0,1}{\}}^{l-2e}$. Then the distribution $\{(h,h(x))\mid h\leftarrow H,x\leftarrow G\}$ is $1/2^e$-quasirandom on $H\times \{\mathrm{0,1}{\}}^{l-2e}$.

Proof: there are two steps to the proof.

Claim: (proof omitted) because $H$ is almost universal, the collision probability

$$\mathrm{coll}((h,h(x){)}_{h\leftarrow H,x\leftarrow G})<(1+2/2^{2e})/\mid H\mid 2^{l-2e}$$

Claim: Let $D$ be a distribution on a finite set $S$. If $\mathrm{coll}(D)<(1+2{\delta }^2)/\mid S\mid$ then $D$ is $\delta$-quasirandom.

Proof of claim: Suppose there exists some subset $X\subseteq S$ such that $D(X)\ge \mid X\mid /\mid S\mid +\delta$. Without loss of generality, assume equality holds (we can just increase $\delta$). We have $D(S\setminus X)=1-D(X)$. Then

$$\begin{array}{ccc}\mathrm{coll}(D)& =& {\mathrm{Pr}}_{x_1,x_2\leftarrow D}[x_1=x_2]\\ & =& {\mathrm{Pr}}_D[x_1=x_2\mid x_1\wedge x_2\in X]\mathrm{Pr}[x_1\wedge x_2\in X]+{\mathrm{Pr}}_D[x_1=x_2\mid x_1\wedge x_2\notin X]\mathrm{Pr}[x_1\wedge x_2\notin X]\\ & =& {\mathrm{Pr}}_D[x_1=x_2\mid x_1\wedge x_2\in X]D(X{)}^2+{\mathrm{Pr}}_D[x_1=x_2\mid x_1\wedge x_2\notin X]D(S\setminus X{)}^2\\ & \ge & 1/\mid X\mid D(X{)}^2+1/\mid S\setminus X\mid D(S\setminus X{)}^2\\ & =& D(X{)}^2/\mid X\mid +(1-D(X){)}^2/(\mid S\mid -\mid X\mid )\\ & =& 1/\mid S\mid +{\delta }^2/\mid X\mid +{\delta }^2/(\mid S\mid -\mid X\mid )\end{array}$$

(Because we are considering collison probabilities, we can ignore the cases when only one of $x_1,x_2$ lies in $X$). The last line is minimized when $\mid X\mid =\mid S\mid /2$, thus we have

$$\mathrm{coll}(D)\ge 1/\mid S\mid +4{\delta }^2/\mid S\mid \ge 1\mid S\mid +2{\delta }^2/\mid S\mid$$

So by the first claim

$$\mathrm{coll}((h,h(x){)}_{h\leftarrow H,x\leftarrow G})<(1+2(1/2^e{)}^2)/\mid H\mid 2^{l-2e}$$

and we have $\mid S\mid =\mid H\mid 2^{l-2e}$, $\delta =1/2^e$. Then by the second claim, $(h,h(x))$ is $1/2^e$-quasirandom.

There are more effective techniques than the leftover lemma [SZ94]. Let $D$ be a distribution on a finiste set $S$ and define

$$\min -\mathrm{entropy}(D)=\underset{x\in S}{\min }\{-\lg D(x)\mid D(x)\ne 0\}.$$

For example, the min-entropy of a point distribution is zero, and for the uniform distribution $U(S)$, it is $\lg \mid S\mid$.

Now suppose $G$ is a set with $\mid G\mid =\mid S\mid /2^{\delta }$. Then $\min -\mathrm{entropy}(U(G))=\lg \mid S\mid -\delta$. Thus we see that $\min -\mathrm{entropy}(D)=\delta$ implies that for all $x\in S$ we have $D(x)\le 2^{-\delta }$. Sometimes the distribution $D$ is referred to as a $\delta$-source. It turns out that it is possible to extract about $\delta$ bits from an arbitrary $\delta$-source.

Theorem: For any $l$, and $e\le l/2$, there exists a family $H$ of hash functions

$$H=\{h_{\lambda }:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^{l-2e}{\}}_{\lambda \in \Lambda }$$

such that

• $\mid H\mid =O(n{2}^{4(l-e)})$ (only $4(l-e)+O(\log n)$ bits are needed to describe the family)

• For any distribution $D$ on $\{\mathrm{0,1}{\}}^m$ with $\min -\mathrm{entropy}(D)=l$, the distribution $\{(h,h(x)\mid h\leftarrow H,x\leftarrow D\}$ is $2/2^e$-quasirandom

The theorem is used to construct cryptosystems with exposure-resilience: even if an adversary learns "crazy" bits of a key, security is still maintained. The idea is to split a key into two parts, the first part specifies the hash function to use while the other bits are fed into the hash function.