Decisional composite residuosity 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 ${\displaystyle n}$ and an integer ${\displaystyle z}$, it is hard to decide whether ${\displaystyle z}$ is an ${\displaystyle n}$-residue modulo ${\displaystyle n^{2}}$. I.e. whether there exists a ${\displaystyle y}$ such that

${\displaystyle z\equiv y^{n}{\pmod {n^{2}}}.\,}$

See also

• Quadratic residuosity problem
• Higher residuosity problem

References

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