http://phys.org/news/2016-06-algorithm-random.html
By Lisa Zyga
June 24, 2016
(Phys.org) — 產生一個隨機數數列也許比字面上更加困難。雖然數字看起來也許隨機，但你如何確定，它們並沒有遵循某些複雜、潛在的模式？為此，尋找一種方法來證明某個數列是真正的隨機，通常比前面提到的產生隨機數數列更具挑戰性。
在一項新研究中，研究者開發出一種新的演算法，那增加一系列試驗性產生的、看似隨機的數字，通過隨機性驗證的數量。位於波蘭、瑞典與巴西的研究者 Piotr Mironowicz 等人，已將他們的論文發表在最近一期的 New Journal of Physics 期刊上。
如同科學家們的解釋，產生一長串通過驗證的隨機數，對於保障電腦、手機與其他電子裝置的安全至關緊要。
"每種電子裝置都需要隨機性，而且需要很多隨機性，" 波蘭 Gdańsk 大學的共同作者 Marcin Pawłowski 表示。"每當你需要安全性時，隨機性就成了必要。每當你想要安全的通訊，就必須產生一個密碼學金鑰。它必須隨機地產生，讓敵手無法輕易猜中。現今每種通訊都是以這種方式加密。每當你用手機打電話、傳簡訊給某人，都必須要產生一串隨機數。如果某人能夠預知這些數字（那不需要完美預測 -- 某人只要能猜中某些數字即已足夠），他們就能夠聆聽你的交談。"
"隨機數不斷地被每一個能夠進行通訊的機器產生。即使沒有通訊產生，每部電腦也都需要隨機性來分配程式在記憶體中的位置。若每次程式被執行，都分配在記憶體中相同的地方時，要駭一部電腦就顯得稀鬆平常。利用隨機數產生器中的後門或惡意功能，是攻擊通訊或電腦系統最常見的方法之一。"
許多數字，沒有模式
雖然要產生並驗證短短的一串隨機數顯得相對容易，不過在密碼學應用中，需要更長的隨機數，而長度正是使這項工作更具挑戰性的原因。
一般來說，研究者使用二種主要方法來產生長隨機數數列。第一種方法是基於物理系統中所固有的隨機性，例如雷射中的光學雜訊與原子中的放射性衰變。這種隨機性可追溯到這些系統的量子特性。第二種方法是使用電腦軟體，那能夠完成複雜的算術程序。技術上來說，只有第一種方法能夠產生真正的隨機數。電腦所產生的隨機數被認為是「偽隨機（pseudorandom）」，因為知道程式開發者如何計算，使得預測這些數字成為可能，那只是看起來隨機。
在這項新研究中，研究者使用第一種方法，透過測量某些物理系統的量子態。然而，這種物理學方法有其自己的問題：你如何能夠確信用來測量此物理系統的測量裝置，不會因為其建構方法，而有某些潛在的可預測性？為了克服此問題，科學家們對於這些裝置發展出嚴格的需求，不過這些「裝置相依（device-independent）」的協定如此嚴格，以至於在產生大量隨機數時非常緩慢。
成為安全性與效率之間的一種妥協，研究者發展出「半裝置相依（semi-device-independent）」協定，那沒有如此嚴格的要求，不過卻會對裝置的容量設限。這些協定能夠產生真正的隨機數字，不過它們仍需要大量的後處理運算能力來證明數列是隨機的。
以更多運算力達到更多隨機性
在這篇新論文中，研究者的主要貢獻是證明半裝置協定存有一種權衡（tradeoff）。當用以分析實驗資料以及驗證其隨機性的運算力愈多，對於產生隨機資料之測量裝置的要求，就可以不需要這麼嚴格。
基於這種權衡，研究者設計了一種新的演算法，那可以從實驗中提取更多資料，接著，使用大量的運算力，就能夠驗證大量的隨機數 -- 比至今所開發出來的任何其他方法都來得多。更重要的是，它能夠更快速的完成，即使那些使用較慢方法無法完成的案子都能夠完成。
"我們的方法讓我們能夠比標準方法驗證更多隨機性，" Pawłowski 說。"讓我們假設，你使用後者（標準方法）並達到 1 bit/second，而使用我們的你可達到 2 bits/second。這表示，以相同的方式來驗證，利用我們的方法你只需要一半的時間就能夠產生需要的位元數量。這很不錯。"
"不過這裡有當我們的方法達到 1 bit/sec 時，標準方法仍為 0 的例子。現在，我們的方法變得真的很重要，因為沒有了它，我們就有了一套完全沒用的裝置。我認為這是最大的優勢：使無用的裝置變得有用。"
這種新方法也有這個優勢：它不像其他方法那樣需要改變物理量子系統，然而其成本來自於需要更龐大的運算能力。無論如何，研究者相信這是一種值得的權衡，而且預期這種新方法將會引領未來的隨機數驗證研究。
"我們在一個例子中證明我們方法的有用，但我們有初步的結果與手工編織的參數（hand-weaving arguments），那指出我們的方法應用到不同的實驗設置與情境中（例如，完全裝置相依，或某一部份獲得完全信任），" Pawłowski。"我們現在試圖證明這個，並看看在那種情況下它最有用。我們的第二個目標是試圖減少驗證更多隨機性所需要的運算時間，我們在此也有一些初步結果，指出那能夠辦到。"
※ 相關報導：
＊ Increased certification of semi-device independent random numbers using many inputs and more post-processing
http://iopscience.iop.org/article/10.1088/1367-2630/18/6/065004
Piotr Mironowicz, Armin Tavakoli, Alley Hameedi,＊ 產生隨機數的新方法能改善網路安全
Breno Marques, Marcin Pawłowski and Mohamed Bourennane
New Journal of Physics.
doi: 10.1088/1367-2630/18/6/065004
沒有留言:
張貼留言