Abstract: We present the notion of PROG-KDM security for public-key encryption schemes. This security notion captures both KDM security and revealing of secret keys (key corruptions) in a single definition. This is achieved by requiring the existence of a simulator that can program ciphertexts when a secret key is revealed, i.e., the simulator can delay the decision what plaintext is contained in what ciphertext to the moment where the ciphertext is opened. The definition is formulated in the random oracle model.
We show that PROG-KDM security can be achieved by showing that a natural and practical construction in the ideal cipher model is PROG-KDM secure (hybrid encryption using authenticated CBC encryption).