改良型Winternitz one time署名の提案と安全性評価

摘要

One Time署名（OTS）とは，ハッシュ関数のみを用いて実現される使い捨て型の電子署名技術であり，比較的計算量が小さく，量子計算機の出現によっても危殆化しない等の特長を持つ．代表的なOTSとしてWinternitz 署名が知られているが，十分な強度を確保したまま署名サイズを小さくすることが難しいという問題がある．そこで本研究では，定数和指紋関数と呼ばれる特殊なfingerprint関数を導入して署名サイズおよび署名検証の計算量を削減し，さらに，署名生成に乱数要素を利用することで，鍵生成および署名作成の計算量も削減する手法を提案する．また，提案方式の安全性について形式的に議論し，ハッシュ関数および指紋関数に関するいくつかの仮定の下で，提案手法が強存在的偽造不可能性を有することを示す．