Let $p,q$ be odd primes, $n:=pq$ and $a,x \in \mathbb{Z}/n\mathbb{Z}$ be quadratic residues such that $x^2 \equiv a \pmod n$. I have understood the proof that calculating the least significant bit of $x$ is computationally as hard as deciding the Quadratic Residuosity Problem and I am aware of the fact that it is even as hard as factoring $n$. Now the "Handbook of Applied Cryptography" states in Fact 3.89 (chapter 3, page 117) that computing the $k = \mathcal{O}(\log(\log(n)))$ least significant bits of $x$ is also as hard as factoring $n$. (The key word is "simultaneous security".)

Could you please tell me how to prove this? How can I relate this to the established result that the least bit of $x$ is secure?

  • 2
    $\begingroup$ A little note on the style of the book; one has to go Notes and Further references of the chapter to find the reference. page 127 section 3.5 $\endgroup$
    – kelalaka
    Oct 8, 2020 at 14:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.