# Decisional Small $e$-Residue Assumption

In 2001, Catalano et. al defined Decisional Small $e$-Residue Assumption as follows:

Let $N$ be a random chosen $\ell$-bit long RSA modulus and $e>2$ a random integer such that $\text{gcd}(e, \lambda(N^2))=1$. For every probabilistic polynomial time algorithm $\mathcal{A}$, define the following probabilities: \begin{equation*} P_{random}=\Pr\left[\begin{array}{r|c} \mathcal{A}(N,x)=1 & x \leftarrow\mathbb{Z}_{N^2}^*\end{array}\right] \end{equation*} and \begin{equation*} P_{residue}=\Pr\left[\begin{array}{r|c} \mathcal{A}(N,y)=1 & x \leftarrow\mathbb{Z}_{N}; y\leftarrow x^e\bmod N^2\end{array}\right] \end{equation*} then, there exists a negligible function $\mathsf{negl}()$ such that $|P_{random}-P_{residue}|<\mathsf{negl}(\ell)$.

Can I state the assumption as follows: For every PPT algorithm $\mathcal{A}$, there exists a negligible function $\mathsf{negl}()$ such that \begin{equation*} \Pr \left[\begin{array}{r|c} \mathcal{A}(N,e, y_b)=b & p, q \leftarrow \mathcal{PRIMES}(\ell/2);N=pq\\ & e\leftarrow \mathbb{Z}_N^* (e>2)\; \text{s.t. gcd}(e, \lambda(N^2))=1 \\ & x\leftarrow \mathbb{Z}_N; y_0=x^e\bmod N^2\\ &y_1 \leftarrow \mathbb{Z}_{N^2}^*; b \leftarrow \lbrace 0, 1 \rbrace\end{array}\right]-\frac{1}{2}<\mathsf{negl}(\ell) \end{equation*}

• $\mathcal{PRIMES}$? Not $\operatorname{PRIMES}$ or something similar? – Maarten Bodewes Jan 5 '17 at 20:20
• Same. $\mathcal{PRIMES}(\ell)$ the set of primes with length $\ell$ in its binary representation. – Pinkimani Goswami Jan 6 '17 at 3:25