Paper 2023/475 Original: eprint.iacr.org/2023/475 ↗
The Jacobi Symbol Problem for Quadratic Congruences and Applications to Cryptography
Abstract
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.
- History
- 2023-04-02: last updated
- 2023-04-02: published
- Short URL
- https://ia.cr/2023/475
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2023/475}
}