Decisional composite residuosity assumption
Encyclopedia
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
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. In particular, the assumption is used in the proof of the Paillier cryptosystem
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...
.
Informally the DCRA states that given a composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
n and an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
z, it is hard to decide whether z is a n-residue modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
n2 or not, i.e., whether there exists y such that
See also
- Computational hardness assumption
- Quadratic residuosity problemQuadratic residuosity problemThe quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
- Higher residuosity problemHigher residuosity problemIn cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such problem...