Trusted agents operating within a trusted execution environment (TEE) of a client computing device are configured with complex computational puzzles (e.g., hash functions or other proof of work puzzles) for a remote service to solve before the trusted agent executes an operation. The trusted agent may have a policy that the puzzle is associated with, in which the policy defines a statistically defined time period over which puzzles are solved. The statistically defined time period is effectuated through parameters which control a complexity of the puzzle. Malware or bad actors that attempt to misuse the trusted agent are throttled until the remote service solves the puzzle, which is configured with a level of complexity that takes the statistically defined time period.