ランダムな巡回行列の作用素ノルムの上限

すっきりと解決したのでメモ.

  1. {-1,0,+1}要素のランダムなn次元ベクトル (c_0,...,c_{n-1}) を考えて対応する巡回行列を確率変数としてP_nとおく.
  2. l_2-ノルムに対応する作用素ノルムの上限は固有値の絶対値の上限に等しい. (n次正方行列を考えるので.)
  3. 巡回行列はフーリエ行列で対角化可能で, 固有値\sum_{k=0}^{n-1} c_k \exp(- 2 \pi i m k/n) (m=0,...,n-1).
  4. よってこの固有値の最大を求めればよい.
  5. Hoeffdingの上界より, ある固有値の絶対値が\sqrt{n} \omega(\sqrt{\log{n}})以下である確率は1-2^{-\omega(\log{n})}以上.
  6. Union bound取って, 全ての固有値の絶対値が同様である確率は1-n2^{-\omega(\log{n})}以上.

という寸法かー. 巡回行列以外に一般化するのは面倒臭そう. cyclicじゃなくてnegacyclicくらいならフーリエ行列もどきで対角化出来るので同様の議論が可能.

一般のランダム行列の場合は, もうちょい良いバウンドが知られていて, 適当な定数Cを取ってC√nにで同様の議論が可能ってのが羨ましい. 対称Toeplitz行列の場合はMark W. Meckes “On the spectral norm of a random Toeplitz matrix” (Electronic Communications in Probability 12 (2007), 315--325) ってのがi.i.d.からちょっとだけ緩めた場合の良い上界を与えているそうだ. 概要だけ読んだ.

格子縮小アルゴリズムの進展

とはいえ多項式時間じゃなくって, 指数時間掛かる方ですけどね.

Ajtai, Kumar, Sivakumar (STOC 2001) を真面目に解析したら時間計算量2^{5.9n}, 空間計算量2^{2.95n}だったよとNguyen and Vidickが報告したのが今年の話 (J. Math. Crypt. 2009).
Voulgaris and Micciancio曰く, 時間計算量2^{3.199n}, 空間計算量2^{1.325n}まで改良出来ました. またヒューリスティックな改良案も示していて, そっちは実験的に時間計算量2^{0.48n}, 空間計算量2^{0.21n}だそうです (ECCC - TR09-065).

最適化の人とか向けですかね, これ.

SchemeでJacobi記号

誰の役に立つのか分からないけど. 分岐が意外と多い.
Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ.

(define (Jacobi a n)
  (cond ((= a 0) 0)
        ((= a -1)
         (cond ((= (modulo n 4) 1) 1)
               ((= (modulo n 4) 3) -1)))
        ((= a 2)
         (cond ((= (modulo n 8) 1) 1)
               ((= (modulo n 8) 3) -1)
               ((= (modulo n 8) 5) -1)
               ((= (modulo n 8) 7) 1)))
        ((< a 0)
         (* (Jacobi (- a) n) (Jacobi -1 n)))
        ((= a 1) 1)
        ((>= a n)
         (Jacobi (modulo a n) n))
        ((even? a)
         (* (Jacobi (/ a 2) n) (Jacobi 2 n)))
        ((even? n)
         (Jacobi n a))
        (else
         (if (= 3 (modulo n 4) (modulo a 4))
             (- (Jacobi n a))
           (Jacobi n a)))))

一般ハードコア関数の証明とフーリエ変換

8月5日はハーコーということでハードコアの日だそうです. (ちゃんと日本記念日協会に届け出たそうで.)

ということなのでハードコア関数の話をします.
Goldreich-Levinハードコア述語とリスト復号の話はよく出るんですが, GLハードコア述語とフーリエ変換の話はあんまり出ないんで大雑把な話を一席.

以下では, F=F2nとします.

述語bが関数f:F→Fのハードコア述語であるとは,

  1. b:F→{0,1}が多項式時間で計算可能,
  2. 任意の多項式時間の敵Dに対して, 無視できる関数εが存在し, \Pr_{x, D}[D(f(x))=b(x)] \leq \frac{1}{2}+\epsilon

が成立することです.

GoldreichとLevinいわく, 適当な一方向性関数f:F→Fに対して, f'(x,r)=(f(x),r):F×F→F×Fも一方向であり, b(x,r)=Σixiri mod 2はf'のハードコア関数である.

