Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
環準同型を計算可能な公開鍵暗号方法、環準同型を計算可能な公開鍵暗号システム、送信装置、処理装置、受信装置、それらのプログラム及び記録媒体
説明

環準同型を計算可能な公開鍵暗号方法、環準同型を計算可能な公開鍵暗号システム、送信装置、処理装置、受信装置、それらのプログラム及び記録媒体

【課題】暗号文に対する演算で平文の加法に対応する新たな暗号文および平文の乗法に対応する新たな暗号文を計算可能で実用的な効率性を有する、環準同型を計算可能な公開鍵暗号方法を提供する。
【解決手段】加算について準同型性を持つ公開鍵暗号を利用し、送信装置と処理装置と受信装置とを用いて暗号化処理及び復号処理を行う。受信装置は処理に先立ち秘密鍵と公開鍵を生成し、公開鍵を公開する。送信装置は、2つのメッセージをそれぞれ暗号化して処理者に送信する。処理装置は、受信した暗号化された2つのメッセージに対して、受信装置と通信しつつ四則演算の組み合わせからなる演算を行い、演算結果の暗号文を受信装置に送信する。受信装置は、受信した暗号文から2つのメッセージが乗算されたメッセージを復号する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、コンピュータによる計算方式で、情報を暗号化したまま処理する環準同型を計算可能な公開鍵暗号方法、環準同型を計算可能な公開鍵暗号システム、送信装置、処理装置、受信装置、それらのプログラム及び記録媒体に関する。
【背景技術】
【0002】
暗号方式において、メッセージを暗号化したまま演算することができる方式を準同型暗号とよぶ。例えば、メッセージ(数値)a、bの暗号文 E(a)、E(b)から、a+bの暗号文E(a+b)が計算できるもの(加算に関して準同型)や、a・bの暗号文E(a・b)が計算できるもの(乗算に関して準同型)をいう。加算に関して準同型暗号の例として非特許文献1のPaillier暗号が、乗算に関して準同型暗号の例としてElGamal暗号やRSA暗号が、それぞれ挙げられる。
【0003】
乗算と加算の双方に関して準同型性を持つ暗号は環準同型暗号と呼ばれる。環準同型暗号では、平文に関する多項式の計算を暗号化したまま行うことができる。この性質は、暗号文を計算することによる、メッセージに対する論理回路の評価やデータベースの検索を可能にする。そのため、環準同型暗号の設計は長年の課題であったが、近年、Gentryが非特許文献2において環準同型暗号が存在することを示した。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】Pascal Paillier, "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes", EUROCRYPT'99, vol. 1592 of Lecture Notes in Computer Science, 2009, p.223-238
【非特許文献2】Craig Gentry, "Fully Homomorphic Encryption Using Ideal Lattices", Proceedings of the 41st annual ACM symposium on Theory of computing, 2009, p.169-178
【発明の概要】
【発明が解決しようとする課題】
【0005】
Gentryが非特許文献2において示した論証は、実用的な効率で動作する環準同型暗号を具体的に構成したものではなく、少なくとも効率性に問題がある。
【0006】
本発明の目的は、暗号文に対する演算で平文の加法に対応する新たな暗号文および平文の乗法に対応する新たな暗号文を計算可能で実用的な効率性を有する、環準同型を計算可能な公開鍵暗号方法、環準同型を計算可能な公開鍵暗号システム、送信装置、処理装置、受信装置、それらのプログラム及び記録媒体を提供することにある。
【課題を解決するための手段】
【0007】
本発明の環準同型を計算可能な公開鍵暗号方法及び公開鍵暗号システムは、加算について準同型性を持つ公開鍵暗号に基づき構成された公開鍵暗号方法及び公開鍵暗号システムであって、送信装置と処理装置と受信装置とが連携して、鍵生成ステップと暗号文生成ステップと第1準備ステップと第1通信ステップと第2準備ステップと第2通信ステップと復号ステップとを実行する。
【0008】
鍵生成ステップでは、受信装置が、任意の2つの大きな素数p,q、任意の整数g、ランダムな整数rを選び、n=p・qとして、c0=g・rn mod n2を求め、ランダムな整数a,bをa+b=1 mod nとなる数として選び、μ=c0a+bを求め、n,g,c0,μを公開鍵として公開し、p,q,a,bを秘密鍵として保持する。
【0009】
暗号文生成ステップでは、送信装置が、ランダムな整数xを選び、入力された2つのメッセージm1,m2に対する暗号文c1,c2をc1=gm1・xn mod n2、c2=gm2・xn mod n2により生成し、処理装置に送信する。
【0010】
第1準備ステップでは、処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ。
【0011】
第1通信ステップでは、第1処理サブステップと第1返信サブステップと第2処理サブステップと第3処理サブステップと第2返信ステップと第4処理サブステップを、最大t回(tはセキュリティパラメータkに対して無視できない値)繰り返して実行し、計算結果としての(w,u)が得られない場合には処理を中止する。
【0012】
第1処理サブステップでは、処理装置が、ランダムな2つの整数r1,r2を選び、暗号文w11=c1・c0r1,w21=c0r2を計算して、受信装置に送信する。
【0013】
第1返信サブステップでは、受信装置が、暗号文w11,w21からメッセージm11,m21をそれぞれ復号し、w'=w11a・m21・w21b・m11を計算して処理装置に返信する。
【0014】
第2処理サブステップでは、処理装置が、w=w'・μ-r1・r2を計算し、u=r2とし、L2の元(υ,s)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(w,u)をリストL1に追加する。
【0015】
第3処理サブステップでは、処理装置が、ランダムな2つの整数r3,r4を選び、暗号文w12=c1・c0r3,w22=c0r4を計算して、受信装置に送信する。
【0016】
第2返信サブステップでは、受信装置が、暗号文w12,w22からメッセージm12,m22をそれぞれ復号し、υ'=w12a・m22・w22b・m12を計算して処理装置に返信する。
【0017】
第4処理サブステップでは、処理装置が、υ=υ'・μ-r3・r4を計算し、s=r2とし、L1の元(w,u)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(υ,s)をリストL2に追加する。
【0018】
第2準備ステップでは、処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ。
【0019】
第2通信ステップでは、第5処理サブステップと第6処理サブステップと第3返信サブステップと第7処理サブステップと第8処理サブステップと第9処理サブステップと第10処理サブステップと第4返信サブステップと第11処理サブステップを、最大t回繰り返して実行し、暗号文としてのzが得られない場合には処理を中止する。
【0020】
第5処理サブステップでは、処理装置が、リストL3を空集合で初期化する。
【0021】
第6処理サブステップでは、処理装置が、ランダムな2つの整数r5,r6を選び、暗号文w13=c1r5,w23=c2・c0u・r6を計算して、受信装置に送信する。
【0022】
第3返信サブステップでは、受信装置が、暗号文w13,w23からメッセージm13,m23をそれぞれ復号し、z'=w13a・m23・w23b・m13を計算して処理装置に返信する。
【0023】
第7処理サブステップでは、処理装置が、z''=z'w-r5・r6を計算し、(z'',r5)をリストL3に追加する。
【0024】
第8処理サブステップでは、処理装置が、リストL3の全ての元 (z1,x1),(z2,x2),・・・,(zi,xi),・・・について、x1,x2,・・・,xi,・・・の最大公約数が1であるかどうかを判定し、もし1であれば、Σiyi・xi=1となる整数y1,y2,・・・,yi,・・・を計算してz=Πiziyiとし、1でなければ第5処理サブステップに戻る。
【0025】
第9処理サブステップでは、処理装置が、L2の元(υ,s)で、zd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければそのzをリストL1に追加する。
【0026】
第10処理サブステップでは、処理装置が、ランダムな2つの整数r7,r8を選び、暗号文w14=c1r7,w24=c2d・c0u・r8を計算して、受信装置に送信する。
【0027】
第4返信サブステップでは、受信装置が、暗号文w14,w24からメッセージm14,m24をそれぞれ復号し、υ'=w14a・m24・w24b・m14を計算して処理装置に返信する。
【0028】
第11処理サブステップでは、処理装置が、υ=υ'・μ-r7・r8を計算し、s=r7とし、L1の元zでzd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければ(υ,s)をリストL2に追加する。
【0029】
復号ステップでは、受信装置が処理装置から受信した暗号文zからメッセージm1・m2を、
【0030】
【数1】

