ハッシュベースの署名(公開鍵署名)を書いてみた - 簡潔なQ

Post-Quantum Cryptography, Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Springer-Verlag Berlin Heidelberg, 2009の冒頭部で、ごく簡単なハッシュベースの署名アルゴリズムが紹介されていて感動したのを思い出したので書いてみた。 コードは長いので一番下に載せる。 概要 これは、堅牢なハッシュ関数を用いて、整数論的な何かに頼らなくても、署名を実現できるというものである。 ハッシュで署名というと、HMACが連想されるが、MACと署名は微妙に異なる。簡単に言うとMACが共通鍵で署名が公開鍵のものを指す。 仕組み Lamport–Diffieのワンタイム署名という部品をベースにしている。これは、大量のハッシュ値を公開鍵として渡しておき、署名をするときは、その一部の元データを