{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T19:36:57Z","timestamp":1775936217495,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,10,26]],"date-time":"2016-10-26T00:00:00Z","timestamp":1477440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,11,8]]},"abstract":"<jats:p>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\u00e9nyi 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.<\/jats:p>","DOI":"10.1145\/2885493","type":"journal-article","created":{"date-parts":[[2016,10,26]],"date-time":"2016-10-26T13:20:01Z","timestamp":1477488001000},"page":"1-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":82,"title":["Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices"],"prefix":"10.1145","volume":"63","author":[{"given":"Carl A.","family":"Miller","sequence":"first","affiliation":[{"name":"University of Michigan"}]},{"given":"Yaoyun","family":"Shi","sequence":"additional","affiliation":[{"name":"University of Michigan"}]}],"member":"320","published-online":{"date-parts":[[2016,10,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.86.062326"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.110.010503"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.010503"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE International Conference on Computers Systems and Signal Processing 11","author":"Bennett Charles","year":"1984"},{"key":"e_1_2_1_6_1","volume-title":"Advances in Cryptology\u2014CRYPTO\u201991","author":"Bennett Charles H."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217014"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0011-3"},{"key":"e_1_2_1_9_1","volume-title":"A Graduate Course in Applied Cryptography. Retrieved","author":"Boneh Dan","year":"2016"},{"key":"e_1_2_1_10_1","volume-title":"Sims and D. Ueltschi (Eds.)","volume":"529","author":"Carlen Eric A.","year":"2009"},{"key":"e_1_2_1_11_1","unstructured":"Kai-Min Chung Xiaodi Wu and Yaoyun Shi. 2014. Physical Randomness Extractors. arXiv:1402.4797v3.  Kai-Min Chung Xiaodi Wu and Yaoyun Shi. 2014. Physical Randomness Extractors. arXiv:1402.4797v3."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/44\/9\/095305"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys2300"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_33"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591873"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2018325"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/100813683"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"A. Dembo and O. Zeitouni. 1997. Large Devitations Techniques and Applications (2nd ed.). Springer New York NY.  A. Dembo and O. Zeitouni. 1997. Large Devitations Techniques and Applications (2nd ed.). Springer New York NY.","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.88.012323"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2371464"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.67.661"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Security and composability of randomness expansion from Bell inequalities","volume":"87","author":"Fehr Serge","year":"2013","journal-title":"Physical Review Letters"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"D. M. Greenberger M. A. Horne and A. Zeilinger. 1989. Going beyond Bell\u2019s theorem. In Bell\u2019s Theorem Quantum Theory and Conceptions of the Universe M. Kafatos (Ed.). Kluwer Dordrecht 69--72.  D. M. Greenberger M. A. Horne and A. Zeilinger. 1989. Going beyond Bell\u2019s theorem. In Bell\u2019s Theorem Quantum Theory and Conceptions of the Universe M. Kafatos (Ed.). Kluwer Dordrecht 69--72.","DOI":"10.1007\/978-94-017-0849-4_10"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214429"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132518"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2006.5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_11"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 21st USENIX Security Symposium.","author":"Heninger Nadia"},{"key":"e_1_2_1_32_1","unstructured":"Vojkan Jaksic Yoshiko Ogata Yan Pautrat and Claude-Alain Pillet. 2010. Entropic fluctuations in quantum statistical mechanics. An introduction. Quantum Theory from Small to Large Scales: Lecture Notes of the Les Houches Summer School 95.  Vojkan Jaksic Yoshiko Ogata Yan Pautrat and Claude-Alain Pillet. 2010. Entropic fluctuations in quantum statistical mechanics. An introduction. Quantum Theory from Small to Large Scales: Lecture Notes of the Les Houches Summer School 95."},{"key":"e_1_2_1_33_1","unstructured":"Arjen K. Lenstra James P. Hughes Maxime Augier Joppe W. Bos Thorsten Kleinjung and Christophe Wachter. 2012. Ron was wrong Whit is right. IACR Cryptology ePrint Archive 64. http:\/\/eprint.iacr.org\/2012\/064  Arjen K. Lenstra James P. Hughes Maxime Augier Joppe W. Bos Thorsten Kleinjung and Christophe Wachter. 2012. Ron was wrong Whit is right. IACR Cryptology ePrint Archive 64. http:\/\/eprint.iacr.org\/2012\/064"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Hoi-Kwong Lo and H. F. Chau. 1999. Unconditional security of quantum key distribution over arbitrarily long distances. Science 283 5410 2050--2056. DOI:http:\/\/dx.doi.org\/10.1126\/science.283.5410.2050  Hoi-Kwong Lo and H. F. Chau. 1999. Unconditional security of quantum key distribution over arbitrarily long distances. Science 283 5410 2050--2056. DOI:http:\/\/dx.doi.org\/10.1126\/science.283.5410.2050","DOI":"10.1126\/science.283.5410.2050"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1244"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382781"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 39th FOCS. 503--509","author":"Mayers D."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54429-3_7"},{"key":"e_1_2_1_39_1","volume-title":"8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC\u201913)","volume":"22","author":"Carl","year":"2013"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4838856"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.80.1083"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature08400"},{"key":"e_1_2_1_43_1","unstructured":"Nicole Perlroth Jeff Larson and Scott Shane. 2013. N.S.A. Able to Foil Basic Safeguards of Privacy on Web. The New York Times September 5.  Nicole Perlroth Jeff Larson and Scott Shane. 2013. N.S.A. Able to Foil Basic Safeguards of Privacy on Web. The New York Times September 5."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"S. Pironio A. Ac\u00edn S. Massar A. Boyer de la Giroday D. N. Matsukevich P. Maunz S. Olmschenk D. Hayes L. Luo T. A. Manning and C. Monroe. 2010. Random numbers certified by Bell\u2019s theorem. Nature 464 1021--1024.  S. Pironio A. Ac\u00edn S. Massar A. Boyer de la Giroday D. N. Matsukevich P. Maunz S. Olmschenk D. Hayes L. Luo T. A. Manning and C. Monroe. 2010. Random numbers certified by Bell\u2019s theorem. Nature 464 1021--1024.","DOI":"10.1038\/nature09008"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.012336"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1874-5849(03)80041-4"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature12035"},{"key":"e_1_2_1_49_1","volume-title":"When good randomness goes bad: Virtual machine reset vulnerabilities and hedging deployed cryptography","author":"Ristenpart Thomas","year":"2016"},{"key":"e_1_2_1_50_1","unstructured":"Jean-Marc Robert. 1985. D\u00e9tection et Correction D\u2019erreurs en Cryptographie. Master\u2019s thesis. Universit\u00e9 de Montr\u00e9al Montr\u00e9al Quebec.  Jean-Marc Robert. 1985. D\u00e9tection et Correction D\u2019erreurs en Cryptographie. Master\u2019s thesis. Universit\u00e9 de Montr\u00e9al Montr\u00e9al Quebec."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.441"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Smith Adam","year":"2007"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2032797"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054130"},{"key":"e_1_2_1_55_1","unstructured":"Marco Tomamichel and Anthony Leverrier. 2015. A Rigorous and Complete Proof of Finite Key Security of Quantum Key Distribution. http:\/\/lanl.arxiv.org\/abs\/1506.08458 arXiv:1506.08458.  Marco Tomamichel and Anthony Leverrier. 2015. A Rigorous and Complete Proof of Finite Key Security of Quantum Key Distribution. http:\/\/lanl.arxiv.org\/abs\/1506.08458 arXiv:1506.08458."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.140501"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213984"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/2\/025009"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.64.032112"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-014-2122-x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2885493","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2885493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:14Z","timestamp":1750273514000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2885493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,26]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,8]]}},"alternative-id":["10.1145\/2885493"],"URL":"https:\/\/doi.org\/10.1145\/2885493","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,26]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}