【0031】
により復号する。
【発明の効果】
【0032】
本発明の環準同型を計算可能な公開鍵暗号方法、環準同型を計算可能な公開鍵暗号システム、送信装置、処理装置、受信装置、それらのプログラム及び記録媒体によれば、実用的な効率性にて暗号文に対する演算で平文の加法に対応する新たな暗号文および平文の乗法に対応する新たな暗号文を計算することができる。これにより、公開鍵暗号の利便性が向上し、特に、代数的回路に対してデータを暗号化したままメッセージに対する演算を行うことが可能となる。
【図面の簡単な説明】
【0033】
【図1】環準同型を計算可能な公開鍵暗号システム100の構成を示すブロック図。
【図2】環準同型を計算可能な公開鍵暗号方法の処理フロー例を示す図。
【発明を実施するための形態】
【0034】
図1に、本発明の環準同型を計算可能な公開鍵暗号システム100の構成を示すブロック図を、図2に当該システムに係る公開鍵暗号方法の各処理ステップのフロー図を示す。本発明の環準同型を計算可能な公開鍵暗号システム100は、送信装置110と処理装置120と受信装置130とから構成される。
【0035】
本発明においては、加算について準同型性を持つ公開鍵暗号方式であるPaillier暗号(非特許文献1)を基礎として、メッセージを暗号化したまま安全に乗算を行うシステムを構成する。なお、加算について準同型性を持つ公開鍵暗号方式においては、2つのPaillier暗号文c1,c2の加算の演算は、c1・c2 mod n2である。すなわち、c1を復号して得られる平文がm1で、c2を復号して得られる平文がm2であるとき、c1・c2 mod n2を復号して得られる平文はm1+m2 mod nである。従って、加算については本発明のシステム構成の下で、送信装置110で2つの平文m1,m2について生成された2つのPaillier暗号文c1,c2を処理装置120に送信し、それを受信した処理装置120がc1・c2 mod n2の演算を行い、これを受信装置130に送信することで、受信装置130は平文m1+m2 mod nを復号することができる。
【0036】
一方、乗算については安全な乗算を実現するため、処理装置120と受信装置130との間で通信しつつ処理を行う。具体的には、処理装置120から任意の2つのPaillier暗号文w1,w2が受信装置130に与えられたとき、受信装置130は、w1を復号してメッセージm1を、w2を復号してメッセージm2を計算した上で、w1a・m2・w2b・m1(a,bは受信装置130の秘密鍵)を計算して処理装置120に返信する。このように処理装置120を利用することで安全性が損なわれることがないよう、本発明では誤りを訂正することが可能な形態でアルゴリズムを構成する。本発明のアルゴリズムでは、「処理装置がメッセージの内容を知ることがないという特徴と、処理装置が受信装置と通信しつつ暗号文を処理する際に、処理中の暗号文が受信者に漏洩することがないという特徴と、処理装置が受信装置と通信しつつ暗号文を処理する際に、何者かが正規の受信者になりすましを試みた場合に処理装置は真の受信装置による応答か否かを選別することが可能であるという特徴とを有する。
【0037】
以下、環準同型を計算可能な公開鍵暗号システム100の具体的な処理内容について説明する。
【0038】
まず、受信装置130が、通信に先立ち秘密鍵と公開鍵を生成する(S1)。具体的には、Paillier暗号を構成するために好適な任意の2つの大きな素数p,qと、Paillier暗号を構成するために好適な整数g(0〜n2-1の元で、例えば2)と、ランダムな整数r(例えば0≦r<n)とを選ぶ。そして、n=p・qとして、c0=g・rn mod n2を求め、ランダムな整数a,bをa+b=1 mod nとなる数として選び、μ=c0a+bを求め、n,g,c0,μを公開鍵として公開し、p,q,a,bを秘密鍵として保持する。
【0039】
続いて、送信装置110が、ランダムな整数x(例えば0≦x<n)を選び、入力された2つのメッセージm1,m2(例えば0≦m1<n、0≦m2<n)に対するPaillier暗号文c1,c2をc1=gm1・xn mod n2、c2=gm2・xn mod n2により生成し、処理装置120に送信する(S2)。
【0040】
続いて、処理装置120と受信装置130は、以下の処理によりc0とc1との乗算に関する量を計算する。
【0041】
まず、処理装置120が、2つのリストL1,L2を空集合で初期化し、ランダムな整数d(例えば2≦d≦2k、kはセキュリティパラメータ)を選ぶ(S3)。
【0042】
続いて、ランダムな2つの整数r1,r2(例えば1≦r1≦2k・n2、1≦r2≦2k・n2)を選び、Paillier暗号文w11=c1・c0r1,w21=c0r2を計算して、受信装置130に送信する(S4−1)。
【0043】
続いて、受信装置130が、Paillier暗号文w11,w21からメッセージm11,m21をそれぞれ復号し、w'=w11a・m21・w21b・m11を計算して処理装置に返信する(S4−2)。
【0044】
続いて、処理装置120が、w=w'・μ-r1・r2を計算し、u=r2とし、L2の元(υ,s)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果としてS5以降の処理に進む。一方、存在しなければその(w,u)をリストL1に追加する(S4−3)。
【0045】
続いて、ランダムな2つの整数r3,r4(例えば1≦r3≦2k・n2、1≦r4≦2k・n2)を選び、Paillier暗号文w12=c1・c0r3,w22=c0r4を計算して、受信装置130に送信する(S4−4)。
【0046】
続いて、受信装置130が、Paillier暗号文w12,w22からメッセージm12,m22をそれぞれ復号し、υ'=w12a・m22・w22b・m12を計算して処理装置120に返信する(S4−5)。
【0047】
続いて、処理装置120が、υ=υ'・μ-r3・r4を計算し、s=r2とし、L1の元(w,u)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果としてS5以降の処理に進む。一方、存在しなければ、その(υ,s)をリストL2に追加する(S4−6)。
【0048】
S4−1〜S4−6の各ステップの処理を最大t回繰り返して実行し、計算結果としての(w,u)が得られない場合には、信頼性が確保されていないとして処理を中止する。ここで、tは処理装置120が成りすまし攻撃を受けたときの受信装置130に対して要求する信頼性であり、セキュリティパラメータkに関して無視できない確率(例えば、1/kなど)とする。
【0049】
上記計算結果として得られた(w,u)について、wはc1とc0の乗算のu乗となっている。計算結果としての(w,u)が得られた場合には、続いて以下の処理によりc1とcの乗算を計算する。
【0050】
まず、処理装置120が、2つのリストL1,L2を空集合で初期化し、ランダムな整数d(例えば2≦d≦2k)を選ぶ(S5)。
【0051】
続いて、リストL3を空集合で初期化する(S6−1)。
【0052】
続いて、ランダムな2つの整数r5,r6(例えば1≦r5≦2k・n2、1≦r6≦2k・n2)を選び、Paillier暗号文w13=c1r5,w23=c2・c0u・r6を計算して、受信装置130に送信する(S6−2)。
【0053】
続いて、受信装置130が、Paillier暗号文w13,w23からメッセージm13,m23をそれぞれ復号し、z'=w13a・m23・w23b・m13を計算して処理装置120に返信する(S6−3)。
【0054】
続いて、処理装置120が、z''=z'・w-r5・r6を計算し、(z'',r5)をリストL3に追加する(S6−4)。
【0055】
続いて、リストL3の全ての元 (z1,x1),(z2,x2),・・・,(zi,xi),・・・について、x1,x2,・・・,xi,・・・の最大公約数が1であるかどうかを判定し、もし1であれば、Σiyi・xi=1となる整数y1,y2,・・・,yi,・・・を計算してz=Πiziyiとし、1でなければS6−1の処理に戻る(S6−5)。
【0056】
続いて、L2の元(υ,s)で、zd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置130に返信してS7以降の処理に進む。一方、存在しなければそのzをリストL1に追加する(S6−6)。
【0057】
続いて、ランダムな2つの整数r7,r8(例えば1≦r7≦2k・n2、1≦r8≦2k・n2)を選び、Paillier暗号文w14=c1r7,w24=c2d・c0u・r8を計算して、受信装置130に送信する(S6−7)。
【0058】
続いて、受信装置130が、Paillier暗号文w14,w24からメッセージm14,m24をそれぞれ復号し、υ'=w14a・m24・w24b・m14を計算して処理装置120に返信する(S6−8)。
【0059】
続いて、処理装置120が、υ=υ'・μ-r7・r8を計算し、s=r7とし、L1の元zでzd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置130に返信してS7以降の処理に進む。一方、存在しなければ(υ,s)をリストL2に追加する(S6−9)。
【0060】
S6−1からS6−9の各ステップを最大t回繰り返して実行し、暗号文としてのzが得られない場合には、信頼性が確保されていないとして処理を中止する。
【0061】
上記計算結果として得られたzについて、zはm1のPaillier暗号文c1とm2のPaillier暗号文c2との乗算(=m1・m2のPaillier暗号文)となっている。以上のS1〜S6の処理により、Paillier暗号文c1,c2について乗算を行うことができる。
【0062】
そして、受信装置130が、処理装置120から受信したPaillier暗号文zからメッセージm1・m2を、
【0063】
【数2】

