Regularity of Lossy RSA on Subdomains and Its Applications

摘要: We build on an approach of Kiltz et al. (CRYPTO ’10) and bring new techniques to bear the study how “lossiness” RSA trapdoor permutation under φ-Hiding Assumption (φA) can be used understand security classical RSA-based cryptographic systems. In particular, we show that, φA, several questions or conjectures about such systems reduced bounds regularity (the distribution primitive e-th roots unity mod N) “lossy” map (where e divides φ(N)). Specifically, this is case for: (i) showing that large consecutive runs input bits are simultaneously hardcore, (ii) widely-deployed PKCS #1 v1.5 encryption semantically secure, (iii) improving for RSA-OAEP. prove results lossy using both recent estimates Gauss sums over finite subgroups, thereby obtaining in above applications. Our deepen connection between “combinatorial” properties exponentiation \(\mathbb{Z}_\emph{N}\) constructions.