暗号システム、暗号方法、プログラム、および、情報記録媒体
【課題】複数の宛先への異なるメッセージを１つの暗号文にしたり、秘密投票に応用できる暗号システム等を提供する。
【解決手段】暗号システム１０１において、秘密鍵計算部１０２は秘密鍵p[1],…,p[s]を計算し、公開鍵計算部１０３は公開鍵g[1],…,g[s]を計算し、サンプリング部１０４は当該秘密鍵の積n = p[1]…p[s]に基づいてサンプルを選び、符号化部１０５はx[1],…,x[s]をg[1]x[1]…g[s]x[s]に符号化し、暗号部１０６は平文を符号化部１０５に与えた結果とサンプリング部１０４に選ばせたサンプルを乗じて暗号文zとし、復号部１０７は暗号文zにOkamoto-Uchiyamaの対数関数に基づく関数を適用して復号文を得る。
【解決手段】暗号システム１０１において、秘密鍵計算部１０２は秘密鍵p[1],…,p[s]を計算し、公開鍵計算部１０３は公開鍵g[1],…,g[s]を計算し、サンプリング部１０４は当該秘密鍵の積n = p[1]…p[s]に基づいてサンプルを選び、符号化部１０５はx[1],…,x[s]をg[1]x[1]…g[s]x[s]に符号化し、暗号部１０６は平文を符号化部１０５に与えた結果とサンプリング部１０４に選ばせたサンプルを乗じて暗号文zとし、復号部１０７は暗号文zにOkamoto-Uchiyamaの対数関数に基づく関数を適用して復号文を得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体に関する。
【背景技術】
【０００２】
従来から各種の公開鍵暗号技術が提案されており、このような公開鍵暗号については、以下の文献に開示がされている。
【非特許文献１】Okamoto T.and Uchiyama S., A New Public-key Cryptosystem as Secure as Factoring, Nyberg，K.(ed.), EUROCRYPT 1998，LNCS, vol.1403, pp.308-318, Springer，Heidelberg, １９９８年
【０００３】
[非特許文献１]では、Okamoto-Uchiyamaの対数関数Lpを利用した公開鍵暗号技術が提案されている。ここで、対数関数Lpとは、以下のように定義される。
【０００４】
すなわち、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
を考える。
【０００５】
Γpは、その位数（order）がpの羃に等しい最大部分群である。
【０００６】
群(Z/p2)*の位数は、オイラーのトーティエント（totient）関数φにより、
φ(p2) = p(p-1)
と書くことができる。
【０００７】
したがって、(Z/p2)*は、Γpと、位数(p-1)の部分群の内部直和（internal direct sum）である。
【０００８】
なお、本願では、AとBの直和をA (+) Bのように記載することとする。一般的な数学記法では、(+)は、+記号を丸で囲んだ符号で表記される。
【０００９】
ここで、x (mod p2)からx (mod p)への射（mapping）は、(Z/p2)*から(Z/p)*の上への準同型写像（ホモモルフィズム；homomorphism）であるから、(Z/p2)*/Γpは、(Z/p)*と準同形である。
【００１０】
したがって、位数p-1の部分群は、(Z/p)*に対する同型（アイソモルフィズム；isomorphism）であり、巡回的である。
【００１１】
一方、Γpは、位数pであり、巡回的である。
【００１２】
pとp-1は互いに素であるから、(Z/p)*は、巡回的である。
【００１３】
ここで、x≡1 (mod p)と仮定すると、あるc∈Zが存在して
x = cp + 1
である。したがって、
xp = (cp + 1)p = Σi=0p pCi(cp)p-i
と展開できる。ここで、pCiは２項係数を意味し、
pC0 = 1；
pC1 = pCp-1 = p；
pC2 = pCp-2 = p(p-1)/2； …
であるから、
Σi=0p pCi(cp)p-i = 1 + (cp)p + (cp)2p(p-1)/2 + …
のように展開できる。
【００１４】
したがって、あるd∈Zが存在して
xp = dp2 + 1
である。
【００１５】
これによって、x≡1 (mod p)ならば、xp≡1 (mod p2)であることが証明された。
【００１６】
したがって、
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
である。
【００１７】
すると、任意のx∈Γpに対して
x - 1 = ap
を満たす整数aが一意に定まる。
【００１８】
そこで、対数関数Lpは、当該xおよびaによって、
Lp(x) = a (mod p)
と定義される。Lpは、Γpから加算群(Z/p,+)の中へのホモモルフィズムである。
【００１９】
さらに、Lpは、Γpから加算群(Z/p,+)の上へのアイソモルフィズムである。
【００２０】
すなわち、任意のa，b∈Γpに対して
Lp(ab) = Lp(a) + Lp(a) (mod p)
が成立する。
【００２１】
特に、任意のx，y∈Γpに対して、m∈Z/pについて
y = xm
が成立すれば、
Lp(y) = mLp(x)
である。
【００２２】
これから、Lp(x)≠0である限り、
m = Lp(y)Lp(x)-1
である。
【００２３】
Lp(x)=0となるのは、xがΓpの単位元(identity element)である場合であり、かつ、その場合に限られる。
【００２４】
そして、このようなホモモルフィズムにおける性質を利用した新たな公開鍵暗号の技術の開発が進められている。
【発明の開示】
【発明が解決しようとする課題】
【００２５】
ここで、複数の平文を１つの暗号文に暗号化する一方で、当該平文を個別に復号できるような暗号システム、特に、複数の宛先に対する異なる平文を安全に１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得でき、応用によっては、複数の暗号文を個別に復号することなく、平文の計算が可能となるような暗号システムが強く望まれている。
【００２６】
本発明は、以上の課題を解決するもので、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２７】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【００２８】
本発明の第１の観点に係る暗号システムは、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用い、公開鍵計算部、サンプリング部、符号化部、暗号部、復号部を有し、以下のように構成する。
【００２９】
すなわち、公開鍵計算部は、当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする。
【００３０】
一方、サンプリング部は、当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングする。
【００３１】
さらに、符号化部は、整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する。
【００３２】
そして、暗号部は、整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、符号化部に符号化させ、サンプリング部にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る。
【００３３】
一方、復号部は、当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る。
【００３４】
また、本発明の暗号システムは、秘密鍵計算部をさらに備え、以下のように構成することができる。
【００３５】
すなわち、秘密鍵計算部は、サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする。
【００３６】
また、本発明の暗号システムにおいて、
s = 4
であり、当該暗号システムは、暗号装置、第１復号装置、第２復号装置を有し、以下のように構成することができる。
【００３７】
すなわち、当該第１復号装置は、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、当該第２復号装置は、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、当該第１復号装置は、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、当該第２復号装置は、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、当該両者にて当該素であることが確認されたら、当該第１暗号装置は、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置は、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]として、秘密鍵計算部として機能する。
【００３８】
一方、当該第１復号装置は、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、当該第２復号装置は、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開して、公開鍵計算部として機能する。
【００３９】
さらに、当該第１復号装置は、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、当該第２復号装置は、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、当該暗号装置は、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングして、サンプリング部として機能する。
【００４０】
そして、暗号装置は、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化して、符号化部として機能する。
【００４１】
一方、暗号装置は、符号化部に当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、サンプリング部にサンプリングさせたrを乗じ、暗号文zを得て、暗号部として機能する。
【００４２】
さらに、第１復号装置は、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して第２復号装置に公開し、第２復号装置は、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して第１復号装置に公開し、第１復号装置は、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、第２復号装置は、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、復号部として機能する。
【００４３】
また、本発明の暗号システムにおいて、暗号部は、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を復号部に与えるように構成することができる。
【００４４】
この場合、復号部では、もとの平文の各要素同士を加算したものが、復号文として得られることになる。
【００４５】
本発明のその他の観点に係る暗号方法は、上記暗号システムが実行する暗号方法である。
【００４６】
典型的には、当該暗号方法は、上記の暗号装置、第１復号装置、第２復号装置が実行する。
【００４７】
本発明の他の観点に係るプログラムは、コンピュータもしくはコンピュータ群を、上記暗号システムの各部として機能させるように構成する。
【００４８】
典型的には、当該プログラムは、３台のコンピュータを、上記の暗号装置、第１復号装置、第２復号装置として機能させるように構成する。
【００４９】
本発明の他の観点に係るコンピュータ読取可能な情報記録媒体は、上記のプログラムを記録するように構成する。たとえば、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記録することができる。
【００５０】
なお、コンピュータもしくはコンピュータ群が、上記プログラムを実行することによって、本発明の暗号システムが実現されるが、当該プログラムは、コンピュータ通信網を介して配布・販売することができる。また、上記情報記憶媒体は、当該コンピュータとは、とは独立して配布・販売することができる。
【発明の効果】
【００５１】
本発明によれば、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することができる。
【発明を実施するための最良の形態】
【００５２】
以下に本発明の実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【実施例１】
【００５３】
図１は、本発明の実施形態の１つに係る暗号システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【００５４】
暗号システム１０１は、秘密鍵計算部１０２、公開鍵計算部１０３、サンプリング部１０４、符号化部１０５、暗号部１０６、復号部１０７を備え、典型的には、コンピュータ通信網を介して相互に通信可能な複数の復号装置１１１および暗号装置１１２からなるコンピュータ群によって実現される。
【００５５】
具体的には、秘密鍵計算部１０２は、復号装置１１１によって実現され、公開鍵計算部１０３は、復号装置１１１によって実現され、サンプリング部１０４は、復号装置１１１によって実現され、符号化部１０５は、暗号装置１１２によって実現され、暗号部１０６は、暗号装置１１２によって実現され、復号部１０７は、復号装置１１１によって実現される。
【００５６】
各コンピュータは、ＣＰＵ（Central Processing Unit）の制御の下、ＮＩＣ（Network Interface Card）を介して相互に通信可能に接続され、ＲＡＭ（Random Access Memory）を一時記憶領域とし、ＲＯＭ（Read Only Memory）やＨＤ（Hard Disk）に格納されたプログラムをＣＰＵが実行して、各種の計算を行うことで、各復号装置１１１や暗号装置１１２が実現される。
【００５７】
本実施形態に係る暗号システム１０１では、上記のように、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
とを用いる。これは、Okamoto-Uchiyamaの対数関数である。
【００５８】
以下、適宜、s = 4であり、かつ、１台の暗号装置１１２と２台の復号装置１１１の組み合わせにより暗号システム１０１が実現される場合を典型例としてあげて説明するが、本発明の原理は、復号装置をさらに増やした場合にも適用可能であり、そのような実施形態についても本発明の範囲に含まれる。
【００５９】
（秘密鍵の計算）
まず、秘密鍵計算部１０２における処理について説明する。図２は、秘密鍵計算部１０２により実行される秘密鍵計算処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００６０】
まず、秘密鍵計算部１０２は、サイズkの互いに異なる素数
q[1]，…，q[s]
を選択する。上記典型例では、第１の復号装置１１１にて、q[1]，q[2]を選択し、第２の復号装置１１１にて、q[3]，q[4]を選択して、これはそのまま秘密としておく（ステップＳ２０１）。
【００６１】
ここで選択される素数は、通常の公開鍵暗号と同様に十分な大きさを持つものが望ましく、また、選択には、たとえばユーザがキーボードを押す間隔や現在の時刻などの条件を乱数の種として使用して、素数を生成することが望ましい。
【００６２】
ついで、第１の復号装置１１１は、積q[1]q[2]を計算し、第２の復号装置１１１は、積q[3]q[4]を計算する（ステップＳ２０２）。
【００６３】
さらに、第１の復号装置１１１は、自身が計算した積q[1]q[2]を他の復号装置１１１に通知し、第２の復号装置１１１は、自身が計算した積q[3]q[4]を、他の復号装置１１１に通知する。すなわち、各復号装置１１１は、自身が計算した積をコンピュータ通信網を介して他の復号装置１１１と交換して、互いに公開する（ステップＳ２０３）。
【００６４】
巨大な数の素因数分解は困難である、ということが公開鍵暗号の根本原理となっており、第２の復号装置１１１は、積q[1]q[2]を受け取ったとしても、これを素因数分解してq[1]，q[2]を得ることは困難であり、第１の復号装置１１１は、積q[3]q[4]を受け取ったとしても、これを素因数分解してq[3]，q[4]を得ることは困難である。したがって、それぞれの復号装置１１１がステップＳ２０１にて生成した素数は、秘密に保たれる。
【００６５】
そして、第１の復号装置１１１は、他の復号装置１１１から受け取った積q[3]q[4]が、自身の生成した素数から得られる数q[1]-1およびq[2]-1に対して素であるか否かを判断し、第２復号装置１１１は、他の復号装置１１１から受け取った積q[1]q[2]が、自身の生成した素数から得られる数q[3]-1およびq[4]-1に対して素であるか否かを判断する（ステップＳ２０４）。
【００６６】
そして、第１の復号装置１１１と第２の復号装置１１１とは、それぞれの判断の結果を交換する。いずれかの復号装置１１１で当該「素である」条件が成立していなければ（ステップＳ２０４；Ｎｏ）、ステップＳ２０１に戻って、それぞれの復号装置１１１は同じ処理を繰り返す。
【００６７】
一方、当該「素である」条件がすべての復号装置１１１で成立すれば（ステップＳ２０４；Ｙｅｓ）、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
という条件が満たされることになる。
【００６８】
なお、実際には、q[3]q[4]がq[1]-1またはq[2]-1と１でない素因子を持つ確率は極めて低く、q[1]q[3]がq[2]-1またはq[1]-1と１でない素因子を持つ確率は極めて低いので、実用上は、この「素である」条件のチェックは省略しても問題のないことが多い。
【００６９】
そこで、第１の復号装置１１１では、q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、第２の復号装置１１１では、q[3]，q[4]を自身の秘密鍵p[3]，p[4]とする。これにより、素数q[1]，…，q[s]から、秘密鍵
p[1]，…，p[s]
が得られ（ステップＳ２０５）、本処理を終了する。
【００７０】
このようにして、秘密鍵をそれぞれの復号装置１１１で生成する。なお、上記のように、復号装置の台数が増加したとしても、同様の処理を行えば良い。
【００７１】
（公開鍵の計算）
上記のように、各復号装置１１１においてサイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
を満たすものを秘密鍵として得ることができたので、これから公開鍵を生成することとなる。
【００７２】
図３は、公開鍵計算部１０３により実行される公開鍵計算処理の制御の流れを示すフローチャートである。
【００７３】
すなわち、公開鍵計算部１０３は、当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択する。上記典型例では、第１の復号装置１１１にて、
h[1]∈Z/p[1]2，h[2]∈Z/p[2]2
をランダムに選択し、第２の復号装置１１１にて、
h[3]∈Z/p[3]2，h[4]∈Z/p[4]2
をランダムに選択する（ステップＳ３０１）。
【００７４】
そして、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすか否かを判断する（ステップＳ３０２）。
【００７５】
この除算条件の判断は、各復号装置１１１で、独立に実行することができる。すなわち、i = 1，2については、第１の復号装置１１１で判断し、i = 3，4については、第２の復号装置１１１で判断する。
【００７６】
そして、当該条件が満たされない復号装置１１１が存在する場合（ステップＳ３０２；Ｎｏ）、当該復号装置１１１において、ステップＳ３０１に戻って、処理を繰り返す。
【００７７】
一方、当該条件がすべての復号装置１１１で満たされたら（ステップＳ３０２；Ｙｅｓ）、各復号装置１１１は、自身が選択したh[i] (1≦i≦s)を他の復号装置１１１に通知して、全復号装置１１１が、
h[1]，…，h[s]
を共有するようにする（ステップＳ３０３）。上記典型例では、第１の復号装置１１１は、h[1]，h[2]を第２の復号装置１１１に公開し、第２の復号装置１１１は、h[3]，h[4]を第１の復号装置１１１に公開することになる。
【００７８】
そして、各復号装置１１１は、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算する。上記典型例では、第１の復号装置１１１は、g[1]，g[2]を計算し、第２の復号装置１１１は、g[3]，g[4]を計算する（ステップＳ３０４）。
【００７９】
この解を求めるには、ユークリッドの互除法を用いるのが典型的であるが、あるg[i]を求めるためには、自身が持つ秘密鍵p[i]を用いたp[i]2による除算のほか、一般には他の復号装置１１１が持つ秘密鍵p[j]を用いたp[j]2による除算が必要となる。
【００８０】
そこで、後者の除算の際には、当該復号装置１１１から、当該他の復号装置１１１に対して、所望の除算を依頼し、除算の結果を応答として貰う。
【００８１】
これを繰り返すことによって、互いの秘密鍵もしくはその自乗を公開せずに、互除法が実現できる。
【００８２】
このようにして、公開鍵
(g[1],…,g[s])
が得られたら、これと、各復号装置１１１が持つ秘密鍵の積と、を、全復号装置１１１および暗号装置１１２に公開して（ステップＳ３０５）、本処理を終了する。
【００８３】
上記典型例では、第１の復号装置１１１は、g[1]，g[2]および積p[1]p[2]を公開し、第２の復号装置１１２は、g[3]，g[4]および積p[3]p[4]を公開する。
【００８４】
なお、ステップＳ３０５における公開時には、後の復号処理で利用される秘密鍵の他の情報も、他の復号装置１１１に公開する。
【００８５】
すなわち、第１の復号装置１１１は、p[1](p[1]-1)p[2](p[2]-1)を公開し、第２の復号装置１１２は、p[3](p[3]-1)p[4](p[4]-1)を公開する。これらの秘密鍵の情報が公開されたとしても、素因数分解の困難性から、秘密鍵が知得されることはない。
【００８６】
すなわち、一般に、第jの復号装置１１１は、秘密鍵p[2j-1]，p[2j]を持ち、公開鍵g[2j-1]，g[2j]、積p[2j-1]p[2j]およびp[2j-1](p[2j-1]-1)p[2j](p[2j]-1)を公開するのである。
【００８７】
この公開は、コンピュータ通信網を介した通知によるのが典型的である。
【００８８】
（暗号処理）
以下では、暗号装置１１２によって実現されるサンプリング部１０４、符号化部１０５、暗号部１０６が実行する暗号処理について説明する。
【００８９】
当該暗号処理では、各復号装置１１１に伝達したい個別のメッセージを表す平文
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
から、一つの暗号文zを生成する。ここで一般に、p[1]，…，p[s]は十分に大きいサイズkの素数であるから、m[1]，…，m[s]は、これより小さいサイズの整数とすれば、すなわち、
|m[1]| < k，…，|m[s]| < k
という条件を満たすものとすれば、
m[1]∈Z，…，m[s]∈Z
となるので、秘密鍵を暗号装置１１２で知る必要はない。
【００９０】
また、上記典型例では、m[1]，m[2]は第１の復号装置１１１宛のメッセージであり、m[3]，m[4]は第２の復号装置１１１宛のメッセージである。
【００９１】
図４は、暗号装置１１２が実行する暗号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００９２】
まず、サンプリング部１０４は、各復号装置１１１が公開した積をすべて乗算して、整数
n = p[1]…p[s]
を計算する（ステップＳ４０１）。上記典型例では、第１の復号装置１１１はp[1]p[2]を公開し、第２の復号装置１１１はp[3]p[4]を公開するから、これらを乗ずれば良い。
【００９３】
次に、サンプリング部１０４は、群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択する（ステップＳ４０２）。これは、公開鍵暗号で用いられるチャレンジ等を生成する場合と同様である。
【００９４】
そして、サンプリング部１０４は、
H = Gn = ｛xn | x∈G｝；
の要素
r = r[0]n
を計算する（ステップＳ４０３）。
【００９５】
さて、符号化部１０５は、直和
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
の要素である平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を構成する整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
が与えられると、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化を行う。すなわち、乗算と羃による計算を行うものである。
【００９６】
そこで、暗号化部１０６は、メッセージを表す整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
を符号化部１０５に与えて、
ε(m[1],…,m[s]) = g[1]m[1]…g[s]m[s]
を計算させる（ステップＳ４０４）。
【００９７】
そして、その結果にサンプリング部１０４が計算したサンプルrを乗算して、暗号文
z = e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る（ステップＳ４０５）。
【００９８】
その後は、当該暗号文zを、各復号装置１１１に送信して（ステップＳ４０６）、本処理を終了する。
【００９９】
（復号処理）
以下では、暗号装置１１２から送信された暗号文zから、複合文を得る処理について説明する。上記典型例では、第１の復号装置１１１では、m[1]，m[2]が得られ、第２の復号装置１１１では、m[3]，m[4]が得られることになる。
【０１００】
図５は、復号部１０７において実行される復号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１０１】
さて、秘密鍵p[i] (1≦i≦s)を持つ復号装置１１１は、全公開鍵
g[1]，…，g[s]
と、公開された秘密鍵の情報
p[1](p[1]-1)，…，p[s](p[s]-1)
と、から、関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
を計算することが可能となる。
【０１０２】
そこで、復号処理においては、復号部１０７は、暗号装置１１２から送信された暗号文zを受信すると（ステップＳ５０１）、関数
d[1](・)，…，d[s](・)
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を計算して（ステップＳ５０２）、これを復号されたメッセージとして、本処理を終了する。すなわち、
d[1](z) = m[1]，…，d[s](z) = m[s]
となるはずである。
【０１０３】
上記の典型例では、第１の復号装置１１１では、d[1](z) = m[1]，d[2](z) = m[2]の復号を行い、第２の復号装置１１１では、d[3](z) = m[3]，d[4](z) = m[4]の復号を行う。しかも、これらの復号は独立に行われ、他の復号装置１１１の秘密鍵そのものを利用する必要はない。
【０１０４】
本実施形態によれば、複数のメッセージをまとめて１つに暗号化することができる。したがって、メッセージ内の一部を改変するような攻撃の可能性を格段に抑制することが可能である。
【０１０５】
また、上記実施形態では、宛先ごとに２つの平文が得られることとしているが、この数は、２以上であれば任意である。すなわち、各復号装置１１１が有する秘密鍵を複数とするような分割方法であれば、上記と同様の処理を適用することができる。
【実施例２】
【０１０６】
上記実施形態の暗号システムは、宛先それぞれに独立に送られるべきメッセージを一つにまとめた暗号文を生成することとしていたが、本発明の原理は、平文に巡回群の直和を利用するものであるから、以下のような応用も可能である。
【０１０７】
すなわち、Ｘ，Ｙ，Ｚ，Ｗの四人の投票者が、Ａ，Ｂの二人の候補者の信任投票を行うものとする。信任する場合には１で、しない場合には０で表すものとする。
【０１０８】
たとえば、ＷがＡを信任、Ｂを不信任の場合には、投票内容は(1,0)となる。同様に、Ｘの投票が(1,0)、Ｙの投票が(0,1)、Ｚの投票が(1,1)であるとする。
【０１０９】
信任投票では、信任票の総数(1+1+0+1,0+0+1+1) = (3,2)が必要であるが、誰が誰を信任し、誰を不信任したか、は秘密に保ちたいのが一般的である。そこで、本発明の原理を応用する。
【０１１０】
上記のステップＳ４０５で用いる符号化関数εには、以下のような性質がある。すなわち、
ε(a+b,c+d)
= g[1]a+b…g[s]c+d
= g[1]ag[1]b…g[s]cg[s]d
= g[1]a…g[s]c×g[1]b…g[s]d
= ε(a,b)ε(c,d)
一般に、
ε(v[1]+…+v[m],w[1]+…+w[m]) = ε(v[1],w[1])…ε(v[m],w[m])
書き直して、
ε(Σi=1m v[i],Σi=1m w[i]) = Πi=1m ε(v[i],w[i])
が成立する。
【０１１１】
そこで、本実施形態における暗号部１０６の処理について説明する。図６は、本実施形態における暗号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１１２】
暗号装置１１１側の暗号部１０６は、復号部１０７に送信する暗号文を一時的に保存する整数変数yを1に初期化する（ステップＳ６０１）。
【０１１３】
そして、投票者による投票入力を受け付けると（ステップＳ６０２）、ステップＳ４０１〜ステップＳ４０５を実行する（ステップＳ６１１）。この際には、一般には、ステップＳ４０１〜ステップＳ４０３で取得されるサンプルは、投票者ごとに異なるものとなる。
【０１１４】
i (1≦i≦m)番目の投票者がＡを信任するか否かをv[i] = 1かv[i] = 0かで表現し、Ｂを信任するか否かをw[i] = 1かw[i] = 0かで表現したとし、当該投票者iについて得られたサンプルがr[i]だったとすると、当該投票者iの暗号文は、
ε(v[i],w[i])r[i]
である。
【０１１５】
ついで、得られた投票者iの暗号文zを、整数変数yに乗算して格納する（ステップＳ６０３）。すなわち、
y←y×z
を実行する。ここで「←」は代入を意味する。
【０１１６】
そして、投票が終わったか否かを判定し（ステップＳ６０４）、終わっていなければ（ステップＳ６０４；Ｎｏ）、ステップＳ６０２に戻る。投票が終わったか否かは、たとえば期間で区切る、定足数で区切る等種々の手法により判断する。
【０１１７】
投票が終わったら（ステップＳ６０４；Ｙｅｓ）、整数変数yの値を、信任投票集計を実現する復号部１０７に送信して（ステップＳ６０５）、本処理を終了する。
【０１１８】
なお、上記の乗算は、逐次に実行しているが、投票者ごとの暗号文を蓄積しておき、最後にまとめてこれらの積を計算して、yを得ることとしても良い。
【０１１９】
さて、整数変数yに格納される値は、投票者1から投票者mまでの投票がされたものとすると、そのそれぞれについて得られた暗号文のすべてを乗算したものである。すなわち、乗算の結果は、
y = ε(v[1],w[1])r[1]×…×ε(v[m],w[m])r[m]
= ε(v[1],w[1])×…×ε(v[m],w[m]) r[1]×…×r[m]
= ε(v[1]+…+v[m],w[1]+…+w[m])×(r[1]…r[m])
となる。ここで、暗号化におけるサンプルの値は任意であるから、この乗算の結果yは、平文(v[1]+…+v[m],w[1]+…+w[m])に対して、サンプル(r[1]…r[m])を用いた暗号文、と考えることができる。
【０１２０】
本実施形態では、復号装置１１１は、単なる集計を行うものであるから、１台にまとめることとして、秘密鍵のすべてp[1]，…，p[s]を知るように構成しても良い。すなわち、上記実施形態において複数の復号装置１１１で分割して行っていた処理は、本実施形態では１つの復号装置１１１で纏めて行うことが可能である。
【０１２１】
すると、復号装置１１１では、復号により、平文(v[1]+…+v[m],w[1]+…+w[m])が得られる。すなわち、各信任投票数が得られ、しかも、誰が誰に投票したのかは秘密に保たれる。
【０１２２】
上記の例では、s = 2としていたが、信任投票の対象となる人数は、一般にs (s≧2)人とすることができる。この拡張は、sの数値を増やすことで自然に表現できる。
【０１２３】
すなわち、本実施形態では、「複数の整数を要素とする平文の暗号文」の積もまた、暗号文として考えることができ、これを復号すると、元の複数の平文の各要素同士を加算したものが復号文として得られるのである。
【０１２４】
本実施形態は、一般に、投票者が何らかの値を投票するが、誰がどんな値を投票したかは秘密に保ち、その総和のみを知りたい、というような場合に適用が可能である。
【産業上の利用可能性】
【０１２５】
以上説明したように、本発明によれば、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することができる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の実施形態に係る暗号システムの概要構成を示す模式図である。
【図２】秘密鍵計算部により実行される秘密鍵計算処理の制御の流れを示すフローチャートである。
【図３】公開鍵計算部により実行される公開鍵計算処理の制御の流れを示すフローチャートである。
【図４】暗号装置が実行する暗号処理の制御の流れを示すフローチャートである。
【図５】復号部において実行される復号処理の制御の流れを示すフローチャートである。
【図６】暗号装置が実行する暗号処理の制御の流れを示すフローチャートである。
【符号の説明】
【０１２７】
１０１ 暗号システム
１０２ 秘密鍵計算部
１０３ 公開鍵計算部
１０４ サンプリング部
１０５ 符号化部
１０６ 暗号部
１０７ 復号部
１１１ 復号装置
１１２ 暗号装置
【技術分野】
【０００１】
本発明は、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体に関する。
【背景技術】
【０００２】
従来から各種の公開鍵暗号技術が提案されており、このような公開鍵暗号については、以下の文献に開示がされている。
【非特許文献１】Okamoto T.and Uchiyama S., A New Public-key Cryptosystem as Secure as Factoring, Nyberg，K.(ed.), EUROCRYPT 1998，LNCS, vol.1403, pp.308-318, Springer，Heidelberg, １９９８年
【０００３】
[非特許文献１]では、Okamoto-Uchiyamaの対数関数Lpを利用した公開鍵暗号技術が提案されている。ここで、対数関数Lpとは、以下のように定義される。
【０００４】
すなわち、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
を考える。
【０００５】
Γpは、その位数（order）がpの羃に等しい最大部分群である。
【０００６】
群(Z/p2)*の位数は、オイラーのトーティエント（totient）関数φにより、
φ(p2) = p(p-1)
と書くことができる。
【０００７】
したがって、(Z/p2)*は、Γpと、位数(p-1)の部分群の内部直和（internal direct sum）である。
【０００８】
なお、本願では、AとBの直和をA (+) Bのように記載することとする。一般的な数学記法では、(+)は、+記号を丸で囲んだ符号で表記される。
【０００９】
ここで、x (mod p2)からx (mod p)への射（mapping）は、(Z/p2)*から(Z/p)*の上への準同型写像（ホモモルフィズム；homomorphism）であるから、(Z/p2)*/Γpは、(Z/p)*と準同形である。
【００１０】
したがって、位数p-1の部分群は、(Z/p)*に対する同型（アイソモルフィズム；isomorphism）であり、巡回的である。
【００１１】
一方、Γpは、位数pであり、巡回的である。
【００１２】
pとp-1は互いに素であるから、(Z/p)*は、巡回的である。
【００１３】
ここで、x≡1 (mod p)と仮定すると、あるc∈Zが存在して
x = cp + 1
である。したがって、
xp = (cp + 1)p = Σi=0p pCi(cp)p-i
と展開できる。ここで、pCiは２項係数を意味し、
pC0 = 1；
pC1 = pCp-1 = p；
pC2 = pCp-2 = p(p-1)/2； …
であるから、
Σi=0p pCi(cp)p-i = 1 + (cp)p + (cp)2p(p-1)/2 + …
のように展開できる。
【００１４】
したがって、あるd∈Zが存在して
xp = dp2 + 1
である。
【００１５】
これによって、x≡1 (mod p)ならば、xp≡1 (mod p2)であることが証明された。
【００１６】
したがって、
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
である。
【００１７】
すると、任意のx∈Γpに対して
x - 1 = ap
を満たす整数aが一意に定まる。
【００１８】
そこで、対数関数Lpは、当該xおよびaによって、
Lp(x) = a (mod p)
と定義される。Lpは、Γpから加算群(Z/p,+)の中へのホモモルフィズムである。
【００１９】
さらに、Lpは、Γpから加算群(Z/p,+)の上へのアイソモルフィズムである。
【００２０】
すなわち、任意のa，b∈Γpに対して
Lp(ab) = Lp(a) + Lp(a) (mod p)
が成立する。
【００２１】
特に、任意のx，y∈Γpに対して、m∈Z/pについて
y = xm
が成立すれば、
Lp(y) = mLp(x)
である。
【００２２】
これから、Lp(x)≠0である限り、
m = Lp(y)Lp(x)-1
である。
【００２３】
Lp(x)=0となるのは、xがΓpの単位元(identity element)である場合であり、かつ、その場合に限られる。
【００２４】
そして、このようなホモモルフィズムにおける性質を利用した新たな公開鍵暗号の技術の開発が進められている。
【発明の開示】
【発明が解決しようとする課題】
【００２５】
ここで、複数の平文を１つの暗号文に暗号化する一方で、当該平文を個別に復号できるような暗号システム、特に、複数の宛先に対する異なる平文を安全に１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得でき、応用によっては、複数の暗号文を個別に復号することなく、平文の計算が可能となるような暗号システムが強く望まれている。
【００２６】
本発明は、以上の課題を解決するもので、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２７】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【００２８】
本発明の第１の観点に係る暗号システムは、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用い、公開鍵計算部、サンプリング部、符号化部、暗号部、復号部を有し、以下のように構成する。
【００２９】
すなわち、公開鍵計算部は、当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする。
【００３０】
一方、サンプリング部は、当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングする。
【００３１】
さらに、符号化部は、整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する。
【００３２】
そして、暗号部は、整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、符号化部に符号化させ、サンプリング部にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る。
【００３３】
一方、復号部は、当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る。
【００３４】
また、本発明の暗号システムは、秘密鍵計算部をさらに備え、以下のように構成することができる。
【００３５】
すなわち、秘密鍵計算部は、サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする。
【００３６】
また、本発明の暗号システムにおいて、
s = 4
であり、当該暗号システムは、暗号装置、第１復号装置、第２復号装置を有し、以下のように構成することができる。
【００３７】
すなわち、当該第１復号装置は、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、当該第２復号装置は、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、当該第１復号装置は、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、当該第２復号装置は、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、当該両者にて当該素であることが確認されたら、当該第１暗号装置は、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置は、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]として、秘密鍵計算部として機能する。
【００３８】
一方、当該第１復号装置は、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、当該第２復号装置は、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開して、公開鍵計算部として機能する。
【００３９】
さらに、当該第１復号装置は、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、当該第２復号装置は、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、当該暗号装置は、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングして、サンプリング部として機能する。
【００４０】
そして、暗号装置は、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化して、符号化部として機能する。
【００４１】
一方、暗号装置は、符号化部に当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、サンプリング部にサンプリングさせたrを乗じ、暗号文zを得て、暗号部として機能する。
【００４２】
さらに、第１復号装置は、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して第２復号装置に公開し、第２復号装置は、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して第１復号装置に公開し、第１復号装置は、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、第２復号装置は、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、復号部として機能する。
【００４３】
また、本発明の暗号システムにおいて、暗号部は、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を復号部に与えるように構成することができる。
【００４４】
この場合、復号部では、もとの平文の各要素同士を加算したものが、復号文として得られることになる。
【００４５】
本発明のその他の観点に係る暗号方法は、上記暗号システムが実行する暗号方法である。
【００４６】
典型的には、当該暗号方法は、上記の暗号装置、第１復号装置、第２復号装置が実行する。
【００４７】
本発明の他の観点に係るプログラムは、コンピュータもしくはコンピュータ群を、上記暗号システムの各部として機能させるように構成する。
【００４８】
典型的には、当該プログラムは、３台のコンピュータを、上記の暗号装置、第１復号装置、第２復号装置として機能させるように構成する。
【００４９】
本発明の他の観点に係るコンピュータ読取可能な情報記録媒体は、上記のプログラムを記録するように構成する。たとえば、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記録することができる。
【００５０】
なお、コンピュータもしくはコンピュータ群が、上記プログラムを実行することによって、本発明の暗号システムが実現されるが、当該プログラムは、コンピュータ通信網を介して配布・販売することができる。また、上記情報記憶媒体は、当該コンピュータとは、とは独立して配布・販売することができる。
【発明の効果】
【００５１】
本発明によれば、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することができる。
【発明を実施するための最良の形態】
【００５２】
以下に本発明の実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【実施例１】
【００５３】
図１は、本発明の実施形態の１つに係る暗号システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【００５４】
暗号システム１０１は、秘密鍵計算部１０２、公開鍵計算部１０３、サンプリング部１０４、符号化部１０５、暗号部１０６、復号部１０７を備え、典型的には、コンピュータ通信網を介して相互に通信可能な複数の復号装置１１１および暗号装置１１２からなるコンピュータ群によって実現される。
【００５５】
具体的には、秘密鍵計算部１０２は、復号装置１１１によって実現され、公開鍵計算部１０３は、復号装置１１１によって実現され、サンプリング部１０４は、復号装置１１１によって実現され、符号化部１０５は、暗号装置１１２によって実現され、暗号部１０６は、暗号装置１１２によって実現され、復号部１０７は、復号装置１１１によって実現される。
【００５６】
各コンピュータは、ＣＰＵ（Central Processing Unit）の制御の下、ＮＩＣ（Network Interface Card）を介して相互に通信可能に接続され、ＲＡＭ（Random Access Memory）を一時記憶領域とし、ＲＯＭ（Read Only Memory）やＨＤ（Hard Disk）に格納されたプログラムをＣＰＵが実行して、各種の計算を行うことで、各復号装置１１１や暗号装置１１２が実現される。
【００５７】
本実施形態に係る暗号システム１０１では、上記のように、サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
とを用いる。これは、Okamoto-Uchiyamaの対数関数である。
【００５８】
以下、適宜、s = 4であり、かつ、１台の暗号装置１１２と２台の復号装置１１１の組み合わせにより暗号システム１０１が実現される場合を典型例としてあげて説明するが、本発明の原理は、復号装置をさらに増やした場合にも適用可能であり、そのような実施形態についても本発明の範囲に含まれる。
【００５９】
（秘密鍵の計算）
まず、秘密鍵計算部１０２における処理について説明する。図２は、秘密鍵計算部１０２により実行される秘密鍵計算処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００６０】
まず、秘密鍵計算部１０２は、サイズkの互いに異なる素数
q[1]，…，q[s]
を選択する。上記典型例では、第１の復号装置１１１にて、q[1]，q[2]を選択し、第２の復号装置１１１にて、q[3]，q[4]を選択して、これはそのまま秘密としておく（ステップＳ２０１）。
【００６１】
ここで選択される素数は、通常の公開鍵暗号と同様に十分な大きさを持つものが望ましく、また、選択には、たとえばユーザがキーボードを押す間隔や現在の時刻などの条件を乱数の種として使用して、素数を生成することが望ましい。
【００６２】
ついで、第１の復号装置１１１は、積q[1]q[2]を計算し、第２の復号装置１１１は、積q[3]q[4]を計算する（ステップＳ２０２）。
【００６３】
さらに、第１の復号装置１１１は、自身が計算した積q[1]q[2]を他の復号装置１１１に通知し、第２の復号装置１１１は、自身が計算した積q[3]q[4]を、他の復号装置１１１に通知する。すなわち、各復号装置１１１は、自身が計算した積をコンピュータ通信網を介して他の復号装置１１１と交換して、互いに公開する（ステップＳ２０３）。
【００６４】
巨大な数の素因数分解は困難である、ということが公開鍵暗号の根本原理となっており、第２の復号装置１１１は、積q[1]q[2]を受け取ったとしても、これを素因数分解してq[1]，q[2]を得ることは困難であり、第１の復号装置１１１は、積q[3]q[4]を受け取ったとしても、これを素因数分解してq[3]，q[4]を得ることは困難である。したがって、それぞれの復号装置１１１がステップＳ２０１にて生成した素数は、秘密に保たれる。
【００６５】
そして、第１の復号装置１１１は、他の復号装置１１１から受け取った積q[3]q[4]が、自身の生成した素数から得られる数q[1]-1およびq[2]-1に対して素であるか否かを判断し、第２復号装置１１１は、他の復号装置１１１から受け取った積q[1]q[2]が、自身の生成した素数から得られる数q[3]-1およびq[4]-1に対して素であるか否かを判断する（ステップＳ２０４）。
【００６６】
そして、第１の復号装置１１１と第２の復号装置１１１とは、それぞれの判断の結果を交換する。いずれかの復号装置１１１で当該「素である」条件が成立していなければ（ステップＳ２０４；Ｎｏ）、ステップＳ２０１に戻って、それぞれの復号装置１１１は同じ処理を繰り返す。
【００６７】
一方、当該「素である」条件がすべての復号装置１１１で成立すれば（ステップＳ２０４；Ｙｅｓ）、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
という条件が満たされることになる。
【００６８】
なお、実際には、q[3]q[4]がq[1]-1またはq[2]-1と１でない素因子を持つ確率は極めて低く、q[1]q[3]がq[2]-1またはq[1]-1と１でない素因子を持つ確率は極めて低いので、実用上は、この「素である」条件のチェックは省略しても問題のないことが多い。
【００６９】
そこで、第１の復号装置１１１では、q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、第２の復号装置１１１では、q[3]，q[4]を自身の秘密鍵p[3]，p[4]とする。これにより、素数q[1]，…，q[s]から、秘密鍵
p[1]，…，p[s]
が得られ（ステップＳ２０５）、本処理を終了する。
【００７０】
このようにして、秘密鍵をそれぞれの復号装置１１１で生成する。なお、上記のように、復号装置の台数が増加したとしても、同様の処理を行えば良い。
【００７１】
（公開鍵の計算）
上記のように、各復号装置１１１においてサイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
を満たすものを秘密鍵として得ることができたので、これから公開鍵を生成することとなる。
【００７２】
図３は、公開鍵計算部１０３により実行される公開鍵計算処理の制御の流れを示すフローチャートである。
【００７３】
すなわち、公開鍵計算部１０３は、当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択する。上記典型例では、第１の復号装置１１１にて、
h[1]∈Z/p[1]2，h[2]∈Z/p[2]2
をランダムに選択し、第２の復号装置１１１にて、
h[3]∈Z/p[3]2，h[4]∈Z/p[4]2
をランダムに選択する（ステップＳ３０１）。
【００７４】
そして、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすか否かを判断する（ステップＳ３０２）。
【００７５】
この除算条件の判断は、各復号装置１１１で、独立に実行することができる。すなわち、i = 1，2については、第１の復号装置１１１で判断し、i = 3，4については、第２の復号装置１１１で判断する。
【００７６】
そして、当該条件が満たされない復号装置１１１が存在する場合（ステップＳ３０２；Ｎｏ）、当該復号装置１１１において、ステップＳ３０１に戻って、処理を繰り返す。
【００７７】
一方、当該条件がすべての復号装置１１１で満たされたら（ステップＳ３０２；Ｙｅｓ）、各復号装置１１１は、自身が選択したh[i] (1≦i≦s)を他の復号装置１１１に通知して、全復号装置１１１が、
h[1]，…，h[s]
を共有するようにする（ステップＳ３０３）。上記典型例では、第１の復号装置１１１は、h[1]，h[2]を第２の復号装置１１１に公開し、第２の復号装置１１１は、h[3]，h[4]を第１の復号装置１１１に公開することになる。
【００７８】
そして、各復号装置１１１は、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算する。上記典型例では、第１の復号装置１１１は、g[1]，g[2]を計算し、第２の復号装置１１１は、g[3]，g[4]を計算する（ステップＳ３０４）。
【００７９】
この解を求めるには、ユークリッドの互除法を用いるのが典型的であるが、あるg[i]を求めるためには、自身が持つ秘密鍵p[i]を用いたp[i]2による除算のほか、一般には他の復号装置１１１が持つ秘密鍵p[j]を用いたp[j]2による除算が必要となる。
【００８０】
そこで、後者の除算の際には、当該復号装置１１１から、当該他の復号装置１１１に対して、所望の除算を依頼し、除算の結果を応答として貰う。
【００８１】
これを繰り返すことによって、互いの秘密鍵もしくはその自乗を公開せずに、互除法が実現できる。
【００８２】
このようにして、公開鍵
(g[1],…,g[s])
が得られたら、これと、各復号装置１１１が持つ秘密鍵の積と、を、全復号装置１１１および暗号装置１１２に公開して（ステップＳ３０５）、本処理を終了する。
【００８３】
上記典型例では、第１の復号装置１１１は、g[1]，g[2]および積p[1]p[2]を公開し、第２の復号装置１１２は、g[3]，g[4]および積p[3]p[4]を公開する。
【００８４】
なお、ステップＳ３０５における公開時には、後の復号処理で利用される秘密鍵の他の情報も、他の復号装置１１１に公開する。
【００８５】
すなわち、第１の復号装置１１１は、p[1](p[1]-1)p[2](p[2]-1)を公開し、第２の復号装置１１２は、p[3](p[3]-1)p[4](p[4]-1)を公開する。これらの秘密鍵の情報が公開されたとしても、素因数分解の困難性から、秘密鍵が知得されることはない。
【００８６】
すなわち、一般に、第jの復号装置１１１は、秘密鍵p[2j-1]，p[2j]を持ち、公開鍵g[2j-1]，g[2j]、積p[2j-1]p[2j]およびp[2j-1](p[2j-1]-1)p[2j](p[2j]-1)を公開するのである。
【００８７】
この公開は、コンピュータ通信網を介した通知によるのが典型的である。
【００８８】
（暗号処理）
以下では、暗号装置１１２によって実現されるサンプリング部１０４、符号化部１０５、暗号部１０６が実行する暗号処理について説明する。
【００８９】
当該暗号処理では、各復号装置１１１に伝達したい個別のメッセージを表す平文
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
から、一つの暗号文zを生成する。ここで一般に、p[1]，…，p[s]は十分に大きいサイズkの素数であるから、m[1]，…，m[s]は、これより小さいサイズの整数とすれば、すなわち、
|m[1]| < k，…，|m[s]| < k
という条件を満たすものとすれば、
m[1]∈Z，…，m[s]∈Z
となるので、秘密鍵を暗号装置１１２で知る必要はない。
【００９０】
また、上記典型例では、m[1]，m[2]は第１の復号装置１１１宛のメッセージであり、m[3]，m[4]は第２の復号装置１１１宛のメッセージである。
【００９１】
図４は、暗号装置１１２が実行する暗号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００９２】
まず、サンプリング部１０４は、各復号装置１１１が公開した積をすべて乗算して、整数
n = p[1]…p[s]
を計算する（ステップＳ４０１）。上記典型例では、第１の復号装置１１１はp[1]p[2]を公開し、第２の復号装置１１１はp[3]p[4]を公開するから、これらを乗ずれば良い。
【００９３】
次に、サンプリング部１０４は、群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択する（ステップＳ４０２）。これは、公開鍵暗号で用いられるチャレンジ等を生成する場合と同様である。
【００９４】
そして、サンプリング部１０４は、
H = Gn = ｛xn | x∈G｝；
の要素
r = r[0]n
を計算する（ステップＳ４０３）。
【００９５】
さて、符号化部１０５は、直和
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
の要素である平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を構成する整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
が与えられると、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化を行う。すなわち、乗算と羃による計算を行うものである。
【００９６】
そこで、暗号化部１０６は、メッセージを表す整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
を符号化部１０５に与えて、
ε(m[1],…,m[s]) = g[1]m[1]…g[s]m[s]
を計算させる（ステップＳ４０４）。
【００９７】
そして、その結果にサンプリング部１０４が計算したサンプルrを乗算して、暗号文
z = e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る（ステップＳ４０５）。
【００９８】
その後は、当該暗号文zを、各復号装置１１１に送信して（ステップＳ４０６）、本処理を終了する。
【００９９】
（復号処理）
以下では、暗号装置１１２から送信された暗号文zから、複合文を得る処理について説明する。上記典型例では、第１の復号装置１１１では、m[1]，m[2]が得られ、第２の復号装置１１１では、m[3]，m[4]が得られることになる。
【０１００】
図５は、復号部１０７において実行される復号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１０１】
さて、秘密鍵p[i] (1≦i≦s)を持つ復号装置１１１は、全公開鍵
g[1]，…，g[s]
と、公開された秘密鍵の情報
p[1](p[1]-1)，…，p[s](p[s]-1)
と、から、関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
を計算することが可能となる。
【０１０２】
そこで、復号処理においては、復号部１０７は、暗号装置１１２から送信された暗号文zを受信すると（ステップＳ５０１）、関数
d[1](・)，…，d[s](・)
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を計算して（ステップＳ５０２）、これを復号されたメッセージとして、本処理を終了する。すなわち、
d[1](z) = m[1]，…，d[s](z) = m[s]
となるはずである。
【０１０３】
上記の典型例では、第１の復号装置１１１では、d[1](z) = m[1]，d[2](z) = m[2]の復号を行い、第２の復号装置１１１では、d[3](z) = m[3]，d[4](z) = m[4]の復号を行う。しかも、これらの復号は独立に行われ、他の復号装置１１１の秘密鍵そのものを利用する必要はない。
【０１０４】
本実施形態によれば、複数のメッセージをまとめて１つに暗号化することができる。したがって、メッセージ内の一部を改変するような攻撃の可能性を格段に抑制することが可能である。
【０１０５】
また、上記実施形態では、宛先ごとに２つの平文が得られることとしているが、この数は、２以上であれば任意である。すなわち、各復号装置１１１が有する秘密鍵を複数とするような分割方法であれば、上記と同様の処理を適用することができる。
【実施例２】
【０１０６】
上記実施形態の暗号システムは、宛先それぞれに独立に送られるべきメッセージを一つにまとめた暗号文を生成することとしていたが、本発明の原理は、平文に巡回群の直和を利用するものであるから、以下のような応用も可能である。
【０１０７】
すなわち、Ｘ，Ｙ，Ｚ，Ｗの四人の投票者が、Ａ，Ｂの二人の候補者の信任投票を行うものとする。信任する場合には１で、しない場合には０で表すものとする。
【０１０８】
たとえば、ＷがＡを信任、Ｂを不信任の場合には、投票内容は(1,0)となる。同様に、Ｘの投票が(1,0)、Ｙの投票が(0,1)、Ｚの投票が(1,1)であるとする。
【０１０９】
信任投票では、信任票の総数(1+1+0+1,0+0+1+1) = (3,2)が必要であるが、誰が誰を信任し、誰を不信任したか、は秘密に保ちたいのが一般的である。そこで、本発明の原理を応用する。
【０１１０】
上記のステップＳ４０５で用いる符号化関数εには、以下のような性質がある。すなわち、
ε(a+b,c+d)
= g[1]a+b…g[s]c+d
= g[1]ag[1]b…g[s]cg[s]d
= g[1]a…g[s]c×g[1]b…g[s]d
= ε(a,b)ε(c,d)
一般に、
ε(v[1]+…+v[m],w[1]+…+w[m]) = ε(v[1],w[1])…ε(v[m],w[m])
書き直して、
ε(Σi=1m v[i],Σi=1m w[i]) = Πi=1m ε(v[i],w[i])
が成立する。
【０１１１】
そこで、本実施形態における暗号部１０６の処理について説明する。図６は、本実施形態における暗号処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１１２】
暗号装置１１１側の暗号部１０６は、復号部１０７に送信する暗号文を一時的に保存する整数変数yを1に初期化する（ステップＳ６０１）。
【０１１３】
そして、投票者による投票入力を受け付けると（ステップＳ６０２）、ステップＳ４０１〜ステップＳ４０５を実行する（ステップＳ６１１）。この際には、一般には、ステップＳ４０１〜ステップＳ４０３で取得されるサンプルは、投票者ごとに異なるものとなる。
【０１１４】
i (1≦i≦m)番目の投票者がＡを信任するか否かをv[i] = 1かv[i] = 0かで表現し、Ｂを信任するか否かをw[i] = 1かw[i] = 0かで表現したとし、当該投票者iについて得られたサンプルがr[i]だったとすると、当該投票者iの暗号文は、
ε(v[i],w[i])r[i]
である。
【０１１５】
ついで、得られた投票者iの暗号文zを、整数変数yに乗算して格納する（ステップＳ６０３）。すなわち、
y←y×z
を実行する。ここで「←」は代入を意味する。
【０１１６】
そして、投票が終わったか否かを判定し（ステップＳ６０４）、終わっていなければ（ステップＳ６０４；Ｎｏ）、ステップＳ６０２に戻る。投票が終わったか否かは、たとえば期間で区切る、定足数で区切る等種々の手法により判断する。
【０１１７】
投票が終わったら（ステップＳ６０４；Ｙｅｓ）、整数変数yの値を、信任投票集計を実現する復号部１０７に送信して（ステップＳ６０５）、本処理を終了する。
【０１１８】
なお、上記の乗算は、逐次に実行しているが、投票者ごとの暗号文を蓄積しておき、最後にまとめてこれらの積を計算して、yを得ることとしても良い。
【０１１９】
さて、整数変数yに格納される値は、投票者1から投票者mまでの投票がされたものとすると、そのそれぞれについて得られた暗号文のすべてを乗算したものである。すなわち、乗算の結果は、
y = ε(v[1],w[1])r[1]×…×ε(v[m],w[m])r[m]
= ε(v[1],w[1])×…×ε(v[m],w[m]) r[1]×…×r[m]
= ε(v[1]+…+v[m],w[1]+…+w[m])×(r[1]…r[m])
となる。ここで、暗号化におけるサンプルの値は任意であるから、この乗算の結果yは、平文(v[1]+…+v[m],w[1]+…+w[m])に対して、サンプル(r[1]…r[m])を用いた暗号文、と考えることができる。
【０１２０】
本実施形態では、復号装置１１１は、単なる集計を行うものであるから、１台にまとめることとして、秘密鍵のすべてp[1]，…，p[s]を知るように構成しても良い。すなわち、上記実施形態において複数の復号装置１１１で分割して行っていた処理は、本実施形態では１つの復号装置１１１で纏めて行うことが可能である。
【０１２１】
すると、復号装置１１１では、復号により、平文(v[1]+…+v[m],w[1]+…+w[m])が得られる。すなわち、各信任投票数が得られ、しかも、誰が誰に投票したのかは秘密に保たれる。
【０１２２】
上記の例では、s = 2としていたが、信任投票の対象となる人数は、一般にs (s≧2)人とすることができる。この拡張は、sの数値を増やすことで自然に表現できる。
【０１２３】
すなわち、本実施形態では、「複数の整数を要素とする平文の暗号文」の積もまた、暗号文として考えることができ、これを復号すると、元の複数の平文の各要素同士を加算したものが復号文として得られるのである。
【０１２４】
本実施形態は、一般に、投票者が何らかの値を投票するが、誰がどんな値を投票したかは秘密に保ち、その総和のみを知りたい、というような場合に適用が可能である。
【産業上の利用可能性】
【０１２５】
以上説明したように、本発明によれば、複数の平文を１つの暗号文にして当該平文を個別に復号でき、特に、複数の宛先に対する異なる平文を１つの暗号文にし、当該暗号文から自身宛の平文を安全に取得できる暗号システム暗号方法、これらをコンピュータを用いて実現するプログラム、ならびに、当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することができる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の実施形態に係る暗号システムの概要構成を示す模式図である。
【図２】秘密鍵計算部により実行される秘密鍵計算処理の制御の流れを示すフローチャートである。
【図３】公開鍵計算部により実行される公開鍵計算処理の制御の流れを示すフローチャートである。
【図４】暗号装置が実行する暗号処理の制御の流れを示すフローチャートである。
【図５】復号部において実行される復号処理の制御の流れを示すフローチャートである。
【図６】暗号装置が実行する暗号処理の制御の流れを示すフローチャートである。
【符号の説明】
【０１２７】
１０１ 暗号システム
１０２ 秘密鍵計算部
１０３ 公開鍵計算部
１０４ サンプリング部
１０５ 符号化部
１０６ 暗号部
１０７ 復号部
１１１ 復号装置
１１２ 暗号装置
【特許請求の範囲】
【請求項１】
サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用いる暗号システムであって、
（１）当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする公開鍵計算部、
（２）当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングするサンプリング部、
（３）整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する符号化部、
（４）整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、前記符号化部に符号化させ、前記サンプリング部にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る暗号部、
（５）当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る復号部
を備えることを特徴とする暗号システム。
【請求項２】
請求項１に記載の暗号システムであって、
サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする秘密鍵計算部
をさらに備えることを特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
s = 4
であり、当該暗号システムは、暗号装置、第１復号装置、第２復号装置を有し、
（１） 当該第１復号装置は、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、
当該第２復号装置は、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、
当該第１復号装置は、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、
当該第２復号装置は、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、
当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、
当該両者にて当該素であることが確認されたら、当該第１暗号装置は、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置は、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]として、
前記秘密鍵計算部として機能し、
（２）当該第１復号装置は、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置は、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開して、
前記公開鍵計算部として機能し、
（３）当該第１復号装置は、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置は、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、
当該暗号装置は、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングして、
前記サンプリング部として機能し、
（４）前記暗号装置は、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化して、
前記符号化部として機能し、
（５）前記暗号装置は、前記符号化部に当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、
前記サンプリング部にサンプリングさせたrを乗じ、暗号文zを得て、
前記暗号部として機能し、
（６）前記第１復号装置は、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して前記第２復号装置に公開し、
前記第２復号装置は、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して前記第１復号装置に公開し、
前記第１復号装置は、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、
前記第２復号装置は、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、
前記復号部として機能する
ことを特徴とする暗号システム。
【請求項４】
請求項１または２に記載の暗号システムであって、
前記暗号部は、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を前記復号部に与える
ことを特徴とする暗号システム。
【請求項５】
サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用いる暗号方法であって、
（１）当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする公開鍵計算工程、
（２）当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングするサンプリング工程、
（３）整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する符号化工程、
（４）整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、前記符号化工程にて符号化し、前記サンプリング工程にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る暗号工程、
（５）当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る復号工程
を備えることを特徴とする暗号方法。
【請求項６】
請求項５に記載の暗号方法であって、
サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする秘密鍵計算工程
をさらに備えることを特徴とする暗号方法。
【請求項７】
請求項６に記載の暗号方法であって、
s = 4
であり、当該暗号方法は、暗号装置、第１復号装置、第２復号装置が実行し、
（１）当該第１復号装置が、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、
当該第２復号装置が、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、
当該第１復号装置が、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、
当該第２復号装置が、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、
当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、
当該両者にて当該素であることが確認されたら、当該第１暗号装置が、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置が、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]とすることにより、
前記秘密鍵計算工程が実行され、
（２）当該第１復号装置が、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置が、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開することにより、
前記公開鍵計算工程が実行され、
（３）当該第１復号装置が、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置が、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、
当該暗号装置が、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングすることにより、
前記サンプリング工程が実行され、
（４）前記暗号装置が、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化することにより、
前記符号化工程が実行され、
（５）前記暗号装置が、前記符号化工程にて当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、
前記サンプリング工程にてサンプリングさせたrを乗じ、暗号文zを得ることにより、
前記暗号工程が実行され、
（６）前記第１復号装置が、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して前記第２復号装置に公開し、
前記第２復号装置が、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して前記第１復号装置に公開し、
前記第１復号装置が、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、
前記第２復号装置が、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、
前記復号工程が実行される
ことを特徴とする暗号方法。
【請求項８】
請求項５または６に記載の暗号方法であって、
前記暗号工程では、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を前記復号工程に与える
ことを特徴とする暗号方法。
【請求項９】
コンピュータもしくはコンピュータ群に、請求項１から４のいずれか１項に記載の暗号システムの各部を実行させることを特徴とするプログラム。
【請求項１０】
コンピュータもしくはコンピュータ群に、請求項１から３のいずれか１項に記載の暗号システムの各部を実行させることを特徴とするプログラムを記録したコンピュータ読取可能な情報記録媒体。
【請求項１】
サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用いる暗号システムであって、
（１）当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする公開鍵計算部、
（２）当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングするサンプリング部、
（３）整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する符号化部、
（４）整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、前記符号化部に符号化させ、前記サンプリング部にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る暗号部、
（５）当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る復号部
を備えることを特徴とする暗号システム。
【請求項２】
請求項１に記載の暗号システムであって、
サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする秘密鍵計算部
をさらに備えることを特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
s = 4
であり、当該暗号システムは、暗号装置、第１復号装置、第２復号装置を有し、
（１） 当該第１復号装置は、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、
当該第２復号装置は、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、
当該第１復号装置は、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、
当該第２復号装置は、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、
当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、
当該両者にて当該素であることが確認されたら、当該第１暗号装置は、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置は、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]として、
前記秘密鍵計算部として機能し、
（２）当該第１復号装置は、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置は、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開して、
前記公開鍵計算部として機能し、
（３）当該第１復号装置は、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置は、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、
当該暗号装置は、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングして、
前記サンプリング部として機能し、
（４）前記暗号装置は、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化して、
前記符号化部として機能し、
（５）前記暗号装置は、前記符号化部に当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、
前記サンプリング部にサンプリングさせたrを乗じ、暗号文zを得て、
前記暗号部として機能し、
（６）前記第１復号装置は、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して前記第２復号装置に公開し、
前記第２復号装置は、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して前記第１復号装置に公開し、
前記第１復号装置は、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、
前記第２復号装置は、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、
前記復号部として機能する
ことを特徴とする暗号システム。
【請求項４】
請求項１または２に記載の暗号システムであって、
前記暗号部は、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を前記復号部に与える
ことを特徴とする暗号システム。
【請求項５】
サイズkの素数pに対する群
(Z/p2)*
と、(Z/p2)*に対して定義されるp-Sylow部分群
Γp = ｛x | x∈(Z/p2)*，x≡1 (mod p)｝
と、当該Γpの任意の要素xに対して
x - 1 = ap
を一意に満たす整数aにより定義される対数関数
Lp(x) = a (mod p)
と、サイズkの互いに異なる素数
p[1]，…，p[s]
であって、任意の整数i，j (1≦i,j≦s，i≠j)について
p[i]は、p[j]-1の素因子ではない
素数に対して定義される整数
n = p[1]…p[s]
および群
G = (Z/n2)*；
H = Gn = ｛xn | x∈G｝；
P = (Z/p[1]) (+) … (+) (Z/p[s]) = ｛(x[1],…,x[s]) | x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])｝
と、を用いる暗号方法であって、
（１）当該素数
p[1]，…，p[s]
のそれぞれに対して、
h[1]∈Z/p[1]2，…，h[s]∈Z/p[s]2
をランダムに選択し、整数i (1≦i≦s)のそれぞれについて、
h[i]がp[i]で割り切れないこと、
かつ、
h[i]p[i]-1≠1 (mod p[i]2)
を満たすまで当該選択を繰り返し、当該選択された
h[1]，…，h[s]
に対して、中国の剰余定理により、整数i,j (1≦i≦s，i≠j)のそれぞれについて、
g[i] = h[i]p[i]-1 (mod p[i]2)；
g[i] = 1 (mod p[j]2)
を満たす
g[1]，…，g[s]
を計算して、
(g[1],…,g[s])
を公開鍵とする公開鍵計算工程、
（２）当該素数
p[1]，…，p[s]
の積
n = p[1]…p[s]
に対する群
G = (Z/n2)*
の要素r[0]をランダムかつ一様に選択して、群
H = Gn
の要素
r = r[0]n
をランダムかつ一様にサンプリングするサンプリング工程、
（３）整数
x[1]∈(Z/p[1])，…，x[s]∈(Z/p[s])
の直和からなる平文
(x[1],…,x[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、公開鍵(g[1],…,g[s])により定義される符号化関数
ε(x[1],…,x[s]) = g[1]x[1]…g[s]x[s]
により符号化する符号化工程、
（４）整数
m[1]∈(Z/p[1])，…，m[s]∈(Z/p[s])
の直和からなる平文
(m[1],…,m[s])∈(Z/p[1]) (+) … (+) (Z/p[s])
を、前記符号化工程にて符号化し、前記サンプリング工程にサンプリングさせたrを乗じて、暗号文
e(m[1],…,m[s]) = ε(m[1],…,m[s])r = g[1]m[1]…g[s]m[s]r
を得る暗号工程、
（５）当該素数
p[1]，…，[s]
と当該公開鍵
(g[1],…,g[s])
に対して、整数i (1≦i≦s)のそれぞれについて定義される関数
d[i](z) = 〔Lp[i](zf[i]) (mod p[i]2)〕/〔Lp[i](g[i]f[i]) (mod p[i]2)〕；
f[i] = 〔Πj=1s p[j](p[j]-1)〕/p[i]
により、暗号文zに対する復号文
d(z) = (d[1](z),…,d[s](z))
を得る復号工程
を備えることを特徴とする暗号方法。
【請求項６】
請求項５に記載の暗号方法であって、
サイズkの互いに異なる素数
q[1]，…，q[s]
を選択し、任意の整数i，j (1≦i,j≦s，i≠j)について
q[i]は、q[j]-1の素因子ではない
ことが満たされるまで当該選択を繰り返し、その結果得られた素数q[1]，…，q[s]を、
p[1]，…，p[s]
とする秘密鍵計算工程
をさらに備えることを特徴とする暗号方法。
【請求項７】
請求項６に記載の暗号方法であって、
s = 4
であり、当該暗号方法は、暗号装置、第１復号装置、第２復号装置が実行し、
（１）当該第１復号装置が、自身の秘密鍵の候補となる素数q[1]，q[2]の積q[1]q[2]を計算して当該第２復号装置に公開し、
当該第２復号装置が、自身の秘密鍵の候補となる素数q[3]，q[4]の積q[3]q[4]を計算して当該第２復号装置に公開し、
当該第１復号装置が、公開されたq[3]q[4]がq[1]-1およびq[2]-1に対して素であることを確認し、
当該第２復号装置が、公開されたq[1]q[2]がq[3]-1およびq[4]-1に対して素であることを確認し、
当該第１復号装置と、当該第２復号装置と、の両者にて、当該素であることが確認されるまでこれを繰り返し、
当該両者にて当該素であることが確認されたら、当該第１暗号装置が、当該素数q[1]，q[2]を自身の秘密鍵p[1]，p[2]とし、当該第２暗号装置が、当該素数q[3]，q[4]を自身の秘密鍵p[3]，p[4]とすることにより、
前記秘密鍵計算工程が実行され、
（２）当該第１復号装置が、自身の秘密鍵p[1]，p[2]からg[1]，g[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置が、自身の秘密鍵p[3]，p[4]からg[3]，g[4]を計算し、これらを当該暗号装置に公開することにより、
前記公開鍵計算工程が実行され、
（３）当該第１復号装置が、自身の秘密鍵p[1]，p[2]の積p[1]p[2]を計算し、これらを当該暗号装置に公開し、
当該第２復号装置が、自身の秘密鍵p[3]，p[4]の積p[3]p[4]を計算し、これらを当該暗号装置に公開し、
当該暗号装置が、当該公開されたp[1]p[2]，p[3]p[4]の積nを計算し、群の要素rをサンプリングすることにより、
前記サンプリング工程が実行され、
（４）前記暗号装置が、公開された公開鍵(g[1],g[2],g[3],g[4])により平文を符号化することにより、
前記符号化工程が実行され、
（５）前記暗号装置が、前記符号化工程にて当該第１復号装置宛の平文m[1],m[2]および第２復号装置宛の平文m[3],m[4]を符号化させ、
前記サンプリング工程にてサンプリングさせたrを乗じ、暗号文zを得ることにより、
前記暗号工程が実行され、
（６）前記第１復号装置が、自身の秘密鍵p[1]，p[2]からp[1](p[1]-1)p[2](p[2]-1)を計算して前記第２復号装置に公開し、
前記第２復号装置が、自身の秘密鍵p[3]，p[4]からp[3](p[3]-1)p[4](p[4]-1)を計算して前記第１復号装置に公開し、
前記第１復号装置が、暗号文zから自身宛の復号文d[1](z)，d[2](z)を計算し、
前記第２復号装置が、暗号文zから自身宛の復号文d[3](z)，d[4](z)を計算して、
前記復号工程が実行される
ことを特徴とする暗号方法。
【請求項８】
請求項５または６に記載の暗号方法であって、
前記暗号工程では、複数の平文を受け付け、平文を受け付けるごとに暗号文を得て、得られた暗号文のすべての積を前記復号工程に与える
ことを特徴とする暗号方法。
【請求項９】
コンピュータもしくはコンピュータ群に、請求項１から４のいずれか１項に記載の暗号システムの各部を実行させることを特徴とするプログラム。
【請求項１０】
コンピュータもしくはコンピュータ群に、請求項１から３のいずれか１項に記載の暗号システムの各部を実行させることを特徴とするプログラムを記録したコンピュータ読取可能な情報記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００９−１４５６６３（Ｐ２００９−１４５６６３Ａ）
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願番号】特願２００７−３２３２８５（Ｐ２００７−３２３２８５）
【出願日】平成１９年１２月１４日（２００７．１２．１４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願日】平成１９年１２月１４日（２００７．１２．１４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]