参考文献：
1.暗号と確率的アルゴリズム入門（シュプリンガー・フェアラーク東京ー絶版）
2.Error Correcting Code and Finite Fields (Oliver Pletzel) Oxford Applied Mathematics and Computing Science Series(外国の学生は教科書から論文の言葉で勉強できるので羨ましい)
3.How to Prove yourself (論文)
この方法はオリジナルのものだと思っていましたが、既に類似の研究がなされていることを指摘されました。
詳しくは以下の論文をお読みください。
というか私の方法ではうまく行かないらしいですが、なんで駄目なのかがわからない。
駄目なものを残しておく価値がないので署名法については消しました。
認証方法で駄目なのは今後の課題として残しておきます。
BBCRSで通じるのはプロしかいないようなので、こういう指摘は誠にありがたい。
この論文を読めば解るという事なので何故駄目なのかについて続報をお知らせします。
でもこの方法はstarnの特許だから金を払わなければならないというのがつまらない。
見るだけならいいのかも。
https://www.di.ens.fr/~stern/data/St47.pdf
https://core.ac.uk/download/pdf/52650821.pdf
概要
20201231：追記
ちなみにこの認証方式にはバイナリGoppa符号というものを使うのですが、何がうれしいかと言うといろんな既約多項式から同じパラメータを持つ異なる符号をたくさん作れるので、楕円曲線みたいにいろんな鍵が作れるということです。
バイナリGoppa符号については以下のウィキに詳しいです。
https://en.wikipedia.org/wiki/Binary_Goppa_code
ただし今回の認証は暗号とは違い、復号する必要がないので（シンドロームが計算できればいい）、ランダムバイナリ符号の方がより安全だと言えるでしょう。
Niederreiter暗号というpost-quantum-cryptographyではかなり注目されている暗号です。そこで何かいい応用はないかと考えてみました。
最初は暗号通貨に使えそうなデジタル署名を作るはずでしたが、徐々に署名そのものが目的になりました。そこでこの記事ではどのような電子署名を作ったのかを解説しようと思います。まず、基礎としてフィアット・シャミア認証を基にフィアット・シャミア変換を使ってデジタル署名を作り、その方法を符号に読み替えました。その結果できたのが今回の方式です。
第一章：予備知識
ここでは公開鍵暗号、ハッシュ関数、デジタル署名、などの基礎的な暗号の知識を前提として話を進める。公開鍵暗号の中でも、今回の記事に直接関係ある項目に関しては、別途ウィキに書いてある内容をリンクしてあるので、参照してほしい。
第２章では、今回やったことを要約してある。第３章では既存の公開鍵暗号の弱点と次世代暗号がなぜ必要なのか簡単に説明してある。そして第４章から本題のフィアット・シャミア認証を、第５章では、フィアット・シャミア署名を解説し、その符号バージョンを与える。第６章では、今回の署名変換に該当する類似の方法が既にないか先行研究の調査を行い、ここで考えた署名法の評価を行う。最後に、この署名の安全性証明を行いたい。また、もし間違いなら何が間違いで何が正しいのかを検証したい。そして小さな具体例を通してこの署名法を理解しやすくしてみたいと思う。
１．Niederreiter（ニーダライター）暗号
https://en.wikipedia.org/wiki/Niederreiter_cryptosystem
２．ゼロ知識証明（私がまずこれを読まないといけないですね。(^^；）
http://lab.iisec.ac.jp/~arita/pdf/lecture3.pdf
第2章：やった事
フィアット・シャミア変換
https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
と呼ばれる、暗号技術の手法がある。何を変換するのかといえば、相手認証方式からデジタル署名に変換することを言う。まず相手認証とは、ネットなどで顔が見えない相手が誰かを見分ける方法のことだと思っていい。そこで今回私は、誤り訂正符号に基づいて、この方法を真似ることができないかをやってみた。そして更に、それをデジタル署名に変換した。
第３章：耐量子計算機暗号
ここで問題になるのが、既存の数論に基づいた暗号方式（及びデジタル署名）は量子計算機に弱く、解読されてしまう運命にあるということだ。そこでアメリカを中心に整備が進められているのが、次世代暗号である耐量子計算機暗号である。耐量子暗号にはいくつかの種類があり、その中でも誤り訂正符号の復号問題に基づく暗号系がある。それが上記の参照先にある、マックエリス暗号や、その双対方式であるニーダライター暗号である。これらの暗号方式はよく符号に基づく暗号（Code Based Cryptography）と呼ばれている。
符号を用いたデジタル署名は最初は自分で作るのは面倒なので、なにかいい方法はないかとネットで検索して探していた。しかし全然いいのがない。ないなら作ってしまえということで、暗号の本を眺めてみたら、参考図書に載っているフィアット・シャミア署名が目に入った。
もしこれが汎用的な手法なら、符号に基づく公開鍵暗号でも同じように構成できるのではないか？そう思って始めたことである。
第４章：フィアット・シャミア認証の読み替え
参考文献から引用します。まずフィアット・シャミア認証です。
１・鍵セットアップ
アリスは乱数$y_i$を$ｔ(0<i<t)$個選び、大きな2つの素数（RSA暗号ではおなじみの）の積である合成数ｎを使って
x_i= y_i^2 \mod n
を計算し、
x_i,n
を公開鍵として公開します。
ここで証明者の秘密鍵はy_iです。
２．認証の開始
まずアリスは、乱数rを選び
s=r^2 \mod n
を計算してsをボブに送信します。
３．チャレンジ
ボブはランダムに
e=\{0,1 \}^t(長さtビットのベクトル)
を選び、アリスに送信します。これをチャレンジといい、ゼロ知識証明ではよく使われます。この認証方式の基礎になっているのは、このゼロ知識証明を使った相手認証です。
４.アリスの証明
アリスはボブからのチャレンジビットcを受け取った後、次のように計算し計算結果をボブに送信します。
４-１
c=0の場合
アリスは送信したｓの平方根ｒをボブに送り、ボブは
s=r^2 \mod n
であることを確かめます。
４-２
c=1の場合
アリスは
b=rΠ^t_{i=1}y^{e_{i}} \mod n
を計算しｂをボブに送信する。
５．ボブの検証
ボブはアリスから受け取った証明ｂを使って次の計算をし、計算が正しいことを確かめます。
b^2 ≠ sΠ^t_{i=1}x_i^{e_i} \mod n
もし上記のように計算が合わない（間違ってる）なら、その証明は無効になります。
そしてこのやり取りを十分多く繰り返します。
以上がFiat-Shamir認証の大まかな流れです。この方式の安全性はモジュラー平方関数
x= y^2 \mod n
の一方向性（ｎの素因数を知らずに、xからｎを法とするxの平方根yを計算することが難しい）が基礎になっています。
第５章その２：フィアット・シャミア認証の符号バージョン
続いてこれを誤り訂正符号に読み替えてみます。
1.鍵セットアップ
アリスはガロア体GF(2^m)上のt次既約多項式をランダムに取り、ｔ誤り訂正符号のパリティ検査行列Hを生成します。バイナリ正則行列S、置換行列Pをとり、秘密鍵はS,H,Pとなります。公開鍵H'はこの3つの行列をかけ合わせた
H'=SHP
になります。
アリスはまずランダムにハミング重みｔのバイナリベクトルeを取り、これを秘密鍵にします。さらに公開鍵H'を使ってシンドローム
s=eH'
を計算して、これを公開鍵にします。
２．通信の開始
アリスはeと異なるランダムバイナリベクトルrを生成し、それからシンドロームyを計算してボブに送ります。
y=rH'
３．ボブのチャレンジ
ボブはシンドロームを受け取った後、チャレンジビットｃとして０か１を送ります。
４．１
ｃ＝０の場合
アリスはyを生成するエラーベクトルrを答えとして返す。
４．２
ｃ＝１の場合
アリスは公開鍵のエラーベクトルeと１で選択したランダムエラーベクトルrを排他的論理和
y'=e ⊕ r
と暗号化し、ボブに答えとして送信します。
（実はここが一番安全性に不安が残るところだが、バーナム暗号のような効果を期待している。）
20201231：追記
エラーベクトルを直接送ることは、危険である。それはアリスの秘密のベクトルが固定であり、たかだか2ｔの重みしかない疎なベクトルであるから、ボブが認証の過程で蓄積されたベクトルからアリスの秘密が解ってしまう可能性がある。
そこで更に安全だと思われるやり方は、エラーベクトルそのものではなく、エラーを入れた符号語を送るということで、これはMcEiece暗号に準ずる方法である。この場合、アリスは公開鍵であるパリティ検査行列から（符号語の）生成行列を構成し、ランダムベクトルから生成された符号語に対してエラーベクトルを加えることでエラーベクトルを秘密にしたままボブに送るという方法を取ることができる。こうすればエラーベクトルが例え疎であっても、どこにエラーが入っているのかはわからないので安全である。
５.ボブは自分のチャレンジとアリスの送ってきたエラーベクトルから
s=H'(r ⊕ {(ec)})
を計算、つまりｃ＝０の場合は
rH'=s
を、１の場合は
x=s ⊕ y=(e ⊕ r)H'
を計算し、計算結果ｘをアリスから送られてきたエラーベクトルから計算できることを確認できればアリスの証明を合格とし、合わなければ無効とします。
もしこのような認証方式に使われるプロトコルが汎用性を持てば、どのような一方向性関数からもこのような認証（ゼロ知識証明）ができるはずです。
(ところが実際には一般的にそうとも言えないらしい。)
今回は誤り訂正符号の復号問題を使いましたが、離散対数でもできることが知られています。
（本当は電子署名までやるはずだったのですが別の記事にまとめます。）