【0064】
により復号する(S7)。
【0065】
以上のように、本発明の環準同型を計算可能な公開鍵暗号方法及び環準同型を計算可能な公開鍵暗号システムによれば、実用的な効率性にて暗号文に対する演算で平文の加法に対応する新たな暗号文および平文の乗法に対応する新たな暗号文を計算することができる。これにより、公開鍵暗号の利便性が向上し、特に、代数的回路に対してデータを暗号化したままメッセージに対する演算を行うことが可能となる。
【0066】
本発明の環準同型を計算可能な公開鍵暗号システム、それを構成する送信装置、処理装置、及び受信装置をコンピュータによって実現する場合、送信装置、処理装置及び受信装置が担う処理機能はプログラムによって記述される。そしてパソコンや携帯端末上で、入力手段や各種記憶手段とCPUとのデータのやりとりを通じてこのプログラムを実行することにより、ハードウェアとソフトウェアが協働し、上記処理機能がコンピュータ上で実現されて本発明の環準同型を計算可能な公開鍵暗号システムの作用効果を奏する。なおこの場合、処理機能の少なくとも一部をハードウェア的に実現することとしてもよい。また、上記の各種処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【0067】
上記の処理機能を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD(Digital Versatile Disc)、DVD−RAM(Random Access Memory)、CD−ROM(Compact Disc Read Only Memory)、CD−R(Recordable)/RW(ReWritable)等を、光磁気記録媒体として、MO(Magneto-Optical disc)等を、半導体メモリとしてEEP−ROM(Electronically Erasable and Programmable-Read Only Memory)等を用いることができる。
【0068】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0069】
また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。

