The 2013 Snowden revelations exposed state-level adversaries' ability to compromise widely used cryptographic schemes via so-called subversion attacks. The scientific community responded by developing models to capture and counter these attacks. However, generic attacks showed the necessity of additional assumptions. One approach is introducing a trusted guardian, the watchdog, to validate cryptographic implementations. This thesis focuses on enhancing practicality in two key domains in the watchdog model while minimizing reliance on trust and avoiding random oracles. Our contributions include the first construction of public-key encryption with practical watchdogs requiring linear testing time, improving feasibility for real-world deployment. Additionally, we introduce the first authenticated encryption and digital signature constructions that are secure under complete subversion without relying on random oracles. While further improvements are needed for large-scale deployment, this thesis represents significant progress toward practical subversion-resilient schemes.