August 10, 1986Open Access

ランダム関数の構築方法

Key Points

Key points are not available for this paper at this time.

Abstract

計算複雑性に基づく関数のための構成的確率理論が展開され、疑似ランダム関数生成器が提示される。この生成器は、任意の一方向関数 g とランダムな k ビット文字列 r のペア (g, r) を多項式時間で計算可能な関数 ƒ_r: 1, …, 2^k → 1, …, 2^k へと変換する決定的多項式時間アルゴリズムである。これらの ƒ_r は、任意の確率的多項式時間アルゴリズムによって、その選択した引数の関数値を問うことでランダム関数と区別できない。結果は暗号理論、ランダム構成、および複雑性理論に応用される。

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Authors

Oded Goldreich

Shafi Goldwasser

Silvio Micali

Journals

Journal of the ACM

Actions

Institutions

Massachusetts Institute of Technology

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Cite this study

Goldreich ら（Sun,）はこの問題を研究した。

www.synapsesocial.com/papers/69001fedbc792ed11ff3023d — DOI: https://doi.org/10.1145/6490.6503

Also consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

RSA bits are .732 + ε secure· 1984 · 14 citations
On the Length of Programs for Computing Finite Binary Sequences· 1966 · 910 citations
Randomness and the density of hard problems· 1983 · 42 citations
On the cryptographic security of single RSA bits· 1983 · 39 citations
A fair protocol for signing contracts· 1990 · 288 citations

ランダム関数の構築方法

Key Points

Abstract

Citation Network

Connected Papers

Discussion

Authors

Journals

Actions

Institutions

References and Citations

Citation Network

Connected Papers

Discussion

Cite this study

Also consider