代数曲面暗号系で用いる代数曲面に関する考察

摘要

代数曲面上の求セクション問題は数学的に計算困難であることが知られており、その計算困難性を安全性の根拠として代数曲面暗号［1］および代数曲面署名（ASS-CC，［6］）が捷案されている。これらの方式では、ランダムに生成したセクションを秘密鍵とし、セクションを含む代数曲面を生成して公開鍵として利用する。文献［1］，［6］の鍵生成アルゴリズムが出力する公開鍵（代数曲面）は、定数項の次数が他の項の次数よりも大きい。そのため、公開鍵のサイズが大きくなる上に、方式の安全性の仮定は次数が偏った代数曲面上の求セクション問題の計算困難性に制限される。本稿では、代数曲面とセクションから、同一のセクションを含む異なる代数曲面を出力する変換手法を提案する。文献［1］，［6］の鍵生成アルゴリズムが出力する代数曲面とセクション（秘密鍵）に提案手法を適用することで、より一般の代数曲面を生成して公開鍵として利用できる。したがって、公開鍵サイズを削減できる、安全性の仮定を弱めることができる。さらに、ASS-CCの署名生成アルゴリズムが出力する署名成分に提案手法を適用することで、署名サイズも削減できる。提案手法を利用することで、公開鍵サイズは11％、署名サイズは29％削減することができる。%The section finding problem (SFP for short) is known to be a mathematically intractable problem. We proposed a public key cryptosystem [1] and a signature scheme (ASS-CC, [6]) whose security relies on the hardness of SFP. These schemes randomly choose a section (secret key) and then generate an algebraic surface (public key) containing the prescribed section. The key generation algorithms of [1] and [6] output a surface (public key) whose defining equation, considered as a polynomial in x and y, has a very high-degree constant term in t. Therefore, it may give the impression that the security of our system relies on special surfaces, as well as the key size tends to be big. This paper proposes a technique that transforms a surface to another by preserving the same section and reducing the degree of the constant term drastically. By applying this technique to the output of surfaces in our key generation algorithm, we have another general surface with a low degree constant term and use it as the public key. In this way, we decrease the public key size (by 11%) and weaken the assumption for security. Our technique can also decrease the signature size of [6] by 29%.