In addition to providing new bounds, we also show that a key lemma of Lewko et al. is incorrect. We prove a weaker version of the claim which is nonetheless sufficient for most, though not all, of their applications.
Our technical results can be viewed as showing that exponentiation in Z_N is a deterministic extractor for every source that is uniform on an arithmetic progression. Previous work showed this type of statement only on average over a large class of sources, or for much longer progressions (that is, sources with much more entropy).
Category / Keywords: public-key cryptography / PKCS, Phi-Hiding, Regularity Original Publication (in the same form): IACR-TCC-2015 Date: received 12 Jan 2015 Contact author: yxz169 at cse psu edu Available format(s): PDF | BibTeX Citation Version: 20150114:164955 (All versions of this report) Short URL: ia.cr/2015/027