千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2020年8月実施 専門 B10

标签：

• 单向函数与归约

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

一方向性関数 $f$ に対し、$|f(x)|\le p(|x|)$ を満たす多項式 $p$ をとり、

$$g(x)=f(x)\Vert1\Vert0^{p(|x|)-|f(x)|}$$

と定める。$\Vert$ はビット列の連結を表す。(1) $|x|=|x'|$ なら $|g(x)|=|g(x')|$ であること、(2) $g$ も一方向性関数であることを示せ。

题目描述

设 $f$ 为单向函数，输出长度满足 $|f(x)|\le p(|x|)$。定义 $g(x)=f(x)\Vert1\Vert0^{p(|x|)-|f(x)|}$。(1) 证明等长输入必有等长输出；(2) 证明 $g$ 仍是单向函数。

Kai

(1) 入力長を $n$ とすると

$$|g(x)|=|f(x)|+1+p(n)-|f(x)|=p(n)+1.$$

従って $g$ は Length-Regular である。

(2) $f$ の計算と多項式長のパディングで $g$ は多項式時間計算可能である。$g$ を非無視確率で反転する確率的多項式時間算法 $A$ があると仮定する。入力長 $n$ と $y=f(x)$ を受け取ったとき、

$$z=y\Vert1\Vert0^{p(n)-|y|}$$

を作り $A$ に渡す。$A$ が $g(x')=z$ を満たす $x'$ を返せば、$g(x')$ の右端の $1$ はパディングの区切りだから、その左側は必ず $f(x')=y$ である。従ってこの算法は同じ成功確率で $f$ を反転し、一方向性に矛盾する。よって $g$ も一方向性関数である。