暗号学的な (符号理論での) 通信路のモデル化

色々端折った説明.

通信路上でエラーが載るので, そのエラーを訂正するために使われるのが誤り訂正符号である.
さて, 符号理論ではエラーのモデルとして以下の二つが考えられる.

  1. シャノン
    • 1文字ごとにエラーが付くか付かないかが決まる (また各エラーは独立である)
  2. ハミング
    • 1ブロック (nアルファベット) 中にt個までエラーを付けられる

というわけだ.
さて, ハミングの方のエラーモデルを見ると, 無限の能力を持った敵がエラーを載せていると考えることが出来る. そこで, この敵って別に計算能力に制限つけてもいいんじゃないの?と考えたのが, Lipton (STACS '94) である.

さて, 暗号学的には2つの状況に分かれる.
共通鍵モデルでの誤り訂正符号がLipton94とGopalan, Lipton, Ding (Manuscript 2004) らしい.
公開鍵モデルで提案したのが, Micali, Peikert, Sudan, Wilson (TCC 2005). 1/2-εの割合で付くエラーでも一意に復号できる. アイデアはリスト復号+署名+送信者側のカウンタ. 1/2-εの割合で付くエラーをリスト復号して署名を検証. カウンタが一番新しいものを選んでそれがもとのメッセージという風にする. 具体的には「ある符号語にエラーを載せて別の符号語に出来るならば署名が偽造できる」という帰着に持ち込んでいる. (実に単純であるが効果的だ.)
じゃあLocal Decodabilityがあるようなものは出来ないのか? というモチベーションで行われた研究が, 今度CRYPTO 2008に出るCryptology ePrint Archive: Report 2007/083 - B. Hemenway, R. Ostrovsky “Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code”である.
大分重い構成だが, イデアルを利用した古典的な符号 (RSとCRT), PIR, 加法的準同型性を持つ公開鍵暗号を上手く組み合わせて構成している. ブロック毎に暗号化→RS符号で拡大→PIRクエリ→最後にバイナリの良い符号で拡大という構成. Local-decodabilityは1ビット読むためにnブロックぐらい復号しないといけないのでlocalityはO(k^2)とかあると.

Micali, Peikert, Sudan, Wilson (TCC 2005) を読むと, 「現実のエラーは全部計算機が載せているんだから、計算量的に制限がある敵がエラーを載せるモデルでいいんだ」と書いてあるんだが, どうなんだろう. ここが一番の謎だ.