三角行列表示を用いない効率的なRainbow型電子署名方式

摘要

多項式公開鍵暗号（MPKC）はポスト量子暗号の候補の一つである。RainbowはMPKCの電子署名方式であり、暗号化および復号化の処理が高速であるという利点を持つ。一方で、MPKCは暗号学的に安全なパラメータを選択すると鍵長がRSA暗号と比較して大きくなるという問題がある。本稿では秘密鍵長を削減するRainbowの変形方式を提案する。我々の方式では、秘密鍵に現れる2次多項式を従来のRainbowの場合に用いられる三角行列表示とは異なる方法で記述することにより秘密鍵を削減している。さらに従来のRainbowに比べ、署名生成の効率性を向上させることができる。特に100ビット安全なRainbowの場合、秘密鍵長を約40％、署名生成の時間を約30％削減できる。