本稿では、この論文を扱います。
https://link.springer.com/content/pdf/10.1007%2F3-540-48405-1_8.pdf
この記事で紹介する内容
公開鍵暗号アルゴリズムであるRSAのプロトコルの一つであるBoneh-Franckrinプロトコルの改良として二つの素数の積Nを共有することなく送信者、受信者の2人が共同で公開鍵と秘密鍵を生成するプロトコルを示す
Boneh-Franckrinプロトコルの流れ
1.候補の選択
AliceがP_a, Q_a 、BobがP_b,Q_bを独立して選びP=P_a+P_b ,Q=Q_a+Q_bを候補とする
2.Nを計算
AliceとBobの両者がN=PQを計算する
3.初期の素数判定
k個(k番目の素数までをかけると2^σを初めて超える)の小さな素数のそれぞれについてNがそれらで割り切れるかを調べる。
4.全ての素数判定
5.dの計算と共有
両当事者間で既知であるeを用いて解読指数dを計算する
Nを共有することのないプログラムへの改良
ここでは
・Nの計算
・初期の素数判定
の部分を改良する
Nの計算
AliceはP_a,Q_bをBobはP_b,Q_bを持っている。このときAliceのみが秘密裏にN=(P_a+P_b)(Q_a+Q_b) = P_aQ_a + P_aQ_b + P_bQ_a + P_bQ_bを計算する
一つ目の方法
a,b∈Rである公に知られている環Rを導入し、AliceがaをBobがbを持っているとする。このときx+y=abとなるｘをAliceが、ｙをBobがoblivious transferによって得ることでNを求めることができる ( https://tech.fressets.com/1624/ )
二つ目の方法
素数p>2^σとしGF(p)を設定することでNを求める
三つ目の方法
Homomorphic encryptionを用いてNを求める
初期の素数判定
候補Nが最初のk個の素数p_1,p_2,…,p_kのうちの一つで割り切れるかどうかを判定し、P,Qが素数であるかを判定する
ここではある候補が初期の素数判定に失敗した場合に、新たな候補を見つけだす際のより効率的な方法が２つ示されている
一つ目の方法
ある候補Nが捨てられた後、Aliceは前のP_a,Q_aを持ったままBobが新たなP_b,Q_bを選択することで新たな候補Nを見つけ出す。
二つ目の方法
homomorphic encryption protocolを用いてP_a,P_b,Q_a,Q_b mod p_iを選びN mod p_iを再計算する
この確率はP_a,P_b,Q_a,Q_bを選ぶ時よりも少なくなる
このプロトコルの性能
このNを共有することのないプロトコルの性能はσ=1024の時 実行時間はBoneh-Franklinプロトコルの約10倍以下、通信の複雑さは約42MB(改良した場合29MB)
