Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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$ –  poncho Apr 25 at 11:51
    
You might have been thinking of $\pi^2/6$, i.e. $\zeta(2) \approx 1.64493$... –  Thomas Apr 25 at 12:09
    
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 :) –  Angela Apr 25 at 13:42

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you very much! –  Angela Apr 28 at 7:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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