FHE over the Integers - reduction to approximate gcd problem

Question

I have three quick questions concerning the reduction of the scheme to the approximate gcd problem:

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

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.

3. 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.

Answer 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:

1. $\gcd(0,v) = v$ and $\gcd(u,0) = u$.
2. $\gcd(u,v) = \gcd(v,u)$.
3. If $u,v \in 2\mathbb{Z}+1$ and $u \geq v$, then $\gcd(u,v) = \gcd((u-v)/2,v)$.
4. If $u,v \in 2\mathbb{Z}$, then $\gcd(u,v) = 2 \cdot \gcd(u/2,v/2)$.
5. 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:

1. If $v > u$, then swap them.
   1. If $v=0$, then output $u$.
2. Let $b_1$ be the parity bit of $u$ and let $b_2$ be the parity bit of $v$.
3. If both $u$ and $v$ are odd, then $u \gets u-v$ and $b_1 \gets 0$.
4. If $b_1=0$, then $u \gets u/2$. If $b_2=0$, then $v \gets v/2$.
5. (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:

1. If $z_2 > z_1$, then swap them.
   1. If $z_2 = 0$, then output $z_1$ and $z_2$.
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}$.)
3. If both $q_p(z_i)$ are odd, then $z_1 \gets z_1 - z_2$ and $b_1 \gets 0$.
4. For each $i = 1,2$, if $b_i = 0$, then $z_i \gets (z_i - \mathsf{parity}(z_i))/2$.
5. (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.