残留物の増加問題

暗号学において、ほとんどの公開鍵暗号システムは、解読不可能であると考えられている問題に基づいています。高位残差問題（n位残差問題^[1]とも呼ばれる）はそのような問題の一つです。この問題は因数分解よりも解くのが容易であるため、この問題が解くのが難しいという仮定は、因数分解が困難であるという仮定よりも 強いと言えます。

数学的背景

nが整数ならば、 nを法とする 整数は環を形成する。pとq が素数であるn = pqならば、中国剰余定理は次のように表す。

${\displaystyle \mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z} }$

任意の環の単位は乗法の下で群を形成し、の単位群は伝統的に と表記されます。 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

上の環同型から、

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }}$

群 の同型として。p と q は素数と仮定したので、群とはそれぞれ位数p −1 とq −1の巡回群である。dがp −1の約数である場合、 のd乗の集合はインデックスdの部分群を形成する。gcd( d , q −1) = 1 である場合、のすべての元はd乗であるため、 のd乗の集合もインデックスdの部分群である。一般に、gcd( d , q −1) = gである場合、 には ( q −1)/ gの d乗が存在するため、 のd乗の集合のインデックスはdgである。これは、 d = 2 のときに最もよく見られ、平方剰余のサブグループを検討している場合、 の要素のちょうど 4 分の 1 が平方剰余であることはよく知られています(ここでのように、 nが 2 つの素数の積である場合)。 ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

重要な点は、p −1（またはq −1）の任意の約数dに対して、 d乗の集合は${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

問題の説明

整数n = pq ( pとqは不明)、整数d ( d はp −1を割り切る) 、整数x < nの場合、 x が nを法としたd乗 ( d番目の剰余と同等)であるかどうかを 判断することは不可能です。

pとqが既知であれば、xがnを法とするd番目の剰余であるかどうかは簡単に判断できる。なぜなら、 xがpを法とするd番目の剰余であるのは、

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod {p}}}$

d = 2の場合、これは二次残差問題と呼ばれます。

アプリケーション

Benaloh 暗号システムとNaccache-Stern 暗号システムの意味的セキュリティは、この問題の解決困難性に依存しています。

参考文献

1. 張玉亮; 松本 勉; 今井 秀樹 (1988). 「奇数番目の剰余問題の暗号応用」電子情報通信学会論文集. 71 (8): 759– 767. CiteSeerX  10.1.1.137.8511 .