Paper 2023/475
The Jacobi Symbol Problem for Quadratic Congruences and Applications to Cryptography
, "Alexandru Ioan Cuza" University of IașiAbstract
The hardness of solving the quadratic residuosity problem is the basis for establishing the security of many cryptographic schemes. Two of these are the public key encryption scheme and the identity-based encryption scheme proposed by Cocks. In this paper, we introduce a new computational problem: the problem of distinguishing between the Jacobi symbols of the solutions of a quadratic congruence modulo an RSA integer. We show that the security of the two encryption schemes is equivalent to the hardness of this problem, while the quadratic residuosity problem reduces to this new problem. We then specialize the problem to roots of quadratic residues and establish several computational indistinguishability relationships.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Jacobi symbolquadratic congruencehard problemidentity-based encryptioncomputational indistinguishability
- Contact author(s)
- fltiplea @ gmail com
- History
- 2023-04-02: approved
- 2023-04-02: received
- See all versions
- Short URL
- https://ia.cr/2023/475
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/475,
author = {Ferucio Laurențiu Țiplea},
title = {The Jacobi Symbol Problem for Quadratic Congruences and Applications to Cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2023/475},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/475}},
url = {https://eprint.iacr.org/2023/475}
}
