FHE over the Integers - reduction to approximate gcd problem I have three quick questions concerning the reduction of the scheme to the approximate gcd problem:


What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)
In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong? 
Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.
Also in step 4: Am I correct that $\overset{\sim}{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?


Link to the paper: https://eprint.iacr.org/2009/616.pdf

I'm referring to section 4.1.
Before my answer, I would like to review the original binary GCD algorithm @wikipedia. Roughly speaking, this algorithm replaces division with binary shifts and subtraction.

For two positive integers $u$ and $v$, the following identities hold:


$\gcd(0,v) = v$ and $\gcd(u,0) = u$.
$\gcd(u,v) = \gcd(v,u)$.
If $u,v \in 2\mathbb{Z}+1$ and $u \geq v$, then $\gcd(u,v) = \gcd((u-v)/2,v)$.
If $u,v \in 2\mathbb{Z}$, then $\gcd(u,v) = 2 \cdot \gcd(u/2,v/2)$.
If $u \in 2\mathbb{Z}$ and $v \in 2\mathbb{Z}+1$, then $\gcd(u, v) = \gcd(a/2,b)$.


By using those identities, the binary GCD algorithm $\mathsf{BGCD}(u,v)$ is defined as follows:


If $v &gt; u$, then swap them.

If $v=0$, then output $u$.

Let $b_1$ be the parity bit of $u$ and let $b_2$ be the parity bit of $v$.
If both $u$ and $v$ are odd, then $u \gets u-v$ and $b_1 \gets 0$.
If $b_1=0$, then $u \gets u/2$. If $b_2=0$, then $v \gets v/2$.
(Recursion) If $b_1=0$ and $b_2=0$, then output $2 \cdot \mathsf{BGCD}(u,v)$. Otherwise, output $\mathsf{BGCD}(u,v)$.


Answer 1


  What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)


Let us consider two positive integers $a$ and $b$, and its GCD.
Then, there is an unique integer $k$ and odd integer $c$ satisfying $\gcd(a,b) = 2^{k} c$.
The authors call this $c$ the odd part of $\gcd(a,b)$.

The reduction algorithm, say $\mathsf{Alg3}(z_1,z_2)$, in Step 3 is defined as follows:


If $z_2 &gt; z_1$, then swap them.

If $z_2 = 0$, then output $z_1$ and $z_2$.

Let $b_i$ be the parity bit of $q_p(z_i)$, that is, $b_i = [q_p(z_i)]_2$.
(Call the LSB oracle implemented by $\mathcal{A}$.)
If both $q_p(z_i)$ are odd, then $z_1 \gets z_1 - z_2$ and $b_1 \gets 0$.
For each $i = 1,2$, if $b_i = 0$, then $z_i \gets (z_i - \mathsf{parity}(z_i))/2$.
(Recursion) Output $\mathsf{Alg3}(z_1,z_2)$.


As the authors wrote, this algorithm (approximately) performs the binary GCD algorithm over quotients on input $q_p(z_1)$ and $q_p(z_2)$.
Since we are interested only in the case $\gcd(q_p(z_1),q_p(z_2)) = 1$,
 the algorithm removes "If" from the step 5 in $\mathsf{BGCD}$.
In addition, the doubling in "If" will introduce another noise.
By this removal, $\mathsf{Alg3}$ (approximately) outputs $z_1'$ whose quotient $q_p(z_1')$ is the odd part of $\gcd(q_p(z_1),q_p(z_2))$, when the current $z_2'$ in Step 1 is $0$.

Answer 2


  In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong? 
  
  Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.


As @Thomas wrote, the probability is that two random numbers are relatively prime.
If so, $\gcd(q_p(z_1^*), q_p(z_2^*))$ is $1$ and the odd part of it is also $1$. 

Answer 3


  Also in step 4: Am I correct that $\tilde{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?


Yes.