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 [4], 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.

  • 1
    $\begingroup$ 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))}$? $\endgroup$ – puzzlepalace Sep 27 '17 at 21:44
  • $\begingroup$ I agree that this is probably the only way, visible at present, this can make sense. Thank you very much for the comment. $\endgroup$ – Mayank Sep 27 '17 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.