



@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 = {<p><span style="font-family: \&quot;Lucida Grande\&quot;, helvetica, arial, verdana, sans-serif; font-size: 14.4px;">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).</span></p>},
	doi = {10.1137/15M1044333},
	url = {http://epubs.siam.org/doi/10.1137/15M1044333},
	author = {Carl Miller and Yaoyun Shi}
}
