本稿では,準同型暗号を対象として,安全性証明の根拠となり得る言語の複雑さを評価することで,安全性証明の限界について検討する.具体的には,任意の二項組(b,c)が与えられたとき,cが平文bの暗号文になっているかどうかを判定する問題(暗号文検証問題)の複雑さがNPの内部階層のLow階層で特徴付けられる場合について,準同型暗号方式に対する安全性証明の限界がLow階層で特徴づけられることを示す.さらに,暗号文検証問題が統計的ゼロ知識証明を持つ言語のクラスSZKで特徴付けられる場合についても同様の考察を行い,この場合については,安全性証明の限界がSZKとAM∩coAMの中間に位置する程度のクラスで特徴付けられることを示す.