儀器獨立隨機放大協定的負面結果

Lower Bounds for Device Independent Randomness Amplification

王教勛(Chiao-Hsun Wang)

指導教授 ： 管希聖

共同指導教授 ： 鐘楷閔(Kai-Min Chung)

國立臺灣大學/理學院/物理學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201703006

摘要

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.

並列關鍵字

Randomness Amplification ； Non-signaling ； Quantum Cryptography

參考文獻

[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.

[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.

[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.