Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-reducibility of CDH.

Throughout the proof the authors reach the following statement:

Let $\mathcal{R}$ be the probabilistic polynomial-time algorithm that is guaranteed to exist by Lemma 3.2. By the definition of $\mathcal{R}$ and our assumption, we have that for any $a, b$ and $c \neq a \cdot b$ in $Z_Q$: $$ |\Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1] - \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1]| > \epsilon(n).$$

Then the authors go on and state that this implies an algorithm that is able to correctly classify all CDH instances with an error probability of at most $2^{-n}$. I am pretty sure that the core of this last step is just the application of Chernof Bounds like one does to amplify the success probability of $\mathcal{BPP}$ algorithms, e.g. like here: http://people.csail.mit.edu/madhu/ST07/scribe/lect11.pdf

My problem: However, as I understand this, in order to apply the Chernoff Bounds, I need that (reusing $P, Q, g, a, b$ and $c$ from above) $$\Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1]> \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1] $$ always holds or at least for all $n$ large enough.

It was intuitive to me to assume this without loss of generality and reason it, by stating that the output of $\mathcal A$ can be negated in order to achieve this. But thinking about it for a couple more minutes, I came to the conclusion that this is not enough. $\mathcal{A}$ could follow several patterns to determine on which type of input it outputs 1 with a higher probability. For example: $\mathcal{A}$ could measure the length of the encoding of $P$ in bits. referring to this number as $k$, $\mathcal{A}$ could flip its output if $k$ is even.

One could imagine many more such strategies. In the end, I came to the conclusion, that the function $$ f(P, Q, g, g^a, g^b, g^c) := \begin{cases} 1 & \text{if } \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1]> \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1]\\ 0 & \text{otherwise} \end{cases} $$ would need to be polynomial time computable.

Question: Assuming $f$ to be polynomial-time computable seems reasonable to me. But I am not 100% sure it holds, because the reason for changes in the function $f$ might also be out of the control of $\mathcal{A}$. So, are there technically sound arguments that $f$ is polynomial-time computable?

Also: I have the impression, that may approach to this might be more complicated than it needs to be. Have I missed a simple explanation? (I already had a look at this question, but it did not answer my question because they limited themselves to concrete $i \in \mathbb{N}$.)

This might be a small technical detail, but I think it's something that appears relatively often and I prefer to understand proofs in detail and not only on a high level.

  • $\begingroup$ @knbk I understand, that you usually use the absolute value to ensure that the advantage is positive. However, in order to apply the chernoff bounds it seems to me, that I'd need to know which of the two probabilities is larger. Also, in the end of the proof of Theorem 3.1 in wisdom.weizmann.ac.il/~naor/PAPERS/gdh.pdf on page 15, also no absolute value is calculated. I think this did not happen by mistake but deliberately, because otherwise it wouldn't imply an algorithm that decides all CDH instances with an error of at most $2^{-n}$ (as stated in Theorem 3.1) directly. $\endgroup$ – Dave Feb 27 '18 at 18:40

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.