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 Zp* and is efficient for the secret-key holder; the second operates in Zn* , and is efficient for the public-key holder. For both protocols, we provide proofs and analysis for correctness, security and efficiency.