If a measurement is made on one half of a bipartite system then, conditioned on the outcome, the other half has a new reduced state. If these reduced states defy classical explanation \— that is, if shared randomness cannot produce these reduced states for all possible measurements \— the bipartite state is said to be steerable. Determining which states are steerable is a challenging problem even for low dimensions. In the case of two-qubit systems a criterion is known for T-states (that is, those with maximally mixed marginals) under projective measurements. In the current work we introduce the concept of keyring models \— a special class of local hidden state model. When the measurements made correspond to real projectors, these allow us to study steerability beyond T-states. Using keyring models, we completely solve the steering problem for real projective measurements when the state arises from mixing a pure two-qubit state with uniform noise. We also give a partial solution in the case when the uniform noise is replaced by independent depolarizing channels. Our results imply that Werner states, which are a special case of the previous states, are unsteerable under real projective measurements if and only if their efficiency is at most 2/π.

}, doi = {10.1063/1.5006199}, url = {http://aip.scitation.org/doi/full/10.1063/1.5006199}, author = {Carl Miller and Roger Colbeck and Yaoyun Shi} } @article {1951, title = {Parallel Device-Independent Quantum Key Distribution}, year = {2017}, month = {2017/03/15}, abstract = {A prominent application of quantum cryptography is the distribution of cryptographic keys with unconditional security. Recently, such security was extended by Vazirani and Vidick (Physical Review Letters, 113, 140501, 2014) to the device-independent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove unconditional security of a protocol where all games are executed in parallel. Our result further reduces the requirements for QKD (allowing for arbitrary information leakage within each players\&$\#$39; lab) and opens the door to more efficient implementation. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate.

}, url = {https://arxiv.org/abs/1703.05426}, author = {Rahul Jain and Carl Miller and Yaoyun Shi} } @article {1982, title = {Randomness in nonlocal games between mistrustful players}, journal = {Quantum Information and Computation}, volume = {17}, year = {2017}, month = {2017/06/15}, pages = {0595-0610}, abstract = {If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player\&$\#$39;s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.

}, url = {https://arxiv.org/abs/1706.04984}, author = {Carl Miller and Yaoyun Shi} } @article {2036, title = {Universal Security for Randomness Expansion from the Spot-Checking Protocol}, journal = {SIAM Journal on Computing}, volume = {46}, year = {2017}, month = {2017/08/01}, abstract = {Colbeck (Thesis, 2006) proposed using Bell inequality violations to generate certified random numbers. While full quantum-security proofs have been given, it remains a major open problem to identify the broadest class of Bell inequalities and lowest performance requirements to achieve such security. In this paper, working within the broad class of spot-checking protocols, we prove exactly which Bell inequality violations can be used to achieve full security. Our result greatly improves the known noise tolerance for secure randomness expansion: for the commonly used CHSH game, full security was only known with a noise tolerance of 1.5\%, and we improve this to 10.3\%. We also generalize our results beyond Bell inequalities and give the first security proof for randomness expansion based on Kochen-Specker inequalities. The central technical contribution of the paper is a new uncertainty principle for the Schatten norm, which is based on the uniform convexity inequality of Ball, Carlen, and Lieb (Inventiones mathematicae, 115:463-482, 1994).

}, doi = {10.1137/15M1044333}, url = {http://epubs.siam.org/doi/10.1137/15M1044333}, author = {Carl Miller and Yaoyun Shi} } @article {1883, title = {Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices}, journal = {Journal of the ACM}, volume = {63}, year = {2016}, month = {2016/10/26}, pages = {33:1{\textendash}33:63}, abstract = {Randomness is a vital resource for modern-day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high-quality random numbers generated securely. Here, we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the R{\'e}nyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements and a method for simulating trusted measurements with untrusted devices.

}, keywords = {key distribution, nonlocal games, privacy, quantum cryptography, random-number generation, untrusted device}, issn = {0004-5411}, doi = {10.1145/2885493}, url = {http://doi.acm.org/10.1145/2885493}, author = {Carl Miller and Yaoyun Shi} } @inbook {1863, title = {Optimal robust self-testing by binary nonlocal XOR games}, booktitle = {8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013}, volume = {22}, year = {2013}, pages = {254{\textendash}262}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing}, organization = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing}, abstract = {Self-testing a quantum apparatus means verifying the existence of a certain quantum state as well as the effect of the associated measuring devices based only on the statistics of the measurement outcomes. Robust (i.e., error-tolerant) self-testing quantum apparatuses are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted devices. We devise a general scheme for proving optimal robust self-testing properties for tests based on nonlocal binary XOR games. We offer some simplified proofs of known results on self-testing, and also prove some new results.

}, keywords = {nonlocal games, quantum cryptography, Random number generation, Self-testing}, doi = {10.4230/LIPIcs.TQC.2013.254}, author = {Carl Miller and Yaoyun Shi} }