文献

J-GLOBAL ID：202102239349865313   整理番号：21A0444898

一方向関数とKolmogorov計算量について【JST・京大機械翻訳】

On One-way Functions and Kolmogorov Complexity

著者 (2件)： Liu Yanyi (Cornell University) ,  Pass Rafael (Cornell Tech)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： FOCS  ページ： 1243-1254  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 著者らは,計算の理論における2つの基本的問題の等価性を証明した。あらゆる多項式t(n)≧(1+ε)_n,ε>0に対して,次のものは等価である:One-way関数が存在する(次に,安全な秘密鍵暗号方式,ディジタル署名,疑似ランダム発生器,疑似ランダム関数,コミットメント方式,およびより多くの)。t-time有界Kolmogorov complexity,Ktは,穏やかなハードオン平均(すなわち,多項式p(n)>0が存在し,PPTアルゴリズムは,nビットストリングの1-1/p(n)画分以上)で,Ktを計算することができる。そうすることで,著者らは,クリプトグラフィにおける中心秘密鍵プリミティブとプロトコルの実現可能性を特徴付ける最初の自然でよく研究された計算問題を提示する。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *多項式 ,  計算理論 ,  等価性 ,  ディジタル署名 ,  暗号鍵 ,  秘密鍵暗号
準シソーラス用語： コミットメント ,  *一方向関数 ,  有界 ,  擬似ランダム , 【Automatic Indexing@JST】

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  パターン認識  (JE07000S)

タイトルに関連する用語 (2件)： 関数 ,  Kolmogorov計算量