文献

J-GLOBAL ID：202002214779395778   整理番号：20A1862431

エントロピー平坦化のためのタイトな下界【JST・京大機械翻訳】

A tight lower bound for entropy flattening

著者 (4件)： Chen Yi-Hsiu (Harvard University) ,  Goos Mika (Harvard University) ,  Vadhan Salil P. (Harvard University) ,  Zhang Jiapeng (University of California San Diego)
資料名： ACM Proceedings  (ACM Proceedings)
号： CCC ’18  ページ： 1-28  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： nビットソースX(すなわち,Xは均一ランダム入力におけるC_Xの出力である)を陰的に記述する回路C_Xを与えられたエントロピー平坦化を研究し,(1)ソースYがほぼ平坦(そのサポートに均一)であるようなソースYを記述する他の回路C_Yを構築し,(2)YのShannonエントロピーはXのものと単調に関係した。標準解はC_Yが独立入力でC_XaltogetherΘ(n2)時間を評価し,結果(漸近等分割特性から補正)を連結する。本論文では,これはブラックボックス構成の中で最適であり,オラクルとしてC_Xを繰り返し質問するエントロピー平坦化のためのAny回路C_Yは,ω(n2)クエリを必要とすることを示した。エントロピー平坦化は,1方向関数[12,22,13,6,11,10,7,24]からの擬似ランダム発生器と他の暗号プリミティブの構築に使用される成分である。また,統計的ゼロ知識[19,23,4,25]に対する問題の完全な低減にも使用した。Θ(n2)クエリ複雑性は,しばしば主要な効率ボトルネックである。著者らの下限は,VadhanとZheng(STOC 2012)による任意の一方向関数からの擬似ランダム発電機の現行最良構築が最適効率を持つことを証明するためのステップとして見ることができる。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *エントロピー ,  ブラックボックス ,  暗号
準シソーラス用語： *下界 ,  一方向関数 ,  オラクル ,  複雑性 ,  クエリー ,  擬似ランダム , 【Automatic Indexing@JST】

著者キーワード (2件)： エントロピー ,  一方向機能

分類 (3件)： 演算方式  (JC02020Z) ,  その他の無機化合物の薄膜  (BK14060A) ,  符号理論  (ND02030R)

タイトルに関連する用語 (3件)： エントロピー ,  平坦化 ,  下界