(57)【要約】  非減少列の存在を効率よく判定する。整列部１０は、集合Piの要素を昇順に並べたベクトルti,i+1とbi,i+1を生成する。併合部２０は、ベクトル（ti,j,bi,j）と（tj,k,bj,k）とを併合してベクトル(ti,k,bi,k)を生成することを繰り返すことでベクトルt0,mとb0,mとを生成する。安定ソート部２１は、ベクトルbi,jとtj,kを連結して安定ソートしたベクトルeを生成する。探索部２２は、e[λ]がbi,j[x]であり、e[λ+1]がtj,k[y]である（λ,x,y）の組を探索し、xをすべて含む集合Xとyをすべて含む集合Yとを生成する。抽出部２３は、ti,j[x]（x∈X）を昇順に並べたベクトルti,kと、bj,k[y]（y∈Y）を昇順に並べたベクトルbi,kとを生成する。判定部３０は、ベクトルt0,mの長さが0であれば非減少列が存在しないことを示す判定結果を出力する。
2016056502.tif 000002
【特許請求の範囲】
【請求項１】
m個の集合P0,…,Pm-1を入力として、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とベクトルbi,i+1を生成する整列部と、
0≦i<j<k≦mを満たすベクトル（ti,j,bi,j）とベクトル（tj,k,bj,k）とを併合してベクトル(ti,k,bi,k)を生成することを繰り返すことで、ベクトルt0,1,…,tm-1,mを併合したベクトルt0,mと、ベクトルb0,1,…,bm-1,mを併合したベクトルb0,mとを生成する併合部と、
ベクトルt0,mの長さが0であれば非減少列が存在しないことを示し、ベクトルt0,mの長さが1以上であれば非減少列が存在することを示す判定結果を出力する判定部と、
を含み、
上記併合部は、
ベクトルbi,jとベクトルtj,kを連結して昇順に安定ソートしたベクトルeを生成する安定ソート部と、
ベクトルeからe[λ]がbi,j[x]であり、e[λ+1]がtj,k[y]である（λ,x,y）の組をすべて探索し、発見されたxをすべて含む集合Xと、発見されたyをすべて含む集合Yとを生成する探索部と、
ベクトルti,jの要素ti,j[x]（x∈X）を昇順に並べたベクトルti,kと、ベクトルbj,kの要素bj,k[y]（y∈Y）を昇順に並べたベクトルbi,kとを生成する抽出部と、
を含む非減少列判定装置。
【請求項２】
(0,1)nは0と1を繰り返した長さ2nのベクトルとし、¬・は・の否定を表し、
m個の集合P0,…,Pm-1を入力として、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とベクトルbi,i+1を生成する整列部と、
集合P0,…,PM-1の各要素が0以上n未満であるとして、k=0,…,n-1、λ=0,…,m-1について、ti,i+1[λ]=kを満たすλが存在すればt'i,i+1[k]=1を設定し、それ以外はt'i,i+1[k]=0を設定したベクトルt'i,i+1を秘匿化した暗号文〔t'i,i+1〕と、bi,i+1[λ]=kを満たすλが存在すればb'i,i+1[k]=1を設定し、それ以外はb'i,i+1[k]=0を設定したベクトルb'i,i+1を秘匿化した暗号文〔b'i,i+1〕とを生成する秘匿化部と、
0≦i<j<k≦mを満たす秘匿文（〔t'i,j〕,〔b'i,j〕）と（〔t'j,k〕,〔b'j,k〕）とを併合して秘匿文(〔t'i,k〕,〔b'i,k〕)を生成することを繰り返すことで、秘匿文〔t'0,1〕,…,〔t'm-1,m〕を併合した秘匿文〔t'0,m〕と、秘匿文〔b'0,1〕,…,〔b'm-1,m〕を併合した秘匿文〔b'0,m〕とを生成する併合部と、
秘匿文〔t'0,m〕を用いて、〔t'0,m[0]〕∨〔t'0,m[1]〕∨…∨〔t'0,m[m-1]〕を計算し、その計算結果を判定結果として出力する判定部と、
を含み、
上記併合部は、
秘匿文〔b'i,j〕と〔t'j,k〕の各要素を交互に配列して秘匿文〔a〕を生成し、¬〔a〕をキーとして秘匿文(〔(0,1)n〕,〔a〕,〔(0,…,2n-1)〕)を安定ソートした秘匿文(〔f'〕,〔a'〕,〔p〕)を生成する第一安定ソート部と、
h=0,…,n-1について、〔a[h]〕×(¬〔f'[h]〕×〔f'[h+1]〕+〔f'[h]〕×¬〔f'[h-1]〕)を計算して秘匿文〔m〕を生成し、秘匿文〔p〕をキーとして秘匿文〔m〕をキー公開ソートした秘匿文〔m'〕を生成する第一キー公開ソート部と、
秘匿文〔m〕の各要素を交互に分解して秘匿文〔m0〕,〔m1〕を生成し、¬〔t'i,j〕をキーとして(〔t'i,j〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔t"0〕,〔p0〕)と、¬〔b'i,j〕をキーとして秘匿文〔m0〕を安定ソートした秘匿文〔m"0〕と、¬〔b'j,k〕をキーとして(〔b'j,k〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔b"1〕,〔p1〕)と、¬〔t'j,k〕をキーとして秘匿文〔m1〕を安定ソートした秘匿文〔m"1〕とを生成する第二安定ソート部と、
秘匿文〔t"0〕と秘匿文〔m"0〕の積である秘匿文〔t"〕と、秘匿文〔b"1〕と秘匿文〔m"1〕の積である秘匿文〔b"〕とを生成し、秘匿文〔p0〕をキーとして秘匿文〔t"〕をキー公開ソートした秘匿文〔t'i,k〕と、秘匿文〔p1〕をキーとして秘匿文〔b"〕をキー公開ソートした秘匿文〔b'i,k〕とを生成する第二キー公開ソート部と、
を含む非減少列判定装置。
【請求項３】
請求項１または２に記載の非減少列判定装置であって、
上記併合部は、次式を満たすi,j,kを選択するものである
【数２２】
2016056502.tif 000024
非減少列判定装置。
【請求項４】
整列部が、m個の集合P0,…,Pm-1を入力として、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とベクトルbi,i+1を生成する整列ステップと、
併合部が、0≦i<j<k≦mを満たすベクトル（ti,j,bi,j）とベクトル（tj,k,bj,k）とを併合してベクトル(ti,k,bi,k)を生成することを繰り返すことで、ベクトルt0,1,…,tm-1,mを併合したベクトルt0,mと、ベクトルb0,1,…,bm-1,mを併合したベクトルb0,mとを生成する併合ステップと、
判定部が、ベクトルt0,mの長さが0であれば非減少列が存在しないことを示し、ベクトルt0,mの長さが1以上であれば非減少列が存在することを示す判定結果を出力する判定ステップと、
を含み、
上記併合ステップは、
安定ソート部が、ベクトルbi,jとベクトルtj,kを連結して昇順に安定ソートしたベクトルeを生成する安定ソートステップと、
探索部が、ベクトルeからe[λ]がbi,j[x]であり、e[λ+1]がtj,k[y]である（λ,x,y）の組をすべて探索し、発見されたxをすべて含む集合Xと、発見されたyをすべて含む集合Yとを生成する探索ステップと、
抽出部が、ベクトルti,jの要素ti,j[x]（x∈X）を昇順に並べたベクトルti,kと、ベクトルbj,kの要素bj,k[y]（y∈Y）を昇順に並べたベクトルbi,kとを生成する抽出ステップと、
を含む非減少列判定方法。
【請求項５】
(0,1)nは0と1を繰り返した長さ2nのベクトルとし、¬・は・の否定を表し、
整列部が、m個の集合P0,…,Pm-1を入力として、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とベクトルbi,i+1を生成する整列ステップと、
秘匿化部が、集合P0,…,PM-1の各要素が0以上n未満であるとして、k=0,…,n-1、λ=0,…,m-1について、ti,i+1[λ]=kを満たすλが存在すればt'i,i+1[k]=1を設定し、それ以外はt'i,i+1[k]=0を設定したベクトルt'i,i+1を秘匿化した暗号文〔t'i,i+1〕と、bi,i+1[λ]=kを満たすλが存在すればb'i,i+1[k]=1を設定し、それ以外はb'i,i+1[k]=0を設定したベクトルb'i,i+1を秘匿化した暗号文〔b'i,i+1〕とを生成する秘匿化ステップと、
併合部が、0≦i<j<k≦mを満たす秘匿文（〔t'i,j〕,〔b'i,j〕）と（〔t'j,k〕,〔b'j,k〕）とを併合して秘匿文(〔t'i,k〕,〔b'i,k〕)を生成することを繰り返すことで、秘匿文〔t'0,1〕,…,〔t'm-1,m〕を併合した秘匿文〔t'0,m〕と、秘匿文〔b'0,1〕,…,〔b'm-1,m〕を併合した秘匿文〔b'0,m〕とを生成する併合ステップと、
判定部が、秘匿文〔t'0,m〕を用いて、〔t'0,m[0]〕∨〔t'0,m[1]〕∨…∨〔t'0,m[m-1]〕を計算し、その計算結果を判定結果として出力する判定ステップと、
を含み、
上記併合ステップは、
第一安定ソート部が、秘匿文〔b'i,j〕と〔t'j,k〕の各要素を交互に配列して秘匿文〔a〕を生成し、¬〔a〕をキーとして秘匿文(〔(0,1)n〕,〔a〕,〔(0,…,2n-1)〕)を安定ソートした秘匿文(〔f'〕,〔a'〕,〔p〕)を生成する第一安定ソートステップと、
第一キー公開ソート部が、h=0,…,n-1について、〔a[h]〕×(¬〔f'[h]〕×〔f'[h+1]〕+〔f'[h]〕×¬〔f'[h-1]〕)を計算して秘匿文〔m〕を生成し、秘匿文〔p〕をキーとして秘匿文〔m〕をキー公開ソートした秘匿文〔m'〕を生成する第一キー公開ソートステップと、
第二安定ソート部が、秘匿文〔m〕の各要素を交互に分解して秘匿文〔m0〕,〔m1〕を生成し、¬〔t'i,j〕をキーとして(〔t'i,j〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔t"0〕,〔p0〕)と、¬〔b'i,j〕をキーとして秘匿文〔m0〕を安定ソートした秘匿文〔m"0〕と、¬〔b'j,k〕をキーとして(〔b'j,k〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔b"1〕,〔p1〕)と、¬〔t'j,k〕をキーとして秘匿文〔m1〕を安定ソートした秘匿文〔m"1〕とを生成する第二安定ソートステップと、
第二キー公開ソート部が、秘匿文〔t"0〕と秘匿文〔m"0〕の積である秘匿文〔t"〕と、秘匿文〔b"1〕と秘匿文〔m"1〕の積である秘匿文〔b"〕とを生成し、秘匿文〔p0〕をキーとして秘匿文〔t"〕をキー公開ソートした秘匿文〔t'i,k〕と、秘匿文〔p1〕をキーとして秘匿文〔b"〕をキー公開ソートした秘匿文〔b'i,k〕とを生成する第二キー公開ソートステップと、
を含む非減少列判定方法。
【請求項６】
請求項４または５に記載の非減少列判定方法であって、
上記併合ステップは、次式を満たすi,j,kを選択するものである
【数２３】
2016056502.tif 000025
非減少列判定方法。
【請求項７】
請求項１から３のいずれかに記載の非減少列判定装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号応用技術に関し、特に、入力データを明かすことなく非減少列の存在を判定する方法に関する。
【背景技術】
【０００２】
暗号化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。【０００３】
秘密計算上で文字列のパターンマッチングを実現した方法として、非特許文献２の方法がある。非特許文献２の方法では、パターンの表す非決定性有限オートマトンを入力テキスト１文字ごとに評価することによってパターンマッチングを実現している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能3パーティ秘匿関数計算の再考”、CSS、2010年
【非特許文献２】原田弘毅、笹川裕人、有村博紀、佐久間淳、“多項式時間・領域秘密正規表現照合アルゴリズム”、 SCIS、pp. 1-8、2014年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２の従来技術はパターンマッチングの入力テキスト長をnとすると、Ω(n)段の乗算を要していた。パターンマッチングを行う場合にパターン中の部分文字列の位置が判明した後にテキストがパターンにマッチしているかを判定する処理は、集合の列から一要素ずつ選んで非減少列を作ることができるかどうかを判定する問題に抽象化できる。【０００６】
この発明の目的は、集合の列から一要素ずつ選んだ非減少列の存在を効率よく判定することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の非減少列判定装置は、m個の集合P0,…,Pm-1を入力として、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とベクトルbi,i+1を生成する整列部と、0≦i<j<k≦mを満たすベクトル（ti,j,bi,j）とベクトル（tj,k,bj,k）とを併合してベクトル(ti,k,bi,k)を生成することを繰り返すことで、ベクトルt0,1,…,tm-1,mを併合したベクトルt0,mと、ベクトルb0,1,…,bm-1,mを併合したベクトルb0,mとを生成する併合部と、ベクトルt0,mの長さが0であれば非減少列が存在しないことを示し、ベクトルt0,mの長さが1以上であれば非減少列が存在することを示す判定結果を出力する判定部と、を含む。併合部は、ベクトルbi,jとベクトルtj,kを連結して昇順に安定ソートしたベクトルeを生成する安定ソート部と、ベクトルeからe[λ]がbi,j[x]であり、e[λ+1]がtj,k[y]である（λ,x,y）の組をすべて探索し、発見されたxをすべて含む集合Xと、発見されたyをすべて含む集合Yとを生成する探索部と、ベクトルti,jの要素ti,j[x]（x∈X）を昇順に並べたベクトルti,kと、ベクトルbj,kの要素bj,k[y]（y∈Y）を昇順に並べたベクトルbi,kとを生成する抽出部と、を含む。
【発明の効果】
【０００８】
この発明の非減少列判定技術によれば、m個の集合から一要素ずつ選んだ非減少列の存在をO(log m)段で判定することができる。したがって、非減少列の存在を効率よく判定することができる。また、これにより、テキストに対するパターンマッチングを効率よく処理することが可能となる。
【図面の簡単な説明】
【０００９】
【図１】図１は、第一実施形態の非減少列判定装置の機能構成を例示する図である。
【図２】図２は、第一実施形態の非減少列判定方法の処理フローを例示する図である。
【図３】図３は、第三実施形態の非減少列判定装置の機能構成を例示する図である。
【図４】図４は、第三実施形態の非減少列判定方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法および用語の定義について説明する。
【００１１】
＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、〔a〕と表記する。秘匿化が秘密分散である場合は、〔a〕により各秘密計算装置が持つ秘密分散の断片の集合を参照する。
【００１２】
行列Xの第i行をX[i]と表記する。ベクトルuの第i要素をu[i]と表記する。行列Xの各要素を秘匿化した行列全体を〔X〕と表記し、Xの秘匿文と呼ぶ。ベクトルuの各要素を秘匿化したベクトル全体を〔u〕と表記し、uの秘匿文と呼ぶ。
【００１３】
【数１】
2016056502.tif 000003
は天井関数であり、・以上の最小の整数を意味する。
【００１４】
【数２】
2016056502.tif 000004
は床関数であり、・以下の最大の整数を意味する。
・Tは・の転置を表す。
【００１５】
＜加算、減算、乗算＞
加算、減算、乗算の各演算は二つの値a, bの秘匿文〔a〕,〔b〕を入力とし、それぞれa+b, a-b, abの計算結果c1, c2, c3の秘匿文〔c1〕,〔c2〕,〔c3〕を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【数３】
2016056502.tif 000005
【００１６】
なお、誤解を招く恐れのない場合は、Add(〔a〕,〔b〕),Sub(〔a〕,〔b〕),Mul(〔a〕,〔b〕)をそれぞれ〔a〕+〔b〕,〔a〕-〔b〕,〔a〕×〔b〕と略記する。
【００１７】
＜論理演算＞
論理和、論理積、否定の各演算は二つの値a, b∈{0, 1}の秘匿文〔a〕,〔b〕を入力とし、それぞれaとbの論理和, aとbの論理積, aの否定の計算結果c1, c2, c3の秘匿文〔c1〕,〔c2〕,〔c3〕を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【数４】
2016056502.tif 000006
【００１８】
これらの論理演算は、次式の計算により実現される。
【数５】
2016056502.tif 000007
【００１９】
＜ソート演算＞
ソートはベクトルの要素を昇順に並べ替えたベクトルを出力する演算である。入力のベクトルk=(k[0],…,k[n-1])に対して出力されるベクトルk’=(k’[0],…,k’[n-1])は、k’[0]≦…≦k’[n-1]を満たすkの要素を並べ替えたベクトルである。
【００２０】
安定ソートは、ソート演算で同じ値が存在した場合に同じ値の要素同士の順序を保存する演算である。ベクトルkとk’の各要素はある全単射πs:{0,…,n-1}→{0,…,n-1}についてk’[πs(i)]=k[i]を満たしており、安定ソートでは次式が成り立つ。
【数６】
2016056502.tif 000008
【００２１】
以下で扱う秘密計算上の安定ソート演算は、複数のベクトルを入力とし、キーとするベクトルの要素の並べ替えに従って他のベクトルの要素の並べ替えを行う。すなわち、安定ソートのキーとする大きさnのベクトルkと、λ個（1≦λ）の大きさnのベクトルa(0),…,a(λ-1)の秘匿文〔k〕,〔a(0)〕,…,〔a(λ-1)〕を入力とし、ベクトルkを安定ソートしたときの並べ替えに従って各ベクトルa(0),…,a(λ-1)の要素を並べ替えたベクトルb(0),…,b(λ-1)の秘匿文〔b(0)〕,…,〔b(λ-1)〕を計算する。この演算の実行を次式のように記述する。
【数７】
2016056502.tif 000009
【００２２】
キー公開ソートは安定ソート演算でキーが公開される処理である。キーを秘匿したまま処理をするソートよりも効率がよく、キーに含まれる値の構成が既知の場合には余計な情報を漏らす心配がない。この演算の実行を次式のように記述する。
【数８】
2016056502.tif 000010
【００２３】
秘匿化、復元、加算、減算、乗算は、例えば、非特許文献１に記載の方法を用いればよい。また、安定ソート、キー公開ソートは、例えば、「Koki Hamada, Dai Ikarashi, Koji Chida, and Katsumi Takahashi, “Oblivious radix sort: An efficient sorting algorithm for practical secure multi-party computation”, IACR Cryptology ePrint Archive, vol. 2014, p. 121, 2014.（参考文献１）」に記載の方法を用いればよい。
【００２４】
＜非減少列＞
非減少列判定技術は、m個の集合P0,P1,…,Pm-1に対して、大きさmの非減少列となっているベクトルp（ただし、p[i]∈Pi（0≦i<m）、かつ、p[0]≦p[1]≦…≦p[m-1]）が存在するかどうかを判定する方法である。
【００２５】
例えば、集合P0,P1,…,P4が以下であるとする。
P0={0,3,7,8,10},
P1={2,5,8,9},
P2={2,4,8},
P3={0,4,7,9},
P4={0,6,7}
このとき、例えば、ベクトルp0=(0,8,2,4,6)は、p0[i]∈Pi（0≦i<m）を満たすが、p0[1]>p0[2]であるのでp0[0]≦p0[1]≦p0[2]≦p0[3]≦p0[4]を満たさず、非減少列ではない。
一方、例えば、ベクトルp1=(0,2,4,4,6)は、p1[i]∈Pi（0≦i<m）を満たし、かつ、p1[0]≦p1[1]≦p1[2]≦p1[3]≦p1[4]を満たすため、非減少列である。
【００２６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２７】
［第一実施形態］
第一実施形態の非減少列判定装置１は、図１に例示するように、整列部１０、併合部２０及び判定部３０を含む。併合部２０は、例えば、安定ソート部２１、探索部２２及び抽出部２３を含む。
【００２８】
非減少列判定装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。非減少列判定装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。非減少列判定装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２９】
以下、図２を参照して、第一実施形態の非減少列判定方法を説明する。
【００３０】
第一実施形態の非減少列判定方法は、m個の集合P0,…,Pm-1を入力として、大きさmの非減少列となっているベクトルpが存在するならば１を、存在しないならば０を返す。
【００３１】
ステップＳ１０において、整列部１０は、i=0,…,m-1について、集合Piの要素を昇順に並べたベクトルti,i+1とbi,i+1を生成する。つまり、集合P0の要素を昇順に並べてベクトルt0,1とb0,1を生成し、集合P1の要素を昇順に並べてベクトルt1,2とb1,2を生成し、…、集合Pm-1の要素を昇順に並べてベクトルtm-1,mとbm-1,mを生成する。
【００３２】
ステップＳ２０aにおいて、併合部２０は、0≦i<j<k≦mを満たすベクトル（ti,j,bi,j）と（tj,k,bj,k）を選択し、ステップＳ２１〜Ｓ２３の処理により、ベクトル（ti,j,bi,j）と（tj,k,bj,k）とを併合してベクトル(ti,k,bi,k)を生成する。併合部２０は、これを再帰的に繰り返すことで、ベクトルt0,1,…,tm-1,mを併合したベクトルt0,mと、ベクトルb0,1,…,bm-1,mを併合したベクトルb0,mとを生成する。
【００３３】
ステップＳ２１において、安定ソート部２１は、ベクトルbi,jとベクトルtj,kを連結して昇順に安定ソートしたベクトルeを生成する。
【００３４】
ステップＳ２２において、探索部２２は、ベクトルeからe[λ]がbi,j[x]であり、e[λ+1]がtj,k[y]である（λ,x,y）の組をすべて探索し、発見されたxをすべて含む集合Xと、発見されたyをすべて含む集合Yとを生成する。
【００３５】
ステップＳ２３において、抽出部２３は、ti,j[x]（x∈X）を昇順に並べたベクトルti,kと、bj,k[y]（y∈Y）を昇順に並べたベクトルbi,kとを生成する。
【００３６】
ステップＳ２０ｂにおいて、併合部２０は、ベクトルt0,1,…,tm-1,mとベクトルb0,1,…,bm-1,mがすべて併合されたかを判断する。すなわち、ベクトル（t0,m,b0,m）が生成されたかを確認する。併合が完了していなければステップＳ２０aへ処理を戻す。併合が完了していればステップＳ３０へ処理を進める。
【００３７】
ステップＳ３０において、判定部３０は、ベクトルt0,mの長さが0であれば非減少列が存在しないことを示す０を判定結果として出力する。ベクトルt0,mの長さが1以上であれば非減少列が存在することを示す１を判定結果として出力する。
【００３８】
上述の方法により非減少列の存在を判定できることを、具体例を用いて示す。
【００３９】
集合P0,P1,…,P4が以下であるとする。
P0={0,3,7,8,10},
P1={2,5,8,9},
P2={2,4,8},
P3={0,4,7,9},
P4={0,6,7}
【００４０】
非減少列はp[i]∈Pi（0≦i<m）かつp1[0]≦p1[1]≦p1[2]≦p1[3]≦p1[4]であるため、集合P0,P1,…,P4には、例えば(0,2,2,4,6), (0,2,2,4,7), (0,2,4,4,6), (0,2,4,4,7), (0,2,4,7,7)などの非減少列が存在する。
【００４１】
ステップＳ１０において、以下のベクトルt0,1,…,t4,5及びb0,1,…,b4,5が生成される。
t0,1=b0,1=(0,3,7,8,10)
t1,2=b1,2=(2,5,8,9)
t2,3=b2,3=(2,4,8)
t3,4=b3,4=(0,4,7,9)
t4,5=b4,5=(0,6,7)
【００４２】
ステップＳ２０aにおいて、i=0, j=1, k=2として、ベクトル(t0,1,b0,1)と(t1,2,b1,2)を選択し、以下のステップＳ２１〜Ｓ２３により併合したベクトル(t0,2,b0,2)を生成する。
【００４３】
ステップＳ２１において、ベクトルb0,1とt1,2から以下のベクトルeが生成される。
e=(0,2,3,5,7,8,8,9,10)
=(b0,1[0],t1,2[0],b0,1[1],t1,2[1],b0,1[2],b0,1[3],t1,2[2],t1,2[3],b0,1[4])
【００４４】
ステップＳ２２において、以下の（λ,x,y）の組が発見される。
(λ=0,x=0,y=0),
(λ=2,x=1,y=1),
(λ=5,x=3,y=2)
したがって、集合X={0,1,3}、集合Y={0,1,2}である。
【００４５】
ステップＳ２３において、以下のベクトル(t0,2,b0,2)が生成される。
t0,2=(t0,1[0],t0,1[1],t0,1[3])=(0,3,8)
b0,2=(b1,2[0],b1,2[1],b1,2[2])=(2,5,8)
【００４６】
ステップＳ２０ｂにおいて、ベクトルt0,5とb0,5が存在しないため、ステップＳ２０ａに処理が戻る。
【００４７】
二度目のステップＳ２０aにおいて、i=2, j=3, k=4として、ベクトル(t2,3,b2,3)と(t3,4,b3,4)を選択し、同様にして併合したベクトル(t2,4,b2,4)を生成する。
【００４８】
ベクトルb2,3=(2,4,8)とベクトルt3,4=(0,4,7,9)を連結して安定ソートすると以下のベクトルeが生成される。
e=(0,2,4,4,7,8,9)
=(t3,4[0],b2,3[0],b2,3[1],t3,4[1],t3,4[2],b2,3[2],t3,4[3])
【００４９】
すると、(λ=2,x=1,y=1),(λ=5,x=2,y=3)が発見されるため、X=(1,2)、Y=(1,3)である。したがって、ベクトル(t2,4,b2,4)は以下のようになる。
t2,4=(t2,3[1],t2,3[2])=(4,8)
b2,4=(b3,4[1],b3,4[3])=(4,9)
【００５０】
三度目のステップＳ２０aにおいて、i=2, j=4, k=5として、ベクトル(t2,4,b2,4)と(t4,5,b4,5)を選択し、同様にして併合したベクトル(t2,5,b2,5)を生成する。
【００５１】
ベクトルb2,4=(4,9)とベクトルt4,5=(0,6,7)を連結して安定ソートすると以下のベクトルeが生成される。
e=(0,4,6,7,9)
=(t4,5[0],b2,4[0],t4,5[1],t4,5[2],b2,4[1])
【００５２】
すると、(λ=1,x=0,y=1)が発見されるため、X=(0)、Y=(1)である。したがって、ベクトル(t2,5,b2,5)は以下のようになる。
t2,5=(t2,4[0])=(4)
b2,5=(b4,5[1])=(6)
【００５３】
四度目のステップＳ２０aにおいて、i=0, j=2, k=5として、ベクトル(t0,2,b0,2)と(t2,5,b2,5)を選択し、同様にして併合したベクトル(t0,5,b0,5)を生成する。
【００５４】
ベクトルb0,2=(2,5,8)とベクトルt2,5=(4)を連結して安定ソートすると以下のベクトルeが生成される。
e=(2,4,5,8)
=(b0,2[0],t2,5[0],b0,2[1],b0,2[2])
【００５５】
すると、(λ=0,x=0,y=0)が発見されるため、X=(0)、Y=(0)である。したがって、ベクトル(t2,5,b2,5)は以下のようになる。
t0,5=(t0,2[0])=(0)
b0,5=(b2,5[0])=(6)
【００５６】
ステップＳ２０ｂにおいて、ベクトルt0,5とb0,5が存在するため、ステップＳ３０に処理を進める。
【００５７】
ステップＳ３０では、t0,5の長さが0ではないため、非減少列が存在することを示す１が判定結果として出力される。
【００５８】
［第二実施形態］
第二実施形態の非減少列判定装置は、併合部２０において、ベクトル(ti,k,bi,k)を生成する際に、次式を満たすようにi,j,kを設定してベクトル(ti,j,bi,j)とベクトル(tj,k,bj,k)を選択する。
【数９】
2016056502.tif 000011
【００５９】
このように構成することで、併合部２０は、
【数１０】
2016056502.tif 000012
段の再帰手続きでベクトル(t0,m,b0,m)を求めることができる。
【００６０】
［第三実施形態］
第三実施形態は非減少列の判定を秘密計算で実現する方法である。第三実施形態では各再帰手続きがO(1)段の計算で実現できるため、全体の処理がO(log m)段で実現できる。
【００６１】
第三実施形態の非減少列判定装置２は、図３に例示するように、整列部１０、秘匿化部４０、併合部５０及び判定部６０を含む。併合部５０は、例えば、第一安定ソート部５１、第一キー公開ソート部５２、第二安定ソート部５３及び第二キー公開ソート部５４を含む。
【００６２】
以下、図４を参照して、第三実施形態の非減少列判定方法を説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００６３】
ステップＳ４０において、秘匿化部４０は、i=0,…,m-1について、集合Piの各要素が0以上n未満であるとして、ベクトルti,i+1を次式によりベクトルt'i,i+1へ変換して秘匿化した暗号文〔t'i,i+1〕を生成する。
【数１１】
2016056502.tif 000013
【００６４】
また同様に、ベクトルbi,i+1を次式によりベクトルb'i,i+1へ変換して秘匿化した暗号文〔b'i,i+1〕を生成する。
【数１２】
2016056502.tif 000014
【００６５】
以下に、ベクトルt'i,i+1とb'i,i+1の具体例を示す。例えば、集合P0,P1,…,P4が以下であるとする。
P0={0,3,7,8,10},
P1={2,5,8,9},
P2={2,4,8},
P3={0,4,7,9},
P4={0,6,7}
【００６６】
n=12とすると、ベクトルt’i,i+1とb'i,i+1は以下のようになる。
t’0,1=b’0,1=(1,0,0,1,0,0,0,1,1,0,1,0),
t’1,2=b’1,2=(0,0,1,0,0,1,0,0,1,1,0,0),
t’2,3=b’2,3=(0,0,1,0,1,0,0,0,1,0,0,0),
t’3,4=b’3,4=(1,0,0,0,1,0,0,1,0,1,0,0),
t’4,5=b’4,5=(1,0,0,0,0,0,1,1,0,0,0,0)
【００６７】
ステップＳ５０ａにおいて、併合部５０は、0≦i<j<k≦mを満たす秘匿文（〔t'i,j〕,〔b'i,j〕）と秘匿文（〔t'j,k〕,〔b'j,k〕）を選択し、ステップＳ５１〜Ｓ５４の処理により、秘匿文（〔t'i,j〕,〔b'i,j〕）と秘匿文（〔t'j,k〕,〔b'j,k〕）とを併合して秘匿文(〔t'i,k〕,〔b'i,k〕)を生成する。併合部５０は、これを再帰的に繰り返すことで、秘匿文〔t'0,1〕,…,〔t'm-1,m〕を併合した秘匿文〔t'0,m〕と、秘匿文〔b'0,1〕,…,〔b'm-1,m〕を併合した秘匿文〔b'0,m〕とを生成する。
【００６８】
ステップＳ５１において、第一安定ソート部５１は、秘匿文〔b'i,j〕と秘匿文〔t'j,k〕の各要素を交互に配列して秘匿文〔a〕を生成する。すなわち、h=0,…,n-1について、次式により秘匿文〔a〕を生成する。
【数１３】
2016056502.tif 000015
【００６９】
そして、第一安定ソート部５１は、(0,1)nは0と1を繰り返した長さ2nのベクトルとし、¬〔a〕をキーとして(〔(0,1)n〕,〔a〕,〔(0,…,2n-1)〕)を安定ソートした秘匿文(〔f'〕,〔a'〕,〔p〕)を生成する。すなわち、次式に示す安定ソートを実行する。
【数１４】
2016056502.tif 000016
【００７０】
ステップＳ５２において、第一キー公開ソート部５２は、h=0,…,n-1について、次式により秘匿文〔m〕を生成する。
【数１５】
2016056502.tif 000017
【００７１】
続いて、第一キー公開ソート部５２は、秘匿文〔p〕をキーとして秘匿文〔m〕をキー公開ソートした秘匿文〔m'〕を生成する。すなわち、次式に示すキー公開ソートを実行する。
【数１６】
2016056502.tif 000018
【００７２】
ステップＳ５３において、第二安定ソート部５３は、秘匿文〔m'〕の各要素を交互に分解し、秘匿文〔m0〕,〔m1〕を生成する。すなわち、h=0,…,n-1について、次式により秘匿文〔m0〕,〔m1〕を生成する。
【数１７】
2016056502.tif 000019
【００７３】
続いて、第二安定ソート部５３は、¬〔t'i,j〕をキーとして(〔t'i,j〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔t"0〕,〔p0〕)を生成し、¬〔b'i,j〕をキーとして秘匿文〔m0〕を安定ソートした秘匿文〔m"0〕を生成し、¬〔b'j,k〕をキーとして(〔b'j,k〕,〔(0,…,n-1)〕)を安定ソートした秘匿文(〔b"1〕,〔p1〕)を生成し、¬〔t'j,k〕をキーとして秘匿文〔m1〕を安定ソートした秘匿文〔m"1〕を生成する。すなわち、次式に示す四つの安定ソートを実行する。
【数１８】
2016056502.tif 000020
【００７４】
ステップＳ５４において、第二キー公開ソート部５４は、次式により秘匿文〔t"〕,〔b"〕を生成する。
【数１９】
2016056502.tif 000021
【００７５】
続いて、第二キー公開ソート部５４は、秘匿文〔p0〕をキーとして秘匿文〔t"〕をキー公開ソートした秘匿文〔t'i,k〕を生成し、秘匿文〔p1〕をキーとして秘匿文〔b"〕をキー公開ソートした秘匿文〔b'i,k〕を生成する。すなわち、次式に示す二つのキー公開ソートを実行する。
【数２０】
2016056502.tif 000022
【００７６】
ステップＳ５０ｂにおいて、併合部５０は、秘匿文〔t'0,1〕,…,〔t'm-1,m〕と秘匿文〔b'0,1〕,…,〔b'm-1,m〕がすべて併合されたか否かを判断する。すなわち、秘匿文（〔t'0,m〕,〔b'0,m〕）が生成されたか否かを確認する。併合が完了していなければステップＳ５０aへ処理を戻す。併合が完了していればステップＳ６０へ処理を進める。
【００７７】
ステップＳ６０において、判定部６０は、秘匿文〔t'0,m〕を用いて、〔t'0,m[0]〕∨〔t'0,m[1]〕∨…∨〔t'0,m[m-1]〕を計算し、その計算結果を判定結果として出力する。
【００７８】
第三実施形態の併合部５０において、上述の第二実施形態の考え方を適用し、秘匿文(〔t'i,k〕,〔b'i,k〕)を生成する際に、次式を満たすようにi,j,kを設定して秘匿文（〔t'i,j〕,〔b'i,j〕）と秘匿文（〔t'j,k〕,〔b'j,k〕）を選択するように構成してもよい。
【数２１】
2016056502.tif 000023
【００７９】
＜発明の効果＞
この発明の非減少列判定技術によれば、m個の集合から一つずつ値を選んだ非減少列の存在の判定をO(log m)段の再帰手続きで実現できる。特に秘密計算で実現する場合には、各再帰手続きがO(1)段の計算で実現できるため、全体の処理がO(log m)段で実現できる。
【００８０】
＜発明のポイント＞
この発明では、m個の集合から一つずつ値を選んだ非減少列の存在の判定を行う際に、分割統治により再帰的に非減少列の集合を構築することで、O(log m)段で非減少列の存在の判定を行う。分割統治を行う際には、すべての非減少列を保持する代わりに効率よく計算可能なよい性質を持つ非減少列の集合のみを維持して計算を行い、非減少列の集合の併合を秘密計算でO(1)段で実現している。その結果、全体の計算がO(log m)段の秘密計算で実現できている。
【００８１】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８２】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００８３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2016056502.tif 000026
【図２】
2016056502.tif 000027
【図３】
2016056502.tif 000028
【図４】
2016056502.tif 000029
【手続補正書】
【提出日】平成29年3月28日(2017.3.28)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
すると、(λ=0,x=0,y=0)が発見されるため、X=(0)、Y=(0)である。したがって、ベクトル(t0,5,b0,5)は以下のようになる。
t0,5=(t0,2[0])=(0)
b0,5=(b2,5[0])=(6)
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2016056502.tif 000030
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2016056502.tif 000031
【国際調査報告】
2016056502.tif 000032
2016056502.tif 000033
2016056502.tif 000034
2016056502.tif 000035