Learningネタ - 186 @ hatenablog

メモ代わりに.

R. Nojima, H. Imai, K. Kobara, K. Morozov "Semantic Secureity for the McEliece Cryptosystem without Random Oracles" (WCC 2007) *1を読んでいるとLPN *2 仮定の元としてJ. Katz and J. S. Shin "Parallel and Concurrent Security of the HB and HB+ Protocols" (Eurocrypt 2006) を引っ張っていた. で, 読んでみた.

まず $A_{\vec{s},\epsilon}$ をオラクルとして定義する.

$\vec{a}$ を $\{0,1\}^{k}$ からランダムに選ぶ
$\nu$ をベルヌーイ分布から選ぶ
$(\vec{a},\langle \vec{s},\vec{a} \rangle \oplus \nu)$ を出力する

このときLPN仮定とは,
任意の多項式時間アルゴリズム $M$ について,
$\Pr[\vec{s} \in_R \{0,1\}^k : M^{A_{\vec{s},\epsilon}}(1^k)=\vec{s}]$
がkについて無視できること.

で, Decision/Searchの関係がRegev (STOC 2005) の証明から言えるので, LPN仮定から $A_{\vec{s},\epsilon}$ の出力の分布と $\{0,1\}^{k+1}$ 上の一様分布とが識別不可能なことが言える. これを使って色々と安全性を証明している.

さて本題. Regev (STOC 2005) いわく, 内積には双線形性があるので, 実は $A_{\vec{s},\epsilon}$ の出力の分布を $A_{\vec{s} \oplus \vec{s}',\epsilon}$ に変換することが出来る. RSRがあるので平均時/最悪時の関係も言える.
ということで, HB/HB+プロトコルの安全性は帰着の効率は落ちるのだが最悪時の仮定から安全性が言える. が, このことにはあまり言及されていないのは何でだろう.
序やら結びやらには最悪時/平均時の関係のことが書かれてるのになぁ, という話.

あと, もうちょっと別のいじり方もできる. $\vec{s}$ のハミング重みを固定した場合でも適当な置換を噛ますことで $A_{\vec{s},\epsilon}$ から $A_{\pi(\vec{s})',\epsilon}$ に変換できる. 固定したから何だっていう話なんだけど.

*1:Kirill Morozov's homepageからダウンロード可能

*2:Learning Parity with Noise. 別名: Learning With Error, LWE