😸

シンドロームとエラーを同時に公開してはならない理由

2025/01/25に公開

符号ベースの(新型?)認証方式

割り算アルゴリズムを使ってシンドロームから符号の生成多項式を計算する方法がある。この時、符号の生成多項式は数多くあるが、エラーベクトルを一緒に公開すると多項式を決定できる。なので、シンドロームとエラーベクトルを一緒に公開してはいけないということになる。

1つのシンドロームに対して衝突を起こすような符号が沢山あるというのが結論です。
実際計算で確認できました。
逆に同じシンドロームでも、符号が違えば違うエラーベクトルに写像されるということです。
以下にその方法を書きます。

シンドロームから割り算で生成多項式を逆算する

g(x),S(x),l(x),w(x)をそれぞれ、Goppa多項式、シンドローム多項式、エラーロケーター、最大公約多項式であるとする。
いま任意のバイト列を係数とするシンドローム多項式S(x)から、符号とエラーベクトルを出力することを考える。
この4つの関数の関係式は、

S(x)l(x)+u(x)g(x)=w(x)

と書ける。この式は符号理論で鍵方程式とよばれています。これは、
S(x) \equiv \frac{w(x)}{l(x)} \pmod{g(x)}

のように書くこともでき、符号の復号でよく見かけます。

シンドロームを共有する

鍵配布や秘密分散に使えないだろうか。

普通は意味のないビット列であるシンドロームに、任意の文字列を使うことができるというのは意外なことに気がついた。つまり同一のシンドロームから異なるエラーベクトルが得られることを利用すれば、u(x)を秘密鍵にして何か出来るのではないかと勝手に期待している。(シンドロームを入力とする多重線形写像?)
即ち、(トラップドアとして)u(x)なしにS(x)l(x)から符号g(x)を計算することができないようにしたいのだった。しかし、エラーを公開するということはl(x)が分かるということで、エラーは公開したらだめなのかも。符号系の暗号は符号多項式g(x)がわからなくても、検査行列というシンドロームを生成するための手段があることが一つの鍵になっているみたいです。

また符号系の公開鍵暗号を攻撃する時、符号の生成多項式を総探索するという方法もありますが、u(x)を総探索したほうが効率が良いことが解ります。

衝突が起きないことを確信できるか?

これだけではあまり面白くないので、検査行列をハッシュ関数fとしたときに、衝突がないことも言えるかも知れない。つまり、g(x)S(x)を固定した時に、l(x)を1次の式に分解できるu(x),w(x)が存在しないことが言えればいい。これが言えると、第2原像困難性が言える。条件付きではあるが、符号理論はそれが前提で成り立っている。つまり入力xに対して、f(x)=f(y)xは既知)であるような別の入力yが存在しないことが言えればいい。またハッシュ関数であるならば、g(x)は常に1つ固定しなければいけない。これが固定された場合でも、長いメッセージを処理する場合に衝突がないようにハッシュ関数を設計するのは難しい。同様にして長さを固定した場合に、f(x)=f(y)である2つの入力x,yを(もしあれば)探すのは鍵方程式があればそんなに難しくない気がする。ハミング重みとか考えると難しいけど、多項式だと考えれば解りそうな気がする。

また一つであること成り立たない場合、つまりエラー位置関数l(x)g(x)の次数を超えた場合、鍵方程式の振舞を見ることで、どのような衝突が起きるのかが分かるかも知れない。

数学力が足りない:ある認証方式への試論

今まで仮定してきた事は、シンドロームとエラーから符号を計算するのは難しいというものでした。
ところが、もしシンドロームとエラーベクトルが与えられれば、u(x)をランダムに選んで、誰でも符号多項式を計算できてしまう。エラーベクトルにはエラーの位置情報が含まれていて、それを1次多項式の積で表せば誤り位置関数になります。なのでエラー位置は固定でも、エラーの値が変わるので、その分自由度が残っっていることになります。(それがw(x)の持つ意味である)
果たしてこの方法でなにか有用なものを作ることはできるのでしょうか?(IDベース方式的ななにか)

鍵生成

