文献

J-GLOBAL ID：201902280189681659   整理番号：19A0914735

有限入力シーケンスによるEliasおよびPeresの抽出器の数値的および非漸近的解析【JST・京大機械翻訳】

Numerical and Non-Asymptotic Analysis of Elias’s and Peres’s Extractors with Finite Input Sequences

著者 (3件)： Prasitsupparote Amonrat (Graduate School of Environment and Information Sciences, Yokohama National University, Yokohama 240-8501, Japan) ,  Konno Norio (Department of Applied Mathematics, Faculty of Engineering, Yokohama National University, Yokohama 240-8501, Japan) ,  Shikata Junji (Graduate School of Environment and Information Sciences, Yokohama National University, Yokohama 240-8501, Japan)
資料名： Entropy (Web)  (Entropy (Web))
巻： 20  号： 10  ページ： 729  発行年： 2018年 
JST資料番号： U7179A  ISSN： 1099-4300  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： スイス (CHE)  言語： 英語 (EN)

抄録/ポイント： 多くの暗号システムは乱数を必要とし,弱い乱数の使用は安全なシステムに導く。現代の世界において,ランダム数を生成するためのいくつかの技術があり,その中で,最も基本的で重要な方法は,von Neumann,Elias,およびPeesによって提案された決定論的抽出器である。Eliass抽出器は,ブロックサイズが無限になると最適速度(すなわち,情報理論的上限)h(p)を達成する。ここで,h()は二値エントロピー関数であり,pは入力系列の各ビットが生じる確率である。入力の長さと反復数が無限になると,ピーク抽出器は最適レートh(p)を達成する。両方の抽出器に関する以前の研究は,有限入力シーケンスによる実行時間とメモリサイズを含む実用的な側面を参照しなかった。本論文では,いくつかの発見的方法に基づいて,著者らは,Peress抽出器の最大冗長性に関する下限を引き出して,著者らが時間複雑性または空間複雑性に注意を払わないならば,Eliass抽出器が最大冗長性(または速度)の観点から,Peress抽出器より良いことを示した。さらに,同じ環境下で任意のバイアス確率を持つ有限入力系列を持つ両方の抽出器の数値的および非漸近的解析を行った。そこで,一般的なPCと簡単な環境に両方の抽出器を実装した。著者らの経験的結果は,非常に類似した実行時間の下で与えられた有限入力シーケンスに対して,Peress抽出器がEliass抽出器よりはるかに優れていることを示した。結果として,Peress抽出器は暗号システムのような応用において,実際に一様にランダムなシーケンスを生成するのにより適している。Copyright 2019 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 冗長性 ,  *抽出装置 ,  乱数 ,  安全性 ,  バイアス ,  情報理論 ,  暗号 ,  発見的方法 ,  記憶装置
準シソーラス用語： 複雑性 ,  実行時間 ,  ブロックサイズ ,  決定論 , 【Automatic Indexing@JST】

著者キーワード (4件)： - ,  - ,  - ,  -

分類 (2件)： 量子力学一般  (BA06010C) ,  量子光学一般  (BD04010X)

引用文献 (22件)：

• Heninger, N.; Durumeric, Z.; Wustrow, E.; Halderman, J.A. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. In Proceedings of the 21st USENIX Security Symposium, Bellevue, WA, USA, 8-10 August 2012.
• Lenstra, A.K.; Hughes, J.P.; Augier, M.; Bos, J.W.; Kleinjung, T.; Wachter, C. Public Keys. In Advances in Cryptology-ECRYPTO 2012; Safavi-Naini, R., Canetti, R., Eds.; Number 7417 in Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2012; pp. 626-642.
• Bendel, M. Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access. Available online: Exophase.com (accessed on 20 September 2018).
• Dorrendorf, L.; Gutterman, Z.; Pinkas, B. Cryptanalysis of the Random Number Generator of the Windows Operating System. ACM Trans. Inf. Syst. Secur. 2009, 13, 10.
• Bonneau, J.; Clark, J.; Goldfeder, S. On Bitcoin as a public randomness source. IACR Cryptol. ePrint Arch. 2015, 2015, 1015.

タイトルに関連する用語 (4件)： シーケンス ,  抽出器 ,  数値 ,  解析