An information processing apparatus includes: a signature generating section that generates an electronic signature σ by using a signature key KS associated with a verification key KV; and a substitute-key generating section that generates, with respect an electronic document m to which the electronic signature σ is attached by the signature generating section, a substitute verification key KV′ (KV′≠KV) that is capable of verifying a validity of the electronic signature σ and a substitute signature key KS′ (KS′≠KS) associated with the substitute verification key KV′. In a predetermined case, the verification key KV and the signature key KS are updated to the substitute verification key KV′ and the substitute signature key KS′.