無題
特に書くことはないのですが何となく.また気が向いたら更新します.
ハードコア関数の誤解(その三)
間が空いてしまいました.前回の続きです.
このGoldreich-Levinの構成方法に対して,一般化した視点を与えたのが以下の論文です.
- T. Holenstein, U. Mauer, and J. Sjodin
- "Complete Classification of Bilinear Hardcore Functions", CRYPTO 2005
この論文では双線型関数がハードコアになるための条件について考察を行っています.例えば,Goldreich-Levinのハードコア述語は単位行列を使って,という双線型関数の形で書くことができます.更にGoldreich-Levinのハードコア関数(ここではのビット目から始まるビット部分列,)は射影行列(ここで単位行列は列目から列目までを成す.)を使って,とやはり双線型関数の形で表すことができます.
より一般に,と双線型関数を書き表した場合,行列がどのような条件を満たすときにハードコアになるのかということについて彼らは考察を行っています.
平たく言うとがlog程度で各のランクが全体的に高い,もう少し正確に言うとかつであれば,その双線型関数は一方向性関数に対してハードコア関数である,というのが彼らの主結果です.
次回に続きます.
出張やら論文書きやら査読者探しやら
で全然解説記事が書けてません.ダメだこりゃ.
ハードコア関数の誤解(その二)
前回のポストの続きです.
前回紹介したGoldreich-Levinのハードコア関数はハードコア述語,つまり出力長が1ビットでした.ハードコア述語はある意味で1ビット分の擬似乱数を与えることになっています.しかし,たくさんのハードコアビットを同時に得られる方が都合が良いことが多々あります.この場合,Goldreich-Levinのハードコア述語を応用して,より長い擬似乱数列を得ることが可能です.
一番単純な方法は,個の独立な付加的乱数と用意して,とするものです.このは一方向性関数に対するハードコア関数であることが示せます.
この場合にはビット長のハードコア関数の出力を得るために,種値であるビット乱数以外にビットの乱数が必要となります.なお,はまで取ること,つまり出力長はビットまで伸ばすことが可能です.
できれば付加的に必要な乱数の量を減らした方が擬似乱数生成の観点からも嬉しいわけですが,GoldreichとLevinによって付加的乱数の量が少なくて済むハードコア関数のもっと賢い以下の構成方法が提案されています.
ここで,はビットで,各はのビット目から連続したビットです.証明はかなり複雑になりますが,ならばハードコアであることが示せます.(証明はGoldreichの教科書に載っています.)
前の構成方法だとビットの乱数が必要だったところをこの構成方法だとビットまで減らすことができます.
次回に続きます.
ハードコア関数の誤解(その一)
ハードコア関数について今まで思い違いをしていた点があったので,備忘録として書いておこうと思います.前提から書き始めると長くなってしまったので何回かに分けてポストします.
ハードコア関数というのは暗号理論や計算量理論でしばしば現れる基本的な概念なのですが,基本的には一方向性関数などの持つ計算複雑さを擬似乱数に変換するための道具として用いられます.
簡単に説明すると,ハードコア関数の出力と一方向性関数の出力を対にして出したときに,それが一様乱数と一方向性関数の出力の対と識別できないというものです.この性質から擬似乱数生成器の構成などに利用されます.
もう少し形式的に言うと,ある多項式時間計算可能な関数が一方向性関数に対するハードコア関数であるとは入力をビット長から一様ランダムに取ったとき,と (はと同じ長さ上の一様乱数)が計算量理論的識別不可能である,つまり効率の良いアルゴリズムでは区別できない,ことを言います.
任意の一方向性関数に対するハードコア関数の構成方法として Goldreich-Levin の結果が有名です.
- O. Goldreich and L. Levin,
- "A Hardcore Predicate for All One-Way Functions," STOC '89.
所謂Goldreich-Levinの定理では,任意の一方向性関数に対して新たにという関数を(は同じ長さ)と定義します.この関数も容易に一方向性関数であることが示せます.Goldreich-Levinの定理は任意の一方向性関数から定義された新たな一方向性関数に対して,関数がハードコア述語(出力長が1ビットのハードコア関数)であることを主張しています.ここで,はを0,1のベクトルとして見たときの内積です.
Goldreich-Levinの定理ではのような関数を経由するハードコア述語の一般的構成方法が与えられているわけですが,任意の一方向性関数に対するハードコア述語が構成できないのか?と疑問が出てくるかと思いますが,実は付加的な入力が必要であることは実は証明できてしまうため,任意の一方向性関数に対するハードコア述語の直接的構成は存在しません.
次回に続きます.