臺灣博碩士論文加值系統

Randomness amplification 協定的目的是要藉由weak source 產生接近完美的亂數位元。在這篇論文中，我們證明了使用兩個儀器的
randomness amplification 協定有一些不能達到的結果。具體的結果是，給定任意使用兩個儀器的Randomness amplification 協定，當協定要求輸入的weak source 之min-entropy 的大小在log n 的量級時，存在一種策略可以以最高機率通過協定每一輪的測試，並且當協定接受時，產生的亂數位元在給定每一輪的輸入值以及額外資訊時是固定的。

Randomness amplification is a protocol that outputs nearly uniform bits using inputs generated from weak source. In this work, we present some
negative results for two-device randomness amplification protocol with weak source. Specifically, given a two-device randomness amplification protocol with inputs generated from a weak source that has log n min-entropy, then there exists a strategy which has the highest probability of passing every round of the protocol, such that if the protocol accepts, then the output of the protocol is deterministic given inputs for all round and side information.

Acknowledgements iii
摘要 v
Abstract vii
1 Introduction 1
2 Preliminary 3
2.1 Min-entropy source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Non-local Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Model 7
3.1 Non-Signaling Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Non-signaling systems and Non-signaling states . . . . . . . . . 7
3.2 Model for Certifiable Extraction of Randomness . . . . . . . . . . . . . . 8
3.3 Two-device DI-RA protocols . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Lower Bounds 13
4.1 Optimal Strategy for Two-Device Protocols . . . . . . . . . . . . . . . . 14
4.2 Lower Bound for Two-Device Finite Round protocols . . . . . . . . . . . 22
4.3 Lower Bounds for Two-device Arbitrary Round Protocols . . . . . . . . 26
5 Conclusion 39
Bibliography 41

[AFRV16] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick. Non-Signaling Parallel Repetition Using de Finetti Reductions. IEEE Transactions on Information Theory, 62(3):1440–1457, 2016.
[CR12] Roger Colbeck and Renato Renner. Free randomness can be amplified. Nat Phys, 8(6):450–453, jun 2012.
[CSW14] K.-M. Chung, Y Shi, and X Wu. Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions. ArXiv e-prints, feb 2014.
[CSW16] Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu. General Randomness Amplification with Non-signaling Security. 2016.
[GMD+13] Rodrigo Gallego, Lluis Masanes, Gonzalo De La Torre, Chirag Dhara, Leandro Aolita, and Antonio Acín. Full randomness from arbitrarily deterministic events. Nature Communications, 4:1–15, 2013.
[SV86] Miklos Santha and Umesh V. Vazirani. Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences,33(1):75–87, 1986.
[Vad12] Salil P Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1–336, 2012.