Computational cryptography › Public-key encryption and key exchange › Classical number theory › Factoring

Decisional composite residuosity

In plain words

A related puzzle about numbers built from two secret primes: tell two kinds of numbers apart. Easy for anyone who can factor.

The idea: Paillier works with numbers modulo N², where N = p × q. Some of these numbers are "N-th powers" and the rest aren't, and without the primes nobody can tell which is which. Encryption hides the message under a random N-th power, so the result looks random to everyone, while the key holder, who knows p and q, can strip the random part away. Because the hiding is done by multiplying, multiplying two ciphertexts adds the hidden messages.

Why it matters: It powers Paillier encryption, which can add numbers while they stay encrypted.

The details

Given N = p × q, tell apart random N-th powers modulo N² from random numbers modulo N². Assumed hard, and easy for anyone who can factor N.

It is the assumption behind Paillier encryption^[1].

Rests on

If any of these breaks, this breaks too.

Integer factorization
One-way functions exist (needed by everything in the computational box)
Public-key encryption / two-message key exchange exist (breaks every KE-tagged assumption)
Trapdoor functions exist (breaks every TD-tagged assumption)

If it falls

If this breaks, these break with it.

Paillier encryption

About the tags

KE: This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD: This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology — EUROCRYPT ’99, 1999. doi:10.1007/3-540-48910-x_16