Supuesto de residuosidad compuesta decisional

Supuesto de decidibilidad

El supuesto de residuosidad compuesta decisional (DCRA) es un supuesto matemático utilizado en criptografía . En particular, el supuesto se utiliza en la prueba del criptosistema de Paillier .

De manera informal, la DCRA establece que dado un compuesto y un entero , es difícil decidir si es un residuo módulo . Es decir, si existe un tal que ${\displaystyle n}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle n}$ ${\displaystyle n^{2}}$ ${\displaystyle y}$

${\displaystyle z\equiv y^{n}{\pmod {n^{2}}}.\,}$

Véase también

• Problema de residuosidad cuadrática
• Problema de mayor residuosidad

Referencias

• P. Paillier, Criptosistemas de clave pública basados ​​en clases de residuosidad de grado compuesto , Eurocrypt 1999.