【特許請求の範囲】
【請求項1】
加算について準同型性を持つ公開鍵暗号に基づき構成された環準同型を計算可能な公開鍵暗号方法であって、
受信装置が、任意の2つの大きな素数p,q、任意の整数g、ランダムな整数rを選び、n=p・qとして、c0=g・rnmod n2を求め、ランダムな整数a,bをa+b=1 mod nとなる数として選び、μ=c0a+bを求め、n,g,c0,μを公開鍵として公開し、p,q,a,bを秘密鍵として保持する鍵生成ステップと、
送信装置が、ランダムな整数xを選び、入力された2つのメッセージm1,m2に対する暗号文c1,c2をc1=gm1・xn mod n2、c2=gm2・xn mod n2により生成し、処理装置に送信する暗号文生成ステップと、
処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ第1準備ステップと、
処理装置が、ランダムな2つの整数r1,r2を選び、暗号文w11=c1・c0r1,w21=c0r2を計算して、受信装置に送信する第1処理サブステップと、
受信装置が、暗号文w11,w21からメッセージm11,m21をそれぞれ復号し、w'=w11a・m21・w21b・m11を計算して処理装置に返信する第1返信サブステップと、
処理装置が、w=w'・μ-r1・r2を計算し、u=r2とし、L2の元(υ,s)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(w,u)をリストL1に追加する第2処理サブステップと、
処理装置が、ランダムな2つの整数r3,r4を選び、暗号文w12=c1・c0r3,w22=c0r4を計算して、受信装置に送信する第3処理サブステップと、
受信装置が、暗号文w12,w22からメッセージm12,m22をそれぞれ復号し、υ'=w12a・m22・w22b・m12を計算して処理装置に返信する第2返信サブステップと、
処理装置が、υ=υ'・μ-r3・r4を計算し、s=r2とし、L1の元(w,u)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(υ,s)をリストL2に追加する第4処理サブステップ、
の各サブステップを最大t回 (tはセキュリティパラメータkに対して無視できない値)繰り返して実行し、計算結果としての(w,u)が得られない場合には処理を中止する第1通信ステップと、
計算結果としての(w,u)が得られた場合に、
処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ第2準備ステップと、
処理装置が、リストL3を空集合で初期化する第5処理サブステップと、
処理装置が、ランダムな2つの整数r5,r6を選び、暗号文w13=c1r5,w23=c2・c0u・r6を計算して、受信装置に送信する第6処理サブステップと、
受信装置が、暗号文w13,w23からメッセージm13,m23をそれぞれ復号し、z'=w13a・m23・w23b・m13を計算して処理装置に返信する第3返信サブステップと、
処理装置が、z''=z'・w-r5・r6を計算し、(z'',r5)をリストL3に追加する第7処理サブステップと、
処理装置が、リストL3の全ての元 (z1,x1),(z2,x2),・・・,(zi,xi),・・・について、x1,x2,・・・,xi,・・・の最大公約数が1であるかどうかを判定し、もし1であれば、Σiyi・xi=1となる整数y1,y2,・・・,yi,・・・を計算してz=Πiziyiとし、1でなければ第5処理サブステップに戻る、第8処理サブステップと、
処理装置が、L2の元(υ,s)で、zd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければそのzをリストL1に追加する第9処理サブステップと、
処理装置が、ランダムな2つの整数r7,r8を選び、暗号文w14=c1r7,w24=c2d・c0u・r8を計算して、受信装置に送信する第10処理サブステップと、
受信装置が、暗号文w14,w24からメッセージm14,m24をそれぞれ復号し、υ'=w14a・m24・w24b・m14を計算して処理装置に返信する第4返信サブステップと、
処理装置が、υ=υ'・μ-r7・r8を計算し、s=r7とし、L1の元zでzd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければ(υ,s)をリストL2に追加する第11処理サブステップ、
の各サブステップを最大t回(tはセキュリティパラメータkに対して無視できない値)繰り返して実行し、暗号文としてのzが得られない場合には処理を中止する第2通信ステップと、
受信装置が、処理装置から受信した暗号文zからメッセージm1・m2を、
【数3】


