研究者用SNS

雑記

Researchmapという研究者専用SNSというものに登録してみました．このブログをご覧になっている研究者の皆さんも登録してみてはいかがでしょうか．科研費の研究者番号があれば登録できますが，それ以外の方は招待が必要です．招待が必要な方はご一報下さい．メリットについてはNIIの新井紀子先生がResearchmapでのブログ記事で紹介されています．

ハードコア関数の誤解（その三）

研究

間が空いてしまいました．前回の続きです．

このGoldreich-Levinの構成方法に対して，一般化した視点を与えたのが以下の論文です．

  • T. Holenstein, U. Mauer, and J. Sjodin
    • "Complete Classification of Bilinear Hardcore Functions", CRYPTO 2005

この論文では双線型関数がハードコアになるための条件について考察を行っています．例えば，Goldreich-Levinのハードコア述語 h(x,r)=\langle x,r\rangleは単位行列Iを使って， h(x,r) = x^T I rという双線型関数の形で書くことができます．更にGoldreich-Levinのハードコア関数h(x,r)=(\langle x,r_1\rangle,...,\langle x,r_\ell\rangle)（ここでr_iはrのiビット目から始まるnビット部分列，\ell\in O(\log n)）は n\times(n+\ell-1)射影行列 M_i=(0,I,0)（ここで単位行列 Iはi列目からi+n-1列目までを成す．）を使って， h(x,r)=(x^T M_1 r,x^T M_2 r,...,x^T M_\ell rとやはり双線型関数の形で表すことができます．

より一般に， h(x,r)=(x^T M_1 r,...,x^T M_\ell r)と双線型関数を書き表した場合，行列M_1,...,M_\ellがどのような条件を満たすときにハードコアになるのかということについて彼らは考察を行っています．

平たく言うと \ellがlog程度で各 M_iのランクが全体的に高い，もう少し正確に言うと\ell\in O(\log n)かつ E(\text{rank}(M_i))=n-O(\log n)であれば，その双線型関数は一方向性関数f'(x,r)=(f(x),r)に対してハードコア関数である，というのが彼らの主結果です．

次回に続きます．

ハードコア関数の誤解（その二）

研究

前回のポストの続きです．

前回紹介したGoldreich-Levinのハードコア関数はハードコア述語，つまり出力長が1ビットでした．ハードコア述語はある意味で1ビット分の擬似乱数を与えることになっています．しかし，たくさんのハードコアビットを同時に得られる方が都合が良いことが多々あります．この場合，Goldreich-Levinのハードコア述語を応用して，より長い擬似乱数列を得ることが可能です．

一番単純な方法は， \ell個の独立な付加的乱数 r_1,r_2,...,r_\ell\in\{0,1\}^nと用意して， h(x,r_1,...,r_\ell)=(\langle x,r_1\rangle,...,\langle x,r_\ell\rangle)とするものです．この hは一方向性関数 f'(x,r_1,...,r_\ell)=(f(x),r_1,...,r_\ell)に対するハードコア関数であることが示せます．

この場合には \ellビット長のハードコア関数の出力を得るために，種値である nビット乱数 x以外に n\ellビットの乱数が必要となります．なお， \ellは O(\log n)まで取ること，つまり出力長は O(\log n)ビットまで伸ばすことが可能です．

できれば付加的に必要な乱数の量を減らした方が擬似乱数生成の観点からも嬉しいわけですが，GoldreichとLevinによって付加的乱数の量が少なくて済むハードコア関数のもっと賢い以下の構成方法が提案されています．

h(x,r)= (\langle x,r_1\rangle,...,\langle x,r_\ell\rangle)

ここで， rは n+\ell-1ビットで，各 r_i\in\{0,1\}^nは rのiビット目から連続した nビットです．証明はかなり複雑になりますが， \ell\in O(\log n)ならばハードコアであることが示せます．（証明はGoldreichの教科書に載っています．）

前の構成方法だと n\ellビットの乱数が必要だったところをこの構成方法だと n+\ell-1ビットまで減らすことができます．

次回に続きます．

ハードコア関数の誤解（その一）

研究

ハードコア関数について今まで思い違いをしていた点があったので，備忘録として書いておこうと思います．前提から書き始めると長くなってしまったので何回かに分けてポストします．

ハードコア関数というのは暗号理論や計算量理論でしばしば現れる基本的な概念なのですが，基本的には一方向性関数などの持つ計算複雑さを擬似乱数に変換するための道具として用いられます．

簡単に説明すると，ハードコア関数の出力と一方向性関数の出力を対にして出したときに，それが一様乱数と一方向性関数の出力の対と識別できないというものです．この性質から擬似乱数生成器の構成などに利用されます．

もう少し形式的に言うと，ある多項式時間計算可能な関数 h:\{0,1\}^*\rightarrow\{0,1\}^*が一方向性関数 f:\{0,1\}^*\rightarrow\{0,1\}^*に対するハードコア関数であるとは入力 xを nビット長から一様ランダムに取ったとき， (f(x),h(x))と (f(x),u) （ uは h(x)と同じ長さ上の一様乱数）が計算量理論的識別不可能である，つまり効率の良いアルゴリズムでは区別できない，ことを言います．

任意の一方向性関数に対するハードコア関数の構成方法として Goldreich-Levin の結果が有名です．

  • O. Goldreich and L. Levin,
    • "A Hardcore Predicate for All One-Way Functions," STOC '89.

所謂Goldreich-Levinの定理では，任意の一方向性関数 fに対して新たに f'という関数を f'(x,r)=(f(x),r)（ x,rは同じ長さ）と定義します．この関数も容易に一方向性関数であることが示せます．Goldreich-Levinの定理は任意の一方向性関数 fから定義された新たな一方向性関数 f'に対して，関数 h(x,r) = \langle x,r\rangleがハードコア述語（出力長が1ビットのハードコア関数）であることを主張しています．ここで， \langle x,r\rangle = \sum_i x_i\cdot r_iは x,rを0,1のベクトルとして見たときの内積です．

Goldreich-Levinの定理ではf'のような関数を経由するハードコア述語の一般的構成方法が与えられているわけですが，任意の一方向性関数 fに対するハードコア述語が構成できないのか？と疑問が出てくるかと思いますが，実は付加的な入力rが必要であることは実は証明できてしまうため，任意の一方向性関数 fに対するハードコア述語の直接的構成は存在しません．

次回に続きます．