Increasing symmetric key lifetime by controlled randomness

Key replacement in cryptographic building blocks (algorithms and protocols) is a required operation in order to meet the security requirements. The common practice is to have only one cryptographic key valid for any given time moment and periodically change this key. We propose a scheme that allows multiple keys to be valid at any moment and describe a method that allows the receiver to identify the key used for each encryption with minimum effort, while not allowing an attacker to deduce this information. The proposed scheme introduces little computational performance overhead at the price of superior security characteristics and lower bandwidth utilization for control information