により復号する復号ステップと、
を実行する環準同型を計算可能な公開鍵暗号方法。
【請求項2】
加算について準同型性を持つ公開鍵暗号に基づき構成された環準同型を計算可能な公開鍵暗号システムであって、
送信装置と処理装置と受信装置とを備え、
受信装置が、任意の2つの大きな素数p,q、任意の整数g、ランダムな整数rを選び、n=p・qとして、c0=g・rnmod n2を求め、ランダムな整数a,bをa+b=1 mod nとなる数として選び、μ=c0a+bを求め、n,g,c0,μを公開鍵として公開し、p,q,a,bを秘密鍵として保持する鍵生成ステップと、
送信装置が、ランダムな整数xを選び、入力された2つのメッセージm1,m2に対する暗号文c1,c2をc1=gm1・xn mod n2、c2=gm2・xn mod n2により生成し、処理装置に送信する暗号文生成ステップと、
処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ第1準備ステップと、
処理装置が、ランダムな2つの整数r1,r2を選び、暗号文w11=c1・c0r1,w21=c0r2を計算して、受信装置に送信する第1処理サブステップと、
受信装置が、暗号文w11,w21からメッセージm11,m21をそれぞれ復号し、w'=w11a・m21・w21b・m11を計算して処理装置に返信する第1返信サブステップと、
処理装置が、w=w'・μ-r1・r2を計算し、u=r2とし、L2の元(υ,s)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(w,u)をリストL1に追加する第2処理サブステップと、
処理装置が、ランダムな2つの整数r3,r4を選び、暗号文w12=c1・c0r3,w22=c0r4を計算して、受信装置に送信する第3処理サブステップと、
受信装置が、暗号文w12,w22からメッセージm12,m22をそれぞれ復号し、υ'=w12a・m22・w22b・m12を計算して処理装置に返信する第2返信サブステップと、
処理装置が、υ=υ'μ-r3・r4を計算し、s=r2とし、L1の元(w,u)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果として第1通信ステップの処理を終了し、存在しなければその(υ,s)をリストL2に追加する第4処理サブステップ、
の各サブステップを最大t回(tはセキュリティパラメータkに対して無視できない値)繰り返して実行し、計算結果としての(w,u)が得られない場合には処理を中止する第1通信ステップと、
計算結果としての(w,u)が得られた場合に、
処理装置が、2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選ぶ第2準備ステップと、
処理装置が、リストL3を空集合で初期化する第5処理サブステップと、
処理装置が、ランダムな2つの整数r5,r6を選び、暗号文w13=c1r5,w23=c2・c0u・r6を計算して、受信装置に送信する第6処理サブステップと、
受信装置が、暗号文w13,w23からメッセージm13,m23をそれぞれ復号し、z'=w13a・m23・w23b・m13を計算して処理装置に返信する第3返信サブステップと、
処理装置が、z''=z'・w-r5・r6を計算し、(z'',r5)をリストL3に追加する第7処理サブステップと、
処理装置が、リストL3の全ての元 (z1,x1),(z2,x2),・・・,(zi,xi),・・・について、x1,x2,・・・,xi,・・・の最大公約数が1であるかどうかを判定し、もし1であれば、Σiyi・xi=1となる整数y1,y2,・・・,yi,・・・を計算してz=Πiziyiとし、1でなければ第5処理サブステップに戻る、第8処理サブステップと、
処理装置が、L2の元(υ,s)で、zd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければそのzをリストL1に追加する第9処理サブステップと、
処理装置が、ランダムな2つの整数r7,r8を選び、暗号文w14=c1r7,w24=c2d・c0u・r8を計算して、受信装置に送信する第10処理サブステップと、
受信装置が、暗号文w14,w24からメッセージm14,m24をそれぞれ復号し、υ'=w14a・m24・w24b・m14を計算して処理装置に返信する第4返信サブステップと、
処理装置が、υ=υ'μ-r7・r8を計算し、s=r7とし、L1の元zでzd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として受信装置に返信して第2通信ステップの処理を終了し、存在しなければ(υ,s)をリストL2に追加する第11処理サブステップ、
の各サブステップを最大t回 (tはセキュリティパラメータkに対して無視できない値)繰り返して実行し、暗号文としてのzが得られない場合には処理を中止する第2通信ステップと、
受信装置が、処理装置から受信した暗号文zからメッセージm1・m2を、
【数4】


