Paillier暗号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/09/28 16:29 UTC 版)
|
出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。
|
Paillier暗号とは Pascal Paillier が1999年に提案した公開鍵暗号方式で、m1 の暗号文と m2 の暗号文から m1 + m2 の暗号文を計算出来る（加法準同型性）という性質を満たす。
RSA暗号やElGamal暗号など、m1 の暗号文と m2 の暗号文から積 m1m2 の暗号文を計算できる（乗法準同型性）方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。
N 次の冪乗剰余性を計算することは困難である（合成数剰余仮定）と信じられており、Paillier暗号の安全性はこの仮定に基づいている。
概要
p, q を素数とし、N = pq とする。
Paillier暗号は、次の性質が成り立つ事を利用している（証明は後述）。
Paillier暗号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/15 01:58 UTC 版)
平文 m ∈ Z n {\displaystyle m\in \mathbb {Z} _{n}} に対するPaillier暗号(en:Paillier cryptosystem)の暗号文は、 g m ⋅ r n mod n 2 {\displaystyle g^{m}\cdot r^{n}{\bmod {n^{2}}}} である。ここで g ∈ Z n 2 ∗ {\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}} 、 r ∈ Z n ∗ {\displaystyle r\in \mathbb {Z} _{n}^{*}} である。この公開鍵暗号は加法に関して、準同型性を有する。すなわち、 m 1 , m 2 {\displaystyle m_{1},m_{2}} の暗号文 g m 1 ⋅ r 1 n , g m 2 ⋅ r 2 n mod n 2 {\displaystyle g^{m_{1}}\cdot {r_{1}}^{n},g^{m_{2}}\cdot {r_{2}}^{n}{\bmod {n^{2}}}} から m 1 + m 2 {\displaystyle m_{1}+m_{2}} の暗号文を計算することは容易である。すなわち、 g m 1 ⋅ r 1 n × g m 2 ⋅ r 2 n mod n 2 = g m 1 + m 2 ⋅ ( r 1 r 2 ) n mod n {\displaystyle g^{m_{1}}\cdot {r_{1}}^{n}\times g^{m_{2}}\cdot {r_{2}}^{n}{\bmod {n^{2}}}=g^{m_{1}+m_{2}}\cdot (r_{1}r_{2})^{n}{\bmod {n}}} とできる。
※この「Paillier暗号」の解説は、「準同型暗号」の解説の一部です。
「Paillier暗号」を含む「準同型暗号」の記事については、「準同型暗号」の概要を参照ください。
Paillier暗号と同じ種類の言葉
- Paillier暗号のページへのリンク
