The Jacobi Symbol Problem for Quadratic Congruences and Applications to Cryptography

Modern security models for public-key cryptography, such as one-way encryption under chosen plaintext attack (OWE-CPA) or indistinguishability under chosen plaintext attack (IND-CPA), rely on reductions between the security of cryptographic schemes and well-studied hard problems, such as integer factorization, discrete logarithm, quadratic residuosity, or learning with errors. The reduction can go from the hard problem to the security property under study, or vice versa, or in both directions (in which case we say there is an equivalence). Equivalences fundamentally tie the security property to the hard problem, thus offering multiple benefits. But obtaining an equivalence between a security property and a computational hard problem can be challenging, as is the case with the equivalence between the OWE-CPA security of the textbook RSA cryptosystem and the integer factorization problem. In this paper, we introduce a new computational problem, namely, distinguishing the Jacobi symbols of the solutions of a quadratic congruence modulo an RSA modulus (JSP(QC)). We show that this problem is at least as hard as the quadratic residuosity problem. Then, we show that the IND-CPA security of two public-key encryption schemes due to Cocks is equivalent to JSP(QC). We then specialize JSP(QC) to roots of quadratic residues and establish several computational indistinguishability results.