# Distinguishing advantage in terms of $\Omega(\omega)$

I was going through this paper ("Fully Homomophic Encryption over the Integers Revisited") and the statement written in the first paragraph on page 5 stating $\DeclareMathOperator{\agcd}{AGCD}$

We say that an algorithm $\mathcal{A}$ is an $(\epsilon_1,\epsilon_2)$-distinguisher for $\agcd_{X,\phi}(\mathcal{D})$ if, with probability $\ge \epsilon_2$ over the randomness of $p \leftarrow \mathcal{D}$, its distinguishing advantage between $A^{\agcd}_{X,\phi}(p)$ and $U(\mathbb{Z} \cap [0, X))$ is $\ge \epsilon_1$.

and the paragraph just before Theorem 1 on page 5 stating -

In , Applebaum et al gave an LWE self-reduction from secret distribution $U((\mathbb{Z} \cup [0, p))^n)$ to secret distribution $D_{\mathbb{Z}^n, O(\alpha p)}$ which reduces the distinguishing advantage from $\epsilon$ to $\Omega(\epsilon)$, if $\alpha \ge \Omega( \sqrt{\ln(n / \epsilon)} \, / \, p )$.

Based on what I understand, shouldn't the distinguishing advantage increase from $\epsilon$ to $\Omega(\epsilon)$ ? Since $\Omega(\epsilon)$ is a function $f(\epsilon)$ such that $f(\epsilon) \geq cg(\epsilon)$ for some $\epsilon > 1$, shouldn't the distinguishing advantage increase because $f(\epsilon)$ is asymptotically $\geq \epsilon$.

Any help is appreciated.

• I can only guess but perhaps what is meant by $\epsilon$ to $\Omega(\epsilon)$ is actually $\frac{1}{poly(x)}$ to $\frac{1}{\Omega(poly(x))}$? – puzzlepalace Sep 27 '17 at 21:44
• I agree that this is probably the only way, visible at present, this can make sense. Thank you very much for the comment. – Mayank Sep 27 '17 at 21:56