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

研究

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

この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)に対してハードコア関数である，というのが彼らの主結果です．

次回に続きます．