Basically, this part of the paper aims at proving that, as long as the approximate GCD problem is hard, the DGHV scheme is "secure". So, as it is standard in reduction proofs, you go and prove the contrapositive: you show that if there exists an adversary $\mathcal{A}$ that is able to break the DGHV scheme, then there exist an adversary $\mathcal{B}$ that uses $\mathcal{A}$ to break the approximate GCD problem. For more information on reduction proof and how they work, I recommend this video.
The outline of the proof is as follows: first, the authors exhibit the Learn-LSB routine, in which $\mathcal{B}$ uses $\mathcal{A}$ to learn the leats significant bit of the secret key. This corresponds to step 2 in the paper. Then (step 3 and 4), the authors show that, using this Learn-LSB, it is possible for $\mathcal{B}$ to fully recover the secret key $p$, which also means breaking the approximate GCD problem.
Concerning the Learn-LSB routine (step 2 of the proof)
Here, $\mathcal{B}$ uses $\mathcal{A}$ in a black-box manner to find the least significant bit of the secret key $p$, assuming that when $\mathcal{A}$ is fed with a ciphertext, it returns the corresponding plaintext. The subroutine LearnLSB takes some number $z$ and a public key $pk$ as input. It should output the least significant bit of the quotient of $z$ by $p$, noted $[q_p(z)]_2$ in the paper.
EDIT: note that $\mathcal{A}$ and $\mathcal{B}$ are sorts of imaginary adversaries. Thought experiments, I you will. It is actually impossible to realize the Learn-LSB subroutine (or at least, all crypto experts agree that it is impossible). We are using them only to show that, IF there exists $\mathcal{A}$ able to break DGHV, THEN we can construct $\mathcal{B}$ that breaks approximate GCD problem (and in passing, that realizes the Learn-LSB oracle). YET we know that approximate GCD is hard. We reach a contradiction: therefore $\mathcal{A}$ can not exist. See the video linked above on this reasoning.
Let's look at what happens in one turn of the loop. In lines 2 and 3 of the subroutine, $\mathcal{B}$ creates a rigged ciphertext $c_j$ for the public key $pk$, which it feeds to $\mathcal{A}$ at line 4. $\mathcal{A}$ should return its guess on the plaintext that is inside $c_j$. $\mathcal{B}$ is not directly interested in the plaintext itself, but a function of it (see line 5). The trick is in how $c_j$ is rigged: notice (on line 3) that $c_j$ is a standard ciphertext, except that $z$ was added to $m_j + 2r_j +2\sum x_k$. So instead of $c_j$ being an encryption of $m_j$ it is actually an encryption of a combination of $z$ and $m_j$: specifically, of $[r_p(z)]_2 \oplus m_j$ where $r_p(z) = z \bmod p$. To understand why, see that the decryption of $c_j$ will give (if we simplify, and under some assumption of the form of $z$, which the authors detail in section 4.1.1):
$$\begin{align}
\mathsf{Dec}(sk = p, c_j) &= \left[ \left[ [z+m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ \left[ [ q_p(z) \cdot p + r_p(z) +m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ r_p(z) +m_j + 2r_j+2\sum x_k \right]_2 \\
&= [r_p(z) + m_j]_2 = [r_p(z)]_2 \oplus m_j \\
\end{align}$$
Therefore, coming back to what $\mathcal{A}$'s guess, on line 4, $a_j$ should be equal to $[r_p(z)]_2 \oplus m_j$. However, remember that we want $[q_p(z)]_2$ and not $[r_p(z)]_2$. But as the authors note $[q_p(z)]_2 = [r_p(z)]_2 \oplus parity(z)$, where $parity(z) = 0$ when $z$ is even, and $1$ otherwise. What this small relation says is that, when $z$ is even, then $[q_p(z)]_2 = [r_p(z)]_2$ ; and when $z$ is odd, then $[q_p(z)]_2 \neq [r_p(z)]_2$. Convince yourself by looking at all possibilities for the parities of $[q_p(z)]_2$ and $[r_p(z)]_2$, knowing that $z = [r_p(z)]_2 \cdot p[r_p(z)]_2$ and $p$ is odd.
At last, we can understand line 5, in which $\mathcal{B}$ translates $\mathcal{A}$'s guess on the rigged ciphertext $c_j$ into $[q_p(z)]_2$ by computing $a_j \oplus parity(z) \oplus m_j$
The whole process is repeated a several times because errors might appears (notably, $c_j$ may not be well formed), and the majority of votes is returned.
Concerning the Binary GCD (step 3)
Now, with the Learn-LSB subroutine, the authors run a special version of the binary GCD algorithm on $z_1$ and $z_2$ near-multiples of $p$, and are able to obtain $z = q \cdot p + r$, where $q$ is the odd part of $GCD(q_p(z_1), q_p(z_2))$.
The binary gcd algorithm is not complex in itself. Only, here, the authors run an algorithm on $z_1$ and $z_2$ in appearance, but the actual GCD is computed on $q_p(z_2)$ and $q_p(z_2)$. The Learn-LSB subroutine is useful to know, given $z_1$ and $z_2$, whether $q_p(z_1)$ and/or $q_p(z_2)$ are odd or not. Indeed, the binary GCD algorithm on some number $a$ and $b$ needs to make decision based on the parity of $a$ and $b$.
Finding the secret key p (last step)
At last, using these tools, it is possible to recover $p$ by a final twist. First, $\mathcal{B}$ takes two near-multiples of $p$, $z_1^*, z_2^*$, and runs the above algorithm on them. The result is: a number $\bar{z} = q \cdot p + r$ where $q$ is the odd part of $GCD(q_p(z_1^*), q_p(z_2^*))$. If $q \neq 1$, $\mathcal{B}$ begins again with new $z_1^*$ and $z_2^*$ ($\mathcal{B}$ can check whether $q = 1$ later actually).
Next, perform the above binary GCD with $z_1^*$ and $\bar{z}$. And magically, the bit-decomposition of $q_p(z_1^*)$ appears during the iteration of the algorithm. That is, at iteration $i$, $b_1$ (of line 2 of the paper's binary-GCD) gives the $i$ least significant bit of $q_p(z_1^*)$. Maybe the best way to see how/why is by running (by hand) the algorithm with small parameters, such as $p = 23$, $z_1^* = 11 \cdot p + 2$ and $\bar{z} = p + 1$. It finishes in 4 steps, yielding in order $b_1 = 1, 1, 0, 1$, and $(1011)_2$ is $11$ (Remember that the authors define that all remainders are $r_p(z)\in (−p/2, p/2]$)
Last step: now that you know $q_p(z_1^*)$, do $z_1^*/q_p(z_1^*) = p + r_p(z_1^*)/q_p(z_1^*)$. Round the result and you obtain $p$, since $r_p(z_1^*)$ is (normally) much smaller than $q_p(z_1^*)$.
Wrap-up
So $\mathcal{B}$ started with access to samples of $\mathcal{D}_{\gamma,\rho}(p)$ giving near-multiples of $p$, and found $p$. Thus, it broke the approximate GCD problem. Yet, the approximate GCD problem is deemed hard and assumed unbreakable: we reach a contradiction. Thus, the DGHV scheme is secure !
Note: the answer, although very long already, purposely ignores many important elements, such as the size of some elements and possible wrap-around in moduli computation.
