Schnorr署名の理論安全性評価

Abstract

Schnorr署名は，代表的なディジタル署名であり，これまでに理論的な安全性評価がされてきた．一方，ディジタル署名の利活用を考えた際，「A) 大量ユーザの公開鍵が攻撃者に知られた状況においても安全であること」と「B) 鍵や署名データの長さを決定するパラメータを短くしても安全であること」の両立が望ましい．A)について，Kiltz, Masny, Panは，Schnorr署名のMU-EUF-CMA（Multi-User Existential Unforgeability under Chosen-Message Attack）について議論されてきた．一方，B)の保証に関して，Fuchsbauer, Plouviez，Seurinは，近年，Algebraic Group Modelと呼ばれるセキュリティモデルに限定した場合，Schnorr署名は「緊密な安全性」を達成できることを示された．しかし，これらの結果が両立できるかどうかは未解決問題であった．本研究では，Schnorr署名のMulti-User Securityと緊密な安全性の両立可能性を分析し，両立不可となる一種の状況証拠を示した．