利用者:Roget/試訳/ハードコア述語

In cryptography, a hard-core predicate of a one-way function f is a predicate b (i.e., a function whose output is a single bit) which is easy to compute given x but is hard to compute given f(x). In formal terms, there is no probabilistic polynomial time algorithm that computes b(x) from f(x) with probability significantly greater than one half over random choice of x.

暗号学において、一方向性関数fに関するハードコア述語とは、xからは簡単に計算出来るがf(x)から計算するのは難しい述語bのことである。 より正確には、xをランダムに選んだときf(x)からb(x)を1/2以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、bをfのハードコア述語と呼ぶ。

A hard-core function can be defined similarly.

ハードコア関数も同様にして定義される。（微妙に違う。弱いハードコア関数と強いハードコア関数がある。）

A hard-core predicate captures "in a concentrated sense" the hardness of inverting f. ハードコア述語は、関数fを逆算するときに「一番難しいところ」を捉えた概念である。

While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage c from the image f(x). For instance, while RSA is conjectured to be a one-way function, the Jacobi symbol of the preimage can be easily computed from that of the image.

一方向性関数は逆算するのが難しい。しかし像f(x)から原像xの部分的な情報cを得ることについては何も言及していない。例えば、RSA関数は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。

It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate. Let f be a one-way function. Define

g(x, r) = (f(x), r),

where the length of r is the same as that of x. Let $x_{j}$ denote the j^th bit of x and $r_{j}$ the j^th bit of r. Then

$b(x,r)=\bigoplus _{j}x_{j}r_{j}$

is a hard core predicate of g. Note that $b(x,r)=<x,r>$ where $<\cdot ,\cdot >$ denotes the standard inner product on the vector space $(\mathbb {Z} /2\mathbb {Z} )^{n}$. This predicate is hard-core due to compuational issues; that is, it is not hard to compute because g(x, r) is information theoretically lossy. Rather, if an algorithm exists to compute this predicate efficiently, then an algorithm exists to invert f efficiently. A similar construction yields a hard-core function with log (|x|) output bits.

一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。GoldreichとLevinは1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。 今、fを一方向性関数だとする。関数gを

g(x,r)=(f(x),r)

と定義する。ただし、rの長さはxの長さと同じであるとする。$x_{j}$をxのjビットとし、$r_{j}$をrのjビットとする。 このとき、

$b(x,r)=\bigoplus _{j}x_{j}r_{j}$

はgのハードコア述語になっている。$b(x,r)=<x,r>$であることに注意されたい（$<\cdot ,\cdot >$はベクトル空間$(\mathbb {Z} /2\mathbb {Z} )^{n}$上の標準的な内積である）。 このハードコア性はあくまで計算量的なものである。g(x, r)は情報理論的にロス関数なのでハードコア関数は原理的には計算可能である??? (注:ここはGoldreichのFoCから抜き書いたようだ. 舌足らず.) f(x)からg(x,r)を1/2以上に無視できない確率で計算できるアルゴリズムが存在するならば、xそのものを効率よく求めることができる。同様の構成により、log(|x|)ビットの出力を持つハードコア関数を構成することができる。（具体的にはどうだったかな。g(x,r_1,...,r_l)=(f(x),r_1,...,r_l)?） （訳者注：なので狭義のアダマール符号（というか二進の一階リードマラー符号）のリスト復号可能性と関係している）

It is sometimes the case that an actual bit of the input x is hard-core. For example, the low-order bit is hard-core for RSA. It is in fact conjectured that the lower half of the bits are all hard-core for RSA; in other words, the latter-half bits constitute a hard-core function. Note that this is stronger than each of the latter bits being hard-core predicates individually, because $f(x)$ may reveal correlations between certain bits of $x$ without revealing anything about individual bits.

入力xの特定のビットがハードコア述語になる場合もある。たとえば、最下位ビットはRSA関数についてハードコアである。ビットの下位はすべてハードコアだと予想されている。言い換えれば、RSA関数について入力の下半分を返す関数はハードコアだと予想されている。（参考: Goldreich Ch. 2.7.3? "FoC I", J. Haastad, A. Schrift, and A. Shamir. The Discrete Logarithm Modulo a Composite Hides O(n) Bits. Journal of Computer and System Science, Vol. 47, pages 376-404, 1993.）これは下半分の各ビットがハードコア述語であるということよりは強い。なぜならばf(x)はxの各々のビットについての情報を漏らすことなく、特定のビット間の相関については情報を漏らしうるからである。 （訳注:Naslund and Hastad 2003で各ビットについて示されている。元々上位ビットはバイアスがかかるのでバイアスより有意に予想できるかどうかで議論されている。）

Hard-core predicates give a way to construct a pseudorandom generator from any one-way permutation. If b is a hard-core predicate of a one way function f, and s is a random seed, then

$\left\{b(f^{n}(s))\right\}_{n}$

is a pseudorandom bit sequence.

任意の一方向性置換から暗号学的疑似乱数を構成することがハードコア述語によって可能となる。もしbがfのハードコア述語ならば、sをランダムな種とし、

$\left\{b(f^{n}(s))\right\}_{n}$

が疑似乱数になる。

Hard-core predicates of trapdoor one-way permutations can be used to construct semantically secure public-key encryption schemes. 落とし戸付き一方向性置換のハードコア述語は、IND-CPA安全な公開鍵暗号方式を構成することにも使える。

References

• Oded Goldreich, Foundations of Cryptography vol 1: Basic Tools, Cambridge University Press, 2001.
• Oded Goldreich and Leonid A. Levin, A Hard-Core Predicate for all One-Way Functions, STOC 1989, pp25–32.