はじめに（Introduction）
量子体制がある（？）署名ということで紹介されていたので、どういう仕組みなのか調べてみました。
仕組みは簡単なものでしたので、サンプル実装も行っていきます。
論文（Paper）
この署名はLeslie Lamport（レスリー ランポート）によって1979年に発明されました。
「Constructing Digital Signatures from a One Way Function」
日本語に直訳すると、「一方向性関数からのデジタル署名の構築」となります。
一方向性関数（Wikipedia）についてはまだ存在性は証明できていませんが、暗号学的ハッシュ関数（Wikipedia）が近い性質を持っている為、これを利用します。
アルゴリズム（Algorithm）
論文は古く、読みにくかったので、Lamport signature - Wikipediaに記載しているものを使用します。
鍵
$k\ $を正の整数とし、$P= \lbrace 0,1 \rbrace ^k$をメッセージとします。
$f:Y\rightarrow Z$を一方向性関数とします。
$1 \leq i \leq k \ $ かつ $\ j \in \lbrace 0, 1 \rbrace \ $の条件で、署名者は$\ y_{ij} \in Y \ $をランダムに生成し、$\ z_{i,j} = f(y_{i,j})\ $を計算します。
秘密鍵$\ K\ $は、$2k\ $個の値$\ y_{i,j}\ $です。
公開鍵は、$2k\ $個の値$\ z_{i,j}\ $です。
署名
$m=m_1 , \ldots , m_k \in \lbrace 0,1 \rbrace^k$とします。
メッセージの署名は
$\text{sig}(m_1 , \ldots , m_k)=(y_{1,m_1} , \ldots , y_{k,m_k})=(s_1 , \ldots , s_k)$
秘密鍵を署名値として提示しますが、半分しかわからないので大丈夫らしいです。
だから、ワンタイム（１回のみ）しか使えないようです。
再利用したら、どんどん秘密鍵が明らかになってしまう。
検証
全ての$1 \leq i \leq k \ $について、$f(s_i)=z_{i,m_i}\ $である事を確認します。
サンプル（Sample）
鍵
$k=256\ $とします。
$f\ $をハッシュ関数SHA256とします。
メッセージが256ビット（32バイト）なので、文字列をSHA256したものをメッセージとします。
秘密鍵（$\ y_{i,j}\ ,\ 1 \leq i \leq 256\ ,\ j \in \lbrace 0, 1 \rbrace \ $）を生成します。（乱数）
| $i$ | $j=0$ | $j=1$ |
|---|---|---|
| 1 | 195814b0a6281edfe6996b078e9ad79030956cb35d84ae5544f11fb51390c553 |
4e95bc07bb409392288ea73ffa54f513b5d936ed6777dc43916f53089a9f5194 |
| 2 | 0eef47108305c184b1f98a5424d212faf7cbb44cd38860cfda3d5d0a24dbbca3 |
1a3dc362668986a8bbc4fda86451a481e2940a8d83ea09b2180b48c2cc4a2b9e |
| 3 | 41c8405f4013bc240de49165563062800644dd84cef949aefb3f6028abba5a28 |
8599f8e4c570301edc82d7da742ab8e346d5882ba35876ffcc39ad0d795be54e |
| 4 | 3f17eeac54fc7523743e1168307ce1966e4e1c4ff726665afaa2f4ff6e9fbb28 |
14c912b9c414ed5714fd929a471721cc199fd00cbe0123214b82c1b9552823e6 |
| : | : | : |
| 256 | fde889181e4260e7fdc4e5fe2a440e1891683b9e12a423fc6f4b8865ee40e44a |
f40594ce35fe05a3ffa3aa4b1f9ec8a5816824e3e30108236709624082c1d6f4 |
公開鍵（$\ z_{i,j}\ ,\ 1 \leq i \leq 256\ ,\ j \in \lbrace 0, 1 \rbrace \ $）は秘密鍵のハッシュ値（SHA256）となります。
| $i$ | $j=0$ | $j=1$ |
|---|---|---|
| 1 | 1db152e1a5d022502a3f55b6b3db8be51dd192dafec017b89cafbe2dce13637e |
fec2b114dfe62f207cf57e86251acd0482272def573d5df5d7b5887324a669f8 |
| 2 | e316702bf0ed6b60153347c9642b64062c18f1f13de08afd3e018c286295ef44 |
317991090537a9566798b6d0464734a3563ad8649c21e25f92efe30f3ca395ef |
| 3 | 1a67cb27dd212c16c7877aec6a02e6efd47879a808d199b86f9d5369f2910bdb |
d5bc9d69cf0db4781f108bcc87a858212f08a95572d3a6c230f3eefea7d073f2 |
| 4 | cf30c97c99c02ca2834b52edd3f063cdfea34fe4c43513f5812d6f3dd1b92236 |
c61ae1d9cb466bcc71577669b2029116111dc16191abe4a4ca4b17132cc34897 |
| : | : | : |
| 256 | 6dae8ea290f5af93b954f3ee6ec92c2511ed46f27fc13da4fefde4a0aa4c68ce |
1b6558bb636dc4343100e4558b6506a5cf356b41c90549c257c5c7fdcd790416 |
署名
メッセージは文字列（ここでは、hogehoge）のハッシュ値（SHA256）を求めます。
１６進数で表すと以下のようになります。
4c716d4cf211c7b7d2f3233c941771ad0507ea5bacf93b492766aa41ae9f720d
２進数で表すと以下のようになります。
0100110001110001011011010100110011110010000100011100011110110111110100101111001100100011001111001001010000010111011100011010110100000101000001111110101001011011101011001111100100111011010010010010011101100110101010100100000110101110100111110111001000001101
署名値は以下のようになります。
$\text{sig}(0,1,0,0, \ldots , 1)=(y_{1,0} ,y_{2,1} ,y_{3,0} ,y_{4,0} , \ldots , y_{256,1})=(s_1 ,s_2 ,s_3 ,s_4 , \ldots , s_{256})$
| $i$ | $s$ |
|---|---|
| 1 | 195814b0a6281edfe6996b078e9ad79030956cb35d84ae5544f11fb51390c553 |
| 2 | 1a3dc362668986a8bbc4fda86451a481e2940a8d83ea09b2180b48c2cc4a2b9e |
| 3 | 41c8405f4013bc240de49165563062800644dd84cef949aefb3f6028abba5a28 |
| 4 | 3f17eeac54fc7523743e1168307ce1966e4e1c4ff726665afaa2f4ff6e9fbb28 |
| : | : |
| 256 | f40594ce35fe05a3ffa3aa4b1f9ec8a5816824e3e30108236709624082c1d6f4 |
検証
全ての$1 \leq i \leq 256 \ $について、署名値のハッシュ値（$f(s_i)$）と対応する公開鍵（$z_{i,m_i}$）が一致する事を確認します。
$f(s_1) \overset{?}{=} z_{1,0}$
$f(s_2) \overset{?}{=} z_{2,1}$
$f(s_3) \overset{?}{=} z_{3,0}$
$f(s_4) \overset{?}{=} z_{4,0}$
:
$f(s_{256}) \overset{?}{=} z_{256,1}$
まとめ（Conclusion）
非常にシンプルな構造だと思いますが、署名値として、秘密鍵の半分を提示してしまうという大胆な発想だとも思いました。
それにより、ワンタイムで使用する事が重要だとも感じました。
とりあえず、JavaScriptでサンプル実装しました。
**ここ**で確認できます。
耐量子性については１ビット毎にハッシュ値を適用する事で対応可能だということらしいです。
量子コンピューターにより、ハッシュ値の逆演算がある程度の時間で出来るようになったとして公開鍵から秘密鍵を求めるのに、単純に計算量が512倍になっただけという気もします。
公開鍵をあらかじめ全て提示するのではなく、公開鍵でハッシュ木を生成し頂点を短縮公開鍵（Short public key）として提示すればより計算量が必要になります。
（これがどのくらい効果があるかはわかりませんが・・・）
メッセージのハッシュ衝突の方も考えなければならないとも思いました。
メッセージの可変可能な箇所を少なくしたり、可変可能部分に対するチェックサムを入れたりする必要もあるかもしれません。