5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You might want to give a link to the paper you're referring to. Also, $\pi \approx 3.14159$, and so $\pi/6 \approx 0.523599$ $\endgroup$ – poncho Apr 25 '14 at 11:51
  • $\begingroup$ You might have been thinking of $\pi^2/6$, i.e. $\zeta(2) \approx 1.64493$... $\endgroup$ – Thomas Apr 25 '14 at 12:09
  • $\begingroup$ My bad, I meant to write $\pi^2/6$ (that's what it says in the paper). I fixed it and posted the link, and I will check out the $\zeta$-function :) $\endgroup$ – Angela Apr 25 '14 at 13:42
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.