証明者は秘密鍵skと公開鍵pkの対(sk,pk)=((H',S,H,P),(y=e_0H',e_0))としpkを公開する。
鍵生成:S,H,P,H'=SHP,y=e_0H'とする。
それぞれバイナリ正則行列、パリティ検査行列、置換行列、公開シンドローム(メアド)であり、sk=(H,P,S,H')であるとする。
ここで、ID=yS^{-1}である。

この時、ユーザはシンドロームy_Xから複数のエラーベクトルを生成できるが、エラーベクトルe'_Xを固定することで、シンドロームに対して公開鍵を1つ固定できる。

個人認証の手順

安全じゃないバージョン(生成多項式をやり取りする)

r(x),g(x)をそれぞれランダムGoppa多項式、Goppa符号の生成多項式とする。
スクランブル行列を秘密鍵と使用しない場合は、直接暗号化した検査行列を送る代わりに符号多項式だけで通信ができる。この問題は、エラーとシンドロームから、符号多項式を特定する問題である。

1.証明者はランダムなシンドロームy_rとそれに対応するエラーベクトルe_rを検証者に送る。

2.検証者は0か1のビットを証明者に送る。

3-1.証明者が受け取ったビットが0の時
検証者にランダムな生成多項式r(x)を送る。
そして検証者はr(x)から検査行列H_rを生成し、s_r=e_rH_rであることを確認する。

3-2.証明者が受け取ったビットが1の時、
証明者は検証者に検査行列の生成多項式としてr(x) \oplus g(x)を送信する。
検証者は送られてきた多項式から検査行列 H_{g \oplus r}とエラーベクトルe_r、更に証明者の公開鍵であるエラーとシンドロームe,yから(e \oplus e_r)H_{g \oplus r}=y \oplus y_rを確認する。

安全だと思われるバージョン(スクランブルを施した検査行列をやり取りする)

安全でないバージョンに秘密のスクランブル行列Sと置換行列Pを検査行列Hに掛けてH'=SHPを検証者に送る。個々での問題は、スクランブルされた符号から符号多項式を計算する問題です。

1.証明者は、ランダムに生成したGoppa多項式r(x)、秘密行列と置換を使い、エラーとそれに対応するシンドロームを検証者に送る。

2.検証者は0か1をチャレンジビットとして返送する。

3−1.検証者のビットが0の時:証明者はr(x)から生成された検査行列を送る。
検証者は証明者から送られてきたパリティ検査行列H'_r=SH_rPを使い、エラーベクトルからシンドロームが計算できることを確かめる。

3−2.チャレンジビットが1の時:証明者はr(x) \oplus g(x)から生成された検査行列H_{r \oplus g}S,Pをかけた検査行列H'_ {g \oplus r}=SH_{g \oplus r}Pを作り、検証者に送る。
検証者はこの検査行列から公開されているエラーベクトルe_0からシンドロームe_0H_{r \oplus g}を計算する。
この時、証明者が公開しているシンドロームy_0と最初に送られてきたシンドロームy_rとの和y_r \oplus y_0を計算し、(e_0 \oplus e_r)H_{r \oplus g}=y_r \oplus y_0となることを確認する。

この方式は、検査行列から生成多項式を計算するのが難しいという問題に基づいている。

この時、割り算アルゴリズムを使えば、公開鍵を証明者の名前やメールアドレスなどわかりやすいものを公開鍵として使えるようになる。

エラーベクトルはないほうが安全なのですが、エラーがないと元の符号と同じかどうかも検査できないことになります。
なのでスターン先生の認証法みたいなアイデアが必要になりますね。(考え中)

電子署名を目指したい

自分の名前やメアドをそのまま公開鍵に設定できれば嬉しい。
どう嬉しいのかというと、PKIが必要なくなるのだ。
鍵は自分のメアドのように、ネット上にただ1つだけ存在するものにする。
この場合メールの相手の鍵であることはセンターなしに保証される。
最初IDベース暗号ができるのではないかと思っていたけど、秘密鍵が誰にでも計算できるのでは暗号の意味がないし、シンドロームからエラーを訂正するのは普通の復号処理と何も変わらないと指摘され、あえなく内容を変更しました。

しかし割り算のみを使う今回の確定的な計算が可能なので、高い次数のGoppa多項式を瞬間で計算できるようになり、どのような値を持つシンドロームにもそれを生成する符号多項式とエラーベクトルの対が計算できるようになりました。
これを使ってなにか新しいことができないかなーと勘案中。

シンドロームだけだと非常に多くの符号に対して異なるエラーパターンが存在することになり、結果を特定できなくなります。うーん、これはどうしたものかの〜。

随時更新中。

参考文献:
[1] A new identification scheme based on syndrome decoding.
https://link.springer.com/content/pdf/10.1007/3-540-48329-2_2.pdf
[2] A Zero-Knowlede Identification Scheme Based on the q-ary Syndrome Decodiong Problem.
https://link.springer.com/content/pdf/10.1007/978-3-642-19574-7_12.pdf

Discussion