Systems, methods, devices and computer program products are provided that improve stego key management of watermarking systems and reduce the impact of leaked secrets related to watermark embedding and extraction operations. In the event that a watermark extractor is compromised and its extraction stego key is revealed, new extraction stego key sets are generated and assigned to a particular group of devices with similar security features. The new extraction stego key sets have significant overlap with one another, and can be retired once a device within the particular group of devices is compromised. The described techniques are complementary to other security enhancement practices, such as obfuscation and tamper resistant techniques, to strengthen the security of a watermarking system.