|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 暗号 ： [あんごう] 【名詞】 1. code 2. password 3. cipher ・ 号 ： [ごう] 1. (n,n-suf) (1) number 2. issue 3. (2) sobriquet 4. pen-name
Paillier暗号とはPascal Paillierが1999年に提案した公開鍵暗号方式で、の暗号文との暗号文からの暗号文を計算出来る（加法準同型性）という性質を満たす。 RSA暗号やElGamal暗号など、の暗号文との暗号文から積の暗号文を計算できる（乗法準同型性）方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。 N次のべき乗剰余性を計算することは困難である（合成数剰余仮定）と信じられており、Paillier暗号の安全性はこの仮定に基づいている。 == 概要 == p,qを素数とし、N=pqとする。 Paillier暗号は、次の性質が成り立つ事を利用している。 （証明は後述。） 上の式で、右辺から1を引いてNで割ればMが求まる。〔通常離散対数問題は困難であるが、以上の事実は、底が(1+N)である場合には離散対数問題のインスタンス(1+N)Mが容易に解ける事を意味している。〕 そこで(1+N)Mを乱数Rでマスクしたデータ をMの暗号文とみなせば、2つの暗号文C=(1+N)MR、C'=(1+N)M'R'の積は、 となり、M+M'の暗号文と一致する。 ここで すなわち、Mの暗号文とM'の暗号文からM+M'の暗号文が求まった事になるので、加法準同型性が成り立つ。 しかし上の「暗号」は、復号する事ができないので、方式を改良する必要がある。ここで次の事実を使う。（証明は後述） そこで前述の「暗号」のRをrNに置き換えてできる暗号 を考え、これをPaillier暗号と呼ぶ。 この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。 またNの素因数p,qを知っていれば、p,qからλを計算し、 を求める事ができる。右辺に式(1)を適用する事でMλが求まるので、Mλをλで割る事で平文Mが復号できる。 Paillier暗号の安全性は以下の仮定（DCR仮定）のもと成り立つ。 実際が一様乱数と区別がつかないのであれば、によってマスクされている暗号文も一様乱数と区別がつかず、Mに関するいかなる情報も知る事はできない。 上では(1+N)をベースにして方式を作ったが、(1+N)の代わりに(1+kN)を使っても同様の方式を実現できる。（kはNと互いに素な任意の定数。）この方式もPaillier暗号と呼ぶ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Paillier暗号」の詳細全文を読む スポンサード リンク
|