**hhnote ([[SoK - Public Key Encryption with Openings]], 280523):** At some point working on this paper I realized that the above kind of argu- ment is potentially problematic when arguing about asymptotics. The cen- tral argument is that in the b = 1 (random) simulation, the challenge bits of A are information-theoretically hidden from it, and so it can’t affect the win probability at all even if it were to discover the simulation. Furthermore we assume adversaries terminate in finite time with well-formed output, so it can’t mess anything up there either. One thing it seems to me that it can do, however, is to decide it’ll run in time 2λ before halting with its guess. It seems to me that this should still be possible even if the adversary is “PPT”, as we are placing it into an envi- ronment that it didn’t expect and that’s therefore not covered by the defini- tion, thus making the reduction potentially exponential-time. Of course (as pointed out by Martijn), this is not an issue in the concrete settings, where adversaries are treated as unit-time. . . . Writing this out, I realize that the way out is probably to require the PPT assumption to cover all environments, whether or not they are exactly what the adversary expects. (I have no idea if this is the standard way to de- fine “PPT” or not.) This issue affects: Thm. 2, Thm. 6, Thm. 3 of the MI paper, Thm. 2 of BRT (none of which argue about asymptotics), and Thm. 3.3 of BY12, (who confusingly state that the relation, corresponding to the distinguisher in Thm. 6, in the b = 1 world need not be PT). **Martijn's response (310523):** In the asymptotic setting, all algorithms are modelled as PPT ITMs. Thus, their worst case run time over all possible tape contents and interactions, is bounded by a polynomial. That gives you your all environ- ments coverage. If you would stick to a environment specific runtime bounds, then indeed the adversary might start to overrun for inputs outside that environment. One solution is to move to non-black-box reductions: if the reductions knows the polynomial bound on the adversary’s runtime (in valid environments), then in non-faithful simulated environments it can simply abort the adversary if its runtime exceeds its bound; the reduction thus learns that the adversary has deemed the environment non-faithful.