最近読んだもの - 186 @ hatenablog

T. Holenstein, U. Maurer, J. Sjödin "Complete Classificaiton of Bilinear Hard-Core Functions" (CRYPTO 2004)

$h:\mathbb{F}_q^n \times \mathbb{F}_q^k \to \mathbb{F}_q^m$ が双線形であるとする. 任意の一方向性関数 $f:\mathbb{F}_q^n \to \mathbb{F}_q^n$ から一方向性関数 $f':\mathbb{F}_q^n \times \mathbb{F}_q^k \to \mathbb{F}_q^n \times \mathbb{F}_q^k$ を $f'(x,y)=(f(x),y)$ として構成する. $h$ が $f'$ のhard-core functionになるのはどういうときか? というのを調べた論文.
hがhard-coreであることを示す場合, hを予想するオラクルPが与えられる. Pを使いながらf(x)からxを求めていく.
すでにGoldreich-Levinから $h':\mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q$ で, $h'(x,r)=\langle x,r\rangle$ を予想するオラクルP'が存在するときには, f(x)からxを求められる. ということで, オラクルPからオラクルP'への変換器を作れば良い. オラクルP'にクエリ $r \in \mathbb{F}_q^n$ を投げるときには, オラクルPへクエリ $y \in \mathbb{F}_q^k$ を投げると.
実際, hが双線形なので, この変換器は上手く作れる. ただhが上手い構造を持っていないと多項式時間で変換出来無さそうではある. 条件としては, $h(x,y)=xMy^T$ と書いたときのM(k×n行列)のランクがそこそこ高いことが求められる.
mが大きいときや, hを行列で表したときのランクが小さい場合はどうなるか? very strong one-way permutationが存在するならば, hがhard-core functionにならないような一方向性関数が存在することが示せるらしい. この部分の証明が今一分からないので, また後で読む.

G. Hast "Nearly One-Sided Tests and the Goldreich-Levin Predicate" (Journal of Cryptology, vol. 17, 2004)

エラーだけではなく消失ありの場合のHadamard符号のリスト復号法を示している. 一応フーリエ変換を使って計算を高速化しているような気がするのでGoldreich-Levinの自明で無い改良になっていると思われる.
nearly one-seided statistical testについてはよく分からない.

L. Xixiang, Y. Bo, C. Pei "Efficient Traitor Tracing Scheme based on NTRU" (PDCAT 2005)

NTRUを使ってbroadcast encryptionしようという論文. 鍵の作り方のアイデアは良いんだが. 安全性は示されていない. 鍵の作り方をいじっているのでNTRUが一方向性関数であるという仮定から示すのは無理そう. ぱっと見だと復号の成功確率の見積もりが怪しい.
あと, 不正者追跡を二分探索法でやっているんだが, これはいいのか?

W. Yu, Y. Zheng, D. He "Constructing SVK_Lattices from Cyclic Bases" (PDCAT 2005)

格子とその最短ベクトルをランダムに生成しようという話. 基底がcyclicなのがミソ. 拡張として基底がcyclicでない場合のものも考えている.
格子で証拠付のランダムインスタンスを生成をするってのは初だと思う. ランダム自己帰着性が言えるかどうかは分からない.

嘘付いてるな. 証拠とインスタンスをセットで生成する方法は, Ajtai96で既に知られている.
具体的には, 行列Aとベクトルxを出力して, ベクトルxはバイナリ. 行列AはZ_q^{n*m}上一様分布というもので, Ax=0. 行列Aから格子L(A)={v∈Z^m|Av=0}が作れて, xはその十分短いベクトルになる.