Trading isolation for certifiable randomness expansion
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/84872 |
| _version_ | 1811083254857465856 |
|---|---|
| author | Coudron, Matthew Ryan |
| author2 | Peter Shor. |
| author_facet | Peter Shor. Coudron, Matthew Ryan |
| author_sort | Coudron, Matthew Ryan |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T12:29:45Z |
| format | Thesis |
| id | mit-1721.1/84872 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:29:45Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/848722019-04-11T07:33:48Z Trading isolation for certifiable randomness expansion Coudron, Matthew Ryan Peter Shor. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (page 41). A source of random bits is an important resource in modern cryptography, algorithms and statistics. Can one ever be sure that a "random" source is truly random, or in the case of cryptography, secure against potential adversaries or eavesdroppers? Recently the study of non-local properties of entanglement has produced an interesting new perspective on this question, which we will refer to broadly as Certifiable Randomness Expansion (CRE). CRE refers generally to a process by which a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two or more black-box devices do not communicate (i.e. are non-signaling). In this work we make progress on a conjecture of [Col09] which proposes a method for indefinite certifiable randomness expansion using a growing number of devices (we actually prove a slight modification of the original conjecture in which we use the CHSH game as a subroutine rather than the GHZ game as originally proposed). The proof requires a technique not used before in the study of randomness expansion, and inspired by the tools developed in [RUV12]. The result also establishes the existence of a protocol for constant factor CRE using a finite number of devices (here the constant factor can be much greater than 1). While much better expansion rates (polynomial, and even exponential) have been achieved with only two devices, our analysis requires techniques not used before in the study of randomness expansion, and represents progress towards a protocol which is provably secure against a quantum eavesdropper who knows the input to the protocol. by Matthew Ryan Coudron. S.M. 2014-02-10T16:56:57Z 2014-02-10T16:56:57Z 2013 Thesis http://hdl.handle.net/1721.1/84872 868332842 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 41 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Coudron, Matthew Ryan Trading isolation for certifiable randomness expansion |
| title | Trading isolation for certifiable randomness expansion |
| title_full | Trading isolation for certifiable randomness expansion |
| title_fullStr | Trading isolation for certifiable randomness expansion |
| title_full_unstemmed | Trading isolation for certifiable randomness expansion |
| title_short | Trading isolation for certifiable randomness expansion |
| title_sort | trading isolation for certifiable randomness expansion |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/84872 |
| work_keys_str_mv | AT coudronmatthewryan tradingisolationforcertifiablerandomnessexpansion |