「一方向性関数」の版間の差分
削除された内容 追加された内容
Negi to kamo (会話 | 投稿記録) 見出しと本文の表記が一致していないため，非一様一方向性関数に統一した． |
|||
52行目:
==非一様一方向性関数==
関数 ''f'': Σ<sup>*</sup> → Σ<sup>*</sup> が以下を満たす時、関数 ''f'' は'''
# ''f'' は[[多項式時間]]で計算可能。
# 任意の多項式時間サイズの回路族 ''A'' = {''A''<sub>''k''</sub>} に対し、ある[[無視可能函数]] ν が存在して、Pr[''x'' ← ''A''<sub>''k''</sub>(''y'') | ''x'' ←<sub>''R''</sub> Σ<sup>''k''</sup>, ''y'' ← ''f''(''x'')] < ν(''l'')。
多項式時間アルゴリズムは多項式時間サイズの回路族で表す事ができるので、
==一方向性関数の候補==
| |||