Two-universal functions

Two-universal functions#

So far we have only given mathematically definitions of functions, the randomness extractors, that fulfill certain conditions. To show that the previous sections are not just a collection of mathematically convenient definitions, in this section we define a class of functions with well-known explicit constructions since the 70s that satisfy the definition of quantum-proof strong randomness extractors: the class of two-universal functions.1Originally denoted as universal\(_2\) functions.

Two-universal functions

This class of functions was originally studied in the context of input independent average linear time computation. Only later they were found useful for cryptographic tasks.

We say that that a family of functions \(\mathcal{F}\), such that \(f:\mathcal{X}\rightarrow\mathcal{Z}\), is two-universal if \(\Pr_f[f(x)=f(x')]\leq\frac{1}{|\mathcal{Z}|}\) for any distinct \(x,x'\in\mathcal{X}\), and \(f\in\mathcal{F}\) chosen uniformly at random.

Carter and Wegman [5, 6] showed explicit constructions of this class of functions. That is why we know that for any integers \(0 < m\leq n\) we can always find a family of two-universal functions from \(\{0,1\}^n\) to \(\{0,1\}^m\).

A randomness extractor, as defined in the previous section, is obtained from a family of two-universal functions in the following way

  1. A uniform seed \(y\) is used to select a particular function \(f_y\in\mathcal{F}\) from the family

  2. The output of the extractor is obtained by applying this function to the input, i.e.,

\[\text{Ext}(x,y) = f_y(x)\]

Quantum leftover hash lemma#

In the late 80s it was already proven that families of two-universal functions can be used in cryptographic applications and, in particular, in the task of randomness extraction. However, in the original research only classical side information was considered. Later, it was proved a quantum version of the leftover hash lemma [7, 8], generalizing the original result and showing that these functions can be used also against quantum side information.

The quantum leftover hash lemma states the following: For a random variable \(X\), quantum side information \(E\), and a family of two-universal functions \(\mathcal{F}\) from \(\{0,1\}^n\) to \(\{0,1\}^m\), on average over the choices of \(f\) from \(\mathcal{F}\), the output \(f(X)\) is \(\epsilon\)-close to uniform conditioned on \(E\), where \(\epsilon\) is given by

\[\epsilon = \frac{1}{2}\sqrt{2^{m-H_\text{min}(X|E)}}\,.\]

In other words, and going back to our quantum-proof randomness extractor, if we know that our weak source of randomness has a lower bound on its quantum conditional min-entropy, i.e., \(H_\text{min}(X|E)\geq k\), and we want our QKD protocol to be \(\epsilon_\text{sec}\)-secret, then privacy amplification can be achieved by choosing a proper family of two-universal functions with

\[m = \Big\lfloor k + 2 - 2\log\frac{1}{\epsilon_\text{sec}} \Big\rfloor\,.\]

Notice that, as we defined the statistical distance in the previous section, the value of \(\epsilon_\text{sec}\)-secret could, in principle, be in the range \([0,1]\). However, the lemma only works for \(\epsilon>0\), and because it is not possible to extract more bits than the amount of bits we input, even in the extreme case \(m=n=H_\text{min}(X|E)\), we obtain that \(\epsilon_\text{sec}\text{-secret}=\frac{1}{2}\). This extreme case represents a situation where the weak random source is already uniform from the adversary’s point of view, so we don’t need an extractor to begin with. Therefore, for practical implementations that make use of this lemma to compute the output length, the value of \(\epsilon_\text{sec}\)-secret should be in the range \((0, \tfrac{1}{2}\sqrt{2^{m-n}})\).

Contents