シンドロームとエラーを同時に公開してはならない理由
符号ベースの(新型?)認証方式
割り算アルゴリズムを使ってシンドロームから符号の生成多項式を計算する方法がある。この時、符号の生成多項式は数多くあるが、エラーベクトルを一緒に公開すると多項式を決定できる。なので、シンドロームとエラーベクトルを一緒に公開してはいけないということになる。
1つのシンドロームに対して衝突を起こすような符号が沢山あるというのが結論です。
実際計算で確認できました。
逆に同じシンドロームでも、符号が違えば違うエラーベクトルに写像されるということです。
以下にその方法を書きます。
シンドロームから割り算で生成多項式を逆算する
いま任意のバイト列を係数とするシンドローム多項式
この4つの関数の関係式は、
と書ける。この式は符号理論で鍵方程式とよばれています。これは、
のように書くこともでき、符号の復号でよく見かけます。
シンドロームを共有する
鍵配布や秘密分散に使えないだろうか。
普通は意味のないビット列であるシンドロームに、任意の文字列を使うことができるというのは意外なことに気がついた。つまり同一のシンドロームから異なるエラーベクトルが得られることを利用すれば、
即ち、(トラップドアとして)
また符号系の公開鍵暗号を攻撃する時、符号の生成多項式を総探索するという方法もありますが、
衝突が起きないことを確信できるか?
これだけではあまり面白くないので、検査行列をハッシュ関数
また一つであること成り立たない場合、つまりエラー位置関数
数学力が足りない:ある認証方式への試論
今まで仮定してきた事は、シンドロームとエラーから符号を計算するのは難しいというものでした。
ところが、もしシンドロームとエラーベクトルが与えられれば、
果たしてこの方法でなにか有用なものを作ることはできるのでしょうか?(IDベース方式的ななにか)
鍵生成
証明者は秘密鍵
鍵生成:
それぞれバイナリ正則行列、パリティ検査行列、置換行列、公開シンドローム(メアド)であり、
ここで、
この時、ユーザはシンドローム
個人認証の手順
安全じゃないバージョン(生成多項式をやり取りする)
スクランブル行列を秘密鍵と使用しない場合は、直接暗号化した検査行列を送る代わりに符号多項式だけで通信ができる。この問題は、エラーとシンドロームから、符号多項式を特定する問題である。
1.証明者はランダムなシンドローム
2.検証者は0か1のビットを証明者に送る。
3-1.証明者が受け取ったビットが0の時
検証者にランダムな生成多項式
そして検証者は
3-2.証明者が受け取ったビットが1の時、
証明者は検証者に検査行列の生成多項式として
検証者は送られてきた多項式から検査行列
安全だと思われるバージョン(スクランブルを施した検査行列をやり取りする)
安全でないバージョンに秘密のスクランブル行列
1.証明者は、ランダムに生成したGoppa多項式
2.検証者は0か1をチャレンジビットとして返送する。
3−1.検証者のビットが0の時:証明者は
検証者は証明者から送られてきたパリティ検査行列
3−2.チャレンジビットが1の時:証明者は
検証者はこの検査行列から公開されているエラーベクトル
この時、証明者が公開しているシンドローム
この方式は、検査行列から生成多項式を計算するのが難しいという問題に基づいている。
この時、割り算アルゴリズムを使えば、公開鍵を証明者の名前やメールアドレスなどわかりやすいものを公開鍵として使えるようになる。
エラーベクトルはないほうが安全なのですが、エラーがないと元の符号と同じかどうかも検査できないことになります。
なのでスターン先生の認証法みたいなアイデアが必要になりますね。(考え中)
電子署名を目指したい
自分の名前やメアドをそのまま公開鍵に設定できれば嬉しい。
どう嬉しいのかというと、PKIが必要なくなるのだ。
鍵は自分のメアドのように、ネット上にただ1つだけ存在するものにする。
この場合メールの相手の鍵であることはセンターなしに保証される。
最初IDベース暗号ができるのではないかと思っていたけど、秘密鍵が誰にでも計算できるのでは暗号の意味がないし、シンドロームからエラーを訂正するのは普通の復号処理と何も変わらないと指摘され、あえなく内容を変更しました。
しかし割り算のみを使う今回の確定的な計算が可能なので、高い次数のGoppa多項式を瞬間で計算できるようになり、どのような値を持つシンドロームにもそれを生成する符号多項式とエラーベクトルの対が計算できるようになりました。
これを使ってなにか新しいことができないかなーと勘案中。
シンドロームだけだと非常に多くの符号に対して異なるエラーパターンが存在することになり、結果を特定できなくなります。うーん、これはどうしたものかの〜。
随時更新中。
参考文献:
[1] A new identification scheme based on syndrome decoding.
[2] A Zero-Knowlede Identification Scheme Based on the q-ary Syndrome Decodiong Problem.
Discussion