新たなRSA型リング署名方式の提案とその安全性評価

摘要

本稿は、SITA2004の予稿集に記載した内容HN04を、一部修正し、新たに加筆したものである。 まず最初に、既存のRSA型リング署名AOS02の安全性についても再評価を行い、従来AOS02よりも高い安全性評価をえた。次に、既存のRSA型リング署名AOS02を改良して新たなリング署名を構成し、Random Oracle Model BR93の仮定の下でその安全性評価を行った。その結果、RSA関数の逆関数問題と等価な安全性を持つことを示した。リング署名は2001年にRivest等RST01によって提案されたデジタル署名方式である。 これまでに様々なリング署名が紹介されてきたが、特に離散対数型のリング署名の安全性評価は離散対数問題と等価な安全性が示されているAOS02。 しかしながら、RSA型のリング署名については、未だRSA関数の逆関数問題と等価な安全性を持つ事は証明されていなかった。 それゆえ、十分な安全性を与えるためには、署名サイズが大きくなってしまうという問題点があった。 そこで本稿ではRSA型リング署名について、よりタイト(tight)な安全性評価を与えた。それによって、署名サイズを減らす事が可能となった。