Tag Info

5

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...

2

Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$? How can you exploit that to obtain $m$ in another way?

2

First, note that if you know $p-q=a$ and $p+q=b$, for some $a,b$, you have two equations with two unknowns and can solve for $p,q$. Now, $$n=p*q=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$$ Rearrange $$\left(\frac{p+q}{2}\right)^2 = n + \left(\frac{p-q}{2}\right)^2$$ Then start guessing values for $p-q$. Start with $2$ and substitute ...

1

The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues.

Only top voted, non community-wiki answers of a minimum length are eligible