暗号化装置、復号装置、暗号化方法、及び復号方法
【課題】 順序保存関数に関する演算を効率的に実行する。
【解決手段】 平文d、シードS、平文空間D={d_1,...,d_m}、暗号文空間R={r_1,..,r_n}が入力され、平文空間の中間の値d_cを決定し、シードSを用いてa=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、d=d_cが成立しているかを判定し、成立の場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立しない場合にd< d_cが成立しているかを判定し、成立の場合、D= {d_｛1},…,d_{c-1}}、R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}とし、成立していない場合、D= {d_｛c+1},…,d_{m}}、R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る。
【解決手段】 平文d、シードS、平文空間D={d_1,...,d_m}、暗号文空間R={r_1,..,r_n}が入力され、平文空間の中間の値d_cを決定し、シードSを用いてa=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、d=d_cが成立しているかを判定し、成立の場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立しない場合にd< d_cが成立しているかを判定し、成立の場合、D= {d_｛1},…,d_{c-1}}、R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}とし、成立していない場合、D= {d_｛c+1},…,d_{m}}、R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化装置、復号装置、暗号化方法、及び復号方法に関する。特に、単純な分布に従う試行のシミュレート方法を用い、効率的に処理を実行する暗号化装置、復号装置、暗号化方法、及び復号方法に関する。
【０００２】
なお、本願において、以降、暗号化処理が施される前のデータを平文とし、暗号化処理が施された後のデータを暗号文と呼ぶ。
【０００３】
また、以降、本願において次のように記載する。
【０００４】
暗号化関数は３変数の関数Enc(,,)と表す。Enc(,,)は第１変数に補助パラメータ、第２変数に鍵、第３変数に平文を入力としてとり、対応した暗号文を出力する。また、復号関数は３変数関数Dec(,,)と表す。Dec(,,)は第一変数に補助パラメータ、第二変数に鍵、第３変数に暗号文を入力としてとり、対応した平文を出力するものとする。なお補助パラメータは複数の情報から構成される場合があるため、それらをまとめるための表現として[]を用いる。例えば、A,B,Cを補助パラメータとして用いる場合であれば、[A,B,C]と書く。さらに、min()が集合を引数に取る関数であり、入力された集合の中から最も小さな値を出力する関数とする。また、max()は集合を引数に取る関数であり、入力された集合の中から最も大きな値を出力する関数とする。size()は集合を引数に取る関数であり、入力された集合の要素数を出力する関数とする。ceil()は実数を入力として、入力を越えない最大の整数を出力する関数とする。
【背景技術】
【０００５】
データベースに登録されている情報の漏洩対策として、登録情報の暗号化が挙げられる。しかし、一般的な暗号方式を用いると、データベースの利便性が大きく損なわれる。例えば登録されている暗号化されているデータに対し、範囲検索を行うことを考える。このとき、通常の暗号化方式を用いる限り、暗号化されたデータから元のデータが目的の範囲に含まれているかどうかの判断はできない。つまり、単純に登録された値から条件に一致しているかどうかの判断は出来ず、範囲検索は困難になってしまう。暗号化されたデータのすべてを復号し、条件にあった値かどうかを確認することはできるが、データベース中に含まれている暗号文のすべてを復号する必要があり、非効率的である。
【０００６】
このような問題を解決する手段の１つとして、特殊な性質を持った暗号化方法を用いる方法が知られているが、非特許文献１では、平文の数字的な大小を保ちながら暗号化することができる暗号方式を用いることが提案されている。 このような暗号方式があれば、暗号文からの範囲検索が実行可能となる。例えば、データベースに暗号文c_{i_1},...,c_{i_n}が記憶されている場合に、m_{j_1}以上m_{j_2}以下の値を持つデータに対する暗号文を検索する場合を考える。このとき、m_{j_1}の暗号文c_{j_1}とm_{j_2}の暗号文c_{j_2}を作成し、c_{j_1}とc_{j_2}の中間の値を持つ暗号文を検索すれば、目的の暗号文を抽出できる。以降、このような性質を持った暗号方式を順序保存暗号と呼ぶ。
【０００７】
しかしながら、非特許文献1に記載の方法では、過去に暗号化した平文をすべて記憶しておく必要がある。この性質は、先に挙げたデータベースを暗号化するためには好ましくない。つまり、非特許文献１に記載の方法を用いると、データベースにデータを追加する際には過去に暗号化したすべての平文の情報を手に入れる手段が必要である。言い換えると、漏洩を防止するためには外部に保管したい情報が、暗号化するために必要な情報となっているので、目的の達成が困難である。
【０００８】
従来の順序保存暗号としては、非特許文献１の他に非特許文献２に記載されている方式が挙げられる。
【０００９】
非特許文献２に記載の方法においては、暗号化のために必要な情報は鍵情報と平文のみであり、復号のために必要な情報は鍵情報と暗号文のみである。このような方法が暗号化した状態で外部データベースにデータを預ける目的では好ましい。以下で、非特許文献２に記載の方法について説明するが、まず、非特許文献２に記載の方法を説明するために必要な事項の説明を行う。
【００１０】
関数F()について、定義域に含まれる任意のx_1,x_2(x_1)に対してF(x_1) < F(x_2)が満たされる場合、F()を順序保存型関数とする。
【００１１】
定義域が{1,...,M}であって、値域が{1,...,N}であるような順序保存型関数の総数はN個からM個を選ぶ組み合わせの総数に等しい。以降、A個からB個を選ぶ組み合わせをC(A,B)と書く。
【００１２】
順序保存暗号は、この順序保存型関数からひとつの関数F()を指定し、効率的にF()および、その逆関数が計算できるような情報である鍵情報を指定することによって構成することができる。
【００１３】
鍵情報はランダムに選択されることが求められるが、選択された鍵情報によって指定される順序保存型関数は定義域と値域によって指定される関数集合の中から出来る限り一様にランダムに選択されることが望ましい。これは、暗号の解読を試みた際に、どの関数を使っているかの推測を困難とするためである。
【００１４】
非特許文献２では、このような鍵情報の選択方法として、超幾何分布に従った乱数生成方法が用いられている。超幾何分布とは以下のような分布である。
【００１５】
（超幾何分布）
ビンにN個のボールが入っており、そのうち、M個が黒、N-M個が白である場合を考える。ビンからランダムにy個のボールを取り出したとき、引いたボールに含まれる黒いボールの数を確率変数とする確率分布が超幾何分布に等しい。ある分布に従う試行の結果がｘとなる確率は確率密度関数と呼ばれる。xの確率密度関数Pr(x)はN,M,yを用いて以下の式によって表されることが知られている。
【００１６】
Pr(x;N,M,y) = (C(y,x)C(N-y,M-x))/C(N,M)
ここで、ある分布に従った乱数を生成することを、試行とする。例えば、超幾何分布に従う試行というように用いる。コンピュータやハードウェアでなんらかの分布に従った試行を実行したい場合、実際にビンにボールを入れてボールを取り出すことはできないため、分布に従った試行をシミュレートする分布シミュレーションアルゴリズムが用いられる。分布シミュレーションアルゴリズムには、分布を定めるパラメータに加えてシードと呼ばれる値が入力され、シミュレーションアルゴリズムのランダム性はシードによって確保される。以降、超幾何分布にしたがった試行をシミュレートするアルゴリズムは、N,M,yを確率分布を指定するパラメータ、ccをシードとしたとき、HGD(N,M,y,cc)と記載する。
【００１７】
シードは擬似乱数生成器を用いて生成する方法が一般的であり、HGD(N,M,y,cc)に用いる擬似乱数を生成するための擬似乱数生成関数をRand_{HGD}(N,M,y,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parは補助パラメータである。補助パラメータParによってK,N,M,yが同一であってもParが調整でき、異なるシードを生成する。
【００１８】
集合Nより一様ランダムに要素を選択するアルゴリズムをシードをkとしてUni(N,cc)とする。Uni(N,cc)で用いるシードを生成するためのアルゴリズムをRand_{Uni}(N,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parの用途はRand_{HGD}と同じである。
【００１９】
超幾何分布に従う試行の効率の良いシミュレートアルゴリズムとしては、非特許文献３に記載の方法が知られている。この方法は浮動小数点数の計算が無限の精度で正確ならば、超幾何分布に従う試行を完全にシミュレートすることができる。
【００２０】
非特許文献２に記載の超幾何分布に従う試行のシミュレート方法を用いた順序保存型関数の指定方法を示す。なお、平文空間Dは{1,...,M}であるとする。また暗号文空間Rは{1,...,N}であるとする。このとき、Enc([D,R],K,m)とDec([D,R],K,c)を以下に示す。
【００２１】
Enc([D,R],K,m)
1. P = size(D)を計算する。
【００２２】
2. Q = size(R)を計算する。
【００２３】
3. d = min(D) -1を計算する。
【００２４】
4. r = min(R)-1を計算する。
【００２５】
5. y = r + ceil(N/2)を計算する。
【００２６】
6. P = 1である場合、 cc = Rand_{Uni}(N,K,m)を計算し、x =HGD(D,R,y,cc)を計算し、xを返し終了する。
【００２７】
7. cc = Rand_{HGD}(N,M,y,cc)を計算する。
【００２８】
8. x = HGD(N,M,y,cc)を計算する。
【００２９】
9. mがx以下であるとき、D = {d+1,...,x}, R = {r+1,...,y}とする。
【００３０】
10. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００３１】
11. Enc([D,R],K,m)の返り値を出力し終了する。
【００３２】
Dec([D,R],K,c)
1. P = size(D)を計算する。
【００３３】
2. Q = size(R)を計算する。
【００３４】
3. d = min(D) -1を計算する。
【００３５】
4. r = min(R)-1を計算する。
【００３６】
5. y = r + ceil(N/2)を計算する。
【００３７】
6. P = 1である場合、 m = min(D)を求め、cc = Rand_{Uni}(N,K,m)及び、w = HGD(D,R,y,cc)を計算する。 ここで、m=wであるならば、mを返し、終了する。それ以外の場合、エラーを返し終了する。
【００３８】
7. cc = Rand_{HGD}(N,M,y,cc)を計算する。
【００３９】
8. x = HGD(N,M,y,cc)を計算する。
【００４０】
9. mがx以下であるとき、D = {d+1,...,x}, R = {r+1,...,y}とする。
【００４１】
10. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００４２】
11. Dec([D,R],K,c)の返り値を出力する。
【００４３】
以上の方法を第一の方法という。第一の方法は、HGDが完全に超幾何分布に従う志向をシミュレートする条件で、定義域がDであって値域がRである順序保存型関数のすべてから一様ランダムに１つの関数を指定できることが証明されている。暗号文空間を２つに分けながら再帰呼び出しが行われる方法なので、最悪の場合、log(size(N))回の再帰処理が行われる。
【００４４】
（負の超幾何分布）
ビンにN個のボールが入っており、そのうち、M個が黒、N-M個が白である場合を考える。ビンからランダムにボールを抜き取っていく試行において（抜き取ったボールは戻さない）、ちょうどx個目の黒いボールを引いたときの、引いたボールの総数yを確率変数とする確率分布が負の超幾何分布に等しい。超幾何分布の確率密度関数Pr(y)はN,M,xを用いて以下の式によって表されることが知られている。
【００４５】
Pr(y;N,M,x) = (C(y-1,x-1)C(N-y,M-x))/C(N,M)
以降、負の超幾何分布に従う試行をシミュレートするアルゴリズムを、N,M,xは確率分布を指定するパラメータ、Kをシードとし、NHGD(N,M,x,K)と記載する。
【００４６】
NHGD(N,M,x,cc)に用いる擬似乱数を生成するための擬似乱数生成関数をRand_{NHGD}(N,M,x,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parは補助パラメータである。Parの用途はRand_{HGD}と同じである。
【００４７】
負の超幾何分布に従う試行の効率の良いシミュレート方法としては、非特許文献４に記載の方法が知られているが、近似アルゴリズムである。
【００４８】
非特許文献４に記載の負の超幾何分布に従う試行のシミュレート方法を用いた順序保存型関数の指定方法を示す。なお、平文空間Dは{1,...,M}であるとする。また暗号文空間Rは{1,...,N}であるとする。このとき、 Enc([D,R],K,m)とDec([D,R],K,c)を以下に示す。
【００４９】
Enc([D,R],K,m)
1. P = size(D)を計算する。
【００５０】
2. Q = size(R)を計算する。
【００５１】
3. d = min(D) -1を計算する。
【００５２】
4. r = min(R)-1を計算する。
【００５３】
5. x = d + ceil(M/2)を計算する。
【００５４】
6. cc = Rand_{NHGD}(N,M,K,m)を計算し、y = NHGD(D,R,x,cc)を計算する。
【００５５】
7. m = x であるとき、 yを出力する。
【００５６】
8. mがxより小さいとき、D = {d+1,...,x-1}, R = {r+1,...,y-1}とする。
【００５７】
9. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００５８】
10. Enc([D,R],K,m)の返り値を出力し終了する。
【００５９】
Dec([D,R],K,c)
1. P = size(D)を計算する。
【００６０】
2. Q = size(R)を計算する。
【００６１】
3. d = min(D) -1を計算する。
【００６２】
4. r = min(R)-1を計算する。
【００６３】
5. x = d + ceil(M/2)を計算する。
【００６４】
6. cc = Rand_{NHGD}(N,M,K,x)及び、y = NHGD(D,R,x,cc)を計算する。 ここで、c=yであるならば、xを返し、終了する。それ以外の場合、エラーを返し終了する。
【００６５】
7. cがyより小さいとき、D = {d+1,...,x-1}, R = {r+1,...,y-1}とする。
【００６６】
8. cがyより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００６７】
9. Dec([D,R],K,c)の返り値を出力して終了する。
【００６８】
以上の方法を第２の方法と呼ぶ。第２の方法は、NHGDが完全に負の超幾何分布に従う試行をシミュレートする条件で、定義域がDであって値域がRである順序保存型関数のすべてから一様ランダムに１つの関数を指定できることが証明されている。暗号文空間を２つに分けながら再帰呼び出しが行われるので、最悪の場合、log(size(M))回の再帰処理が行われる。
【００６９】
以下、第２の方法の実施する装置の構成およびフローチャートを示す。第２の方法を実施する装置は暗号化装置100と復号装置200を備える。
【００７０】
図１は第２の方法を実施するための暗号化装置100の構成例を示すブロック図である。暗号化装置100の構成について、図１を用いて説明を行う。図１を参照すると、暗号化装置100は、暗号化処理制御部101と、負の超幾何分布シミュレート部102を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【００７１】
図２は暗号化装置100の実施の形態の動作を示すフローチャートである。図２を参照して暗号化装置100の実施の形態の動作について説明する。
【００７２】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップA1）。
【００７３】
暗号化処理制御部101は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップA2)。
【００７４】
暗号化処理制御部101は、|R|をボール数、|D|を黒いボール数とし、|D|/2個の黒いボールがでたときの引いたボールの総数eをSをシードとした負の超幾何分布に従う試行のシミュレーション処理を負の超幾何分シュミレート部102を用いて求め、r_eをd_cに対する暗号文とする（ステップA3）。
【００７５】
暗号化処理制御部101は、d=d_cが成立しているかを調べる(ステップA4)。
【００７６】
ステップA4が成立している場合、暗号化処理制御部101は、r_eをdの暗号文として出力する(ステップA5)。ステップA4が成立していない場合、暗号化処理制御部101は、d < d_cが成立しているかを調べる(ステップA6)。
【００７７】
ステップA6が成立している場合、暗号化処理制御部101は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップA2に戻る(ステップA8)。ステップA6が成立していない場合、暗号化処理制御部101は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n}ステップA2に戻る(ステップA7)。
【００７８】
図３は第２の方法を実施するための復号装置200の構成例を示すブロック図である。復号装置200の構成について、図３を用いて説明を行う。図３を参照すると、復号装置200は、復号処理制御部101と、負の超幾何分布シミュレート部102を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。
【００７９】
図４は復号装置200の実施の形態の動作を示すフローチャートである。図４を参照して復号装置200の実施の形態の動作について説明する。
【００８０】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップB1）。
【００８１】
復号処理制御部201は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップB2)。
【００８２】
復号処理制御部201は、|R|をボール数、|D|を黒いボール数とし、|D|/2個の黒いボールがでたときの引いたボールの総数eをSをシードとした負の超幾何分布に従う試行のシミュレーション処理によって求め、r_eをd_cに対する暗号文とする（ステップB3）。
【００８３】
復号処理制御部201は、r_e=rが成立しているかを調べる(ステップB4)。ステップB4が成立している場合、復号処理制御部201は、r_eをdの暗号文として出力する(ステップB5)。ステップB4が成立していない場合、復号処理制御部201は、r_e < rが成立しているかを調べる(ステップB6)。
【００８４】
ステップB6が成立している場合、復号処理制御部201は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n}とし、ステップB2に戻る(ステップB7)。ステップB6が成立していない場合、復号処理制御部201は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップB2に戻る(ステップB8)。
【先行技術文献】
【非特許文献】
【００８５】
【非特許文献１】Alexandra Boldyreva, Nathan Chenette, Younho Lee and Adam O'Neill. Order-Preserving Symmetric Encryption. Advances in Cryptology - Eurocrypt 2009 Proceedings, Lecture Notes in Computer Science Vol. 5479, pp. 224-241, A. Joux ed., 2009.
【非特許文献２】Jun. Li, and Edward. Omiecinski. Efficiency and Security Trade-Off in Supporting Range Queries on Encrypted Databases. pp. 69-83. DBSec 2005:
【非特許文献３】V. Kachitvichyanukul and B. W. Schmeiser. Computer generation of hypergeometric random variates. Journal of Statistical Computation and Simulation, 22(2):127-145,1985.
【非特許文献４】F.Lopes-Blazquez and B.Salamanca Mino. Exact and approximated relations between negative hypergeometric and negative binomial probabilities. Communications in Statistics. Theory and Methods, 30(5):957-967,2001
【非特許文献５】計算機シミュレーションのための確率分布乱数生成法 四辻哲章 プレアデス出版、第1版、2010年7月1日発行、P.244-247、P.228-239
【発明の概要】
【発明が解決しようとする課題】
【００８６】
従来の方式は、順序保存型関数から一様ランダムに選択する方法のみを示している。また、超幾何分布や負の超幾何分布に従う試行のシミュレーション方法として効率的であるといわれている方法は複雑である。さらに、超幾何分布のシミュレーション方法として効率的であるとされている方法は浮動小数点数の計算が無制限に精確であるという前提のもとでしか完全に超幾何分布に従う試行シミュレートができない。加えて、負の超幾何分布に従う試行を効率的に実行する方法は近似されたアルゴリズムしか知られていない。
【００８７】
つまり、実際にはすべての順序保存型関数から一様ランダムに選択できず、ある程度の誤差を伴う。実際には誤差を許容するならば、よりシンプルな方法を用いて効率的に順序保存型暗号を選択する方法でもよい。
【００８８】
本発明の目的は、従来の方法に比べて、単純な分布に従う試行のシミュレート方法を用い、効率的に処理を実行する暗号化装置、復号装置、暗号化方法、及び復号方法を提供することにある。
【課題を解決するための手段】
【００８９】
本発明に係わる暗号化装置は、ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シュミレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置である。
【００９０】
本発明に係わる復号装置は、ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置である。
【００９１】
また本発明に係わる暗号化装置は、一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置である。
【００９２】
また本発明に係わる復号装置は、一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置である。
【００９３】
また本発明は、暗号化装置の暗号化方法及び復号装置の復号方法に関する。
【発明の効果】
【００９４】
本発明によれば、平文の順序が保存される暗号を用いて、データベースに登録されている暗号文に対し、範囲検索を行うことができる。また、本発明をデータベースの暗号化方法として用いれば、暗号化されるデータのデータ長が長い場合であっても効率的な暗号化処理が実行できるため、暗号化されたデータベースの範囲検索を効率的に実行することが可能となる。
【図面の簡単な説明】
【００９５】
【図１】非特許文献２に係わる暗号化装置の一構成例を示すブロック図である。
【図２】図１に示された暗号化装置の動作を示すフローチャートである。
【図３】非特許文献２に係わる復号装置の一構成例を示すブロック図である。
【図４】図３に示された復号装置の動作を示すフローチャートである。
【図５】本発明の第１の実施の形態の暗号化装置３００の構成を示すブロック図である。
【図６】本発明の第１の実施の形態の復号装置４００の構成を示すブロック図である。
【図７】本発明の第２の実施の形態の暗号化装置３１０の構成を示すブロック図である。
【図８】本発明の第２の実施の形態の復号装置４１０の構成を示すブロック図である。
【図９】暗号化装置又は復号装置として機能するコンピュータの一構成例を示すブロック図である。
【図１０】図５の暗号化装置の動作を示すフローチャートである。
【図１１】図６の復号装置の動作を示すフローチャートである。
【図１２】図７の暗号化装置の動作を示すフローチャートである。
【図１３】図８の復号装置の動作を示すフローチャートである。
【発明を実施するための形態】
【００９６】
以下、本発明に係わる典型的な実施形態について図面を用いて詳細に説明する。
【００９７】
本発明に係わる第１の実施形態の暗号化装置及び復号装置は、ベータ分布に従う試行のシミュレーション方法を用いた暗号化装置及び復号装置である。
【００９８】
ベータ分布とは、0≦y≦1を確率変数とする確率分布であって、ベータ分布に従う試行の確率密度関数は、以下の式によって表される。
【００９９】
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B(a,b)はベータ関数
この分布は、0と1間の値の一様分布に従う独立なa+b-1個の確率変数を大きさの順に並べ替えたときの小さいほうからa番目で大きいほうからb番目の値の確率変数である。
【０１００】
a=bである場合ならば、ceil((a+b)/2)番目の値を表す確率変数となる。定義域が{1,...,M}であり、値域が{1,...,N}であるような順序保存関数を一様にランダムに選ぶ場合、同じ要素が選ばれない限り、1からNの中から一様ランダムにM個の値を選び、これを小さいほうから並べた集合に定義域内の小さな値から対応させることで選択できる。
【０１０１】
つまり、a=bであるベータ分布に従う試行をシミュレートした結果である yに対し、ceil(N*y)は順序保存関数からランダムに関数が選ばれる場合、定義域中の中間の値が、値域のどの値に対応しているかを表すことになる。つまり、負の超幾何分布に従う試行のシミュレートをベータ分布に従う試行のシミュレーションで代替できることを表している。ベータ分布に従う試行は、負の超幾何分布に従う試行に比べて、効率的にシミュレートする方法がよく知られており（非特許文献５など）、さらに、a=bである場合に特に効率的に動作するアルゴリズムが知られている。以上のような方法で、第２の方法における暗号化処理、復号処理において実行される。
【０１０２】
負の超幾何分布に従う試行のシミュレーションを効率的な方法によって代替することで、定義域、値域に対する順序保存関数の中からほぼ一様ランダムに関数を効率的に指定することができる第２の解決法は、r_eを選択する処理を一様分布に従う試行を用いて行う方法である。すなわち、本発明に係わる第２の実施形態の暗号化装置及び復号装置は、一様分布に従う試行のシミュレーション方法を用いた暗号化装置及び復号装置である。
【０１０３】
一様分布とは、a≦y≦b (0≦a≦1, 0≦b≦1)を確率変数とする確率分布であって、その確率密度関数は以下の式によって表される。
【０１０４】
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
この方法は、aとb間の値の一様分布に従う試行によってyを選択し、ceil(N*y)をr_eとする方法である。一様分布は、様々な分布をシミュレートするためにベースの分布として利用されている。この分布に従う試行は非常に簡単にシミュレート可能な値とされているため、順序保存関数に関する演算を効率的に実行することができる。
【０１０５】
まず、ベータ分布に従う試行のシミュレーション方法を用いた場合の第１の実施形態について説明する。
【０１０６】
図５は本発明の第１実施形態に係わる暗号化装置のブロック図である。暗号化装置の構成について、図５を用いて説明を行う。
【０１０７】
図５を参照すると、暗号化装置300は、暗号化処理制御部301と、ベータ分布シミュレート部303 を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【０１０８】
図１０は、本実施形態の暗号化装置300の動作を示すフローチャートである。これを用いて、暗号化装置300の実施の形態の動作について説明する。
【０１０９】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される(ｍ及びｎは１を超える自然数)（ステップC1）。
【０１１０】
暗号化処理制御部301は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する。(ステップC2)。
【０１１１】
暗号化処理制御部301は、Sをシードとしてベータ分布シミュレート部303を動作させ、a=bであるベータ分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップC3）。
【０１１２】
暗号化処理制御部301は、d=d_cが成立しているかを調べる(ステップC4)。ステップC4が成立している場合、暗号化処理制御部301は、r_{ceil(|R|*y)}をdの暗号文として出力する(ステップC5)。
【０１１３】
ステップC4が成立していない場合、暗号化処理制御部301は、d < d_cが成立しているかを調べる(ステップC6)。
【０１１４】
ステップC6が成立している場合、暗号化処理制御部301は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップC2に戻る(ステップC7)。ステップC6が成立していない場合、暗号化処理制御部301は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n} とし、ステップC2に戻る(ステップC8)。
【０１１５】
図６は本発明の第１実施形態に係わる復号装置のブロック図である。復号装置４００の構成について、図６を用いて説明を行う。
【０１１６】
図６を参照すると、復号装置400は、復号処理制御部401と、ベータ分布シミュレート部303を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。図１１は復号装置400の動作を示すフローチャートである。これを用いて復号装置400の実施の形態の動作について説明する。
【０１１７】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップD1）。復号処理制御部401は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップD2)。復号処理制御部401は、Sをシードとしてベータ分布シミュレート部303を動作させ、a=bであるベータ分布に従った試行をシミュレートした結果であるyを生成し、r_e = ceil(|R|*y)をd_cに対する暗号文とする（ステップD3）。
【０１１８】
復号処理制御部401は、r_e=rが成立しているかを調べる(ステップD4)。ステップD4が成立している場合、復号処理制御部401は、d_c をrの平文として出力する(ステップD5)。
【０１１９】
ステップD4が成立していない場合、復号処理制御部401は、r_e< rが成立しているかを調べる(ステップD6)。
【０１２０】
ステップD6が成立している場合、復号処理制御部401は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップD2に戻る(ステップD7)。ステップD6が成立していない場合、復号処理制御部401は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n} とし、ステップD2に戻る(ステップD8)。
【０１２１】
次に、一様分布に従う試行のシミュレーション方法を用いた場合の第２の実施形態について説明する。
【０１２２】
図７は本発明の第２の実施形態に係わる暗号化装置のブロック図である。暗号化装置の構成について、図７を用いて説明を行う。
【０１２３】
図7を参照すると、暗号化装置310は、暗号化処理制御部301と、 一様分布シミュレート部304 を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【０１２４】
図１２は、本実施形態の暗号化装置310の実施の形態の動作を示すフローチャートである。これを用いて、暗号化装置310の実施の形態の動作について説明する。
【０１２５】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップE1）。
【０１２６】
暗号化処理制御部301は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する。(ステップE2)。
【０１２７】
暗号化処理制御部301は、Sをシードとして一様分布シミュレート部304を動作させ、0と1の間の値の一様分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップE3）。
【０１２８】
暗号化処理制御部301は、d=d_cが成立しているかを調べる(ステップE4)。ステップE4が成立している場合、暗号化処理制御部301は、r_{ceil(|R|*y)}をdの暗号文として出力する(ステップE5)。
【０１２９】
ステップE4が成立していない場合、暗号化処理制御部301は、d<d_cが成立しているかを調べる(ステップE6)。
【０１３０】
ステップE6が成立している場合、暗号化処理制御部301は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n}とし、ステップE2に戻る(ステップE7)。ステップE6が成立していない場合、暗号化処理制御部301は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップE2に戻る(ステップE8)。
【０１３１】
図８は本発明の第２の実施形態に係わる復号装置のブロック図である。復号装置４１０の構成について、図８を用いて説明を行う。
【０１３２】
図８を参照すると、復号装置410は、復号処理制御部401と、一様分布シミュレート部304を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。図１３は復号装置410の動作を示すフローチャートである。これを用いて復号装置410の実施の形態の動作について説明する。
【０１３３】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップF1）。 復号処理制御部401は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップF2)。復号処理制御部401は、Sをシードとして一様分布シミュレート部304を動作させ、0と1の間の一様分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップF3）。
【０１３４】
復号処理制御部401は、r_{ceil(|R|*y)}=rが成立しているかを調べる(ステップF4)。ステップF4が成立している場合、復号処理制御部401は、d_c をrの平文として出力する(ステップF5)。
【０１３５】
ステップF4が成立していない場合、復号処理制御部401は、r_{ceil(|R|*y)}<rが成立しているかを調べる(ステップF6)。
【０１３６】
ステップF6が成立している場合、復号処理制御部401は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n}とし、ステップF2に戻る(ステップF7)。ステップF6が成立していない場合、復号処理制御部401は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップF2に戻る(ステップF8)。
【０１３７】
上記実施形態の一様分布において、0付近、もしくは1付近が生成されると、各暗号文間の広さが小さくなる可能性がある。暗号文間の広さが小さいと、それらの平文間の差も小さいことが解析できてしまう。
【０１３８】
これは、a,bが0から1ではなく、0 < a< b < 1であるような区間[a,b]の一様分布を用いることで防ぐことができる。
【０１３９】
以上説明した、第１及び第２の実施形態の暗号化装置及び復号装置は、ハードウェアで構成することができる。しかし、当該かかる暗号化装置及び復号装置の機能をソフトウェアで実現することができる。図９は、暗号化装置又は復号装置として機能するコンピュータの一構成例を示すブロック図である。
【０１４０】
図9に示す処理装置10は、CPU11と、CPU11の処理に必要な情報を一時的に記憶する主記憶装置１２と、CPU11に 暗号化装置300又は310、復号装置400又は410、としての処理を実行させるためのプログラムが記録された記録媒体１３と、平文や、暗号文、鍵情報などが格納されるデータ蓄積装置１４と、主記憶装置１２、記録媒体１３及びデータ蓄積装置１４とのデータ転送を制御するメモリ制御インターフェース部１５と、入力装置２０及び出力装置３０とのインターフェース装置であるI/Oインターフェース部１６とを有し、それらは バス１７を介して接続された構成である。
なお、データ蓄積装置１４は、処理装置 １０内にある必要はなく、処理装置１０から独立して備えていてもよい。
処理装置１０は、暗号化装置300又は310、復号装置400又は410、の機能を実現する。
記録媒体１３は、磁気ディスク装置、半導体メモリ、光ディスク装置あるいはその他の 記録媒体であってもよい。
【０１４１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下の構成には限られない。
【０１４２】
（付記１）
ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【０１４３】
（付記２）
ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【０１４４】
（付記３）
一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【０１４５】
（付記４）
一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【０１４６】
（付記５）
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【０１４７】
（付記６）
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【０１４８】
（付記７）
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【０１４９】
（付記８）
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【０１５０】
（付記９）
コンピュータに、
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成する手順と、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５１】
（付記１０）
コンピュータに、
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成する手順と、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５２】
（付記１１）
コンピュータに、
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成する手順と、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５３】
（付記１２）
コンピュータに、
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成する手順と、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【産業上の利用可能性】
【０１５４】
本発明は登録情報が暗号化されているデータベースにおいて範囲検索を行う場合の暗号化装置、暗号化方法、復号装置及び復号方法に適用できる。
【符号の説明】
【０１５５】
10 処理装置
11 CPU
12 主記憶装置
13 記録媒体
14 データ蓄積装置
15 メモリ制御インターフェース部
16 I/Oインターフェース部
20 入力装置
30 出力装置
100, 300, 310 暗号化装置
101, 301 暗号化処理制御装置
102 負の超幾何分布シミュレート装置
303 ベータ分布シミュレート装置
304 一様分布シミュレート装置
200, 400, 410 復号装置
201, 401 復号処理制御装置
【技術分野】
【０００１】
本発明は暗号化装置、復号装置、暗号化方法、及び復号方法に関する。特に、単純な分布に従う試行のシミュレート方法を用い、効率的に処理を実行する暗号化装置、復号装置、暗号化方法、及び復号方法に関する。
【０００２】
なお、本願において、以降、暗号化処理が施される前のデータを平文とし、暗号化処理が施された後のデータを暗号文と呼ぶ。
【０００３】
また、以降、本願において次のように記載する。
【０００４】
暗号化関数は３変数の関数Enc(,,)と表す。Enc(,,)は第１変数に補助パラメータ、第２変数に鍵、第３変数に平文を入力としてとり、対応した暗号文を出力する。また、復号関数は３変数関数Dec(,,)と表す。Dec(,,)は第一変数に補助パラメータ、第二変数に鍵、第３変数に暗号文を入力としてとり、対応した平文を出力するものとする。なお補助パラメータは複数の情報から構成される場合があるため、それらをまとめるための表現として[]を用いる。例えば、A,B,Cを補助パラメータとして用いる場合であれば、[A,B,C]と書く。さらに、min()が集合を引数に取る関数であり、入力された集合の中から最も小さな値を出力する関数とする。また、max()は集合を引数に取る関数であり、入力された集合の中から最も大きな値を出力する関数とする。size()は集合を引数に取る関数であり、入力された集合の要素数を出力する関数とする。ceil()は実数を入力として、入力を越えない最大の整数を出力する関数とする。
【背景技術】
【０００５】
データベースに登録されている情報の漏洩対策として、登録情報の暗号化が挙げられる。しかし、一般的な暗号方式を用いると、データベースの利便性が大きく損なわれる。例えば登録されている暗号化されているデータに対し、範囲検索を行うことを考える。このとき、通常の暗号化方式を用いる限り、暗号化されたデータから元のデータが目的の範囲に含まれているかどうかの判断はできない。つまり、単純に登録された値から条件に一致しているかどうかの判断は出来ず、範囲検索は困難になってしまう。暗号化されたデータのすべてを復号し、条件にあった値かどうかを確認することはできるが、データベース中に含まれている暗号文のすべてを復号する必要があり、非効率的である。
【０００６】
このような問題を解決する手段の１つとして、特殊な性質を持った暗号化方法を用いる方法が知られているが、非特許文献１では、平文の数字的な大小を保ちながら暗号化することができる暗号方式を用いることが提案されている。 このような暗号方式があれば、暗号文からの範囲検索が実行可能となる。例えば、データベースに暗号文c_{i_1},...,c_{i_n}が記憶されている場合に、m_{j_1}以上m_{j_2}以下の値を持つデータに対する暗号文を検索する場合を考える。このとき、m_{j_1}の暗号文c_{j_1}とm_{j_2}の暗号文c_{j_2}を作成し、c_{j_1}とc_{j_2}の中間の値を持つ暗号文を検索すれば、目的の暗号文を抽出できる。以降、このような性質を持った暗号方式を順序保存暗号と呼ぶ。
【０００７】
しかしながら、非特許文献1に記載の方法では、過去に暗号化した平文をすべて記憶しておく必要がある。この性質は、先に挙げたデータベースを暗号化するためには好ましくない。つまり、非特許文献１に記載の方法を用いると、データベースにデータを追加する際には過去に暗号化したすべての平文の情報を手に入れる手段が必要である。言い換えると、漏洩を防止するためには外部に保管したい情報が、暗号化するために必要な情報となっているので、目的の達成が困難である。
【０００８】
従来の順序保存暗号としては、非特許文献１の他に非特許文献２に記載されている方式が挙げられる。
【０００９】
非特許文献２に記載の方法においては、暗号化のために必要な情報は鍵情報と平文のみであり、復号のために必要な情報は鍵情報と暗号文のみである。このような方法が暗号化した状態で外部データベースにデータを預ける目的では好ましい。以下で、非特許文献２に記載の方法について説明するが、まず、非特許文献２に記載の方法を説明するために必要な事項の説明を行う。
【００１０】
関数F()について、定義域に含まれる任意のx_1,x_2(x_1)に対してF(x_1) < F(x_2)が満たされる場合、F()を順序保存型関数とする。
【００１１】
定義域が{1,...,M}であって、値域が{1,...,N}であるような順序保存型関数の総数はN個からM個を選ぶ組み合わせの総数に等しい。以降、A個からB個を選ぶ組み合わせをC(A,B)と書く。
【００１２】
順序保存暗号は、この順序保存型関数からひとつの関数F()を指定し、効率的にF()および、その逆関数が計算できるような情報である鍵情報を指定することによって構成することができる。
【００１３】
鍵情報はランダムに選択されることが求められるが、選択された鍵情報によって指定される順序保存型関数は定義域と値域によって指定される関数集合の中から出来る限り一様にランダムに選択されることが望ましい。これは、暗号の解読を試みた際に、どの関数を使っているかの推測を困難とするためである。
【００１４】
非特許文献２では、このような鍵情報の選択方法として、超幾何分布に従った乱数生成方法が用いられている。超幾何分布とは以下のような分布である。
【００１５】
（超幾何分布）
ビンにN個のボールが入っており、そのうち、M個が黒、N-M個が白である場合を考える。ビンからランダムにy個のボールを取り出したとき、引いたボールに含まれる黒いボールの数を確率変数とする確率分布が超幾何分布に等しい。ある分布に従う試行の結果がｘとなる確率は確率密度関数と呼ばれる。xの確率密度関数Pr(x)はN,M,yを用いて以下の式によって表されることが知られている。
【００１６】
Pr(x;N,M,y) = (C(y,x)C(N-y,M-x))/C(N,M)
ここで、ある分布に従った乱数を生成することを、試行とする。例えば、超幾何分布に従う試行というように用いる。コンピュータやハードウェアでなんらかの分布に従った試行を実行したい場合、実際にビンにボールを入れてボールを取り出すことはできないため、分布に従った試行をシミュレートする分布シミュレーションアルゴリズムが用いられる。分布シミュレーションアルゴリズムには、分布を定めるパラメータに加えてシードと呼ばれる値が入力され、シミュレーションアルゴリズムのランダム性はシードによって確保される。以降、超幾何分布にしたがった試行をシミュレートするアルゴリズムは、N,M,yを確率分布を指定するパラメータ、ccをシードとしたとき、HGD(N,M,y,cc)と記載する。
【００１７】
シードは擬似乱数生成器を用いて生成する方法が一般的であり、HGD(N,M,y,cc)に用いる擬似乱数を生成するための擬似乱数生成関数をRand_{HGD}(N,M,y,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parは補助パラメータである。補助パラメータParによってK,N,M,yが同一であってもParが調整でき、異なるシードを生成する。
【００１８】
集合Nより一様ランダムに要素を選択するアルゴリズムをシードをkとしてUni(N,cc)とする。Uni(N,cc)で用いるシードを生成するためのアルゴリズムをRand_{Uni}(N,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parの用途はRand_{HGD}と同じである。
【００１９】
超幾何分布に従う試行の効率の良いシミュレートアルゴリズムとしては、非特許文献３に記載の方法が知られている。この方法は浮動小数点数の計算が無限の精度で正確ならば、超幾何分布に従う試行を完全にシミュレートすることができる。
【００２０】
非特許文献２に記載の超幾何分布に従う試行のシミュレート方法を用いた順序保存型関数の指定方法を示す。なお、平文空間Dは{1,...,M}であるとする。また暗号文空間Rは{1,...,N}であるとする。このとき、Enc([D,R],K,m)とDec([D,R],K,c)を以下に示す。
【００２１】
Enc([D,R],K,m)
1. P = size(D)を計算する。
【００２２】
2. Q = size(R)を計算する。
【００２３】
3. d = min(D) -1を計算する。
【００２４】
4. r = min(R)-1を計算する。
【００２５】
5. y = r + ceil(N/2)を計算する。
【００２６】
6. P = 1である場合、 cc = Rand_{Uni}(N,K,m)を計算し、x =HGD(D,R,y,cc)を計算し、xを返し終了する。
【００２７】
7. cc = Rand_{HGD}(N,M,y,cc)を計算する。
【００２８】
8. x = HGD(N,M,y,cc)を計算する。
【００２９】
9. mがx以下であるとき、D = {d+1,...,x}, R = {r+1,...,y}とする。
【００３０】
10. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００３１】
11. Enc([D,R],K,m)の返り値を出力し終了する。
【００３２】
Dec([D,R],K,c)
1. P = size(D)を計算する。
【００３３】
2. Q = size(R)を計算する。
【００３４】
3. d = min(D) -1を計算する。
【００３５】
4. r = min(R)-1を計算する。
【００３６】
5. y = r + ceil(N/2)を計算する。
【００３７】
6. P = 1である場合、 m = min(D)を求め、cc = Rand_{Uni}(N,K,m)及び、w = HGD(D,R,y,cc)を計算する。 ここで、m=wであるならば、mを返し、終了する。それ以外の場合、エラーを返し終了する。
【００３８】
7. cc = Rand_{HGD}(N,M,y,cc)を計算する。
【００３９】
8. x = HGD(N,M,y,cc)を計算する。
【００４０】
9. mがx以下であるとき、D = {d+1,...,x}, R = {r+1,...,y}とする。
【００４１】
10. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００４２】
11. Dec([D,R],K,c)の返り値を出力する。
【００４３】
以上の方法を第一の方法という。第一の方法は、HGDが完全に超幾何分布に従う志向をシミュレートする条件で、定義域がDであって値域がRである順序保存型関数のすべてから一様ランダムに１つの関数を指定できることが証明されている。暗号文空間を２つに分けながら再帰呼び出しが行われる方法なので、最悪の場合、log(size(N))回の再帰処理が行われる。
【００４４】
（負の超幾何分布）
ビンにN個のボールが入っており、そのうち、M個が黒、N-M個が白である場合を考える。ビンからランダムにボールを抜き取っていく試行において（抜き取ったボールは戻さない）、ちょうどx個目の黒いボールを引いたときの、引いたボールの総数yを確率変数とする確率分布が負の超幾何分布に等しい。超幾何分布の確率密度関数Pr(y)はN,M,xを用いて以下の式によって表されることが知られている。
【００４５】
Pr(y;N,M,x) = (C(y-1,x-1)C(N-y,M-x))/C(N,M)
以降、負の超幾何分布に従う試行をシミュレートするアルゴリズムを、N,M,xは確率分布を指定するパラメータ、Kをシードとし、NHGD(N,M,x,K)と記載する。
【００４６】
NHGD(N,M,x,cc)に用いる擬似乱数を生成するための擬似乱数生成関数をRand_{NHGD}(N,M,x,K,Par)とする。Kは擬似乱数生成関数の鍵であり、Parは補助パラメータである。Parの用途はRand_{HGD}と同じである。
【００４７】
負の超幾何分布に従う試行の効率の良いシミュレート方法としては、非特許文献４に記載の方法が知られているが、近似アルゴリズムである。
【００４８】
非特許文献４に記載の負の超幾何分布に従う試行のシミュレート方法を用いた順序保存型関数の指定方法を示す。なお、平文空間Dは{1,...,M}であるとする。また暗号文空間Rは{1,...,N}であるとする。このとき、 Enc([D,R],K,m)とDec([D,R],K,c)を以下に示す。
【００４９】
Enc([D,R],K,m)
1. P = size(D)を計算する。
【００５０】
2. Q = size(R)を計算する。
【００５１】
3. d = min(D) -1を計算する。
【００５２】
4. r = min(R)-1を計算する。
【００５３】
5. x = d + ceil(M/2)を計算する。
【００５４】
6. cc = Rand_{NHGD}(N,M,K,m)を計算し、y = NHGD(D,R,x,cc)を計算する。
【００５５】
7. m = x であるとき、 yを出力する。
【００５６】
8. mがxより小さいとき、D = {d+1,...,x-1}, R = {r+1,...,y-1}とする。
【００５７】
9. mがxより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００５８】
10. Enc([D,R],K,m)の返り値を出力し終了する。
【００５９】
Dec([D,R],K,c)
1. P = size(D)を計算する。
【００６０】
2. Q = size(R)を計算する。
【００６１】
3. d = min(D) -1を計算する。
【００６２】
4. r = min(R)-1を計算する。
【００６３】
5. x = d + ceil(M/2)を計算する。
【００６４】
6. cc = Rand_{NHGD}(N,M,K,x)及び、y = NHGD(D,R,x,cc)を計算する。 ここで、c=yであるならば、xを返し、終了する。それ以外の場合、エラーを返し終了する。
【００６５】
7. cがyより小さいとき、D = {d+1,...,x-1}, R = {r+1,...,y-1}とする。
【００６６】
8. cがyより大きいとき、D = {x+1,...,d+M}, R = {y+1,...,r+N}とする。
【００６７】
9. Dec([D,R],K,c)の返り値を出力して終了する。
【００６８】
以上の方法を第２の方法と呼ぶ。第２の方法は、NHGDが完全に負の超幾何分布に従う試行をシミュレートする条件で、定義域がDであって値域がRである順序保存型関数のすべてから一様ランダムに１つの関数を指定できることが証明されている。暗号文空間を２つに分けながら再帰呼び出しが行われるので、最悪の場合、log(size(M))回の再帰処理が行われる。
【００６９】
以下、第２の方法の実施する装置の構成およびフローチャートを示す。第２の方法を実施する装置は暗号化装置100と復号装置200を備える。
【００７０】
図１は第２の方法を実施するための暗号化装置100の構成例を示すブロック図である。暗号化装置100の構成について、図１を用いて説明を行う。図１を参照すると、暗号化装置100は、暗号化処理制御部101と、負の超幾何分布シミュレート部102を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【００７１】
図２は暗号化装置100の実施の形態の動作を示すフローチャートである。図２を参照して暗号化装置100の実施の形態の動作について説明する。
【００７２】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップA1）。
【００７３】
暗号化処理制御部101は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップA2)。
【００７４】
暗号化処理制御部101は、|R|をボール数、|D|を黒いボール数とし、|D|/2個の黒いボールがでたときの引いたボールの総数eをSをシードとした負の超幾何分布に従う試行のシミュレーション処理を負の超幾何分シュミレート部102を用いて求め、r_eをd_cに対する暗号文とする（ステップA3）。
【００７５】
暗号化処理制御部101は、d=d_cが成立しているかを調べる(ステップA4)。
【００７６】
ステップA4が成立している場合、暗号化処理制御部101は、r_eをdの暗号文として出力する(ステップA5)。ステップA4が成立していない場合、暗号化処理制御部101は、d < d_cが成立しているかを調べる(ステップA6)。
【００７７】
ステップA6が成立している場合、暗号化処理制御部101は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップA2に戻る(ステップA8)。ステップA6が成立していない場合、暗号化処理制御部101は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n}ステップA2に戻る(ステップA7)。
【００７８】
図３は第２の方法を実施するための復号装置200の構成例を示すブロック図である。復号装置200の構成について、図３を用いて説明を行う。図３を参照すると、復号装置200は、復号処理制御部101と、負の超幾何分布シミュレート部102を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。
【００７９】
図４は復号装置200の実施の形態の動作を示すフローチャートである。図４を参照して復号装置200の実施の形態の動作について説明する。
【００８０】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップB1）。
【００８１】
復号処理制御部201は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップB2)。
【００８２】
復号処理制御部201は、|R|をボール数、|D|を黒いボール数とし、|D|/2個の黒いボールがでたときの引いたボールの総数eをSをシードとした負の超幾何分布に従う試行のシミュレーション処理によって求め、r_eをd_cに対する暗号文とする（ステップB3）。
【００８３】
復号処理制御部201は、r_e=rが成立しているかを調べる(ステップB4)。ステップB4が成立している場合、復号処理制御部201は、r_eをdの暗号文として出力する(ステップB5)。ステップB4が成立していない場合、復号処理制御部201は、r_e < rが成立しているかを調べる(ステップB6)。
【００８４】
ステップB6が成立している場合、復号処理制御部201は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n}とし、ステップB2に戻る(ステップB7)。ステップB6が成立していない場合、復号処理制御部201は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップB2に戻る(ステップB8)。
【先行技術文献】
【非特許文献】
【００８５】
【非特許文献１】Alexandra Boldyreva, Nathan Chenette, Younho Lee and Adam O'Neill. Order-Preserving Symmetric Encryption. Advances in Cryptology - Eurocrypt 2009 Proceedings, Lecture Notes in Computer Science Vol. 5479, pp. 224-241, A. Joux ed., 2009.
【非特許文献２】Jun. Li, and Edward. Omiecinski. Efficiency and Security Trade-Off in Supporting Range Queries on Encrypted Databases. pp. 69-83. DBSec 2005:
【非特許文献３】V. Kachitvichyanukul and B. W. Schmeiser. Computer generation of hypergeometric random variates. Journal of Statistical Computation and Simulation, 22(2):127-145,1985.
【非特許文献４】F.Lopes-Blazquez and B.Salamanca Mino. Exact and approximated relations between negative hypergeometric and negative binomial probabilities. Communications in Statistics. Theory and Methods, 30(5):957-967,2001
【非特許文献５】計算機シミュレーションのための確率分布乱数生成法 四辻哲章 プレアデス出版、第1版、2010年7月1日発行、P.244-247、P.228-239
【発明の概要】
【発明が解決しようとする課題】
【００８６】
従来の方式は、順序保存型関数から一様ランダムに選択する方法のみを示している。また、超幾何分布や負の超幾何分布に従う試行のシミュレーション方法として効率的であるといわれている方法は複雑である。さらに、超幾何分布のシミュレーション方法として効率的であるとされている方法は浮動小数点数の計算が無制限に精確であるという前提のもとでしか完全に超幾何分布に従う試行シミュレートができない。加えて、負の超幾何分布に従う試行を効率的に実行する方法は近似されたアルゴリズムしか知られていない。
【００８７】
つまり、実際にはすべての順序保存型関数から一様ランダムに選択できず、ある程度の誤差を伴う。実際には誤差を許容するならば、よりシンプルな方法を用いて効率的に順序保存型暗号を選択する方法でもよい。
【００８８】
本発明の目的は、従来の方法に比べて、単純な分布に従う試行のシミュレート方法を用い、効率的に処理を実行する暗号化装置、復号装置、暗号化方法、及び復号方法を提供することにある。
【課題を解決するための手段】
【００８９】
本発明に係わる暗号化装置は、ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シュミレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置である。
【００９０】
本発明に係わる復号装置は、ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置である。
【００９１】
また本発明に係わる暗号化装置は、一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置である。
【００９２】
また本発明に係わる復号装置は、一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置である。
【００９３】
また本発明は、暗号化装置の暗号化方法及び復号装置の復号方法に関する。
【発明の効果】
【００９４】
本発明によれば、平文の順序が保存される暗号を用いて、データベースに登録されている暗号文に対し、範囲検索を行うことができる。また、本発明をデータベースの暗号化方法として用いれば、暗号化されるデータのデータ長が長い場合であっても効率的な暗号化処理が実行できるため、暗号化されたデータベースの範囲検索を効率的に実行することが可能となる。
【図面の簡単な説明】
【００９５】
【図１】非特許文献２に係わる暗号化装置の一構成例を示すブロック図である。
【図２】図１に示された暗号化装置の動作を示すフローチャートである。
【図３】非特許文献２に係わる復号装置の一構成例を示すブロック図である。
【図４】図３に示された復号装置の動作を示すフローチャートである。
【図５】本発明の第１の実施の形態の暗号化装置３００の構成を示すブロック図である。
【図６】本発明の第１の実施の形態の復号装置４００の構成を示すブロック図である。
【図７】本発明の第２の実施の形態の暗号化装置３１０の構成を示すブロック図である。
【図８】本発明の第２の実施の形態の復号装置４１０の構成を示すブロック図である。
【図９】暗号化装置又は復号装置として機能するコンピュータの一構成例を示すブロック図である。
【図１０】図５の暗号化装置の動作を示すフローチャートである。
【図１１】図６の復号装置の動作を示すフローチャートである。
【図１２】図７の暗号化装置の動作を示すフローチャートである。
【図１３】図８の復号装置の動作を示すフローチャートである。
【発明を実施するための形態】
【００９６】
以下、本発明に係わる典型的な実施形態について図面を用いて詳細に説明する。
【００９７】
本発明に係わる第１の実施形態の暗号化装置及び復号装置は、ベータ分布に従う試行のシミュレーション方法を用いた暗号化装置及び復号装置である。
【００９８】
ベータ分布とは、0≦y≦1を確率変数とする確率分布であって、ベータ分布に従う試行の確率密度関数は、以下の式によって表される。
【００９９】
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B(a,b)はベータ関数
この分布は、0と1間の値の一様分布に従う独立なa+b-1個の確率変数を大きさの順に並べ替えたときの小さいほうからa番目で大きいほうからb番目の値の確率変数である。
【０１００】
a=bである場合ならば、ceil((a+b)/2)番目の値を表す確率変数となる。定義域が{1,...,M}であり、値域が{1,...,N}であるような順序保存関数を一様にランダムに選ぶ場合、同じ要素が選ばれない限り、1からNの中から一様ランダムにM個の値を選び、これを小さいほうから並べた集合に定義域内の小さな値から対応させることで選択できる。
【０１０１】
つまり、a=bであるベータ分布に従う試行をシミュレートした結果である yに対し、ceil(N*y)は順序保存関数からランダムに関数が選ばれる場合、定義域中の中間の値が、値域のどの値に対応しているかを表すことになる。つまり、負の超幾何分布に従う試行のシミュレートをベータ分布に従う試行のシミュレーションで代替できることを表している。ベータ分布に従う試行は、負の超幾何分布に従う試行に比べて、効率的にシミュレートする方法がよく知られており（非特許文献５など）、さらに、a=bである場合に特に効率的に動作するアルゴリズムが知られている。以上のような方法で、第２の方法における暗号化処理、復号処理において実行される。
【０１０２】
負の超幾何分布に従う試行のシミュレーションを効率的な方法によって代替することで、定義域、値域に対する順序保存関数の中からほぼ一様ランダムに関数を効率的に指定することができる第２の解決法は、r_eを選択する処理を一様分布に従う試行を用いて行う方法である。すなわち、本発明に係わる第２の実施形態の暗号化装置及び復号装置は、一様分布に従う試行のシミュレーション方法を用いた暗号化装置及び復号装置である。
【０１０３】
一様分布とは、a≦y≦b (0≦a≦1, 0≦b≦1)を確率変数とする確率分布であって、その確率密度関数は以下の式によって表される。
【０１０４】
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
この方法は、aとb間の値の一様分布に従う試行によってyを選択し、ceil(N*y)をr_eとする方法である。一様分布は、様々な分布をシミュレートするためにベースの分布として利用されている。この分布に従う試行は非常に簡単にシミュレート可能な値とされているため、順序保存関数に関する演算を効率的に実行することができる。
【０１０５】
まず、ベータ分布に従う試行のシミュレーション方法を用いた場合の第１の実施形態について説明する。
【０１０６】
図５は本発明の第１実施形態に係わる暗号化装置のブロック図である。暗号化装置の構成について、図５を用いて説明を行う。
【０１０７】
図５を参照すると、暗号化装置300は、暗号化処理制御部301と、ベータ分布シミュレート部303 を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【０１０８】
図１０は、本実施形態の暗号化装置300の動作を示すフローチャートである。これを用いて、暗号化装置300の実施の形態の動作について説明する。
【０１０９】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される(ｍ及びｎは１を超える自然数)（ステップC1）。
【０１１０】
暗号化処理制御部301は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する。(ステップC2)。
【０１１１】
暗号化処理制御部301は、Sをシードとしてベータ分布シミュレート部303を動作させ、a=bであるベータ分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップC3）。
【０１１２】
暗号化処理制御部301は、d=d_cが成立しているかを調べる(ステップC4)。ステップC4が成立している場合、暗号化処理制御部301は、r_{ceil(|R|*y)}をdの暗号文として出力する(ステップC5)。
【０１１３】
ステップC4が成立していない場合、暗号化処理制御部301は、d < d_cが成立しているかを調べる(ステップC6)。
【０１１４】
ステップC6が成立している場合、暗号化処理制御部301は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップC2に戻る(ステップC7)。ステップC6が成立していない場合、暗号化処理制御部301は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n} とし、ステップC2に戻る(ステップC8)。
【０１１５】
図６は本発明の第１実施形態に係わる復号装置のブロック図である。復号装置４００の構成について、図６を用いて説明を行う。
【０１１６】
図６を参照すると、復号装置400は、復号処理制御部401と、ベータ分布シミュレート部303を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。図１１は復号装置400の動作を示すフローチャートである。これを用いて復号装置400の実施の形態の動作について説明する。
【０１１７】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップD1）。復号処理制御部401は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップD2)。復号処理制御部401は、Sをシードとしてベータ分布シミュレート部303を動作させ、a=bであるベータ分布に従った試行をシミュレートした結果であるyを生成し、r_e = ceil(|R|*y)をd_cに対する暗号文とする（ステップD3）。
【０１１８】
復号処理制御部401は、r_e=rが成立しているかを調べる(ステップD4)。ステップD4が成立している場合、復号処理制御部401は、d_c をrの平文として出力する(ステップD5)。
【０１１９】
ステップD4が成立していない場合、復号処理制御部401は、r_e< rが成立しているかを調べる(ステップD6)。
【０１２０】
ステップD6が成立している場合、復号処理制御部401は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{e-1}}とし、ステップD2に戻る(ステップD7)。ステップD6が成立していない場合、復号処理制御部401は、D= {d_｛c+1},…,d_m}とし、R={r_{e+1},..,r_n} とし、ステップD2に戻る(ステップD8)。
【０１２１】
次に、一様分布に従う試行のシミュレーション方法を用いた場合の第２の実施形態について説明する。
【０１２２】
図７は本発明の第２の実施形態に係わる暗号化装置のブロック図である。暗号化装置の構成について、図７を用いて説明を行う。
【０１２３】
図7を参照すると、暗号化装置310は、暗号化処理制御部301と、 一様分布シミュレート部304 を備え、平文、シード、平文空間、暗号文空間を入力として、暗号文を出力する。
【０１２４】
図１２は、本実施形態の暗号化装置310の実施の形態の動作を示すフローチャートである。これを用いて、暗号化装置310の実施の形態の動作について説明する。
【０１２５】
まず、平文dとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップE1）。
【０１２６】
暗号化処理制御部301は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する。(ステップE2)。
【０１２７】
暗号化処理制御部301は、Sをシードとして一様分布シミュレート部304を動作させ、0と1の間の値の一様分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップE3）。
【０１２８】
暗号化処理制御部301は、d=d_cが成立しているかを調べる(ステップE4)。ステップE4が成立している場合、暗号化処理制御部301は、r_{ceil(|R|*y)}をdの暗号文として出力する(ステップE5)。
【０１２９】
ステップE4が成立していない場合、暗号化処理制御部301は、d<d_cが成立しているかを調べる(ステップE6)。
【０１３０】
ステップE6が成立している場合、暗号化処理制御部301は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n}とし、ステップE2に戻る(ステップE7)。ステップE6が成立していない場合、暗号化処理制御部301は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップE2に戻る(ステップE8)。
【０１３１】
図８は本発明の第２の実施形態に係わる復号装置のブロック図である。復号装置４１０の構成について、図８を用いて説明を行う。
【０１３２】
図８を参照すると、復号装置410は、復号処理制御部401と、一様分布シミュレート部304を備え、暗号文、シード、平文空間、暗号文空間を入力として、平文を出力する。図１３は復号装置410の動作を示すフローチャートである。これを用いて復号装置410の実施の形態の動作について説明する。
【０１３３】
まず、暗号文rとシードSと平文空間D={d_1,...,d_m}と暗号文空間R={r_1,..,r_n}が入力される（ステップF1）。 復号処理制御部401は、平文空間の要素を数字的大小で並べた時の中間の値d_cを求め記憶する(ステップF2)。復号処理制御部401は、Sをシードとして一様分布シミュレート部304を動作させ、0と1の間の一様分布に従った試行をシミュレートした結果であるyを生成し、r_{ceil(|R|*y)}をd_cに対する暗号文とする（ステップF3）。
【０１３４】
復号処理制御部401は、r_{ceil(|R|*y)}=rが成立しているかを調べる(ステップF4)。ステップF4が成立している場合、復号処理制御部401は、d_c をrの平文として出力する(ステップF5)。
【０１３５】
ステップF4が成立していない場合、復号処理制御部401は、r_{ceil(|R|*y)}<rが成立しているかを調べる(ステップF6)。
【０１３６】
ステップF6が成立している場合、復号処理制御部401は、D= {d_｛c+1},…,d_m}とし、R={r_{ceil(|R|*y)+1},..,r_n}とし、ステップF2に戻る(ステップF7)。ステップF6が成立していない場合、復号処理制御部401は、D= {d_1,…,d_{c-1}}とし、R={r_1,..,r_{ceil(|R|*y)-1}}とし、ステップF2に戻る(ステップF8)。
【０１３７】
上記実施形態の一様分布において、0付近、もしくは1付近が生成されると、各暗号文間の広さが小さくなる可能性がある。暗号文間の広さが小さいと、それらの平文間の差も小さいことが解析できてしまう。
【０１３８】
これは、a,bが0から1ではなく、0 < a< b < 1であるような区間[a,b]の一様分布を用いることで防ぐことができる。
【０１３９】
以上説明した、第１及び第２の実施形態の暗号化装置及び復号装置は、ハードウェアで構成することができる。しかし、当該かかる暗号化装置及び復号装置の機能をソフトウェアで実現することができる。図９は、暗号化装置又は復号装置として機能するコンピュータの一構成例を示すブロック図である。
【０１４０】
図9に示す処理装置10は、CPU11と、CPU11の処理に必要な情報を一時的に記憶する主記憶装置１２と、CPU11に 暗号化装置300又は310、復号装置400又は410、としての処理を実行させるためのプログラムが記録された記録媒体１３と、平文や、暗号文、鍵情報などが格納されるデータ蓄積装置１４と、主記憶装置１２、記録媒体１３及びデータ蓄積装置１４とのデータ転送を制御するメモリ制御インターフェース部１５と、入力装置２０及び出力装置３０とのインターフェース装置であるI/Oインターフェース部１６とを有し、それらは バス１７を介して接続された構成である。
なお、データ蓄積装置１４は、処理装置 １０内にある必要はなく、処理装置１０から独立して備えていてもよい。
処理装置１０は、暗号化装置300又は310、復号装置400又は410、の機能を実現する。
記録媒体１３は、磁気ディスク装置、半導体メモリ、光ディスク装置あるいはその他の 記録媒体であってもよい。
【０１４１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下の構成には限られない。
【０１４２】
（付記１）
ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【０１４３】
（付記２）
ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【０１４４】
（付記３）
一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【０１４５】
（付記４）
一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【０１４６】
（付記５）
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【０１４７】
（付記６）
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【０１４８】
（付記７）
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【０１４９】
（付記８）
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【０１５０】
（付記９）
コンピュータに、
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成する手順と、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５１】
（付記１０）
コンピュータに、
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成する手順と、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５２】
（付記１１）
コンピュータに、
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成する手順と、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【０１５３】
（付記１２）
コンピュータに、
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する手順を実行させるためのプログラムであって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成する手順と、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定する手順と、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順と、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る手順とを実行させるためのプログラム。
【産業上の利用可能性】
【０１５４】
本発明は登録情報が暗号化されているデータベースにおいて範囲検索を行う場合の暗号化装置、暗号化方法、復号装置及び復号方法に適用できる。
【符号の説明】
【０１５５】
10 処理装置
11 CPU
12 主記憶装置
13 記録媒体
14 データ蓄積装置
15 メモリ制御インターフェース部
16 I/Oインターフェース部
20 入力装置
30 出力装置
100, 300, 310 暗号化装置
101, 301 暗号化処理制御装置
102 負の超幾何分布シミュレート装置
303 ベータ分布シミュレート装置
304 一様分布シミュレート装置
200, 400, 410 復号装置
201, 401 復号処理制御装置
【特許請求の範囲】
【請求項１】
ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【請求項２】
ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【請求項３】
一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【請求項４】
一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【請求項５】
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【請求項６】
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【請求項７】
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【請求項８】
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【請求項１】
ベータ分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【請求項２】
ベータ分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記ベータ分布シミュレート部を動作させて、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【請求項３】
一様分布シミュレート部と、暗号化処理制御部とを備え、入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置であって、
前記暗号化処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置。
【請求項４】
一様分布シミュレート部と、復号処理制御部とを備え、入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置であって、
前記復号処理制御部は、
前記平文空間の中間の値d_cを決定し、前記シードSを用いて前記一様分布シミュレート部を動作させて、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置。
【請求項５】
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【請求項６】
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、ベータ分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= y{a-1}(1-y){b-1}/B(a,b) 0≦a≦1, 0≦b≦1, B (a,b)はベータ関数
a=bであるベータ分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【請求項７】
入力された、平文d、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、暗号文を出力する暗号化装置の暗号化方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b < 1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
d=d_cが成立しているかを判定し、成立している場合、r_{ceil(|R|*y)}をd_cに対する暗号文として出力し、成立していない場合にd< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る暗号化装置の暗号化方法。
【請求項８】
入力された、暗号文r、シードS、平文空間D={d_1,...,d_m}、及び暗号文空間R={r_1,..,r_n}に基づいて、平文を出力する復号装置の復号方法であって、
前記平文空間の中間の値d_cを決定し、前記シードSを用い、一様分布に従う試行の確率密度関数を、以下の式で表したときに、
Pr(y)= 1/(b-a) (a≦y≦b)
Pr(y)=0 (y<aまたはb<y)
a, bが0と1の間の値である一様分布又は0< a < b <1を満たすaとbの間の値である一様分布に従う試行をシミュレートした結果であるyを生成し、
r=r_{ceil(|R|*y)}が成立しているかを判定し、成立している場合、d_cを平文として出力し、成立していない場合に、d< d_cが成立しているかを判定し、
d< d_cが成立している場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛1},…,d_{c-1}}、暗号文空間R={r_{1},...,r_{ceil(|R|*y)-1},..,r_n}として、平文空間の中間の値を決定する処理に戻り、
d< d_cが成立していない場合、前記平文空間D={d_1,...,d_m}、及び前記暗号文空間R={r_1,..,r_n}をそれぞれ平文空間D= {d_｛c+1},…,d_{m}}、暗号文空間R={r_{ceil(|R|*y)+1},..,r_n}として、平文空間の中間の値を決定する処理に戻る復号装置の復号方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１３−３３１０１（Ｐ２０１３−３３１０１Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１１−１６８６０２（Ｐ２０１１−１６８６０２）
【出願日】平成２３年８月１日（２０１１．８．１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願日】平成２３年８月１日（２０１１．８．１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]