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 n and an integer z, it is hard to decide whether z is a n-residue modulo n² or not, i.e., whether there exists y such that

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

References

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

This article is issued from Wikipedia - version of the Friday, April 13, 2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Decisional composite residuosity assumption

See also

References