# Decisional composite residuosity assumption

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 n2 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.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Computational hardness assumption — In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one time pad is a common example. In many cases, information… …   Wikipedia

• Paillier cryptosystem — The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n th residue classes is believed to be computationally difficult. This… …   Wikipedia

• Damgaard-Jurik cryptosystem — The Damgård Jurik cryptosystem [Ivan Damgård, Mads Jurik: [http://www.brics.dk/RS/00/45/ A Generalisation, a Simplification and Some Applications of Paillier s Probabilistic Public Key System] . Public Key Cryptography 2001: 119 136] is a… …   Wikipedia

• Damgård–Jurik cryptosystem — The Damgård–Jurik cryptosystem[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ns + 1 where n is an RSA modulus and s a (positive) natural number. Paillier s scheme is the special case with s = 1. The order φ(ns + …   Wikipedia