Two-source extractors secure against quantum adversaries
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
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.
- Near-optimal extractors against quantum storage
- Quantum-resilient randomness extraction. (Invited talk)
- Secure Two-Party Quantum Evaluation of Unitaries against Specious Adversaries
- Two-source extractors secure against quantum adversaries
- On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
- The Bounded-Storage Model in the Presence of a Quantum Adversary
- Two-sources randomness extractors in finite fields and in elliptic curves
This page was built for publication: Two-source extractors secure against quantum adversaries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913822)
