決定的複合残余仮定

決定的複合残余仮定 (DCRA)は、暗号学で使用される数学的仮定です。特に、この仮定はPaillier 暗号システムの証明に使用されます。

非公式には、DCRAは、合成数 と整数が与えられた場合、が を法とする剰余であるかどうかを判断することは難しいと述べています。つまり、が存在するかどうかです。 ${\displaystyle n}$ ${\displaystyle z}$${\displaystyle z}$${\displaystyle n}$ ${\displaystyle n^{2}}$${\displaystyle y}$

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

• 二次残差問題
• 残留物問題の増加

• P. Paillier、「複合次数残余クラスに基づく公開鍵暗号システム」、Eurocrypt 1999。