V. Lyubashevsky “Lattice-Based Identificaton Schemes Secure Under Active Attacks” (PKC 2008)

On-the-fly (Girault, Poupard, Stern) で知識が漏れやすい場合ってあるじゃないですか. そういうときは証明者が何も送らなければいいんじゃないか? という発想が元だと思う.

秘密鍵はm次元バイナリベクトルx. 公開鍵は格子ハッシュのインデックスであるZq要素のn×m行列Aとハッシュ値のy=Ax.
基本方式は割と単純. S0を各要素が0以上5m-1以下のm次元整数係数ベクトルの集合とする. S1は各要素が1以上5m-1以下のm次元整数係数ベクトルの集合.

コミットメント

rをS0からランダムに選ぶ. a=Arをコミットメントとして検証者に送信.

チャレンジ

cを{0,1}からランダムに選び, 証明者に送信.

レスポンス

x+rがS1に含まれていないかつc=1の場合, z=⊥を送信. そうでない場合, z=r+cxを送信.

検証

zのノルムが5m^{1.5}以下かつ, Az=cw+yならばd=1に. そうでないならd=0に.

このままだと結構な確率で正当な証明者もz=⊥を送信してしまう. パラレルに実行することでd=1が多数決で勝てるようにしていると.
証明の方針は普通. WIであることを示して, 適当な公開鍵だと秘密鍵が2つ以上対応することを示す. 後, 敵が存在するなら10m^{1.5}以下のベクトルが二本取れてSISの平均時が解けることを示している.

感想.

1章のRelated WorksにThe conversion is non-trivial (due to the problem of zero-knowledge not being closed under parallel-composition), and many details remain to be filled inとあるが, Micciancio-VadhanのOrGapSVPへの変形はよく読むとMV03の5章に書いてある. Lyubashevskyの現指導者がMicciancioなのに.
上のアイデアは結構面白いのだが, SISのパラメータが大分悪い. GapSVPに直すと近似度がÕ(n^2). MV03のOrGapSVPを使った場合は, GapSVP換算で近似度Õ(n)かÕ(n^{1.5})だったか.
あとLyubashevsky and Micciancio (TCC 2008)と同様に, 現実的なパラメータ (n≦1000) だとLLLで解かれやすいようだ. 攻撃の際にはm+1次元の格子かつ最短ベクトルの長さがm^{0.5}以下という条件の下, 近似度が大体mの最短ベクトル問題の平均時には落ちるので.