により復号する復号ステップと、
を実行する環準同型を計算可能な公開鍵暗号システム。
【請求項3】
任意の2つの大きな素数p,qからn=p・qにより得られたnと任意の整数gとが公開鍵として公開され、これらを用い、
ランダムな整数xを選び、入力された2つのメッセージm1,m2に対する暗号文c1,c2をc1=gm1・xn mod n2、c2=gm2・xn mod n2により生成する送信装置。
【請求項4】
任意の2つの大きな素数p,q、任意の整数g、ランダムな整数rから、n=p・qとしてc0=g・rnmod n2により求められたc0、a+b=1 mod nとなる数として選ばれたランダムな整数a,bからμ=c0a+bにより求められたμに関し、n,g,c0,μが公開鍵として公開され、これらを用い、
2つのリストL1,L2を空集合で初期化し、ランダムな整数dを選び、
ランダムな2つの整数r1,r2を選び、入力された暗号文c1について、暗号文w11=c1・c0r1,w21=c0r2を計算して出力し、
入力されたw'=w11a・m21・w21b・m11(m11,m21はw11,w21から復号されたメッセージ)について、w=w'・μ-r1・r2を計算し、u=r2とし、L2の元(υ,s)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果とし、存在しなければその(w,u)をリストL1に追加し、
ランダムな2つの整数r3,r4を選び、暗号文w12=c1・c0r3,w22=c0r4を計算して出力し、
入力されたυ'=w12a・m22・w22b・m12(m12,m22はw12,w22から復号されたメッセージ)について、υ=υ'・μ-r3・r4を計算し、s=r2とし、L1の元(w,u)でwd・s=υu mod n2またはwd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、その(w,u)を計算結果とし、存在しなければその(υ,s)をリストL2に追加し、
前記ランダムな2つの整数r1,r2の選定以降の処理を最大t回(tはセキュリティパラメータkに対して無視できない値)繰り返して実行して、計算結果としての(w,u)が得られない場合には処理を中止し、
計算結果としての(w,u)が得られた場合に、
2つのリストL1,L2を空集合で初期化し、
リストL3を空集合で初期化し、
ランダムな2つの整数r5,r6を選び、暗号文w13=c1r5,w23=c2・c0u・r6を計算して出力し、
入力されたz'=w13a・m23・w23b・m13(m13,m23はw13,w23から復号されたメッセージ)について、z''=z'・w-r5・r6を計算し、(z'',r5)をリストL3に追加し、
リストL3の全ての元 (z1,x1),(z2,x2),・・・,(zi,xi),・・・について、x1,x2,・・・,xi,・・・の最大公約数が1であるかどうかを判定し、もし1であれば、Σiyi・xi=1となる整数y1,y2,・・・,yi,・・・を計算してz=Πiziyiとし、1でなければ前記リストL3の空集合による初期化以降の処理を再度実行し、
L2の元(υ,s)で、zd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として出力して処理を終了し、存在しなければそのzをリストL1に追加し、
ランダムな2つの整数r7,r8を選び、暗号文w14=c1r7,w24=c2d・c0u・r8を計算して出力し、
入力されたυ'=w14a・m24・w24b・m14(m14,m24はw14,w24から復号されたメッセージ)について、υ=υ'・μ-r7・r8を計算し、s=r7とし、L1の元zでzd・s=υu mod n2またはzd・s=-υu mod n2となるものが存在するかどうかを判定し、もし存在すれば、そのzを暗号文として出力して処理を終了し、存在しなければ(υ,s)をリストL2に追加し、
前記リストL3の空集合による初期化以降の処理を最大t回 (tはkに対して無視できない値)繰り返して実行し、暗号文としてのzが得られない場合には処理を中止する
処理装置。
【請求項5】
任意の2つの大きな素数p,q、任意の整数g、ランダムな整数rを選び、n=p・qとして、c0=g・rnmod n2を求め、ランダムな整数a,bをa+b=1 mod nとなる数として選び、μ=c0a+bを求め、n,g,c0,μを公開鍵として公開し、p,q,a,bを秘密鍵として保持し、
入力された暗号文w1,w2からメッセージm1,m2をそれぞれ復号し、w1a・m2・w2b・m1を計算して出力し、
入力された暗号文zからメッセージm1・m2を、
【数5】


により復号する
受信装置。
【請求項6】
請求項2乃至5のいずれかに記載のシステム又は装置としてコンピュータを機能させるためのプログラム。
【請求項7】
請求項2乃至5のいずれかに記載のシステム又は装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。

【図1】
image rotate

【図2】
image rotate


【公開番号】特開2011−227193(P2011−227193A)
【公開日】平成23年11月10日(2011.11.10)
【国際特許分類】
【出願番号】特願2010−95131(P2010−95131)
【出願日】平成22年4月16日(2010.4.16)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】