Decisional composite residuosity assumption

Template:Short description 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 $n$ and an integer $z$, it is hard to decide whether $z$ is an $n$-residue modulo $n^2$. I.e. whether there exists a $y$ such that

$z\equiv y^n(\mathrm{mod}{n}^2).$

See also

• Quadratic residuosity problem
• Higher residuosity problem

References

• P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.