一方向性関数族
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/17 00:27 UTC 版)
I を Σ* の部分集合とし、 D = {Dn}n ∈ I、R ={Rn}n ∈ I を Σ* の 部分集合の族とする。G1、G2 を多項式時間アルゴリズムとし、F = {fk: Dk → Rk} を関数の族とする。組 (D, R, G1, G2, F) が以下を満たすとき、(D, R, G1, G2, F) を一方向性関数族という： G1 は 1k を入力すると n ∈ I∩Σk を出力するアルゴリズム。 G2 は n ∈ I を入力すると x ∈ Dn を出力するアルゴリズム。 ある多項式時間アルゴリズム C があって C(x, n) = fn(x)。 任意の多項式時間アルゴリズム A に対し、ある negligible な関数 ν とある k0 ∈ N {\displaystyle {\mathbb {N} }} が存在して、全ての k > k0 に対し、Pr[x ← A(n, y) | n ← G1(1k), x ← G2(n), y ← f(x)] < ν(l)。 一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。
※この「一方向性関数族」の解説は、「一方向性関数」の解説の一部です。
「一方向性関数族」を含む「一方向性関数」の記事については、「一方向性関数」の概要を参照ください。
ウィキペディア小見出し辞書の「一方向性関数族」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 一方向性関数族のページへのリンク
