(57)【特許請求の範囲】
【請求項１】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体の乗法群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理方法であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成し、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信し、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成し、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信し、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る
ことを特徴とするデータベース情報処理方法。
【請求項２】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体上のだ円曲線の群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理方法であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成し、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信し、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成し、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信し、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る
ことを特徴とするデータベース情報処理方法。
【請求項３】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、p2qの剰余群の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理方法であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成し、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信し、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成し、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信し、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る
ことを特徴とするデータベース情報処理方法。
【請求項４】
平方剰余問題を前記請求項１ないし３のいずれかに記載のアルゴリズムの問題として定式化させて実現するデータベース情報処理方法。
【請求項５】
Diffie-Hellman判定問題を前記請求項１ないし３のいずれかに記載のアルゴリズムの問題として定式化させて実現するデータベース情報処理方法。
【請求項６】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体の乗法群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理装置であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアを生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを生成する演算手段を、ユーザ側端末装置は有し、
データベース管理者側端末装置に問い合わせを送信するデータ送受信手段を、ユーザ側端末装置は有し、
データ送受信手段で受信した問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成する演算手段を、データベース管理者側端末装置は有し、
問い合わせの回答をユーザ側端末装置に送信するデータ送受信手段を、データベース管理者側端末装置は有し、
データ送受信手段で受信した問い合わせの回答を、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る演算手段を、ユーザ側端末装置は有する
ことを特徴とするプライベートインフォメーションリトリーバル装置。
【請求項７】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体上のだ円曲線の群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理装置であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアを生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを生成する演算手段を、ユーザ側端末装置は有し、
データベース管理者側端末装置に問い合わせを送信するデータ送受信手段を、ユーザ側端末装置は有し、
データ送受信手段で受信した問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成する演算手段を、データベース管理者側端末装置は有し、
問い合わせの回答をユーザ側端末装置に送信するデータ送受信手段を、データベース管理者側端末装置は有し、
データ送受信手段で受信した問い合わせの回答を、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る演算手段を、ユーザ側端末装置は有する
ことを特徴とするプライベートインフォメーションリトリーバル装置。
【請求項８】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、p2qの剰余群の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理装置であって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアを生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを生成する演算手段を、ユーザ側端末装置は有し、
データベース管理者側端末装置に問い合わせを送信するデータ送受信手段を、ユーザ側端末装置は有し、
データ送受信手段で受信した問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成する演算手段を、データベース管理者側端末装置は有し、
問い合わせの回答をユーザ側端末装置に送信するデータ送受信手段を、データベース管理者側端末装置は有し、
データ送受信手段で受信した問い合わせの回答を、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得る演算手段を、ユーザ側端末装置は有する
ことを特徴とするプライベートインフォメーションリトリーバル装置。
【請求項９】
平方剰余問題を前記請求項６ないし８のいずれかに記載のアルゴリズムの問題として定式化させて実現するプライベートインフォメーションリトリーバル装置。
【請求項１０】
Diffie-Hellman判定問題を前記請求項６ないし８のいずれかに記載のアルゴリズムの問題として定式化させて実現するプライベートインフォメーションリトリーバル装置。
【請求項１１】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体の乗法群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理を行なうプログラムであって、
群のある元が部分群に属するか否かを示す｛０，１｝ｋの入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成するステップと、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信するステップと、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成するステップと、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信するステップと、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得るステップともつ
ことを特徴とするプライベートインフォメーションリトリーバルプログラム。
【請求項１２】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、有限体上のだ円曲線の群を用いた直積の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理を行なうプログラムであって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成するステップと、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信するステップと、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成するステップと、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信するステップと、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得るステップともつ
ことを特徴とするプライベートインフォメーションリトリーバルプログラム。
【請求項１３】
記録手段及び演算手段並びにデータ送受信手段を備えたユーザ側端末装置と、記録手段及び演算手段並びに及びデータ送受信手段を備えたデータベース管理者側端末装置とを有し、その間でデータを送受信可能な情報処理システムにおいて、
データベース管理者側端末装置の記録手段に備わるデータベースについて、p2qの剰余群の部分群に関して、ある元がある群の部分群に属するかどうかを判定するアルゴリズムのメンバーシップ問題を定義、一般化した上で、該問題の困難性がデータ秘匿の安全性と計算量的に等価であることを利用し、ユーザ側端末装置で選択したデータベース中の特定のビット列に関する情報を、データベース管理者側端末装置に伝達することなく入手するデータベースの情報処理を行なうプログラムであって、
群のある元が部分群に属するか否かを示す｛０，１｝k の入力によって、セキュリティーパラメータのビット数ｋによって全ての元を表現可能でありデータベース管理者側端末装置及びユーザ側端末装置で共有される有限群と、その部分群とのペアと、その部分群メンバーシップ問題のための多項式時間アルゴリズムを提供し秘密情報として保管するトラップドアをユーザ側端末装置の演算手段によって生成すると共に、ランダムテープを使用して、１個の元を部分群に属さない元から選び残りの元を部分群から選びぶことによって、データベース管理者側端末装置への問い合わせを、ユーザ側端末装置の演算手段によって生成するステップと、
ユーザ側端末装置のデータ送受信手段によって、ユーザ側端末装置からデータベース管理者側端末装置にその問い合わせを送信するステップと、
データベース管理者側端末装置のデータ送受信手段で問い合わせを受信したデータベース管理者側端末装置では、その演算手段によって、問い合わせに含まれる元が部分群に属していたか属していなかったかによらず、問い合わせを用いてデータベースから、ターゲットに関する情報を含む回答を生成するステップと、
データベース管理者側端末装置のデータ送受信手段によって、データベース管理者側端末装置からユーザ側端末装置に、その問い合わせの回答を送信するステップと、
問い合わせの回答を受信したユーザ側端末装置では、その演算手段によって、既知である部分群メンバーシップ問題に関するトラップドアを用い、回答に含まれる各元が部分群に属すか否かをセキュリティーパラメータの多項式時間で決定して、所望のデータを得るステップともつ
ことを特徴とするプライベートインフォメーションリトリーバルプログラム。
【請求項１４】
平方剰余問題を前記請求項１１ないし１３のいずれかに記載のアルゴリズムの問題として定式化させて実現するプライベートインフォメーションリトリーバルプログラム。
【請求項１５】
Diffie-Hellman判定問題を前記請求項１１ないし１３のいずれかに記載のアルゴリズムの問題として定式化させて実現するプライベートインフォメーションリトリーバルプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、部分群メンバーシップ問題を定義、一般化した上で、その問題を用いたデータベース情報処理方法及びプライベートインフォメーションリトリーバル装置並びにプログラムに関する。
【０００２】
【従来の技術】
本発明におけるデータベースの情報処理方法や、プライベートインフォメーションリトリーバル装置、そのソフトウェアにおいて、用いるプロトコルは、システムの安全性を左右し、その重要性は極めて高い。
【０００３】
データベースを管理する管理者（以下、ＤＢと呼ぶ。）とユーザ（以下、Ｕと呼ぶ。）や、その他の第三者間でいかにデータベースの情報を保護し、円滑に管理できるかは、プロトコルの性能によるところも大きい。例えば、データベースはビット列 X=x0x1・・・xn-1によって構成されるとすると、プライベートインフォメーションリトリーバルのプロトコルの大きな目的は、Ｕが自らの選択したｉ番目のビットxiを、ＤＢにｉについて何らの情報も渡さずに、Ｕが得ることであり、この場合、ＤＢはデータベースの管理をしながらもその情報にアクセスできない。
【０００４】
従来においても様々なシステムが提案されており、例えば、B.Chor,O.Golsreich,E.Kushilivitz and M.Sudenらによるシステム（"Private information retrieval",IEEE Symp on Foundations of Computer Science(FOCS),1995,pp41-50.）は、情報理論的な安全性を達成してはいるが、同一のデータベースが複数のデータベース管理者によって管理されていなければならない上にデータベース同士が結託しないという仮定が必要である。また、同じく複数のデータベース管理者を必要とし、ただし計算量安全性な安全性に妥協する事により通信の効率を上げたシステム（B.Chor and N.Gilboa,"Computationally private information retrieval"ACM Symp.Theory of Computing(STOC),(1997),pp304-313.）もある。更に、平方剰余の難しさを安全性の根拠とし、１人のデータベース管理者とのプロトコルで計算量理論的に安全なシステム（E.Kushilevitz and R.Ostrovsky,"Replication is not needed:Single database,computationally private information retrieval",IEEE Symp on Foundations of Computer Science(FOCS)）等がある。
【０００５】
【発明が解決しようとする課題】
しかしながら、これら従来のデータベース情報処理方法では、必要な条件が多く、利用可能な理論的問題も非常に限られていた。本発明では、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題という、より一般化された問題を利用したデータベース情報処理方法及びプライベートインフォメーションリトリーバル装置並びにそのプログラム提供することを目的としている。
【０００６】
【課題を解決するための手段】
上記目的を達成するために本発明においてまず、有限体の乗法群または有限体上のだ円曲線の群またはp2qの剰余群上において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題を定義し、平方剰余問題やDiffie-Hellman判定問題を上記アルゴリズムの問題として定式化させてデータベース情報処理方法及びプライベートインフォメーションリトリーバル装置並びにそのプログラムを提供した。
【０００７】
またこれら２つの問題（平方剰余問題やDiffie-Hellman判定問題）以外にも、上記アルゴリズムの問題として定式化できるものはいくつも存在すると考えられ、それらのいずれも適用可能な柔軟性のあるデータベース情報処理方法を提供できる。
【０００８】
さらに、本発明では、同様の手法によって、プライベートインフォメーションリトリーバル装置や、そのプログラムを提供することもできる。
【０００９】
【発明の実施の形態】
以下に、本発明の一実施例として、プライベートインフォメーションリトリーバル装置を示すが、本発明の利用は該装置に限られることなく、データベース管理者にデータを秘匿する必要のない一般的なデータベース情報処理方法として用いることも出来るし、また、プライベートインフォメーションリトリーバルを実現するプログラムとして提供してもよい。
【００１０】
具体的な実施の形態に入る前にまずその前提となる用語の定義などを、以下に説明する。本発明において利用する群としては有限体の乗法群または有限体上の楕円曲線の群またはp2qの剰余群という３つの群を考えるものとする。また、このシステムはＵとデータベース管理者（ＤＢ）とのプロトコルである。
【００１１】
セキュリティーパラメータを自然数ｋとし、全ての元がｋビットで表現されるような有限群をＧとし、ＨをＧの部分群とする。また、S=G＼Hとする。ここでＧの群演算はｋに関して多項式時間で実行できるとする。ここで部分群Ｈのメンバーシップ（Ｇの元ｘが部分群Ｈの元であるかどうか）に関する述語Memを次のように定義する。（式１）
【数１】
0004392489.tif 000002
【００１２】
また、確率的多項式時間アルゴリズムIは｛0,1｝kの入力に対して、群Ｇ、部分群Ｈ、及びトラップドアを出力するとすると、部分群メンバーシップ問題とは｛0,1｝kがIに入力されたとき、出力された（Ｇ、Ｈ）と、コイン投げに従ってＳまたはＨからランダムにそして一様に選ばれた元ｇに対してMem(G,H,g)を計算することである。もし述語Memをｋに関して多項式時間で１／２より無視できないほど大きな確率で計算するアルゴリズムが存在するとき、そのアルゴリズムは部分群メンバーシップ問題を解くという。
【００１３】
平方剰余問題の他にDiffie-Hellman決定問題も部分群メンバーシップ問題として定式化できる。以下にそのことを示す。（平方剰余問題）ｐ、ｑを素数とし、N=pq、G=(Z/(N))*とする。Ｈは、
【数２】
0004392489.tif 000003
つまり平方剰余のなすＧの部分群とする。平方剰余問題とは与えられたg∈Gに対してｇがＨに属しているかどうかを決定するアルゴリズムの存在の有無のことである。入力｛0,1｝kに対してサイズがｋであるｐとｑに関する乗法群G=(Z/(N))*を出力するインスタンスジェネレータを考えることにより、平方剰余問題はＨに関する部分群メンバーシップ問題と考えることができる。
【００１４】
（Diffie-Hellman決定問題）Ｃを位数が素数ｐの巡回群とする。Diffie-Hellman決定問題とは与えられた４つ組(g1,h1,g2,h2)に対して、ある1≦a≦p-1(a∈Z)に対して、h1=g1aかつh2=g2aとなっているかどうかを決定する問題である。そうである場合には(g1,h1,g2,h2)はDiffie-Hellman４つ組といい、整数aはDiffie-Hellman決定問題のトラップドアとなる。群ＧをＣ×Ｃとする。(x,y)をＧの元のペアとする。ここでx=(g1,h2),y=(g2,h2)とする。(g1,h1,g2,h2)がDiffie-Hellman４つ組であるためにはｙがｘで生成されるＧの部分群＜ｘ＞に属することが必要十分である。従って、Ｃに関するDiffie-Hellman決定問題はG=C×C=＜g1＞×＜g1＞の部分群Ｈ＝＜ｘ＞のメンバーシップ問題と考えることができる。
【００１５】
ここから部分群メンバーシップ問題に基づくデータベース情報処理方法及び装置及びプログラムについての構成を図面も参照しながら説明する。図１に本発明の各ステップを示す。ユーザＵとデータベース管理者ＤＢとのプロトコルを図面化したものを図２に示す。
【００１６】
ステップ０（１０）において、初期設定（ユーザＵ（２１）によるＧ、Ｈ、トラップドアの生成、問い合わせQuery(i) (２３)を計算する。Ｕ（２１）は｛0,1｝kをIに入力して群と部分群のペア（Ｇ、Ｈ）とトラップドアを得る。全てのＧの元はサイズがｋである。ＧはＤＢ（２３）とＵ（２１）の両方で共有される。他方、Ｕ（２１）はトラップドアを秘密情報として保管する。ＸをＤＢ（２２）の管理するデータベースとする。X=x0x1・・・Xn-1と仮定する。更にn=t1(t,l∈N)と仮定する。Ｕ（２１）は問い合わせQuery(i)（２３）を彼のランダムテープを使用して計算する。Ｕ（２１）はそれを秘密にして保持する。
【００１７】
次いで、ステップ１（１１）において、ユーザＵ（２１）→ データベース管理者ＤＢ（２２）：Query(i)（２３）を送信する。Ｕ（２１）はxi-1(1≦i≦n)への問い合わせQuery(i)（２３）を次のように計算する。まずiのt-進展開を求める。i=α0と置く。t-進展開は以下のように計算される。
α0=α1t+β1 0≦α0＜tl-1 かつ 0≦β1＜t-1α1=α2t+β2 0≦α1＜tl-2 かつ 0≦β2＜t-1αl-1=αlt+βl 0≦αl-2＜t かつ 0≦βl-1＜t-10≦αl-1=βl＜t-1かつαl=0【００１７】このときiのt-進展開はβ1βl-1 β1である。全てのu(1≦u≦l)に対して、Ｕ（２１）はランダムにそして一様にt-1個の元
【数３】
0004392489.tif 000004
をＨから選ぶ。アトランダムに、そして一様に元
【数４】
0004392489.tif 000005
をS=G＼Hから選ぶ。
【００１８】
群の元の列Q(u)
【数５】
0004392489.tif 000006
を構成する。従ってQ(u)はＧの元の列で、βu番目の要素はS=G＼Hからランダムに選ばれて、他の要素はＨからランダムに選ばれている。そしてQ(1),Q(2), Q(l)がＸのi番目のデータxi-1に対する問い合わせQuery(i)（２３）である。
【００１９】
Ｕ（２１）はQuery(i)（２３）をＤＢ（２２）に送信する。Q(u)はｔ個のＧの元から構成されているので、Q(u)はｋ×ｔビットで表現される。よってQuery(i)（２３）はktlビットで表現される。
【００２０】
ステップ２（１２）において、ＤＢ（２２）はQuery(i)（２３）を受け取り、再帰的にＸ（２４）の子データベースを作成する。Ｘ（２４）は以下で与えられるtl-1×t行列とみなされる。
【数６】
0004392489.tif 000007
この行列をD(0,λ)と記す。
【００２１】
ここでλは[1,2, k]*における空語を示す。このときターゲットであるxi-1はD(0,λ)の(α1,β1)成分であることに注意する。これをTarget(D(0,λ)と書く。子データベース(D(u,s)(0≦u＜l-1 および s∈[1,2,・・・,k]u)とそのターゲットは再帰的に定義される。
【００２２】
D(u,s)とそのターゲットTarget(D(u,s))(0≦u＜l-1 および s∈[1,2,・・・,k]u)まで定義したと仮定しよう。データベースD(u,s)はtl-uビットで構成されているので、D(u,s)を下記のtl-u-1×t行列とみなす。
【数７】
0004392489.tif 000008
【００２３】
ｋ個のデータベースD(u+1,s1),D(u+1,s2), D(u+1,sk)を次のように構成する。ここでQ(u)はｔ個のＧの元g(u,1),g(u,2),・・・,g(u,t-1)で構成されていることに注意する。各v=0,1,・・・,tl-u-1-1に対して群の元gvを以下のように定義する。
【数８】
0004392489.tif 000009
ここでD(u,s)(v,w)はD(u,s)の(v,w)成分を表す。
【００２４】
各行v=0,1,・・・,tl-u-1-1に対してfD(u,s),vを以下のように定義する。
【数９】
0004392489.tif 000010
よってfD(u,s),v(0≦v≦tl-u-1はｋビットで表現される群の元である。この時、補題（Ｇを群、ＨをＧの部分群とする。g∈Gとh∈Hとに対して、gh∈Hであるための必要十分条件はg∈Hである）によりfD(u,s),v∈Hであることが必要十分である。ｒ番目の子データベースD(u+1,sr)(1≦r≦k)はビット
【数１０】
0004392489.tif 000011
からなる。
【００２５】
ＤＢ（２２）は以下のような行列方程式を持つ。
【数１１】
0004392489.tif 000012
ここでD(u+1,sr)は列ベクトルであり、fD(u,s),vは行ベクトルである。各D(u+1,sr)は長さtl-u-1のビット列である。我々はそれをtl-u-2×t行列と考える。各r∈[0,1,・・・,k]に対して、Target(D(u+1,sr))はD(u+1,sr)の(αu+1,βu+1)成分と定義される。
【００２６】
ステップ３（１３）では、データベース管理者ＤＢ（２２）はAnswer(Query(i))（２５）をユーザＵ（２１）に送信する。子データベースの構成の最後の段階でＤＢ（２２）はkt-1個の子データベースD(t-1,s)(s∈[1,2,・・・,k]t-1)を保有している。各D(t-1,s)はｔビット含む。D(t-1,s)は1×t行列と考えることができる。
【００２７】
各D(t-1,s)に対して、群の元A(s)を以下のようにして定義する。まず、
【数１２】
0004392489.tif 000013
と定義する。そして、
【数１３】
0004392489.tif 000014
と定義する。
【００２８】
A(s)=fD(t-1,s),0と置く。[1,2,・・・,k]t-1の各元ｓに対して、群の元A(s)はｋの長さのビット列である。A(s)(s∈[0,1,・・・,k]t-1がQuery(i)に対する返答Answer(Query(i))である。ＤＢはAnswer(Query(i))をＵに送信する。
【００２９】
さらに、ステップ４（１４）において、ユーザＵ（２１）はxi=Target(D(0,λ))を計算する。ＵはAnswer(Query(i))を受信して、ｋ、ｎに関して多項式時間でxi=Target(D(0,λ))を計算することができる。その計算方法と証明を以下に示す。その前にまず補題を一つあげておく。補題．Ｇを群、ＨをＧの部分群とする。g∈Gとh∈Hに対して、gh∈Hであるための必要十分条件はg∈hである。
【００３０】
Target(D(u+1,s1)),Target(D(u+1,s2)),・・・,Target(D(u+1,sk))が与えられているとする。全てのデータベースD(u,s)(0≦u≦l-2,s∈[1,2,・・・,k]uに対してＵはターゲットビットTarget(D(u+,s))をn,kに関して多項式時間で計算することができる。
【００３１】
Target(D(u+1,s1)),Target(D(u+1,s2)),・・・,Target(D(u+1,sk))が与えられているとする。ここでＵはＨの部分群メンバーシップ問題に関するトラップドアを保有していることに注意する。また、g(u,βu)∈s = G＼H 及び
【数１４】
0004392489.tif 000015
であることを知っている。
【００３２】
ここで問い合わせQ(u)は、
【数１５】
0004392489.tif 000016
で与えられた。βuはＵの秘密情報である。Target(D(u,s))はD(u,s)の（αu,βu）成分である。
ＤＢの計算
【数１６】
0004392489.tif 000017
により
【数１７】
0004392489.tif 000018
である。
【００３３】
補題と、
【数１８】
0004392489.tif 000019
より、
【数１９】
0004392489.tif 000020
であるための必要十分条件は（αu,βu）成分が０であること。更に、
【数２０】
0004392489.tif 000021
より、
【数２１】
0004392489.tif 000022
は、(D(u+1),s1)D(u+1,s2)・・・D(u+1,sk))のαu行である。
【００３４】
全てのｒ＝１，２，・・・,ｋに対して、データベースD(u+1,sr)のαu番目のビットは行列D(u+1,sr)の（αu+1,βu+1）成分である。D(u+1,sr)の（αu+1,βu+1)成分はTarget(D(u+1,sr))である。
【００３５】
ＵはTarget(D(u+1,s1)),Target(D(u+1,s2)),・・・,Target(D(u+1,sk))を知っているので、
【数２２】
0004392489.tif 000023
を計算することができる。
【数２３】
0004392489.tif 000024
を受け取った後Ｕは
【数２４】
0004392489.tif 000025
がＨに属するかどうか調べる。トラップドアを知っているのでメンバーシップを多項式時間で決定できる。従ってＵはTarget(D(u,s))をn,kに関して多項式時間で計算することができる。以上が本発明の実施の形態である。
【００３６】
【発明の効果】
本発明は、以上説明したように構成されているので、次に記載されるような効果を奏する。有限体の乗法群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用することによって、有限体の乗法群におけるデータベース情報処理方法として適用できる問題をより一般化させることができる。
【００３７】
有限体上のだ円曲線の群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用することによって、有限体上のだ円曲線の群におけるデータベース情報処理方法として適用できる問題をより一般化させることができる。
【００３８】
p2qの剰余群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用することによって、 の剰余群におけるデータベース情報処理方法として適用できる問題をより一般化させることができる。
【００３９】
平方剰余問題を前記アルゴリズムの問題として定式化させてデータベース情報処理方法を実現することにより、その安全性をその問題を解くための困難性と計算量的に等しくすることができる。
【００４０】
Diffie-Hellman判定問題を前記アルゴリズムの問題として定式化させてデータベース情報処理方法を実現することにより、その安全性をその問題を解くための困難性と計算量的に等しくすることができる。
【００４１】
有限体の乗法群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベース情報処理装置を構成することで、従来よりも一般化された問題を適用可能な装置を実現することができる。
【００４２】
有限体上のだ円曲線の群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベース情報処理装置を構成することで、従来よりも一般化された問題を適用可能な装置を実現することができる。
【００４３】
p2qの剰余群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベース情報処理装置を構成することで、従来よりも一般化された問題を適用可能な装置を実現することができる。
【００４４】
平方剰余問題を前記アルゴリズムの問題として定式化させてデータベース情報処理装置を構成したことにより、安全性がその問題を解くための困難性と計算量的に等価となるような装置を実現することができる。
【００４５】
Diffie-Hellman判定問題を前記アルゴリズムの問題として定式化させてデータベース情報処理装置を構成したことにより、安全性がその問題を解くための困難性と計算量的に等価となるような装置を実現することができる。
【００４６】
有限体の乗法群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベース情報処理プログラムを構成することで、従来のプログラムに比べ、適用する問題により柔軟性をもたせたソフトウェアを実現することができる。
【００４７】
有限体上のだ円曲線の群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベース情報処理プログラムを構成することで、従来のプログラムに比べ、適用する問題により柔軟性をもたせたソフトウェアを実現することができる。
【００４８】
p2qの剰余群において、ある元がある群の部分群に属するかどうかを判定するアルゴリズムの問題の難しさを利用したデータベースプログラムを構成することで、従来のプログラムに比べ、適用する問題により柔軟性をもたせたプログラムを実現させることができる。
【００４９】
平方剰余問題を前記アルゴリズムの問題として定式化させてデータベース情報処理ソフトウェアを構成することにより、安全性がその問題を解くための困難性と計算量的に等価であるようなプログラムを実現させることができる。
【００５０】
Diffie-Hellman判定問題を前記アルゴリズムの問題として定式化させてデータベース情報処理プログラムを構成することにより、安全性がその問題を解くための困難性と計算量的に等価であるようなプログラムを実現させることができる。
【図面の簡単な説明】
【図１】部分群メンバーシップ問題に基づくデータベース情報処理方法のステップを示す説明図
【図２】ユーザＵとデータベース管理者ＤＢとのプロトコルを示す説明図
【図１】
0004392489.tif 000026
【図２】
0004392489.tif 000027