準同型暗号システム、準同型暗号方法、プログラム
【課題】 ＩＮＤ−ＣＣＡ１安全性を満たす準同型暗号を実現すること。
【解決手段】 鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【解決手段】 鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、準同型暗号システム、準同型暗号方法、プログラムに関する。
【背景技術】
【０００２】
インターネット上の通信の安全性を守る為に、暗号技術はかせない。暗号技術の中に，準同型暗号方式と呼ばれる技術がある。この技術は電子投票や電子現金といった様々な暗号プロトコルの部品として用いられている為、非常に重要である。
【０００３】
準同型暗号方式は公開鍵暗号方式の一種で、平文の空間が群をなしており、「準同型変換」という変換を持っており、しかも平文Mの暗号文Cと平文M'の暗号文C'とを準同型変換すると、積MM'の暗号文が計算できるものの事である。厳密には、鍵生成アルゴリズム、暗号化アルゴリズム、準同型変換アルゴリズム、復号アルゴリズムという４つのアルゴリズムの組を準同型暗号方式と呼ぶ。ここで、鍵生成アルゴリズム、暗号化アルゴリズム、準同型変換アルゴリズム、復号アルゴリズムとは、以下の入出力を持つアルゴリズムの事である。
【０００４】
１−１） 鍵生成アルゴリズムは公開鍵と秘密鍵とを出力する。
１−２） 暗号化アルゴリズムは公開鍵と平文とを入力として受けとり、暗号文を出力する。
１−３） 準同型変換アルゴリズムは２つの暗号文を入力として受け取り、(一般にはそれらとは異なる)変換した暗号文を出力する。
１−４） 復号アルゴリズムは秘密鍵と暗号文とを入力として受け取り、平文を出力する。
【０００５】
ただしこれらのアルゴリズムは以下の２つの性質を満たさねばならない。
【０００６】
２−１） 平文Mを暗号化アルゴリズムに入力して得た暗号文を復号すると、Mに戻る。
２−２） 平文Mを暗号化アルゴリズムに入力する事で暗号文Cを得、平文M'を暗号化アルゴリズムに入力する事で暗号文C'を得、準同型変換アルゴリズムにCとC'を入力する事で暗号文C''を得、そしてC''を復号アルゴリズムに入力すると、その出力として積MM'を得る。
【０００７】
代表的な準同型暗号方式として、ElGamal暗号方式がある。qを素数とし、Ｇを位数がqである有限群とし、Ｚq={0,1,...,q-1}とするとき、ElGamal暗号方式とは以下の準同型暗号方式の事である。
【０００８】
３−１） (鍵生成アルゴリズム) Ｇの元gとＺqの元xをランダムに選び、h=gxを計算し、(g,h)を公開鍵とし、xを秘密鍵とする。
３−２） (暗号化アルゴリズム) Ｇの元である平文Mと公開鍵(g,h)とを入力として受け取り、Ｚqの元rをランダムに選び、u=grとv=Mhrとを計算し、(u,v)を暗号文Ｃとして出力する。
３−３） (準同型変換アルゴリズム) ２つの暗号文Ｃ＝(u,v)，Ｃ’＝(u',v')を入力として受け取り、変換した暗号文Ｃ”＝(uu',vv')を出力する。
３−４） (復号アルゴリズム) 秘密鍵xと暗号文Ｃ＝(u,v)とを受け取り、v/uxを平文Ｍとして出力する。
【０００９】
ところで、公開鍵暗号への攻撃のタイプとして、選択平文攻撃（Chosen Plaintext Attack、以下ＣＰＡ）と選択暗号文攻撃（Chosen Ciphertext Attack、以下ＣＣＡ１）とが知られている。また、いかなる部分解読も困難である場合、その暗号方式は「強秘匿性（indistinguishability of encryption、以下ＩＮＤとする）」を有していると呼ばれる。
【００１０】
しかしながら、ElGamal暗号をはじめとして既存の準同型暗号は、IND-CPA（選択平文攻撃に対して強秘匿）安全性という弱い安全性しか満たさない。
【００１１】
このように、ElGamal暗号は準同型暗号であるが、IND-CCA1（選択暗号文攻撃に対して強秘匿）安全性を満たさない。ElGamal暗号は不正な方法で作られた暗号文を排除できない事がIND-CCA1安全性を満たさない理由である事が知られている。
【００１２】
一方、非特許文献１において提案されている暗号方式は、不正な方法で作られた暗号文を排除する機構を持ち、その結果としてIND-CCA1安全性よりさらに強い安全性を満たすが、準同型暗号ではない。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Dennis Hofheinz, Eike Kiltz: Secure Hybrid Encryption from Weakened Key Encapsulation. CRYPTO 2007: 553-571
【発明の概要】
【発明が解決しようとする課題】
【００１４】
インターネット上の通信の安全性を高める為には、可能な限り強い安全性を見たす暗号方式を利用する事が望ましい。しかしながら、既存の準同型暗号は、IND-CPA安全性という弱い安全性しか満たさない。
【００１５】
本発明が解決しようとする課題は、IND-CCA1安全性というより強い安全性を満たす準同型暗号を実現する事にある。
【課題を解決するための手段】
【００１６】
そこで本発明では、非特許文献１に類似したテクニックを用いて不正な方法で作られた暗号文を排除しつつ、ElGamal暗号をベースにする事でIND-CCA1安全な準同型暗号を実現する。
【００１７】
すなわち、本発明による準同型暗号システムは、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、この暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【発明の効果】
【００１８】
本発明によれば、IND-CCA1安全性というより強い安全性を満たす準同型暗号を実現する事ができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施の形態に係る準同型暗号システムの構成を示すブロック図である。
【図２】図１に示した準同型暗号システムの各装置の構成を示すブロック図である。
【図３】図１に示した鍵生成装置の動作を説明するためのフローチャートである。
【図４】図１に示した暗号化装置の動作を説明するためのフローチャートである。
【図５】図１に示した準同型変換装置の動作を説明するためのフローチャートである。
【図６】図１に示した復号装置の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００２０】
図１、図２は本発明の装置構成を描いたブロック図である。図１は、本発明の一実施の形態に係る準同型暗号システムを示すブロック図である。図示の準同型暗号システムは、送信者装置１、変換装置２、および受信者装置３から構成されている。図１ではこれら３つが別の装置である場合を想定しているが、これら３つのうち２つ以上が同一の装置であっても構わない。たとえば、変換装置２と受信者装置３が同一であってもよい。
【００２１】
図２に示されるように、各装置には、演算部１１，入出力部１２、記憶部１３、および通信部１４が備わっている。これらの手段１１〜１４を用いる事で、本発明の利用者はそれぞれデータの演算を行ったり、データの入出力を行ったり、データを記憶したり、装置同士が通信したりする事ができる。
【００２２】
演算部１１は例えばコンピュータのCPUを用いて実装する事ができる。記憶部１３は例えばコンピュータのメモリやハードディスクを用いて実装する事ができる。通信部１４は例えばインターネットを用いて実装する事ができる。
【００２３】
各装置の演算部１１には、以下の装置が備わっている。送信者装置１は鍵生成装置４と暗号化装置５とを持つ。変換装置２は準同型変換装置６を持つ。受信者装置３は復号装置７を持つ。
【００２４】
鍵生成装置４は、後述するような、公開鍵Ｙと秘密鍵Ｘとを出力する。暗号化装置５は公開鍵Ｙと平文Ｍとを入力として受けとり、後述するような暗号文Ｃを出力する。準同型変換装置６は２つの暗号文Ｃ、Ｃ’を入力として受け取り、(一般にはそれらとは異なる)変換した暗号文Ｃ”を出力する。復号装置７は秘密鍵Ｘと暗号文ＣないしＣ”とを入力として受け取り，平文Ｍを出力する。
【００２５】
本発明の装置は以下の順序で実施される。まず送信者装置１は鍵生成装置４を動作させて，公開鍵Ｙと秘密鍵Ｘとを得、公開鍵Ｙを公開し、秘密鍵Ｘを記憶部１３に秘密裡に保管する。受信者装置３は公開されている公開鍵Ｙを入手する。送信者装置１がどのような方法で公開鍵Ｙを公開し、受信者装置３がどのような方法で公開鍵Ｙを入手するかは問わない。例えばPKI（Public Key Infrastructure）を利用して公開および入手ができる。
【００２６】
送信者装置１は暗号化装置５を動作させる事で平文Ｍを暗号化できる。暗号化装置５を複数回動作あせれば，複数の平文Ｍ、Ｍ’を暗号化でき、その結果として複数の暗号文Ｃ、Ｃ’が得られる。送信者装置１は通信部１４を用いる事で、暗号文Ｃ、Ｃ’を必要に応じて変換装置２ないし受信者装置３に送る。
【００２７】
変換装置２は通信部１４から２つの暗号文Ｃ、Ｃ’を入手したら、準同型変換装置６を動作せる事で、変換した暗号文Ｃ”を得る事ができる。変換装置２は通信部１４を用いる事で、変換した暗号文Ｃ”を必要に応じて受信者装置３に送信する。
【００２８】
受信者装置３は通信部１４から暗号文Ｃないし変換した暗号文Ｃ”を入手し、復号装置７を動作せる事で平文Ｍを得る。
【００２９】
次に、各装置の詳細を説明する。
【００３０】
qを素数とし、Ｇを位数がqである有限群とし、nを非負の整数とする。安全性上の観点から言えば、Ｇはn-Linear仮定を満たす事が望ましい。n-Linear仮定の詳細については、上記非特許文献１に記載されている。この仮定を満たすＧとして例えば楕円曲線群がある。各装置の詳細は以下のとおりである。
【００３１】
図３を参照して、鍵生成装置４の動作について説明する。
【００３２】
まず、鍵生成装置４は、Ｇの元g[1]，...，g[n]，hをランダムに選ぶ（ステップ３１)。
【００３３】
次に、鍵生成装置４は、Ｚqの元x[1]，...，x[n]，y[1]，...，y[n]，α，βをランダムに選ぶ(ステップ３２)。
【００３４】
次に、鍵生成装置４は、c[1]=g[1]x[1]hα，...，c[n]=g[n]x[n]hαを計算する(ステップ３３)。すなわち、鍵生成装置４は、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する。
【００３５】
次に、鍵生成装置４は、d[1]=g[1]y[1]hβ，...，d[n]=g[n]y[n]hβを計算する(ステップ３４)。すなわち、鍵生成装置４は、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する。
【００３６】
次に、鍵生成装置４は、(g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n])を公開鍵Ｙとして出力する(ステップ３５)。
【００３７】
最後に、鍵生成装置４は、(x[1]，...，x[n]，y[1]，...，y[n]，α，β)を秘密鍵Ｘして出力する(ステップ３６)。
【００３８】
上述したように鍵生成装置４は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う鍵生成プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、鍵生成装置４を実現することができる。
【００３９】
次に、図４を参照して、暗号化装置５の動作について説明する。
【００４０】
まず、暗号化装置５は、公開鍵Ｙ＝(g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n])と平文Mとを入力として受け取る(ステップ４１)。
【００４１】
次に、暗号化装置５は、Ｚqの元r[1]，...，r[n]をランダムに選ぶ(ステップ４２)。
【００４２】
次に、暗号化装置５は、u[1]=g[1]r[1]，...，g[n]=c[n]r[n]を計算する(ステップ４３)。すなわち、暗号化装置５は、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する。
【００４３】
次に、暗号化装置５は、v=hr[1]+…+r[n]を計算する(ステップ４４)。すなわち、暗号化装置５は、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する。
【００４４】
次に、暗号化装置５は、w=Mc[1]r[1]…c[n]r[n]を計算する(ステップ４５)。すなわち、暗号化装置５は、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する。
【００４５】
次に、暗号化装置５は、π=d[1]r[1]…d[n]r[n]を計算する(ステップ４６)。すなわち、暗号化装置５は、d[1]のr[1]乗，...，[n]のr[n]乗を全てかけたものをπとして計算する。
【００４６】
最後に、暗号化装置５は、(u[1],...,u[n],v,w,π)を暗号文Ｃとして出力する(ステップ４７)。
【００４７】
上述したように暗号化装置５は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う暗号化プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、暗号化装置５を実現することができる。
【００４８】
次に、図５を参照して、準同型変換装置６の動作について説明する。
【００４９】
まず、準同型変換装置６は、２つの暗号文Ｃ＝(u[1],...,u[n],v,w,π)，Ｃ’＝(u'[1],...,u'[n],v',w',π')を入力として受け取る(ステップ５１)。すなわち、準同型変換装置６は、暗号化装置５から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文Ｃと、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文Ｃ’とを受け取る。
【００５０】
最後に、準同型変換装置６は、(u[1]u'[1],...,u[n]u'[n],vv',ww',ππ')、を変換した暗号文Ｃ”として出力する(ステップ５２)。すなわち、準同型変換装置６は、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文Ｃ”として出力する。
【００５１】
上述したように準同型変換装置６は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う準同型変換プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、準同型変換装置６を実現することができる。
【００５２】
図６を参照して、復号装置７の動作について説明する。
【００５３】
まず、復号装置７は、秘密鍵Ｘ＝(x[1]，...，x[n]，y[1]，...，y[n]，α，β)と暗号文Ｃ＝(u[1],...,u[n],v,w,π)とを入力として受け取る(ステップ６１)。
【００５４】
次に、復号装置７は、π=u[1]x[1]…u[n]x[n]vαならw/u[1]y[1]…u[n]y[n]vβを復号結果Ｍとして出力し，そうでなければ暗号文が不正である旨を出力する(ステップ６２)。すなわち、復号装置７は、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００５５】
上述したように復号装置７は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う復号プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、復号装置７を実現することができる。
【００５６】
インターネット上の通信の安全性を守る為には、そこで使われている暗号の強度が強ければ強いほどよい。したがって準同型暗号方式の代表例であるElGamal暗号の代わりに、本発明に係る準同型暗号システムを用いる事でより安全にインターネット通信ができる。準同型暗号方式の代表例であるElGamal暗号は、電子投票や電子現金といった産業上有益な暗号プロトコルを作る部品として用いられている。従ってこうした暗号プロトコルにおけるElGamal暗号を本発明に係る準同型暗号システムと置き換える事で、より安全性の高い暗号プロトコルを実現できる。
【００５７】
上述したように準同型暗号システムは動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う暗号プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、準同型暗号システムを実現することができる。
【００５８】
以下に、本発明の態様について説明する。
【００５９】
本発明の第１の態様による準同型暗号システムは、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、この暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【００６０】
上記本発明の第１の態様による準同型暗号システムにおいて、上記暗号化装置は、公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含むものであってよい。上記準同型変換装置は、上記暗号化装置から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含むものであってよい。上記復号装置は、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含むものであってよい。
【００６１】
本発明の第２の態様による準同型暗号方法は、公開鍵と秘密鍵とを出力する鍵生成ステップと、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップと、この暗号化ステップから出力される２つの暗号文から変換した暗号文を出力する準同型変換ステップと、秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップとを含む、準同型暗号方法であって、鍵生成ステップは、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００６２】
上記本発明の第２の態様による準同型暗号方法において、上記暗号化ステップは、公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力するものであってよい。上記準同型変換ステップは、上記暗号化ステップから、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力するものであってよい。上記復号ステップは、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力するものであってよい。
【００６３】
本発明の第３の態様による送信者装置は、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置とを含む送信者装置であって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]の[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【００６４】
上記本発明の第３の態様による送信者装置において、上記暗号化装置は、公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含むものであってよい。
【００６５】
本発明の第４の態様による変換装置は、２つの暗号文から変換した暗号文を出力する準同型変換装置を含む変換装置であって、準同型変換装置は、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含む。
【００６６】
本発明の第５の態様による受信者装置は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置を含む受信者装置であって、復号装置は、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含む。
【００６７】
本発明の第６の態様による送信方法は、公開鍵と秘密鍵とを出力する鍵生成ステップと、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップとを含む送信方法であって、鍵生成ステップは、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００６８】
上記本発明の第６の態様による送信方法において、上記暗号化ステップは、公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力するものであってよい。
【００６９】
本発明の第７の態様による変換方法は、２つの暗号文から変換した暗号文を出力する準同型変換ステップを含む変換方法であって、準同型変換ステップは、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する。
【００７０】
本発明の第８の態様による受信方法は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップを含む受信方法であって、復号ステップは、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００７１】
本発明の第９の態様による鍵生成装置は、公開鍵と秘密鍵とを出力する鍵生成装置であって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を含む。
【００７２】
本発明の第１０の態様による暗号化装置は、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置であって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含む。
【００７３】
本発明の第１１の態様による準同型変換装置は、２つの暗号文から変換した暗号文を出力する準同型変換装置であって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含む。
【００７４】
本発明の第１２の態様による復号装置は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置であって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含む。
【００７５】
本発明の第１３の態様による鍵生成方法は、公開鍵と秘密鍵とを出力する鍵生成方法であって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００７６】
本発明の第１４の態様による暗号化方法は、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化方法であって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力する。
【００７７】
本発明の第１５の態様による準同型変換方法は、２つの暗号文から変換した暗号文を出力する準同型変換方法であって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する。
【００７８】
本発明の第１６の態様による復号方法は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号方法であって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００７９】
本発明の第１７の態様による鍵生成プログラムは、コンピュータに、公開鍵と秘密鍵とを出力させるための鍵生成プログラムであって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手順と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手順と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手順と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手順と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手順と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手順と、を前記コンピュータに実行させる。
【００８０】
本発明の第１８の態様による暗号化プログラムは、コンピュータに、公開鍵と平文（Ｍ）とから暗号文を出力させる暗号化プログラムであって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取る手順と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手順と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手順と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手順と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手順と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手順と、u[1],...,u[n],v,w,πを暗号文として出力する手順と、をコンピュータに実行させる。
【００８１】
本発明の第１９の態様による準同型変換プログラムは、コンピュータに、２つの暗号文から変換した暗号文を出力させる準同型変換プログラムであって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手順と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手順と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手順と、をコンピュータに実行させる。
【００８２】
本発明の第２０の態様による復号プログラムは、コンピュータに、秘密鍵と暗号文とから平文（Ｍ）を復号させる復号プログラムであって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手順と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手順と、をコンピュータに実行させる。
【００８３】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【００８４】
本発明は、電子投票や電子現金といった産業上有益で、より安全性の高い暗号プロトコルを作る部品として利用され得る。
【符号の説明】
【００８５】
１ ・・・ 送信者装置
２ ・・・ 変換装置
３ ・・・ 受信者装置
４ ・・・ 鍵生成装置
５ ・・・ 暗号化装置
６ ・・・ 準同型変換装置
７ ・・・ 復号装置
Ｍ ・・・ 平文
Ｘ ・・・ 秘密鍵
Ｙ ・・・ 公開鍵
Ｃ、Ｃ’ ・・・ 暗号文
Ｃ” ・・・ 変換した暗号文
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、準同型暗号システム、準同型暗号方法、プログラムに関する。
【背景技術】
【０００２】
インターネット上の通信の安全性を守る為に、暗号技術はかせない。暗号技術の中に，準同型暗号方式と呼ばれる技術がある。この技術は電子投票や電子現金といった様々な暗号プロトコルの部品として用いられている為、非常に重要である。
【０００３】
準同型暗号方式は公開鍵暗号方式の一種で、平文の空間が群をなしており、「準同型変換」という変換を持っており、しかも平文Mの暗号文Cと平文M'の暗号文C'とを準同型変換すると、積MM'の暗号文が計算できるものの事である。厳密には、鍵生成アルゴリズム、暗号化アルゴリズム、準同型変換アルゴリズム、復号アルゴリズムという４つのアルゴリズムの組を準同型暗号方式と呼ぶ。ここで、鍵生成アルゴリズム、暗号化アルゴリズム、準同型変換アルゴリズム、復号アルゴリズムとは、以下の入出力を持つアルゴリズムの事である。
【０００４】
１−１） 鍵生成アルゴリズムは公開鍵と秘密鍵とを出力する。
１−２） 暗号化アルゴリズムは公開鍵と平文とを入力として受けとり、暗号文を出力する。
１−３） 準同型変換アルゴリズムは２つの暗号文を入力として受け取り、(一般にはそれらとは異なる)変換した暗号文を出力する。
１−４） 復号アルゴリズムは秘密鍵と暗号文とを入力として受け取り、平文を出力する。
【０００５】
ただしこれらのアルゴリズムは以下の２つの性質を満たさねばならない。
【０００６】
２−１） 平文Mを暗号化アルゴリズムに入力して得た暗号文を復号すると、Mに戻る。
２−２） 平文Mを暗号化アルゴリズムに入力する事で暗号文Cを得、平文M'を暗号化アルゴリズムに入力する事で暗号文C'を得、準同型変換アルゴリズムにCとC'を入力する事で暗号文C''を得、そしてC''を復号アルゴリズムに入力すると、その出力として積MM'を得る。
【０００７】
代表的な準同型暗号方式として、ElGamal暗号方式がある。qを素数とし、Ｇを位数がqである有限群とし、Ｚq={0,1,...,q-1}とするとき、ElGamal暗号方式とは以下の準同型暗号方式の事である。
【０００８】
３−１） (鍵生成アルゴリズム) Ｇの元gとＺqの元xをランダムに選び、h=gxを計算し、(g,h)を公開鍵とし、xを秘密鍵とする。
３−２） (暗号化アルゴリズム) Ｇの元である平文Mと公開鍵(g,h)とを入力として受け取り、Ｚqの元rをランダムに選び、u=grとv=Mhrとを計算し、(u,v)を暗号文Ｃとして出力する。
３−３） (準同型変換アルゴリズム) ２つの暗号文Ｃ＝(u,v)，Ｃ’＝(u',v')を入力として受け取り、変換した暗号文Ｃ”＝(uu',vv')を出力する。
３−４） (復号アルゴリズム) 秘密鍵xと暗号文Ｃ＝(u,v)とを受け取り、v/uxを平文Ｍとして出力する。
【０００９】
ところで、公開鍵暗号への攻撃のタイプとして、選択平文攻撃（Chosen Plaintext Attack、以下ＣＰＡ）と選択暗号文攻撃（Chosen Ciphertext Attack、以下ＣＣＡ１）とが知られている。また、いかなる部分解読も困難である場合、その暗号方式は「強秘匿性（indistinguishability of encryption、以下ＩＮＤとする）」を有していると呼ばれる。
【００１０】
しかしながら、ElGamal暗号をはじめとして既存の準同型暗号は、IND-CPA（選択平文攻撃に対して強秘匿）安全性という弱い安全性しか満たさない。
【００１１】
このように、ElGamal暗号は準同型暗号であるが、IND-CCA1（選択暗号文攻撃に対して強秘匿）安全性を満たさない。ElGamal暗号は不正な方法で作られた暗号文を排除できない事がIND-CCA1安全性を満たさない理由である事が知られている。
【００１２】
一方、非特許文献１において提案されている暗号方式は、不正な方法で作られた暗号文を排除する機構を持ち、その結果としてIND-CCA1安全性よりさらに強い安全性を満たすが、準同型暗号ではない。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Dennis Hofheinz, Eike Kiltz: Secure Hybrid Encryption from Weakened Key Encapsulation. CRYPTO 2007: 553-571
【発明の概要】
【発明が解決しようとする課題】
【００１４】
インターネット上の通信の安全性を高める為には、可能な限り強い安全性を見たす暗号方式を利用する事が望ましい。しかしながら、既存の準同型暗号は、IND-CPA安全性という弱い安全性しか満たさない。
【００１５】
本発明が解決しようとする課題は、IND-CCA1安全性というより強い安全性を満たす準同型暗号を実現する事にある。
【課題を解決するための手段】
【００１６】
そこで本発明では、非特許文献１に類似したテクニックを用いて不正な方法で作られた暗号文を排除しつつ、ElGamal暗号をベースにする事でIND-CCA1安全な準同型暗号を実現する。
【００１７】
すなわち、本発明による準同型暗号システムは、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、この暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【発明の効果】
【００１８】
本発明によれば、IND-CCA1安全性というより強い安全性を満たす準同型暗号を実現する事ができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施の形態に係る準同型暗号システムの構成を示すブロック図である。
【図２】図１に示した準同型暗号システムの各装置の構成を示すブロック図である。
【図３】図１に示した鍵生成装置の動作を説明するためのフローチャートである。
【図４】図１に示した暗号化装置の動作を説明するためのフローチャートである。
【図５】図１に示した準同型変換装置の動作を説明するためのフローチャートである。
【図６】図１に示した復号装置の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００２０】
図１、図２は本発明の装置構成を描いたブロック図である。図１は、本発明の一実施の形態に係る準同型暗号システムを示すブロック図である。図示の準同型暗号システムは、送信者装置１、変換装置２、および受信者装置３から構成されている。図１ではこれら３つが別の装置である場合を想定しているが、これら３つのうち２つ以上が同一の装置であっても構わない。たとえば、変換装置２と受信者装置３が同一であってもよい。
【００２１】
図２に示されるように、各装置には、演算部１１，入出力部１２、記憶部１３、および通信部１４が備わっている。これらの手段１１〜１４を用いる事で、本発明の利用者はそれぞれデータの演算を行ったり、データの入出力を行ったり、データを記憶したり、装置同士が通信したりする事ができる。
【００２２】
演算部１１は例えばコンピュータのCPUを用いて実装する事ができる。記憶部１３は例えばコンピュータのメモリやハードディスクを用いて実装する事ができる。通信部１４は例えばインターネットを用いて実装する事ができる。
【００２３】
各装置の演算部１１には、以下の装置が備わっている。送信者装置１は鍵生成装置４と暗号化装置５とを持つ。変換装置２は準同型変換装置６を持つ。受信者装置３は復号装置７を持つ。
【００２４】
鍵生成装置４は、後述するような、公開鍵Ｙと秘密鍵Ｘとを出力する。暗号化装置５は公開鍵Ｙと平文Ｍとを入力として受けとり、後述するような暗号文Ｃを出力する。準同型変換装置６は２つの暗号文Ｃ、Ｃ’を入力として受け取り、(一般にはそれらとは異なる)変換した暗号文Ｃ”を出力する。復号装置７は秘密鍵Ｘと暗号文ＣないしＣ”とを入力として受け取り，平文Ｍを出力する。
【００２５】
本発明の装置は以下の順序で実施される。まず送信者装置１は鍵生成装置４を動作させて，公開鍵Ｙと秘密鍵Ｘとを得、公開鍵Ｙを公開し、秘密鍵Ｘを記憶部１３に秘密裡に保管する。受信者装置３は公開されている公開鍵Ｙを入手する。送信者装置１がどのような方法で公開鍵Ｙを公開し、受信者装置３がどのような方法で公開鍵Ｙを入手するかは問わない。例えばPKI（Public Key Infrastructure）を利用して公開および入手ができる。
【００２６】
送信者装置１は暗号化装置５を動作させる事で平文Ｍを暗号化できる。暗号化装置５を複数回動作あせれば，複数の平文Ｍ、Ｍ’を暗号化でき、その結果として複数の暗号文Ｃ、Ｃ’が得られる。送信者装置１は通信部１４を用いる事で、暗号文Ｃ、Ｃ’を必要に応じて変換装置２ないし受信者装置３に送る。
【００２７】
変換装置２は通信部１４から２つの暗号文Ｃ、Ｃ’を入手したら、準同型変換装置６を動作せる事で、変換した暗号文Ｃ”を得る事ができる。変換装置２は通信部１４を用いる事で、変換した暗号文Ｃ”を必要に応じて受信者装置３に送信する。
【００２８】
受信者装置３は通信部１４から暗号文Ｃないし変換した暗号文Ｃ”を入手し、復号装置７を動作せる事で平文Ｍを得る。
【００２９】
次に、各装置の詳細を説明する。
【００３０】
qを素数とし、Ｇを位数がqである有限群とし、nを非負の整数とする。安全性上の観点から言えば、Ｇはn-Linear仮定を満たす事が望ましい。n-Linear仮定の詳細については、上記非特許文献１に記載されている。この仮定を満たすＧとして例えば楕円曲線群がある。各装置の詳細は以下のとおりである。
【００３１】
図３を参照して、鍵生成装置４の動作について説明する。
【００３２】
まず、鍵生成装置４は、Ｇの元g[1]，...，g[n]，hをランダムに選ぶ（ステップ３１)。
【００３３】
次に、鍵生成装置４は、Ｚqの元x[1]，...，x[n]，y[1]，...，y[n]，α，βをランダムに選ぶ(ステップ３２)。
【００３４】
次に、鍵生成装置４は、c[1]=g[1]x[1]hα，...，c[n]=g[n]x[n]hαを計算する(ステップ３３)。すなわち、鍵生成装置４は、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する。
【００３５】
次に、鍵生成装置４は、d[1]=g[1]y[1]hβ，...，d[n]=g[n]y[n]hβを計算する(ステップ３４)。すなわち、鍵生成装置４は、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する。
【００３６】
次に、鍵生成装置４は、(g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n])を公開鍵Ｙとして出力する(ステップ３５)。
【００３７】
最後に、鍵生成装置４は、(x[1]，...，x[n]，y[1]，...，y[n]，α，β)を秘密鍵Ｘして出力する(ステップ３６)。
【００３８】
上述したように鍵生成装置４は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う鍵生成プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、鍵生成装置４を実現することができる。
【００３９】
次に、図４を参照して、暗号化装置５の動作について説明する。
【００４０】
まず、暗号化装置５は、公開鍵Ｙ＝(g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n])と平文Mとを入力として受け取る(ステップ４１)。
【００４１】
次に、暗号化装置５は、Ｚqの元r[1]，...，r[n]をランダムに選ぶ(ステップ４２)。
【００４２】
次に、暗号化装置５は、u[1]=g[1]r[1]，...，g[n]=c[n]r[n]を計算する(ステップ４３)。すなわち、暗号化装置５は、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する。
【００４３】
次に、暗号化装置５は、v=hr[1]+…+r[n]を計算する(ステップ４４)。すなわち、暗号化装置５は、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する。
【００４４】
次に、暗号化装置５は、w=Mc[1]r[1]…c[n]r[n]を計算する(ステップ４５)。すなわち、暗号化装置５は、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する。
【００４５】
次に、暗号化装置５は、π=d[1]r[1]…d[n]r[n]を計算する(ステップ４６)。すなわち、暗号化装置５は、d[1]のr[1]乗，...，[n]のr[n]乗を全てかけたものをπとして計算する。
【００４６】
最後に、暗号化装置５は、(u[1],...,u[n],v,w,π)を暗号文Ｃとして出力する(ステップ４７)。
【００４７】
上述したように暗号化装置５は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う暗号化プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、暗号化装置５を実現することができる。
【００４８】
次に、図５を参照して、準同型変換装置６の動作について説明する。
【００４９】
まず、準同型変換装置６は、２つの暗号文Ｃ＝(u[1],...,u[n],v,w,π)，Ｃ’＝(u'[1],...,u'[n],v',w',π')を入力として受け取る(ステップ５１)。すなわち、準同型変換装置６は、暗号化装置５から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文Ｃと、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文Ｃ’とを受け取る。
【００５０】
最後に、準同型変換装置６は、(u[1]u'[1],...,u[n]u'[n],vv',ww',ππ')、を変換した暗号文Ｃ”として出力する(ステップ５２)。すなわち、準同型変換装置６は、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文Ｃ”として出力する。
【００５１】
上述したように準同型変換装置６は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う準同型変換プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、準同型変換装置６を実現することができる。
【００５２】
図６を参照して、復号装置７の動作について説明する。
【００５３】
まず、復号装置７は、秘密鍵Ｘ＝(x[1]，...，x[n]，y[1]，...，y[n]，α，β)と暗号文Ｃ＝(u[1],...,u[n],v,w,π)とを入力として受け取る(ステップ６１)。
【００５４】
次に、復号装置７は、π=u[1]x[1]…u[n]x[n]vαならw/u[1]y[1]…u[n]y[n]vβを復号結果Ｍとして出力し，そうでなければ暗号文が不正である旨を出力する(ステップ６２)。すなわち、復号装置７は、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００５５】
上述したように復号装置７は動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う復号プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、復号装置７を実現することができる。
【００５６】
インターネット上の通信の安全性を守る為には、そこで使われている暗号の強度が強ければ強いほどよい。したがって準同型暗号方式の代表例であるElGamal暗号の代わりに、本発明に係る準同型暗号システムを用いる事でより安全にインターネット通信ができる。準同型暗号方式の代表例であるElGamal暗号は、電子投票や電子現金といった産業上有益な暗号プロトコルを作る部品として用いられている。従ってこうした暗号プロトコルにおけるElGamal暗号を本発明に係る準同型暗号システムと置き換える事で、より安全性の高い暗号プロトコルを実現できる。
【００５７】
上述したように準同型暗号システムは動作するが、このような動作をコンピュータ（演算部１１）上で実現することもできる。例えば、上記動作を行う暗号プログラムをメモリ（記憶部１３）に格納しておき、それをプログラム制御プロセッサ（コンピュータ（演算部１１））によって実現することで、準同型暗号システムを実現することができる。
【００５８】
以下に、本発明の態様について説明する。
【００５９】
本発明の第１の態様による準同型暗号システムは、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、この暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【００６０】
上記本発明の第１の態様による準同型暗号システムにおいて、上記暗号化装置は、公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含むものであってよい。上記準同型変換装置は、上記暗号化装置から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含むものであってよい。上記復号装置は、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含むものであってよい。
【００６１】
本発明の第２の態様による準同型暗号方法は、公開鍵と秘密鍵とを出力する鍵生成ステップと、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップと、この暗号化ステップから出力される２つの暗号文から変換した暗号文を出力する準同型変換ステップと、秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップとを含む、準同型暗号方法であって、鍵生成ステップは、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００６２】
上記本発明の第２の態様による準同型暗号方法において、上記暗号化ステップは、公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力するものであってよい。上記準同型変換ステップは、上記暗号化ステップから、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力するものであってよい。上記復号ステップは、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力するものであってよい。
【００６３】
本発明の第３の態様による送信者装置は、公開鍵と秘密鍵とを出力する鍵生成装置と、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置とを含む送信者装置であって、鍵生成装置は、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]の[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を有する。
【００６４】
上記本発明の第３の態様による送信者装置において、上記暗号化装置は、公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含むものであってよい。
【００６５】
本発明の第４の態様による変換装置は、２つの暗号文から変換した暗号文を出力する準同型変換装置を含む変換装置であって、準同型変換装置は、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含む。
【００６６】
本発明の第５の態様による受信者装置は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置を含む受信者装置であって、復号装置は、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含む。
【００６７】
本発明の第６の態様による送信方法は、公開鍵と秘密鍵とを出力する鍵生成ステップと、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップとを含む送信方法であって、鍵生成ステップは、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００６８】
上記本発明の第６の態様による送信方法において、上記暗号化ステップは、公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力するものであってよい。
【００６９】
本発明の第７の態様による変換方法は、２つの暗号文から変換した暗号文を出力する準同型変換ステップを含む変換方法であって、準同型変換ステップは、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する。
【００７０】
本発明の第８の態様による受信方法は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップを含む受信方法であって、復号ステップは、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００７１】
本発明の第９の態様による鍵生成装置は、公開鍵と秘密鍵とを出力する鍵生成装置であって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手段と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手段と、を含む。
【００７２】
本発明の第１０の態様による暗号化装置は、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置であって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取る手段と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手段と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手段と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手段と、u[1],...,u[n],v,w,πを暗号文として出力する手段と、を含む。
【００７３】
本発明の第１１の態様による準同型変換装置は、２つの暗号文から変換した暗号文を出力する準同型変換装置であって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手段と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手段と、を含む。
【００７４】
本発明の第１２の態様による復号装置は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置であって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手段と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手段と、を含む。
【００７５】
本発明の第１３の態様による鍵生成方法は、公開鍵と秘密鍵とを出力する鍵生成方法であって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力し、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する。
【００７６】
本発明の第１４の態様による暗号化方法は、公開鍵と平文（Ｍ）とから暗号文を出力する暗号化方法であって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取り、Ｚｑの元r[1]，...，r[n]をランダムに選び、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算し、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算し、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算し、u[1],...,u[n],v,w,πを暗号文として出力する。
【００７７】
本発明の第１５の態様による準同型変換方法は、２つの暗号文から変換した暗号文を出力する準同型変換方法であって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算し、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する。
【００７８】
本発明の第１６の態様による復号方法は、秘密鍵と暗号文とから平文（Ｍ）を復号する復号方法であって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取り、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する。
【００７９】
本発明の第１７の態様による鍵生成プログラムは、コンピュータに、公開鍵と秘密鍵とを出力させるための鍵生成プログラムであって、位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手順と、Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手順と、g[1]のx[1]乗にhのα乗をかけたものをc[1]とし、g[2]のx[2]乗にhのα乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手順と、g[1]のy[1]乗にhのβ乗をかけたものをd[1]とし，g[2]のｙ[2]乗にhのβ乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手順と、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータを公開鍵として出力する手順と、x[1]，...，x[n]，y[1]，...，y[n]，α，βを秘密鍵として出力する手順と、を前記コンピュータに実行させる。
【００８０】
本発明の第１８の態様による暗号化プログラムは、コンピュータに、公開鍵と平文（Ｍ）とから暗号文を出力させる暗号化プログラムであって、g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる公開鍵と平文（Ｍ）とを入力として受け取る手順と、Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手順と、g[1]のr[1]乗をu[1]とし、g[2]のr[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手順と、hをr[1]，...，r[n]を全て加えたものでべき乗したものをvとして計算する手順と、c[1]のr[1]乗，...，c[n]のr[n]乗を全てかけたものにさらにＭをかけたものをwとして計算する手順と、d[1]のr[1]乗，...，d[n]のr[n]乗を全てかけたものをπとして計算する手順と、u[1],...,u[n],v,w,πを暗号文として出力する手順と、をコンピュータに実行させる。
【００８１】
本発明の第１９の態様による準同型変換プログラムは、コンピュータに、２つの暗号文から変換した暗号文を出力させる準同型変換プログラムであって、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手順と、u[1]とu'[1]の積u''[1],...,u[n]とu'[n]の積u''[n]を計算し、vとv'の積v''を計算し、wとw'の積w''を計算し、πとπ'の積π''を計算する手順と、u''[1],...,u''[n],v'',w'',π''を含むデータを変換した暗号文として出力する手順と、をコンピュータに実行させる。
【００８２】
本発明の第２０の態様による復号プログラムは、コンピュータに、秘密鍵と暗号文とから平文（Ｍ）を復号させる復号プログラムであって、x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ暗号文とを入力として受け取る手順と、u[1]のx[1]乗，...,u[n]のx[n]乗を全てかけあわせたものにさらにvのα乗をかけあわせたものがπと等しければ、u[1]のy[1]乗,…,u[n]のy[n]乗を全てかけあわせたものにさらにｖのβ乗をかけあわせたものによってw剰余したものを出力し、そうでなければ暗号文が不正である旨を出力する手順と、をコンピュータに実行させる。
【００８３】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【００８４】
本発明は、電子投票や電子現金といった産業上有益で、より安全性の高い暗号プロトコルを作る部品として利用され得る。
【符号の説明】
【００８５】
１ ・・・ 送信者装置
２ ・・・ 変換装置
３ ・・・ 受信者装置
４ ・・・ 鍵生成装置
５ ・・・ 暗号化装置
６ ・・・ 準同型変換装置
７ ・・・ 復号装置
Ｍ ・・・ 平文
Ｘ ・・・ 秘密鍵
Ｙ ・・・ 公開鍵
Ｃ、Ｃ’ ・・・ 暗号文
Ｃ” ・・・ 変換した暗号文
【特許請求の範囲】
【請求項１】
公開鍵と秘密鍵とを出力する鍵生成装置と、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、該暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、前記秘密鍵と前記暗号文とから前記平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、
前記鍵生成装置は、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を有する、準同型暗号システム。
【請求項２】
前記暗号化装置は、
前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
前記Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む、請求項１に記載の準同型暗号システム。
【請求項３】
前記準同型変換装置は、
前記暗号化装置から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む、請求項２に記載の準同型暗号システム。
【請求項４】
前記復号装置は、
前記x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵と前記u[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む請求項２又は３に記載の準同型暗号システム。
【請求項５】
公開鍵と秘密鍵とを出力する鍵生成ステップと、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップと、該暗号化ステップから出力される２つの暗号文から変換した暗号文を出力する準同型変換ステップと、前記秘密鍵と前記暗号文とから前記平文（Ｍ）を復号する復号ステップとを含む、準同型暗号方法であって、
前記鍵生成ステップは、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
準同型暗号方法。
【請求項６】
前記暗号化ステップは、
前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
前記Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
請求項５に記載の準同型暗号方法。
【請求項７】
前記準同型変換ステップは、
前記暗号化ステップから、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
請求項６に記載の準同型暗号方法。
【請求項８】
前記復号ステップは、
前記x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵と前記u[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
請求項６又は７に記載の準同型暗号方法。
【請求項９】
公開鍵と秘密鍵とを出力する鍵生成装置と、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置とを含む送信者装置であって、
前記鍵生成装置は、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を有する、送信者装置。
【請求項１０】
前記暗号化装置は、
前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
前記Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む、請求項９に記載の送信者装置。
【請求項１１】
２つの暗号文から変換した暗号文を出力する準同型変換装置を含む変換装置であって、
前記準同型変換装置は、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む、変換装置。
【請求項１２】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置を含む受信者装置であって、前記復号装置は、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む受信者装置。
【請求項１３】
公開鍵と秘密鍵とを出力する鍵生成ステップと、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップとを含む送信方法であって、
前記鍵生成ステップは、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
送信方法。
【請求項１４】
前記暗号化ステップは、
前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
前記Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
請求項１３に記載の送信方法。
【請求項１５】
２つの暗号文から変換した暗号文を出力する準同型変換ステップを含む変換方法であって、
前記準同型変換ステップは、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
変換方法。
【請求項１６】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップを含む受信方法であって、前記復号ステップは、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
受信方法。
【請求項１７】
公開鍵と秘密鍵とを出力する鍵生成装置であって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を含む鍵生成装置。
【請求項１８】
公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置であって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む暗号化装置。
【請求項１９】
２つの暗号文から変換した暗号文を出力する準同型変換装置であって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む準同型変換装置。
【請求項２０】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置であって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む復号装置。
【請求項２１】
公開鍵と秘密鍵とを出力する鍵生成方法であって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
鍵生成方法。
【請求項２２】
公開鍵と平文（Ｍ）とから暗号文を出力する暗号化方法であって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
暗号化方法。
【請求項２３】
２つの暗号文から変換した暗号文を出力する準同型変換方法であって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
準同型変換方法。
【請求項２４】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号方法であって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
復号方法。
【請求項２５】
コンピュータに、公開鍵と秘密鍵とを出力させるための鍵生成プログラムであって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手順と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手順と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手順と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手順と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手順と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手順と、
を前記コンピュータに実行させる鍵生成プログラム。
【請求項２６】
コンピュータに、公開鍵と平文（Ｍ）とから暗号文を出力させる暗号化プログラムであって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取る手順と、
Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手順と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手順と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手順と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手順と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手順と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手順と、
を前記コンピュータに実行させる暗号化プログラム。
【請求項２７】
コンピュータに、２つの暗号文から変換した暗号文を出力させる準同型変換プログラムであって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手順と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手順と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手順と、
を前記コンピュータに実行させる準同型変換プログラム。
【請求項２８】
コンピュータに、秘密鍵と暗号文とから平文（Ｍ）を復号させる復号プログラムであって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手順と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手順と、
を前記コンピュータに実行させる復号プログラム。
【請求項１】
公開鍵と秘密鍵とを出力する鍵生成装置と、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置と、該暗号化装置から出力される２つの暗号文から変換した暗号文を出力する準同型変換装置と、前記秘密鍵と前記暗号文とから前記平文（Ｍ）を復号する復号装置とを含む、準同型暗号システムであって、
前記鍵生成装置は、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を有する、準同型暗号システム。
【請求項２】
前記暗号化装置は、
前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
前記Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む、請求項１に記載の準同型暗号システム。
【請求項３】
前記準同型変換装置は、
前記暗号化装置から、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む、請求項２に記載の準同型暗号システム。
【請求項４】
前記復号装置は、
前記x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵と前記u[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む請求項２又は３に記載の準同型暗号システム。
【請求項５】
公開鍵と秘密鍵とを出力する鍵生成ステップと、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップと、該暗号化ステップから出力される２つの暗号文から変換した暗号文を出力する準同型変換ステップと、前記秘密鍵と前記暗号文とから前記平文（Ｍ）を復号する復号ステップとを含む、準同型暗号方法であって、
前記鍵生成ステップは、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
準同型暗号方法。
【請求項６】
前記暗号化ステップは、
前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
前記Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
請求項５に記載の準同型暗号方法。
【請求項７】
前記準同型変換ステップは、
前記暗号化ステップから、u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
請求項６に記載の準同型暗号方法。
【請求項８】
前記復号ステップは、
前記x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵と前記u[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
請求項６又は７に記載の準同型暗号方法。
【請求項９】
公開鍵と秘密鍵とを出力する鍵生成装置と、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置とを含む送信者装置であって、
前記鍵生成装置は、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を有する、送信者装置。
【請求項１０】
前記暗号化装置は、
前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
前記Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む、請求項９に記載の送信者装置。
【請求項１１】
２つの暗号文から変換した暗号文を出力する準同型変換装置を含む変換装置であって、
前記準同型変換装置は、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む、変換装置。
【請求項１２】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置を含む受信者装置であって、前記復号装置は、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む受信者装置。
【請求項１３】
公開鍵と秘密鍵とを出力する鍵生成ステップと、前記公開鍵と平文（Ｍ）とから暗号文を出力する暗号化ステップとを含む送信方法であって、
前記鍵生成ステップは、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
送信方法。
【請求項１４】
前記暗号化ステップは、
前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
前記Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
請求項１３に記載の送信方法。
【請求項１５】
２つの暗号文から変換した暗号文を出力する準同型変換ステップを含む変換方法であって、
前記準同型変換ステップは、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
変換方法。
【請求項１６】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号ステップを含む受信方法であって、前記復号ステップは、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
受信方法。
【請求項１７】
公開鍵と秘密鍵とを出力する鍵生成装置であって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手段と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手段と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手段と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手段と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手段と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手段と、
を含む鍵生成装置。
【請求項１８】
公開鍵と平文（Ｍ）とから暗号文を出力する暗号化装置であって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取る手段と、
Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手段と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手段と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手段と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手段と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手段と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手段と、
を含む暗号化装置。
【請求項１９】
２つの暗号文から変換した暗号文を出力する準同型変換装置であって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手段と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手段と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手段と、
を含む準同型変換装置。
【請求項２０】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号装置であって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手段と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手段と、
を含む復号装置。
【請求項２１】
公開鍵と秘密鍵とを出力する鍵生成方法であって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選び、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選び、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算し、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算し、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力し、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する、
鍵生成方法。
【請求項２２】
公開鍵と平文（Ｍ）とから暗号文を出力する暗号化方法であって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取り、
Ｚｑの元r[1]，...，r[n]をランダムに選び、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算し、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算し、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算し、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算し、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する、
暗号化方法。
【請求項２３】
２つの暗号文から変換した暗号文を出力する準同型変換方法であって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取り、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算し、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する、
準同型変換方法。
【請求項２４】
秘密鍵と暗号文とから平文（Ｍ）を復号する復号方法であって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取り、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する、
復号方法。
【請求項２５】
コンピュータに、公開鍵と秘密鍵とを出力させるための鍵生成プログラムであって、
位数が素数ｑである有限群Ｇの元g[1]，...，g[n]，およびhをランダムに選ぶ手順と、
Ｚｑの元x[1]，...，x[n]，y[1]，...，y[n]，α，およびβをランダムに選ぶ手順と、
前記g[1]の前記x[1]乗に前記hの前記α乗をかけたものをc[1]とし、前記g[2]の前記x[2]乗に前記hの前記α乗をかけたものをc[2]とし，...という操作をnまで繰り返す事でc[1],...,c[n]を計算する手順と、
前記g[1]の前記y[1]乗に前記hの前記β乗をかけたものをd[1]とし，前記g[2]の前記ｙ[2]乗に前記hの前記β乗をかけたものをd[2]とし，...という操作をnまで繰り返す事でd[1],...,d[n]を計算する手順と、
前記g[1]，...，前記g[n]，前記h，前記c[1]，...，前記c[n]，前記d[1]，...，前記d[n]を含むデータを前記公開鍵として出力する手順と、
前記x[1]，...，前記x[n]，前記y[1]，...，前記y[n]，前記α，前記βを前記秘密鍵として出力する手順と、
を前記コンピュータに実行させる鍵生成プログラム。
【請求項２６】
コンピュータに、公開鍵と平文（Ｍ）とから暗号文を出力させる暗号化プログラムであって、
g[1]，...，g[n]，h，c[1]，...，c[n]，d[1]，...，d[n]を含むデータからなる前記公開鍵と前記平文（Ｍ）とを入力として受け取る手順と、
Ｚｑの元r[1]，...，r[n]をランダムに選ぶ手順と、
前記g[1]の前記r[1]乗をu[1]とし、前記g[2]の前記r[2]乗をu[2]とし、...という操作をnまで繰り返す事でu[1],...,u[n]を計算する手順と、
前記hを前記r[1]，...，前記r[n]を全て加えたものでべき乗したものをvとして計算する手順と、
前記c[1]の前記r[1]乗，...，前記c[n]の前記r[n]乗を全てかけたものにさらに前記Ｍをかけたものをwとして計算する手順と、
前記d[1]の前記r[1]乗，...，前記d[n]の前記r[n]乗を全てかけたものをπとして計算する手順と、
前記u[1],...,前記u[n],前記v,前記w,前記πを前記暗号文として出力する手順と、
を前記コンピュータに実行させる暗号化プログラム。
【請求項２７】
コンピュータに、２つの暗号文から変換した暗号文を出力させる準同型変換プログラムであって、
u[1],...,u[n],v,w,πをデータとして持つ第１の暗号文と、u'[1],...,u'[n],v',w',π'をデータとして持つ第２の暗号文とを受け取る手順と、
前記u[1]と前記u'[1]の積u''[1],...,前記u[n]と前記u'[n]の積u''[n]を計算し、前記vと前記v'の積v''を計算し、前記wと前記w'の積w''を計算し、前記πと前記π'の積π''を計算する手順と、
前記u''[1],...,前記u''[n],前記v'',前記w'',前記π''を含むデータを前記変換した暗号文として出力する手順と、
を前記コンピュータに実行させる準同型変換プログラム。
【請求項２８】
コンピュータに、秘密鍵と暗号文とから平文（Ｍ）を復号させる復号プログラムであって、
x[1]，...，x[n]，y[1]，...，y[n]，α，βをデータとして持つ前記秘密鍵とu[1],...,u[n],v,w,πをデータとして持つ前記暗号文とを入力として受け取る手順と、
前記u[1]の前記x[1]乗，...,前記u[n]の前記x[n]乗を全てかけあわせたものにさらに前記vの前記α乗をかけあわせたものが前記πと等しければ、前記u[1]の前記y[1]乗,…,前記u[n]の前記y[n]乗を全てかけあわせたものにさらに前記ｖの前記β乗をかけあわせたものによって前記w剰余したものを出力し、そうでなければ前記暗号文が不正である旨を出力する手順と、
を前記コンピュータに実行させる復号プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−１０７４０７（Ｐ２０１１−１０７４０７Ａ）
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願番号】特願２００９−２６２１９４（Ｐ２００９−２６２１９４）
【出願日】平成２１年１１月１７日（２００９．１１．１７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願日】平成２１年１１月１７日（２００９．１１．１７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]