Two-source extractors secure against quantum adversaries (Q2913822)

Roughly speaking an \(n\)-bits string extractor from \(k\) sources, each producing \(m\)-bits strings, is a map \(E:\left(\{0,1\}^m\right)^k\to\{0,1\}^n\). It is intended that the output of \(E\) is indistinguishable from a uniformly distributed random variable \(U_n\), valued at \(\{0,1\}^n\), although the input sources were imperfect. Randomness should be extracted from weak sources. Such bit-string extractors are very important in cryptography and in many fields involved with the notion of randomness. An adversary may store \(n-k\) bits from an uniform extractor, thus from its own point of view the process may have a min-entropy \(k\): the extractor is weaken. Classical results from the eighties assert that no monic extractor (\(k=1\)) may exist, but binary extractors (\(k=2\)) may do exist (usually, the inner product is used as blender to build extractors). In the context of quantum computing, the bits storage may be simulated by entanglement, thus extractors strong in the classical sense may be weak in the quantum computing context, and several examples have been shown in the last decade.NEWLINENEWLINEThe authors show a two-source extractor which is robust even against adversaries using entangled quantum states. Two parties share an entangled state, each part stores short information of its components using a density operator, and these density operators produce a global density operator. An extractor is built which is enough close to a uniform distribution even if access is allowed to the global density operator.NEWLINENEWLINE The paper is highly technical. A complete exposition is produced at the cost of lengthy details. The authors are extending classical (in both senses, theoretical and computational) important procedures for extractors to the case of quantum computing with entanglement. This is a significant improvement for effective bit-string extractors.