多次多変数多項式の組Ｆ＝（ｆ １ ，…，ｆ ｍ ）、署名鍵ｓ、及び文書Ｍに基づいて生成された第１の情報と、前記文書Ｍ、前記多次多変数多項式の組Ｆ、及びベクトルｙに基づいて前記第１の情報が前記署名鍵ｓを用いて生成されたことを検証するために必要な複数の第２の情報と、を含む電子署名を取得する署名取得部と、前記電子署名に含まれる複数の第２の情報を用いて前記第１の情報を復元可能か否かを確認することで前記文書Ｍの正当性を検証する署名検証部と、を備える署名検証装置が提供される。前記署名検証部は、所定数ずつ取得される前記第２の情報を用いて逐次的に前記第１の情報を復元し、復元処理に不要な前記第２の情報を不要になった段階で消去する。