Secure key-evolving for public key cryptosystems based on the discrete logarithm problem

This paper addresses the security and efficiency of key-evolving protocols in public key encryption and signature schemes, where the security assumption is the intractability of the discrete logarithm problem. We identify the key-independence property as the security goal of key-evolving, so that each periodic secret key is independent of each other. The first protocol operates in Z_p* and is efficient for the secret-key holder; the second operates in Z_n*, and is efficient for the public-key holder. For both protocols, we provide proofs and analysis for correctness, security and efficiency.