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}. \,

See also


  • 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: [ 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”