Superpolynomially secure RE ⇒ RE

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

An efficient CPA adversary runs in time for a polynomial , and for all large because . Its IND-CPA advantage is therefore at most for all large , which is negligible. Correctness and perfect rerandomization are the same requirements in both, so a scheme secure against slightly super-polynomial adversaries is a rerandomizable encryption scheme — folklore.