このハードコア関数の証明は以下の手順を踏みます.

  1. ハードコア性を破る敵Dを用いて, 一方向性を破る敵Aを構成する.
  2. とりあえずxとDに与える乱数を固定する.
  3. 標準的な議論から, F×coinsの部分集合Sが存在して,
    1. Sの割合はε/2以上
    2. Sに入るxとDのコインωの組に対して\Pr_{r \in F}[D(f(x),r;\omega)=b(x,r)] \geq \frac{1+\epsilon}{2}.
  4. xとωを固定して, xを求められることを示せば十分.

というわけで手元に
\Pr_{r \in F}[D_x(r)=b(x,r)] \geq \frac{1+\epsilon}{2}
を満たす決定性の敵Dxが存在するとしましょう.

rが入っている集合Fを2つに分割します.

  • Gd = {r | Dx(r)=h(x,r)},
  • Bd = {r | Dx(r)≠h(x,r)}

とします.
簡単な計算で, |Gd| = (1+ε) 2n-1, |Bd| = (1-ε) 2n-1であることが分かります.

こっから強自己訂正器に持っていくのがRackoff流の証明ですが, ここで視点を変えます.
今考えているb(x,r)をちょっと変更して, b'(x,r)=(-1)b(x,r)としましょう.
すると,
\Pr_{r \in F}[D_x=b'(x,r)] \geq \frac{1+\epsilon}{2}
を満たすDが存在すると考えてもいいわけです.

ここまでが前提です.
次にちょっと横道にそれてフーリエ変換の話を始めます.

F=F2nの離散フーリエ変換

関数fを要素としてもつ環V={f:F→R}を考えます. 和と積は項別に計算することにして演算を入れてあります.
この環に内積\langle f, g \rangle = E_{r \leftarrow F}[f(r) g(r)] = \frac{1}{2^n} \sum_{r \in F} f(r) g(r)という定義で入れます.
関数のノルムは内積の2乗ということにします.
するとf:F→{-1,+1}はノルムが必ず1になります.

次にフーリエ基底を用意します.
関数族{χx}x∈Fただし, \chi_{x}(r) = (-1)^{\sum_{i=1}^{n} x_i r_i} = (-1)^{b(x,r)} = b'(x,r)です.
定義より, χxのノルムは1です.
簡単な計算により, 任意のx≠x'で<χx, χx'>=0が言えます.
従って, この関数族はベクトル空間Vの正規直交基底になっています.

内積やノルムを入れた御利益として以下があります.

  1. g'(x) = <g, χx>と定義します. (gのフーリエ係数.)
  2. g(r) = Σx g'(x) χx(r)が成立します.
  3. ||g||2 = Σx g'2(x) = 1です.

合流

さて, 先ほど見たように, 今
\Pr_{r \in F}[D_x(r)=b'(x,r)] \geq \frac{1+\epsilon}{2}
を満たすDxが存在すると考えています.
面倒なので, g(r)=Dx(r)と置いて, b'(x,r)=χx(r)に注意すると,
\Pr_{r \in F}[g(r)=\chi_x(r)] \geq \frac{1+\epsilon}{2}.
書き直すと,
\Pr_{r \in F}[g(r) \chi_x(r) = 1] \geq \frac{1+\epsilon}{2}.
従って,
g'(x) = \langle g(r), \chi_x(r) \rangle \geq \epsilonが成立することになります.

以上より, xを求める問題だったのが, g(r)=D(f(x),r)の大きなフーリエ係数を求める問題に変わりました.
ありがたいことに, そのようなフーリエ係数の個数は高々1/ε2個しか無いこともノルムの議論から証明出来ます.
ここから先は頑張ってKushilevitz and Mansourなり, Akavia, Goldwasser, and Safraを読んでください. 以上.

undecidable problems

とりあえず10個かー.

授業で証明読んだもの

  • 停止問題とそのヴァリアント
  • ビジービーバー
  • ライスの定理
  • L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2)
  • PCP (Postの方)

証明知らないもの

読みたいもの

DBLPから見繕う.

  • 群同型
    • en.wikipediaにあった.
    • 環同型は判定可能でNP∩coAM (Kayal and Saxena, CCC 2005). さらに, グラフ同型問題の困難性は環同型問題の困難性以下.
  • コラッツ‐角谷予想の決定不能性
  • 文脈自由言語関係
  • 正規言語でもあるの?
    • Juhani Karhumäki, Yael Maon: A Simple Undecidable Problem: Existential Agreement of Inverses of Two Morphisms on a Regular Language. J. Comput. Syst. Sci. (JCSS) 32(3):315-322 (1986)
  • 項書き換え
    • Max Dauchet: Termination of Rewriting is Undecidable in the One-Rule Case. MFCS 1988:262-270
    • ルールが1つらしいよ
  • π計算
  • 真理値表
    • Jan Kalicki: An Undecidable Problem in the Algebra of Truth-Tables. J. Symb. Log. (JSYML) 19(3):172-176 (1954)
  • 組合わせ系
    • Kevin J. Compton: An Undecidable Problem in Finite Combinatorics. J. Symb. Log. (JSYML) 49(3):842-850 (1984)
    • Stefan A. Burr: Some undecidable problems involving the edge-coloring and vertex-coloring of graphs. Discrete Mathematics (DM) 50:171-177 (1984)

Signed QR

まぁ詳しくはR. Ficshlin and C.-P. Schnorr (JoC 200)を見ていただくとして, Hofheinz and KiltzがCRYPTO 2009で発表する論文がDennis Hofheinzのサイトから読めるようになったのでメモですよ.

とりあえず, Nをnビットのブラム数とします. N=PQで, PとQはそれぞれn/2ビットの奇素数で, 特にP = Q = 3 mod 4です. ZN*は位数がφ(N) = (P-1)(Q-1)です.
JNでヤコビ記号が1になるような部分群を表します. するとJNの位数は(P-1)(Q-1)/2です. なんでかって, -1がJNに入るので.
次にQRNで平方剰余がなす群を表します. 今度はQRNがJNの部分群になって, さらに位数は(P-1)(Q-1)/4です.
さて, x∈ZNについて, |x|でxの絶対値を表します. x∈{-(N-1)/2,...,(N-1)/2}と表わされているとして, 符号を無視したものを絶対値とします.
で, ZN*の部分群Gについて, G+を{|x|:x∈G}として定義します.
ここに積をg*h = |g h mod N|で入れます. するとこれはちゃんと部分群になっています.
Nがブラム数なので, -1はQRNに入りません. これに注意すると,

  1. (QRN+, *)は位数(P-1)(Q-1)/4の群
  2. QRN+ = JN+.
    • したがって, x∈ZNがQRN+に入るかどうか簡単に判定可能.
  3. QRN巡回群ならQRN+巡回群

が言えます.
すると定理2にある通り, 素因数分解が困難と仮定すると, ほとんど帰着のロス無しに, この群でSDH仮定が成立します. びっくりですね.

あー, ただSDHの仮定がちょっと違う点がポイントで, DDHオラクルは, (g,X,Y,Z)を受け取るのでも(X,Y,Z)を受け取るのでもなく, (g,X)固定で(Y,Z)だけ受取ります. これがうまくDDHオラクルをシミュレーションするためのミソになってます.

最近の格子話

2008年9月以降だとこんな感じですかね.

  • 一般の格子
    • IND-CCA2 PKE (modular GGH) (STOC 2009)
    • KDM-CPA PKE (CRYPTO 2009)
    • EUF-CMA Sig w/o RO (Manuscript)
    • SID-IND-ANON-CPA HIBE w/o RO (Manuscript)
  • イデアル格子
    • IND-CCA2 PKE (modular GGH, w/ quantum reduction) (ePrint)
    • EUF-CMA Sig w/ RO (ePrint)
    • EUF-CMA Sig w/o RO (??) (Manuscript)
    • SID-IND-ANON-CPA HIBE w/o RO (??) (Manuscript)

それぞれの下2つはついさっきPeikertが公表してた. 実はBonehAgrawalとBoyenがIBEをCash, Hofheinz, KiltzがHIBEを研究していたらしいけど.
一応, イデアル版の下2つの証明が通るかどうか確認しておくか. Bonsai Treeって名前はまぁいいか.

そろそろ逆輸入が始まりそうだなぁ.

補遺

  • Peikert “Bonsai Trees (or, Arboriculture in Lattice-Based Cryptography).” (ePrint 2009/359)
  • Cash, Hofheinz, Kiltz “How to Delegate a Lattice Basis.” (ePrint 2009/351)

Peikertの方は抽象化して書いてある. テクニカルな部分を他に押し付けているとも言う.
CHKの方ではちゃんとサンプリングの方法にも言及しており多少細かい解析が載っている. ただしこちらはイデアル格子版についての言及がない.