New method of producing random numbers could improve cybersecurity
http://phys.org/news/2016-05-method-random-cybersecurity.html
May 16, 2016
在一位密碼學專家口中所謂的「傑作」有了這樣的進展：德州大學 Austin 分校的電腦科學家開發出一種產生真正隨機數（random numbers，亂數）的新方法，這項突破可用來加密資料、使電子投票（e-voting）更安全、進行統計上顯著的民調以及更精確地模擬複雜系統，例如地球的氣候。
這種新方法以較其他方法更少的運算精力來創造真正的隨機數，那能使明顯更高層次的安全性，從客戶信用卡交易到軍事通信的每樣事物，更易達成。
電腦科學教授 David Zuckerman 以及畢業生 Eshan Chattopadhyay 將在六月於每年舉辦一次的 Symposium on Theory of Computing (STOC，ACM 最主要的理論性電腦科學研討會) 上報告他們的研究。受邀出席該研討會的簡報得經過同儕審核過程，以評估研究的正確性與重要性。他們的論文將是榮獲 STOC Best Paper Award 的三篇論文之一。
"這個問題我已不斷輾轉反思超過 20 年，" Zuckerman。"能解決這個問題，令我十分激動！" 去年在一個線上論壇上 Chattopadhyay 與 Zuckerman 公開釋出一份論文草稿，描述他們用來製造隨機數的方法。在一個慣於小型、持續性改善的領域中，電腦科學社群讚揚這種方法、提出建議、與其他更早被提出的方法進行比較，這猶如領先了一光年。
Oded Goldreich，一位以色列 Weizmann 科學研究所的電腦科學教授，如此評論：如果它僅是一個比現有方法更加適度的改進，那麼它只會被評斷為 "一夜狂歡。"
"當我聽到這件事，我幾乎難以闔眼，" Yael Kalai 表示，在 Microsoft Research New England 負責密碼學研究的資深研究者，其亦在研究隨機萃取（randomness extraction，隨機提取）。"我相當興奮。我不感相信。我跑到（線上）歸檔中查看論文。那真的是一篇傑作。"
這種新方法採用二種弱隨機數列（weakly random sequences of numbers）然後將它們轉變成一個真正隨機的數列。弱隨機數列，例如溫度與隨時間取樣的股市價格，藏有可預測的模式（patterns）。真正隨機的數列，沒有什麼可以預測的，例如硬幣拋擲。
這項新研究似乎藐視了電腦程式設計中的古老格言："垃圾進，垃圾出（Garbage in, garbage out）。" 事實上，它是 Zuckerman 在 1990 年代作為先鋒，所提出某一類型方法的最新加強版，稱為：隨機萃取器（randomness extractors）
先前的隨機萃取器版本較不實用，因為它們不是要求二個來源數列的其中之一必須是真正地隨機（那呈現出雞生蛋、蛋生雞的問題），就是要二個來源數列都要接近真正的隨機。這個新方法閃過了這些限制，並且只要用二個弱隨機數列就能辦到。
隨機數的一項重要應用是產生用來加密資料的金鑰，那難以讓駭客破解。資料加密在眾多實際應用中，對於安全的信用卡購物與銀行交易、保護個人醫療資料隱私以及防護軍事通訊不被敵軍竊聽至關緊要。
Zuckerman 表示，隨然已有方法能產生高品質的隨機數，不過它們在運算上非常要求。他的方法能以更省力的方式製造出更高品質的隨機。
"加密常被誤用的常見方式之一是不使用高品質的隨機，" Zuckerman 說。"如果能使得高品質的隨機更容易獲得，在那種情況下，我們的方法能改善安全性。"
他們的論文證明如何能產生只有一個真正的隨機數 -- 相似於拋擲一個硬幣 -- 不過 Zuckerman 以前的學生 Xin Li 已經證明如何將之擴展以創造出包更多隨機數的數列。
Zuckerman 與 Chattopadhyay 在去年夏天張貼其論文草稿的網站稱為 Electronic Colloquium on Computational Complexity，允許研究者共享他們的研究，並在期刊或研討會發表最終版本前收到回饋。電腦科學家與數學家會仔細審核文章，提供建議，甚至擴展方法，使它們更強大。
※ 相關報導：
＊ Explicit Two-Source Extractors and Resilient Functions
http://eccc.hpi-web.de/report/2015/119/
＊ 宇宙是個「虛擬實境」？
＊ 質數的新模式與Riemann zeta zeros
＊ 張益唐破解孿生素數猜想一夜成名
＊ 運算「機率」的電腦晶片
＊ 搖動愛因斯坦的骰子：開發量子亂數產生器
＊ 隨機雜訊可使訊號更清晰
沒有留言:
張貼留言