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 an n-residue modulo n². I.e. whether there exists a 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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Computational hardness assumptions
Number theoretic	Integer factorization Phi-hiding RSA problem Strong RSA Quadratic residuosity Decisional composite residuosity Higher residuosity
Group theoretic	Discrete logarithm Diffie-Hellman Decisional Diffie–Hellman Computational Diffie–Hellman
Pairings	External Diffie–Hellman Sub-group hiding Decision linear
Lattices	Shortest vector problem (gap) Closest vector problem (gap) Learning with errors Ring learning with errors Short integer solution
Non-cryptographic	Exponential time hypothesis Unique games conjecture Planted clique conjecture

Decisional composite residuosity assumption

See also

References