For your sleeping proposal, it sounds a little like differential privacy [1] where you can add some randomness to gain some privacy but spend some of the predetermined privacy budget. In that case, `N` depends on the (roughly) variance of the computation time, the noise amount, and your privacy budget. If you get it right, it has provable security properties. However, that doesn't work as well when the adversary has access to the machine and can observe the intermediate state (or side channel leaks thereof).
[0]: https://github.com/dalek-cryptography/subtle
[1]: https://blog.openmined.org/privacy-series-basics-definition/
That said, it's fairly easy to tell if a CPU spends time sleeping or doing actual work, so it depends on who is in control of the CPU.
But there’s still a high risk of some side channel letting the attacker tell when the program is working and when it’s sleeping.
I'm also wondering how this interacts with bounds checking, which would introduce branches. I tried searching the paper (sorry, no time to read the whole thing today) for 'bounds' but did not get a result.
Semi-related. One (insufficient) option for dealing with timing leaks is to add a random delay. ie: `sleep_ms(rand(1,1000))`. The problem is that given N leaks an attacker can remove that noise. I have two questions here:
1. What is "N"?
2. Does that sleeping introduce any additional vulnerabilities? Basically, is this a "if you can afford that latency it won't hurt".