多項式公開鍵暗号(MPKC)はポスト量子暗号の候補の一つである。RainbowはMPKCの電子署名方式であり、暗号化および復号化の処理が高速であるという利点を持つ。一方で、MPKCは暗号学的に安全なパラメータを選択すると鍵長がRSA暗号と比較して大きくなるという問題がある。本稿では秘密鍵長を削減するRainbowの変形方式を提案する。我々の方式では、秘密鍵に現れる2次多項式を従来のRainbowの場合に用いられる三角行列表示とは異なる方法で記述することにより秘密鍵を削減している。さらに従来のRainbowに比べ、署名生成の効率性を向上させることができる。特に100ビット安全なRainbowの場合、秘密鍵長を約40%、署名生成の時間を約30%削減できる。%Multivariate Public Key Cryptography (MPKC) is one of candidates of post-quantum cryptography. The Rainbow is a digital signature scheme in MPKC, whose encryption and decryption are relatively efficient. However, the key size of MPKC becomes substantially large compared with that of RSA cryptosystem with the same security level. In this paper, we propose a variation of Rainbow which reduces the size of secret key. The reduction of the secret key is due to different description of quadratic polynomials appearing in the secret key from that of the original Rainbow. In addition, our scheme improves the efficiency of the signature generation of Rainbow. In particular, the secret key size of the proposed NC-Rainbow is reduced by about 40% and the signature generation speeds up by about 30% in the security level of 100 bits.
展开▼