Cryptanalysis and improvement on key-insulated signature scheme

The security of a system is often compromised by exposure of secret key even if its underlying cryptographic tools are perfectly secure. A key-insulated signature scheme is useful cryptographic primitive for reducing the damage caused by such leakage. Recently, Go Ohtake et al. proposed an efficient strong key-insulated signature scheme, and claimed that their scheme was significantly more efficient than conventional strong key-insulated signature scheme in terms of signature size, and it was provably secure under the discrete logarithm assumption in the random oracle model. But, in this paper, we point that their scheme has some weaknesses, and propose the improved scheme. The improved scheme is not only secure, but also more efficient than their scheme. Especially, the new key-insulated signature scheme has the random-access key-update property.