Decisional composite residuosity assumption
Decidability assumption
The decisional composite residuosity assumption (DCRA) is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem.
Informally, the DCRA states that given a composite and an integer , it is hard to decide whether is an -residue modulo . I.e. whether there exists a such that
See also
- Quadratic residuosity problem
- Higher residuosity problem
References
- P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.
- v
- t
- e
Computational hardness assumptions
- Integer factorization
- Phi-hiding
- RSA problem
- Strong RSA
- Quadratic residuosity
- Decisional composite residuosity
- Higher residuosity
- Discrete logarithm
- Diffie-Hellman
- Decisional Diffie–Hellman
- Computational Diffie–Hellman
- External Diffie–Hellman
- Sub-group hiding
- Decision linear
- Shortest vector problem (gap)
- Closest vector problem (gap)
- Learning with errors
- Ring learning with errors
- Short integer solution