Decisional composite residuosity assumption explained

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.

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 thatz \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.