JP2009271584A - 類似情報検索システムおよび類似情報検索プログラム - Google Patents

Abstract

【課題】管理者および第三者から秘匿された状態で検索情報の類似情報を効率良く検索する。
【解決手段】多項式点集合（Ｒ）を記憶する秘匿登録情報記憶手段ＣＤ２と、秘匿検索情報（Ｂ^＊）に含まれる検索数値（ｂ_１〜ｂ_ｍ−Ｌ）が各秘匿登録情報（Ｒ_１〜Ｒ_Ｎ）に含まれる数値（ａ_１〜ａ_ｒ）と同値であるか否かを判別する検索数値判別手段ＣＤ４と、多項式点部分集合（Ｑ_１ ^＊〜Ｑ_Ｎ ^＊）を演算する多項式点部分集合演算手段ＣＤ５と、多項式点部分集合（Ｑ_１ ^＊〜Ｑ_Ｎ ^＊）の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段ＣＤ６と、（ｃ−Ｌ）個以上の点を有する多項式点部分集合（Ｑ_１ ^＊〜Ｑ_Ｎ ^＊）に対応する各秘匿登録情報（Ｒ_１〜Ｒ_Ｎ）を演算することにより秘匿類似情報（Ｒ_Ａ）を演算する秘匿類似情報演算手段ＣＤ７とを備えた類似情報検索システム。
【選択図】図２

Description

本発明は、データベースの外部委託業者としての管理者および第三者から秘匿された状態で前記データベースから検索情報の類似情報を検索する類似情報検索システムおよび類似情報検索プログラムに関する。

従来より、データベースの管理業務について、前記データベースの構築等の技術的な問題や、前記データベースのメンテナンス費や管理費の削減等の経済的な問題から、外部委託をすることが行われている。前記データベースの外部委託のモデルについて、例えば、Database-as-a-Service（ＤＡＳ、ＤａａＳ）モデルが知られている。なお、本願明細書では、以降、「ＤＡＳモデル」と記載する。
前記ＤＡＳモデルは、前記データベースに情報（データ）を登録する（格納する）データ所有者としての「登録者」と、前記データベースから前記情報を検索する「検索者」と、前記データベースを管理する「管理者」とによって構成される。なお、前記登録者と前記検索者とは必ずしも同一人物である必要はなく、前記管理者は、いわゆる、外部委託業者であり、前記データベースの管理業務のみ委託されるものとする。

前記ＤＡＳモデルにおいて、例えば、前記情報が個人情報や機密情報等であった場合には、前記登録者および前記検索者以外の第三者、すなわち、前記登録者および前記検索者と前記データベースとの間の通信路上の第三者から、前記情報を秘匿できることが望ましい。また、この場合、外部委託業者である前記管理者からも、前記第三者と同様に、前記情報を秘匿できることが望ましい。
前記データベースに格納された前記情報を、前記第三者等から秘匿するための技術として、下記の非特許文献１〜４に記載の技術が知られている。

非特許文献１〜３には、ＤＡＳモデルにおいて、暗号化されたデータである暗号化データが格納されたデータベース、いわゆる、暗号化データベースについての技術が記載されている。非特許文献１〜３には、従来公知のＳＱＬ（Structured Query Language）を用いて問い合わせ等の操作が行われる、いわゆる、関係データベース（ＲＤＢ：Relational Database、リレーショナルデータベース）について、前記ＳＱＬにより、前記暗号化データに関する問い合わせ処理を行う技術について記載されている。
なお、非特許文献１〜３において、前記暗号化データは、属性等の情報が付与された、いわゆる、関係データである。このため、前記ＳＱＬによる問い合わせ処理は、前記属性に基づいて、効率的に行うことができる。例えば、所定の範囲内の属性の値を有する前記暗号化データのみを抽出するフィルタリング処理等を行うことができる。

また、非特許文献４には、ＤＡＳモデルとは直接関係ないが、複数のデータ提供者（provider、Bob）およびデータ検索者（querier、Alice）が存在する場合に、前記データ検索者の問い合わせた質問のデータ、いわゆる、クエリ（query）が、前記データ提供者が有するドキュメント（document）のデータベースに含まれるか否かを安全に問い合わせるために、ブルームフィルタ（Bloom filter）を用いた技術が記載されている。ここで、前記ブルームフィルタとは、前記データ提供者の鍵（Ｋ_Ｂ）で暗号化された前記ドキュメントおよび前記データ検索者の鍵（Ｋ_Ａ）で暗号化された前記クエリのことである。

非特許文献４では、まず、前記データ提供者が、前記データ提供者のブルームフィルタを公開する。次に、前記データ検索者が、前記データ検索者のブルームフィルタを、信頼できる第三者機関（trusted third party，Ted）に送信する。次に、前記第三者機関が、グループ暗号の原理に基づいて、前記データ検索者のブルームフィルタ、すなわち、前記データ検索者の鍵で暗号化された前記クエリを変換して、前記データ提供者の鍵で暗号化された前記クエリを出力する。そして、前記第三者機関が、前記データ提供者の鍵で暗号化された前記クエリと、公開された前記データ提供者のブルームフィルタとを照合することにより、前記クエリが、前記ドキュメントとして前記データベースに格納されているか否かを判別する。すなわち、非特許文献４には、前記クエリと、前記ドキュメントとを暗号化した状態で照合する技術が記載されている。

ハカン・ハジグィムィシ（Hakan Hacigumus）、他２名、"暗号化されたデータの検索について（Search on Encrypted Data）"、"アドバンシーズ・イン・インフォメーション・セキュリティ（第３３巻）セキュア・データ・マネジメント・イン・ディセントラライズド・システムズ（Advances in Information Security / Secure Data Management in Decentralized Systems (Edited by T. Yu and S. Jajodia)）"、（米国）、シュプリンガー（Springer）、２００７年５月１１日、ｐ．３８３−４２６ ハカン・ハジグィムィシ（Hakan Hacigumus）、他３名、"データベースサービスプロバイダモデルの暗号化されたデータに対するＳＱＬの実施について（Executing SQL over Encrypted Data in the Database-Service-Provider Model）"、"エスアイジーエムオーディ・カンファレンス（SIGMOD Conference（Edited by M. J. Franklin, B. Moon and A. Ailamaki））"、（米国）、エーシーエム（ACM）、２００２年、ｐ．２１６−２２７ 三浦志保、渡辺知恵美、"管理者に対しても機密を保持できる暗号化データベースの索引構成法"、「online」、２００７年、電子情報通信学会第１８回データ工学ワークショップ／第５回日本データベース学会年次大会（DEWS2007）、「２００８年３月２６日検索」、インターネット＜ＵＲＬ：http://www.ieice.org/iss/de/DEWS/DEWS2007/pdf/e7-8.pdf＞ スティーブン・エム・ベロビン（Steven M. Bellovin）、他１名、"暗号化されたブルームフィルタを用いて秘匿性が高められた検索について（Privacy-Enhanced Searches Using Encrypted Bloom Filters）"、（米国）、エーティアンドティ（AT&T）、２００４年３月２９日 エスコ・ウッコネン（Esko Ukkonen）、"ｑ−ｇｒａｍおよび最大の共通文字列集合に関する類似文字列照合について（Approximate string matching with q-grams and maximal matches）"、セオレシカル・コンピュータ・サイエンス・９２（Theoretical Computer Science 92）、（米国）、エルシビアー（Elsevier）、１９９２年、ｐ．１９１−２１１ 今井秀樹著、「符号理論」、社団法人電子情報通信学会、１９９０年、ｐ．４７−５４，１５５−１６０，１６９−１７４，１７９−１８０ アリ・ジュエルズ（Ari Juels）、他１名、"ファジーボールトについて（A Fuzzy Vault Scheme）"、「online」、２００６年、デザインズ・コーズ・アンド・クリプトグラフィ（Designs, Codes and Cryptography）、「２００８年４月１日検索」、インターネット＜ＵＲＬ：http://www.rsa.com/rsalabs/staff/bios/ajuels/publications/fuzzy-vault/fuzzy_vault.pdf＞ 大貫泰紀、高橋佑介、「指紋がキーとなる金庫 "Indexed Fuzzy Vault" の開発」、「online」、２００８年２月１４日、東海大学、「２００８年３月７日検索」、インターネット＜ＵＲＬ：http://www.cs.dm.u-tokai.ac.jp/DM2007/A1-Kikuchi2.doc＞ 權娟大、他２名、"ＧＧＤＢ：糖鎖遺伝子データベース検索システム（GGDB: A database system for glycogenes）"、"第２回 糖鎖科学コンソーシアムシンポジウム（The Second Symposium of Japanese Consortium for Glycobiology and Glycotechnology）"、日本糖鎖科学コンソーシアム、２００４年、ｐ．４２−４３ ルイ・ヤン（Rui Yang）、他２名、"木構造データの類似評価について（Similarity Evaluation on Tree-structured Data）"、"エスアイジーエムオーディー・カンファレンス（SIGMOD Conference）"、（米国）、エーシーエム（ACM）、２００５年、ｐ．７５４−７６５ カリン・カイリング（Karin Kailing）、他３名、"大規模データベースにおける階層データの効果的な類似検索について（Efficient Similarity Search for Hierarchical Data in Large Databases）"、（ギリシャ共和国）、エクステンディング・データベース・テクノロジー（Extending Database Technology）、２００４年、ｐ．６７６−６９３ アポストロス・エヌ・パラドポウロス（Apostolos N. Papadopoulos）、他１名、"グラフのヒストグラムによる構造化された類似検索について（Structure-Based Similarity Search with Graph Histograms）"、（ギリシャ共和国）、"ディーイーエックスエー・ワークショップ（DEXA Workshop）"、１９９９年、ｐ．１７４−１７８

（従来技術の問題点）
前記ＤＡＳモデルにおいて、例えば、前記情報がＤＮＡ（Deoxyribonucleic acid、デオキシリボ核酸）の塩基配列情報（核酸配列情報）や、蛋白質のアミノ酸配列情報等の、いわゆる、遺伝子情報であった場合、前記データベースは、前記遺伝子情報が格納された遺伝子情報データベースとなる。なお、前記遺伝子情報データベースは、いわゆる、遺伝子解析の分野における研究機関等において利用されている。
ここで、前記遺伝子情報が、疾患等に関わる可能性がある遺伝子、いわゆる、候補遺伝子の情報を含む場合には、経済的・商業的・実用的な用途や価値を有する可能性があり、機密情報として取り扱われることがある。この場合、前記第三者および前記管理者から、前記遺伝子情報を秘匿できることが望ましい。

図９はＤＡＳモデルにおける遺伝子情報データベースに従来公知の暗号化データベースの技術を適用した場合の説明図である。
よって、前記遺伝子情報を秘匿するために、図９に示すように、前記非特許文献１〜３に記載された暗号化データベースの技術を適用することが考えられる。
しかしながら、前記非特許文献１〜３の技術では、前記暗号化データを暗号化する際に従来公知の暗号アルゴリズムを使用する場合には、前記登録者および前記検索者が、暗号化された前記関係データや前記問い合わせを生成するための鍵が必要になる。

このため、前記登録者および前記検索者の人数に応じて前記鍵の管理等の問題があった。すなわち、前記登録者および前記検索者の人数に比例して前記鍵の数が多くなるため、鍵管理の安全性（厳格性）やそれに伴う管理コスト等の問題があった。
また、前記非特許文献４の技術については、前記複数のデータ提供者およびデータ検索者と、信頼できる第三者機関とが存在する場合に適用される。すなわち、前記非特許文献４の技術は、前記第三者機関を介した前記各データ提供者と前記各データ検索者との直接通信、いわゆる、Ｐ２Ｐ（Peer to Peer，peer-to-peer）型の通信に用いられることが想定されている。このため、前記各データ提供者どうしで共有する前記遺伝子情報データベースを構築すること自体が想定されておらず、前記ＤＡＳモデルを適用できないという問題がある。また、仮に、前記各データ提供者のデータベースを前記遺伝子情報データベースと想定した場合でも、前記非特許文献１〜３と同様に、前記各データ提供者、前記各データ検索者、前記第三者機関が有する鍵について、前記鍵管理の問題があった。

また、前記遺伝子解析では、前記検索者が知得した遺伝子情報が業界内で既知であるか否かを判別するために、前記遺伝子情報に基づく検索情報（問い合わせ情報）から、前記遺伝子情報データベースに格納された遺伝子情報のうち、前記検索情報に類似する前記遺伝子情報である類似情報を検索する類似情報検索処理が頻繁に行われる。例えば、図９に示すように、前記遺伝子情報を塩基配列の文字列情報とした場合に、前記検索情報（「ＧＧＣＣＡＧＧＧＣＡＣＣ」）に対して、前記遺伝子情報データベースに格納された前記類似情報（「ＧＡＣＣＧＧＧＧＴＧＣＡ」）が出力される前記類似情報検索処理が頻繁に行われる。

しかしながら、前記非特許文献１〜３では、前記関係データベースに格納された暗号化データは、前記ＳＱＬによる問い合わせ処理に応じた前記属性等の情報が付加された関係データである。このため、前記類似情報検索処理のような類似文字列検索等が想定されておらず、暗号化された前記関係データのままでは効率良く前記類似情報を出力できないという問題があった。例えば、前記暗号化データの完全一致や属性一致による検索等しか行うことができないという問題があった。
また、前記非特許文献４の技術についても、前記類似情報検索処理のような類似文字列検索等が想定されておらず、前記類似情報であるか否かを判別するために、暗号化された前記ブルームフィルタを復号化してから照合する必要があるため、効率的に前記類似情報を出力できないという問題があった。

本発明は、前述の事情に鑑み、管理者および第三者から秘匿された状態で検索情報の類似情報を効率良く検索することを技術的課題とする。

前記技術的課題を解決するために、請求項１記載の発明の類似情報検索システムは、
登録対象の情報である登録情報を記憶する記憶装置と、
前記記憶装置と情報の送受信が可能に接続され、前記記憶装置に対して、前記登録情報を登録させる登録装置と、
前記記憶装置と情報の送受信が可能に接続され、前記記憶装置に対して、記憶された前記登録情報のうち、検索対象の情報である検索情報と同一または類似する前記登録情報である類似情報を検索させる検索装置と、
を有する類似情報検索システムであって、
自然数をそれぞれｃ，ｄ，ｋ，Ｌ，ｎ，ｍ，ｑ，ｒとし、前記検索情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であり、且つ、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌ，ｒ≧ｎがそれぞれ成立するものとした場合に、
前記登録装置は、
前記登録情報に基づいて、（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式を演算する多項式演算手段と、
前記登録情報に基づいて、前記登録情報を復元可能なｎ個の前記部分情報である登録部分情報を抽出する登録部分情報抽出手段と、
抽出されたｎ個の前記登録部分情報に基づいて、ｎ種類の数値である登録数値を要素とする集合である登録集合を演算する登録集合演算手段と、
前記登録数値が代入された前記多項式の数値である登録代入値を演算する登録代入値演算手段と、
前記登録数値以外の数値である（ｒ−ｎ）種類の擬似数値を演算する擬似数値演算手段と、
前記擬似数値が代入された前記多項式の数値以外の数値である擬似代入値を演算する擬似代入値演算手段と、
前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、前記擬似数値および前記擬似数値に対応する前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を演算することにより、前記登録情報が秘匿化された秘匿登録情報を演算する秘匿登録情報演算手段と、
演算された前記秘匿登録情報を、前記記憶装置に対して送信する秘匿登録情報送信手段と、
を有し、
前記記憶装置は、
前記秘匿登録情報送信手段により送信された前記秘匿登録情報を受信する秘匿登録情報受信手段と、
受信した前記秘匿登録情報を記憶する秘匿登録情報記憶手段と、
を有し、
前記検索装置は、
前記検索情報に基づいて、前記検索情報を復元可能なｍ個の前記部分情報である検索部分情報を抽出する検索部分情報抽出手段と、
抽出されたｍ個の前記検索部分情報に基づいて、ｍ種類の数値である検索数値を要素とする集合である検索集合を演算する検索集合演算手段と、
演算された前記検索集合を記憶する検索集合記憶手段と、
ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を演算することにより、前記検索情報が秘匿化された秘匿検索情報を演算する秘匿検索情報演算手段と、
演算された前記秘匿検索情報を、前記記憶装置に対して送信する秘匿検索情報送信手段と、
を有し、
前記記憶装置は、
前記秘匿検索情報送信手段により送信された前記秘匿検索情報を受信する秘匿検索情報受信手段と、
受信した前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段と、
演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段と、
（ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段と、
演算された前記秘匿類似情報を、前記検索装置に対して送信する秘匿類似情報送信手段と、
を有し、
前記検索装置は、
前記秘匿類似情報送信手段により送信された前記秘匿類似情報を受信する秘匿類似情報受信手段と、
記憶した前記検索集合に含まれる前記検索数値が、受信した前記各秘匿類似情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
前記検索数値と同値となる前記登録数値および前記擬似数値を抽出する数値抽出手段と、
抽出された前記登録数値および前記擬似数値がｃ個以上であるか否かを判別することにより、前記各秘匿類似情報が、前記検索情報に対する前記類似情報として復元可能であるか否かを判別する類似情報復元判別手段と、
抽出された前記登録数値および前記擬似数値がｃ個以上である場合に、前記登録数値および前記擬似数値に基づいて、前記多項式を演算して前記類似情報を復元する類似情報復元手段と、
を有する
ことを特徴とする。

請求項２に記載の発明は、請求項１に記載の類似情報検索システムにおいて、
前記自然数ｃ，ｋ，ｎについて、ｃ≧（ｎ＋ｋ）／２が成立するものとした場合に、
前記登録装置は、
前記登録情報に基づいて、（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元するために必要な前記多項式上の点が｛（ｎ＋ｋ）／２｝個以上となる前記多項式を演算する多項式演算手段と、
を有する
ことを特徴とする。

前記技術的課題を解決するために、請求項３記載の発明の類似情報検索システムは、
登録対象の情報を登録情報とし、
前記登録情報と同一または類似する情報を類似情報とし、
自然数をそれぞれｄ，ｋ，ｎ，ｑ，ｒとし、
前記登録情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記登録情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、ｒ≧ｎが成立するものとし、
前記登録情報に基づいて抽出された前記登録情報を復元可能なｎ個の前記部分情報を登録部分情報とし、
抽出されたｎ個の前記登録部分情報に基づいて演算されたｎ種類の数値である登録数値を要素とする集合を登録集合とし、
前記登録情報に基づいて演算された（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式に前記登録数値が代入されて演算された数値を登録代入値とし、
前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、
前記登録数値以外の数値である擬似数値および前記擬似数値に対応する擬似代入値であって、前記擬似数値が代入された前記多項式の数値以外の数値である前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、
ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を、前記登録情報が秘匿化された秘匿登録情報として記憶する秘匿登録情報記憶手段と、
検索対象の情報を検索情報とし、
自然数をそれぞれｃ，Ｌ，ｍとし、
前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であり、且つ、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌがそれぞれ成立するものとし、
前記検索情報のうちの前記操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記検索情報に基づいて抽出された前記検索情報を復元可能なｍ個の前記部分情報を検索部分情報とし、
抽出されたｍ個の前記検索部分情報に基づいて演算されたｍ種類の数値である検索数値を要素とする集合を検索集合とし、
ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を、前記検索情報が秘匿化された秘匿検索情報とした場合に、
前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段と、
演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段と、
（ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段と、
を備えたことを特徴とする。

前記技術的課題を解決するために、請求項４記載の発明の類似情報検索プログラムは、
コンピュータを、
登録対象の情報を登録情報とし、
前記登録情報と同一または類似する情報を類似情報とし、
自然数をそれぞれｄ，ｋ，ｎ，ｑ，ｒとし、
前記登録情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記登録情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、ｒ≧ｎが成立するものとし、
前記登録情報に基づいて抽出された前記登録情報を復元可能なｎ個の前記部分情報を登録部分情報とし、
抽出されたｎ個の前記登録部分情報に基づいて演算されたｎ種類の数値である登録数値を要素とする集合を登録集合とし、
前記登録情報に基づいて演算された（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式に前記登録数値が代入されて演算された数値を登録代入値とし、
前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、
前記登録数値以外の数値である擬似数値および前記擬似数値に対応する擬似代入値であって、前記擬似数値が代入された前記多項式の数値以外の数値である前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、
ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を、前記登録情報が秘匿化された秘匿登録情報として記憶する秘匿登録情報記憶手段、
検索対象の情報を検索情報とし、
自然数をそれぞれｃ，Ｌ，ｍとし、
前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であれば、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌがそれぞれ成立するものとし、
前記検索情報のうちの前記操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記検索情報に基づいて抽出された前記検索情報を復元可能なｍ個の前記部分情報を検索部分情報とし、
抽出されたｍ個の前記検索部分情報に基づいて演算されたｍ種類の数値である検索数値を要素とする集合を検索集合とし、
ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を、前記検索情報が秘匿化された秘匿検索情報とした場合に、
前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段、
前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段、
演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段、
（ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段、
として機能させることを特徴とする。

請求項１に記載の発明によれば、前記各装置間で送受信される各情報（登録情報、検索情報、類似情報）が秘匿化されているため、前記各装置のユーザ以外の第三者から前記各情報を秘匿することができる。また、請求項１に記載の発明によれば、前記記憶装置では、前記登録情報が前記秘匿登録情報として秘匿化されており、且つ、前記検索情報が前記秘匿検索情報として秘匿化されているため、前記記憶装置のユーザである管理者からも前記各情報を秘匿することができる。この結果、前記第三者および前記管理者から、前記各情報が秘匿された状態で、前記登録情報の所有者であって前記登録装置のユーザである登録者と、前記検索情報の知得者であって前記検索装置のユーザである検索者と、前記記憶装置の管理業務を委託された外部委託業者としての前記管理者とを有する前記ＤＡＳモデルを構成できる。

また、請求項１に記載の発明によれば、前記登録装置は、前記登録者ごとの鍵を使用しなくても、前記登録情報を秘匿化できると共に、前記登録装置は、前記検索者ごとの鍵を使用しなくても、前記検索情報を秘匿化できる。この結果、前記各装置との間で送受信される各情報（登録情報、検索情報、類似情報）が、前記鍵を使用せずに秘匿化でき、従来公知の前記暗号化データベースにおける鍵管理の安全性（厳格性）やそれに伴う管理コスト等の問題を解決することができる。
また、請求項１に記載の発明によれば、前記秘匿類似情報を検索する際に、前記秘匿検索情報に含まれる検索数値と、前記各秘匿登録情報に含まれる各数値とを照合するため、暗号化された登録情報や検索情報を復号化してから照合を行う場合に比べ、効率的に前記秘匿類似情報を検索できる。

請求項２に記載の発明によれば、｛（ｎ＋ｋ）／２｝個以上の前記登録多項式点が判明すれば前記多項式が復元できることが保証されており、且つ、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧（ｎ＋ｋ）／２，ｃ≧Ｌがそれぞれ成立する。このため、前記検索装置は、受信した前記各秘匿類似情報に含まれるｃ個以上の前記登録数値または前記擬似数値に、｛（ｎ＋ｋ）／２｝個以上の前記登録数値が含まれていれば、前記各秘匿類似情報から前記各類似情報を常に復元することができる。この結果、前記検索装置は、前記秘匿類似情報を復元する際に、抽出された前記登録数値および前記擬似数値がｃ個以上であるか否かを判別することにより、前記各秘匿類似情報が、前記検索情報に対する前記類似情報として復元可能であるか否かを適切に判別することができる。また、前記記憶装置は、前記秘匿類似情報を検索する際に、抽出された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別することにより、前記多項式点集合が、前記検索情報に対する前記類似情報として復元可能であるか否かを適切に判別することができる。

請求項３に記載の発明によれば、記憶した前記秘匿登録情報を、前記登録情報に復元されずに秘匿化されたままの状態で検索できる。また、検索対象としての前記検索情報も、前記秘匿検索情報として秘匿化されたままの状態で前記検索が実行できる。したがって、前記検索情報の知得者である検索者以外の第三者から前記各情報（登録情報、検索情報、類似情報）を秘匿することができると共に、前記類似情報検索システムの管理者からも前記各情報を秘匿することができる。
また、請求項３に記載の発明によれば、前記検索者ごとの鍵を使用しなくても、前記検索情報を秘匿化できる。この結果、従来公知の前記暗号化データベースにおける鍵管理の安全性（厳格性）やそれに伴う管理コスト等の問題を解決することができる。
また、請求項３に記載の発明によれば、前記秘匿類似情報を検索する際に、前記秘匿検索情報に含まれる検索数値と、前記各秘匿登録情報に含まれる各数値とを照合するため、暗号化された登録情報や検索情報を復号化してから照合を行う場合に比べ、効率的に前記秘匿類似情報を検索できる。

請求項４に記載の発明によれば、記憶した前記秘匿登録情報を、前記登録情報に復元されずに秘匿化されたままの状態で検索できる。また、検索対象としての前記検索情報も、前記秘匿検索情報として秘匿化されたままの状態で前記検索が実行できる。したがって、前記検索情報の知得者である検索者以外の第三者から前記各情報（登録情報、検索情報、類似情報）を秘匿することができると共に、前記類似情報検索システムの管理者からも前記各情報を秘匿することができる。
また、請求項４に記載の発明によれば、前記検索者ごとの鍵を使用しなくても、前記検索情報を秘匿化できる。この結果、従来公知の前記暗号化データベースにおける鍵管理の安全性（厳格性）やそれに伴う管理コスト等の問題を解決することができる。
また、請求項４に記載の発明によれば、前記秘匿類似情報を検索する際に、前記秘匿検索情報に含まれる検索数値と、前記各秘匿登録情報に含まれる各数値とを照合するため、暗号化された登録情報や検索情報を復号化してから照合を行う場合に比べ、効率的に前記秘匿類似情報を検索できる。

次に図面を参照しながら、本発明の実施の形態の具体例（以下、実施例と記載する）を説明するが、本発明は以下の実施例に限定されるものではない。
なお、以下の図面を使用した説明において、理解の容易のために説明に必要な部材以外の図示は適宜省略されている。

図１は本発明の実施例１の類似情報検索システムの全体説明図である。
図１において、本発明の実施例１の類似情報検索システムＳは、登録対象の情報（データ）である登録情報を記憶する記憶装置の一例としてのデータベースサーバ（類似情報検索装置）ＤＳを有する。また、前記類似情報検索システムＳは、通信回線の一例としてのインターネット１を介して前記データベースサーバＤＳと情報の送受信が可能に接続され、前記データベースサーバＤＳに対して、前記登録情報を登録させる（格納させる）登録装置の一例としての登録用クライアントパソコンＰＣａを有する。

さらに、前記類似情報検索システムＳは、前記インターネット１を介して前記データベースサーバＤＳと情報の送受信が可能に接続され、前記データベースサーバＤＳに対して、記憶された前記登録情報のうち、検索対象の情報である検索情報と同一または類似する前記登録情報である類似情報を検索させる検索装置の一例としての検索用クライアントパソコンＰＣｂを有する。
実施例１の前記データベースサーバＤＳおよび前記各クライアントパソコンＰＣａ，ＰＣｂは、コンピュータ本体Ｈ１、ディスプレイＨ２、入力装置であるキーボードＨ３、マウスＨ４、図示しないハードディスクドライブ、ＤＶＤ（Digital Versatile Disc）ドライブ等により構成されている。

（実施例１の制御部の説明）
図２は本発明の実施例１の類似情報検索システムを構成する各装置の機能をブロック図（機能ブロック図）で示した説明図である。
図２において、前記データベースサーバＤＳおよび前記各クライアントパソコンＰＣａ，ＰＣｂのコンピュータ本体Ｈ１は、外部との信号の入出力および入出力信号レベルの調節等を行うＩ／Ｏ（入出力インターフェース）、必要な起動処理を行うためのプログラムおよびデータ等が記憶されたＲＯＭ（リードオンリーメモリ、記録媒体）、必要なデータ及びプログラムを一時的に記憶するためのＲＡＭ（ランダムアクセスメモリ、記録媒体）、ＲＯＭ等に記憶された起動プログラムに応じた処理を行うＣＰＵ（中央演算処理装置）、ならびにクロック発振器等を有しており、前記ＲＯＭ及びＲＡＭ等に記憶されたプログラムを実行することにより種々の機能を実現することができる。
前記構成の前記データベースサーバＤＳおよび前記各クライアントパソコンＰＣａ，ＰＣｂは、前記ハードディスクやＲＯＭ等に記憶されたプログラムを実行することにより種々の機能を実現することができる。

（登録用クライアントパソコンＰＣａの制御部の説明）
前記登録用クライアントパソコンＰＣａのハードディスクドライブには、前記登録用クライアントパソコンＰＣａの基本動作を制御する基本ソフト（オペレーティングシステム）ＯＳや、アプリケーションプログラムとしての秘匿登録情報送信プログラムＡＰ１、その他の図示しないソフトウェアが記憶されている。

（秘匿登録情報送信プログラムＡＰ１）
前記秘匿登録情報送信プログラムＡＰ１は、下記の機能手段（プログラムモジュール）を有する。

図３は実施例１の登録画像の説明図である。
ＣＡ１：登録画像表示手段
登録画像表示手段ＣＡ１は、図３に示す、前記登録情報を前記データベースサーバＤＳに登録させるための登録画像２を前記ディスプレイＨ２に表示する。実施例１の前記登録画像２は、前記登録情報を入力するための登録情報入力部２ａと、入力された前記登録情報を前記データベースサーバＤＳに登録するための登録ボタン２ｂとを有する。なお、実施例１では、前記登録情報入力部２ａには、図３に示すように、文字列情報により構成された前記登録情報ｓ（例えば、塩基配列の文字列情報である「ＡＧＣＣＧＧＡＡＧＧＣＣ」）が入力される。

ＣＡ２：登録判別手段
登録判別手段ＣＡ２は、前記登録情報ｓを前記データベースサーバＤＳに登録するか否かを判別する。実施例１の前記登録判別手段ＣＡ２は、前記登録情報入力部２ａに前記登録情報ｓが入力されて前記登録ボタン２ｂが入力されたか否かを判別することにより、前記登録情報ｓを前記データベースサーバＤＳに登録するか否かを判別する。
ここで、実施例１の前記類似情報検索システムＳでは、類似文字列検索手法であるｑ−ｇｒａｍの技術と、生体認証やパスワードの復元等に利用されている曖昧照合法であるファジーボールト（Fuzzy Vault、Fuzzy Vault Scheme）の技術とを組み合わせることにより、前記登録情報ｓが秘匿化された状態で登録・検索等の各処理が実行される。

（ｑ−ｇｒａｍを用いた類似文字列検索手法について）
ここで、類似文字列検索手法とは、ある文字列に対して、文字の挿入・削除・置換の各編集操作の回数である編集距離が、所定の値以下になる文字列を類似文字列として検出する手法をいう。すなわち、２つの文字列を同一にするために必要な前記各編集操作の最小値である前記編集距離に基づいて、データベース内の全ての文字列から前記類似文字列を検索する手法をいう。
また、ｑ−ｇｒａｍとは、０を除いた自然数をｑとした場合に、元の文字列の長さｑとなる部分文字列のことをいう。例えば、元の文字列を「ＡＢＣＤＥＦＧ」とし、ｑ＝４とした場合、前記ｑ−ｇｒａｍは、「ＡＢＣＤ」，「ＢＣＤＥ」，「ＣＤＥＦ」，「ＤＥＦＧ」の４つである。

なお、０を除いた自然数をそれぞれｄ，ｎ，ｍとし、長さｎの第１の文字列と長さｍの第２の文字列との前記編集距離をｄとし、前記自然数ｎ，ｍのうちのいずれか大きい値をｍａｘ（ｎ，ｍ）とした場合に、前記第１の文字列と前記第２の文字列とは、少なくとも、｛ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１｝個の前記ｑ−ｇｒａｍを共通に持つことが保証されている（例えば、非特許文献１０参照）。
したがって、ｑ−ｇｒａｍを用いた類似文字列検索手法は、まず、前記文字列をｓ_ｑｇとした場合に、予め設定された前記自然数ｎ，ｍ，ｑ，ｄの値に基づいて、前記ｑ−ｇｒａｍの共有数の最小値（ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１）を演算し、前記文字列ｓ_ｑｇと、前記データベース内の各文字列との各共有数を演算することにより、共有数が前記最小値以下となる前記各文字列を前記類似文字列の候補から排除する、いわゆる、フィルタリング処理を実行する。そして、前記文字列ｓ_ｑｇと、前記類似文字列の候補となった前記各文字列との前記編集距離を実際に演算することにより、最終的な解である前記類似文字列を演算する、いわゆる、洗練化処理を実行する。

この結果、ｑ−ｇｒａｍを用いた類似文字列検索手法は、総当りの類似文字列検索手法に比べ、処理を高速化できる。すなわち、長さｎの第１の文字列と長さｍの第２の文字列との前記編集距離の計算について、計算量を評価するためのランダウの記号（ランダウの記法、Ｏ-記法）を用いた場合、総当りの類似文字列検索手法では、前記計算量がＯ（ｎｍ）時間となる。すなわち、ｎ＝ｍとした場合、Ｏ（ｎ^２）時間であるため、計算量がｎの二乗関数的に大きくなる。これに対して、前記ｑ−ｇｒａｍを用いた類似文字列検索手法では、前記計算量がＯ（ｎ＋ｍ）時間となる。このため、前記フィルタリング処理を高速化できる。すなわち、ｎ＝ｍとした場合、Ｏ（２ｎ）時間であるため、計算量がｎの線形関数的に大きくなり、計算量を低減できる。

（ファジーボールトについて）
また、ファジーボールトとは、誤り訂正符号を用いて、秘匿化された情報どうしの曖昧な照合を実行する手法である。ここで、誤り訂正符号とは、冗長性（redundancy）が付加された情報の集合としての符号であって、前記冗長性が前記情報に含まれる誤りの訂正に用いられる符号のことである。このため、前記誤り訂正符号であれば、例えば、送信中にノイズが混入した場合でも、前記冗長性に基づいて、前記ノイズが除去された前記情報を受信できる。
前記ファジーボールトでは、秘密情報を施錠する施錠処理と、施錠された前記秘密情報を開錠する開錠処理とが実行される。

まず、０を除いた自然数をそれぞれｋ，ｔ，ｐ，ｒとし、前記自然数ｐを位数とする有限体（finite field）をＦとし、前記有限体Ｆのｋ次拡大体をＦ^ｋとし、前記有限体Ｆのｔ次拡大体をＦ^ｔとし、前記有限体Ｆのｒ次拡大体をＦ^ｒとし、前記ｋ次拡大体Ｆ^ｋの部分体としての秘密情報をｓ_ｆｖとし（ｓ_ｆｖ∈Ｆ^ｋ）、前記ｔ次拡大体Ｆ^ｔの部分体としての第１の集合をＡとし（Ａ∈Ｆ^ｔ）、前記ｒ次拡大体Ｆ^ｒの部分体としての集合、いわゆる、ボールト（vault）をＲとし（Ｒ∈Ｆ^ｒ）、ｒ＞ｔとした場合に、前記秘密情報ｓ_ｆｖと、前記第１の集合Ａとに基づいて、前記ボールトＲを演算する前記施錠処理を実行する。
そして、前記ｔ次拡大体Ｆ^ｔの部分体としての第２の集合をＢとし（Ｂ∈Ｆ^ｔ）、前記第１の集合Ａと前記第２の集合Ｂとが十分近い場合、例えば、前記各集合Ａ，Ｂの各要素について、前記各要素の値が８割以上同一である場合に、前記ボールトＲと、前記第２の集合Ｂとに基づいて、前記秘密情報ｓ_ｆｖを演算する前記開錠処理を実行する。

なお、体（field）とは、加減乗除の四則演算が定義された集合であって、前記集合の要素である元どうしの前記四則演算が前記集合内で閉じている（演算結果が元として集合に含まれる）場合の前記集合のことをいう。また、有限体とは、前記集合の元の数（位数）が、有限個である体のことであり、前記有限体は、ガロア体（Galois field）とも呼ばれ、特に位数が素数の場合には素体（prime field）とも呼ばれる。また、拡大体とは、前記体を部分集合として含む体のことであり、例えば、実数体（実数全体の集合）は、有理数体（有理数全体の集合）の拡大体である。また、有限体のｋ次拡大体とは、加減乗除の四則演算が定義された、前記有限体の元を係数とする（ｋ−１）次以下の多項式を元とする集合（多項式集合）のことをいう。さらに、部分体とは、前記体の部分集合であり、前記体で定義されている前記四則演算が成立する前記部分集合のことをいう。
なお、体、有限体、拡大体、部分体等については、例えば、非特許文献６に記載されており、公知であるため、詳細な説明を省略する。

（ＲＳ符号を用いたファジーボールトについて）
前記ファジーボールトでは、前記施錠処理および前記開錠処理を実行するために、前記誤り訂正符号として、誤り訂正能力が高いとされている、ＲＳ符号（Reed-Solomon符号、リード・ソロモン符号）が利用される場合がある。ここで、前記ＲＳ符号とは、前記情報がビットのブロックに分割されて表現され、前記ブロック単位の誤り訂正ができる符号である。なお、前記ブロックは、具体的には、前記有限体（Ｆ）のｋ次拡大体（Ｆ^ｋ）の元である前記多項式上の点である。すなわち、前記ＲＳ符号では、所定の数の前記多項式上の点を要素とする集合が、いわゆる、符号語としてビットで表現される。なお、ｎ個の前記多項式上の点からなる集合を前記符号語として表現する場合、前記ＲＳ符号は、特に、（ｎ，ｋ）符号（（ｎ，ｋ）ＲＳ符号）という。
なお、前記ＲＳ符号等については、例えば、非特許文献６等に記載されており、公知であるため、詳細な説明を省略する。

前記ＲＳ符号を用いたファジーボールトでは、前記施錠処理において、まず、ｎ＝ｔ，ｒ＞ｎとした場合に、ｋ個の要素からなる前記秘密情報ｓ_ｆｖ（ｓ_ｆｖ∈Ｆ^ｋ）と、ｎ個の要素からなる前記第１の集合Ａ（Ａ∈Ｆ^ｎ）とに基づいて、前記多項式上のｎ個の点からなる前記（ｎ，ｋ）符号を演算する。次に、前記（ｎ，ｋ）符号に対して、前記多項式上の点以外のランダムな（ｒ−ｎ）点からなる集合であるチャフ（chaff）を前記（ｎ，ｋ）符号に付与する。そして、前記（ｎ，ｋ）符号と、前記チャフとによって構成されたｒ個の点からなる集合が前記ボールトＲ（Ｒ∈Ｆ^ｒ）として出力される。
また、前記ＲＳ符号を用いたファジーボールトでは、前記開錠処理において、前記第１の集合Ａのｎ個以下の要素を有する前記第２の集合Ｂ（Ｂ∈Ｆ^ｔ）と、ｒ個の点からなる前記ボールトＲとに基づいて、前記多項式を復元することにより、前記秘密情報ｓ_ｆｖを演算する。

なお、前記ＲＳ符号では、前記（ｎ，ｋ）符号における（ｎ−ｋ）／２個以下の点の誤りを訂正できることが保証されている（例えば、非特許文献６、７参照）。すなわち、前記（ｎ，ｋ）符号における｛（ｎ＋ｋ）／２｝個以上の点が判明すれば前記多項式の復元に成功することが知られている（ｎ−｛（ｎ−ｋ）／２｝＝（ｎ＋ｋ）／２）。この結果、前記ＲＳ符号を用いたファジーボールトでは、前記各集合Ａ，Ｂの各要素について、｛（ｎ＋ｋ）／２｝個以上の要素が同一である場合には、前記多項式が復元でき、前記秘密情報ｓ_ｆｖを演算できることが保証されている。
したがって、前記ＲＳ符号を用いたファジーボールトでは、前記チャフを含む前記ボールトＲから前記（ｎ，ｋ）符号を特定する問題と、前記（ｎ，ｋ）符号から前記多項式を復元する問題、いわゆる、多項式復元問題との困難性によって、前記秘密情報ｓ_ｆｖの秘匿化についての安全性が保証されている。
なお、前記ＲＳ符号を用いたファジーボールトについては、例えば、非特許文献７、８等に記載されており、公知であるため、詳細な説明を省略する。

ＣＡ３：多項式演算手段
多項式演算手段ＣＡ３は、前記登録情報ｓに基づいて、（ｋ−１）次元で１変数の多項式であって、前記登録情報ｓを復元するために必要な前記多項式上の点が｛（ｎ＋ｋ）／２｝個以上となる前記多項式を演算する。実施例１の前記多項式演算手段ＣＡ３は、前記多項式の変数をｘとし、前記多項式のｋ個の係数をｓ_０〜ｓ_ｋ−１とし、前記多項式をｆ（ｘ）として以下の式（１）に示すものとした場合、前記係数ｓ_０〜ｓ_ｋ−１を演算することにより、前記多項式ｆ（ｘ）を演算する。
ｆ（ｘ）＝ｓ_０＋ｓ_１ｘ＋ｓ_２ｘ^２＋…＋ｓ_ｋ−２ｘ^ｋ−２＋ｓ_ｋ−１ｘ^ｋ−１…（１）
すなわち、実施例１の前記多項式演算手段ＣＡ３は、前記登録情報ｓを前記秘密情報ｓ_ｆｖとみなして（ｓ＝ｓ_ｆｖ）、前記登録情報ｓに基づいて、前記ＲＳ符号を用いたファジーボールトにおける前記多項式ｆ（ｘ）の係数ｓ_０〜ｓ_ｋ−１を演算する。

実施例１の前記登録情報ｓは、具体的には、まず、前記登録情報ｓを前記文字列ｓ_ｑｇとみなすことにより（ｓ＝ｓ_ｆｖ＝ｓ_ｑｇ）、（ｋ−１）個の部分文字列を抽出する。ここで、前記登録情報ｓの長さ（文字数）を‖ｓ‖とした場合、（‖ｓ‖−ｑ＋１）個のｑ−ｇｒａｍが抽出されることが知られている（例えば、非特許文献６等参照）。すなわち、前記登録情報ｓからｎ個のｑ−ｇｒａｍが抽出されるとした場合には、ｑ＝‖ｓ‖−ｎ＋１が成立する。よって、前記部分文字列をｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}とした場合、長さ（‖ｓ‖−（ｋ−１）＋１）の前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}が抽出される。そして、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}を、前記有限体Ｆの元としての前記係数ｓ_０〜ｓ_ｋ−１（ｓ_０，ｓ_１，…，ｓ_ｋ−２，ｓ_ｋ−１∈Ｆ）に対応付けることにより、前記多項式ｆ（ｘ）を演算する。例えば、ｓ_ｋ−１＝１とし、且つ、予め設定された双方向関数の一例としての可逆関数により、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}を、前記有限体Ｆの元となる前記係数ｓ_０〜ｓ_ｋ−２に変換する。

ここで、可逆関数とは、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}から前記係数ｓ_０〜ｓ_ｋ−１に変換可能、且つ、前記係数ｓ_０〜ｓ_ｋ−１から前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}に変換可能な関数である。例えば、前記登録情報ｓを「ＡＧＣＣＧＧＡＡＧＧＣＣ」とし、ｋ＝１０とし、長さ４（１２−（１０−１）＋１＝４）の前記部分文字列ｓ_ｋ（１）を「ＡＧＣＣ」とし、ｓ_０＝５とした場合に、前記可逆関数とは、「ＡＧＣＣ」→５が成立する対応関係、いわゆる、写像（map）のことである。また、この場合、前記可逆関数をＴとし、前記可逆関数Ｔの逆関数をＴ^−１とし、前記部分文字列ｓ_ｋ（１）を入力した前記可逆関数Ｔの出力値をＴ（ｓ_ｋ（１））とし、前記係数ｓ_０を入力した前記逆関数Ｔ^−１の出力値をＴ^−１（ｓ_０）とした場合に、Ｔ（ｓ_ｋ（１））＝ｓ_０＝５、Ｔ^−１（ｓ_０）＝Ｔ^−１（５）＝ｓ_ｋ（１）が成立する。

なお、実施例１では、前記登録情報ｓのｑ−ｇｒａｍを抽出するために、前記自然数ｑの値が予め設定されている。よって、前記登録情報入力部２ａに前記登録情報ｓが入力された場合、前記自然数ｎの値が、ｎ＝‖ｓ‖−ｑ＋１として設定されている。また、実施例１では、前記登録情報ｓと前記検索情報との前記編集距離ｄについての最大値がｄ_ｍａｘ（ｄ≦ｄ_ｍａｘ）として予め設定されている。さらに、実施例１では、前記自然数（次元数）ｋの値が、以下の式（２）を前記自然数ｋについて解いた式（２）′により設定されている。
（ｎ＋ｋ）／２＝ｎ−（ｄ_ｍａｘ−１）ｑ−１ …（２）
ｋ＝ｎ−２（ｄ_ｍａｘ−１）ｑ−２ …（２）′

ＣＡ４：登録部分情報抽出手段
登録部分情報抽出手段ＣＡ４は、前記登録情報ｓに基づいて、前記登録情報ｓを復元可能なｎ個の部分情報である登録部分情報を抽出する。実施例１の前記登録部分情報抽出手段ＣＡ４は、前記登録情報ｓを前記文字列ｓ_ｑｇとみなすことにより（ｓ＝ｓ_ｆｖ＝ｓ_ｑｇ）、ｎ個の前記ｑ−ｇｒａｍを前記登録部分情報として抽出する。実施例１の前記登録部分情報抽出手段ＣＡ４は、前記登録部分情報をｓ_ｑ１〜ｓ_ｑｎとした場合に、前記多項式演算手段ＣＡ３と同様に、ｎ個（ｎ＝‖ｓ‖−ｑ＋１）の部分文字列である前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎを抽出する。例えば、ｑ＝４とした場合、前記登録情報ｓ（「ＡＧＣＣＧＧＡＡＧＧＣＣ」）の登録部分情報ｓ_ｑ１〜ｓ_ｑｎは、ｓ_ｑ１（「ＡＧＣＣ」），ｓ_ｑ２「ＧＣＣＧ」，…，ｓ_ｑｎ＝ｓ_ｑ９「ＧＧＣＣ」の９つである（ｎ＝１２−４＋１＝９）。
ＣＡ５：登録集合演算手段
登録集合演算手段ＣＡ５は、前記登録部分情報抽出手段ＣＡ４により抽出されたｎ個の前記登録部分情報に基づいて、ｎ種類の数値である登録数値を要素とする集合である登録集合を演算する。すなわち、実施例１の前記登録集合演算手段ＣＡ５は、前記ＲＳ符号を用いたファジーボールトにおける前記第１の集合Ａの一例としての前記登録集合Ａを演算する（Ａ∈Ｆ^ｎ）。

なお、実施例１の前記登録集合演算手段ＣＡ５は、予め設定された一方向関数、いわゆる、ハッシュ関数により、前記登録集合Ａを演算する。前記登録集合演算手段ＣＡ５は、具体的には、前記ハッシュ関数をＨとし、前記ハッシュ関数Ｈによる前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎの出力値をＨ（ｓ_ｑ１）〜Ｈ（ｓ_ｑｎ）とし、前記登録数値をａ_１〜ａ_ｎとした場合に（ａ_１，ａ_２，…，ａ_ｎ∈Ｆ）、Ｈ（ｓ_ｑ１）＝ａ_１，Ｈ（ｓ_ｑ２）＝ａ_２，…，Ｈ（ｓ_ｑｎ）＝ａ_ｎを演算することにより、前記登録集合Ａを演算する（Ａ＝（ａ_１，ａ_２，…，ａ_ｎ））。

ＣＡ６：登録代入値演算手段
登録代入値演算手段ＣＡ６は、前記登録数値ａ_１〜ａ_ｎが代入された前記多項式ｆ（ｘ）の数値である登録代入値を演算する。実施例１の前記登録代入値演算手段ＣＡ６は、前記式（１）について、ｘ＝ａ_１，ｘ＝ａ_２，…，ｘ＝ａ_ｎとした場合の前記多項式ｆ（ｘ）の値である前記登録代入値ｆ（ａ_１），ｆ（ａ_２），…，ｆ（ａ_ｎ）を演算する。
ＣＡ７：擬似数値演算手段
擬似数値演算手段ＣＡ７は、前記登録数値ａ_１〜ａ_ｎ以外の数値である（ｒ−ｎ）種類の擬似数値を演算する。実施例１の前記擬似数値演算手段ＣＡ７は、前記擬似数値をａ_ｎ＋１〜ａ_ｒとした場合に、前記有限体Ｆのｐ個の要素（元）のうち、前記登録数値ａ_１〜ａ_ｎ以外の（ｒ−ｎ）個の要素を抽出することにより、前記擬似数値ａ_ｎ＋１〜ａ_ｒを演算する（ａ_ｎ＋１，ａ_ｎ＋２，…，ａ_ｒ∈Ｆ）。

ＣＡ８：擬似代入値演算手段
擬似代入値演算手段ＣＡ８は、前記擬似数値が代入された前記多項式ｆ（ｘ）の数値以外の数値である擬似代入値を演算する。実施例１の前記擬似代入値演算手段ＣＡ８は、１からｒまで値をとる変数をｉ，ｊとし、前記擬似数値ａ_ｎ＋１〜ａ_ｒに対応する前記擬似代入値をｆ′（ａ_ｎ＋１）〜ｆ′（ａ_ｒ）とした場合に、ｆ′（ａ_ｉ）≠ｆ（ａ_ｉ）且つｆ′（ａ_ｉ）≠ｆ（ａ_ｊ）且つｆ′（ａ_ｉ）≠ｆ′（ａ_ｊ）となる前記擬似代入値をｆ′（ａ_ｎ＋１）〜ｆ′（ａ_ｒ）を演算する。

ＣＡ９：秘匿登録情報演算手段
秘匿登録情報演算手段ＣＡ９は、前記登録数値ａ_１〜ａ_ｎおよび前記登録数値ａ_１〜ａ_ｎに対応する前記登録代入値ｆ（ａ_１），ｆ（ａ_２），…，ｆ（ａ_ｎ）を一組とする前記多項式上の点を登録多項式点とし、前記擬似数値ａ_ｎ＋１〜ａ_ｒおよび前記擬似数値ａ_ｎ＋１〜ａ_ｒに対応する前記擬似代入値ｆ′（ａ_ｎ＋１）〜ｆ′（ａ_ｒ）を一組とする前記多項式以外の点を擬似多項式点とした場合に、ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を演算することにより、前記登録情報が秘匿化された秘匿登録情報を演算する。すなわち、実施例１の前記秘匿登録情報演算手段ＣＡ９は、前記ＲＳ符号を用いたファジーボールトにおける前記（ｎ，ｋ）符号の一例としての前記登録多項式点と、前記チャフの一例としての前記擬似多項式点とを有する前記ボールトＲの一例としての前記多項式点集合Ｒ（秘匿登録情報Ｒ）を演算する。

実施例１の前記秘匿登録情報演算手段ＣＡ９は、前記登録多項式点を（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））とし、前記擬似多項式点を（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））とした場合に、以下の式（３）に示す前記多項式点集合Ｒを演算する。
Ｒ＝（（ａ_１，ｆ（ａ_１）），
（ａ_２，ｆ（ａ_２）），…，
（ａ_ｎ，ｆ（ａ_ｎ）），
（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１）），
（ａ_ｎ＋２，ｆ′（ａ_ｎ＋２）），…，
（ａ_ｒ，ｆ′（ａ_ｒ））） …（３）
なお、実施例１の前記秘匿登録情報演算手段ＣＡ９では、前記秘匿登録情報Ｒは、前記式（３）に示す前記多項式点集合Ｒの各数値ａ_１〜ａ_ｒについて、昇順に並び替えられた状態で出力される（演算される）。

ＣＡ10：秘匿登録情報送信手段
秘匿登録情報送信手段ＣＡ10は、前記秘匿登録情報演算手段ＣＡ９により演算された前記秘匿登録情報Ｒを、前記データベースサーバＤＳに対して送信する。
ＣＡ11：終了判別手段
終了判別手段ＣＡ11は、前記秘匿登録情報送信プログラムＡＰ１を終了する入力がされたか否かを判別する。

（検索用クライアントパソコンＰＣｂの制御部の説明）
前記検索用クライアントパソコンＰＣｂのハードディスクドライブには、前記検索用クライアントパソコンＰＣｂの基本動作を制御する基本ソフト（オペレーティングシステム）ＯＳや、アプリケーションプログラムとしての秘匿検索情報送信プログラムＡＰ２、秘匿類似情報復元プログラムＡＰ３、その他の図示しないソフトウェアが記憶されている。

（秘匿検索情報送信プログラムＡＰ２）
前記秘匿検索情報送信プログラムＡＰ２は、下記の機能手段（プログラムモジュール）を有する。

図４は実施例１の登録画像の説明図である。
ＣＢ１：検索画像表示手段
検索画像表示手段ＣＢ１は、図４に示す、前記検索情報と同一または類似する前記類似情報を前記データベースサーバＤＳに検索させるための検索画像３を前記ディスプレイＨ２に表示する。実施例１の前記登録画像３は、前記検索情報をｔとし、前記類似情報をｔ′とした場合に、前記検索情報ｔ（例えば、「ＧＧＣＣＡＧＧＧＣＡＣＣ」）を入力するための検索情報入力部３ａと、入力された前記検索情報ｔの類似情報ｔ′を、秘匿化した状態で、前記データベースサーバＤＳに検索させる処理、いわゆる、秘匿類似情報検索処理を開始させるための検索開始ボタン３ｂと、検索結果としての前記類似情報ｔ′（例えば、「ＧＧＣＣＧＧＧＧＴＧＣＡ」等）を表示するための類似情報出力部３ｃとを有する。

ＣＢ２：検索判別手段
検索判別手段ＣＢ２は、前記データベースサーバＤＳに前記類似情報検索処理を開始させるか否かを判別する。実施例１の前記検索判別手段ＣＢ２は、前記検索情報入力部３ａに前記検索情報ｔが入力されて前記検索開始ボタン３ｂが入力されたか否かを判別することにより、前記データベースサーバＤＳに前記秘匿類似情報検索処理を開始させるか否かを判別する。
ＣＢ３：検索部分情報抽出手段
検索部分情報抽出手段ＣＢ３は、前記検索情報ｔに基づいて、前記検索情報ｔを復元可能なｍ個の前記部分情報である検索部分情報を抽出する。実施例１の前記検索部分情報抽出手段ＣＢ３は、前記検索情報ｔを前記文字列ｓ_ｑｇとみなすことにより（ｔ＝ｓ_ｑｇ）、ｍ個の前記ｑ−ｇｒａｍを前記検索部分情報として抽出する。実施例１の前記検索部分情報抽出手段ＣＢ３は、前記登録部分情報抽出手段ＣＡ４と同様に、前記検索部分情報をｔ_ｑ１〜ｔ_ｑｍとし、前記検索情報ｔの長さ（文字数）を‖ｔ‖とした場合に、ｍ個（ｍ＝‖ｔ‖−ｑ＋１）の部分文字列である前記検索部分情報ｔ_ｑ１〜ｔ_ｑｍを抽出する。例えば、ｑ＝４とした場合、前記検索情報ｔ（「ＧＧＣＣＡＧＧＧＣＡＣＣ」）の検索部分情報ｔ_ｑ１〜ｇ_ｑｍは、ｔ_ｑ１（「ＧＧＣＣ」），ｔ_ｑ２（「ＧＣＣＡ」），…，ｔ_ｑｍ＝ｔ_ｑ９（「ＣＡＣＣ」）の９つである（ｍ＝１２−４＋１＝９）。

ＣＢ４：検索集合演算手段
検索集合演算手段ＣＢ４は、前記検索部分情報抽出手段ＣＢ３により抽出されたｍ個の前記検索部分情報ｔ_ｑ１〜ｔ_ｑｍに基づいて、ｍ種類の数値である検索数値を要素とする集合である検索集合を演算する。すなわち、実施例１の前記検索集合演算手段ＣＢ４は、前記ＲＳ符号を用いたファジーボールトにおける前記第２の集合Ｂの一例としての前記検索集合Ｂを演算する（Ｂ∈Ｆ^ｍ）。
なお、実施例１の前記検索集合演算手段ＣＢ４は、前記ハッシュ関数Ｈにより、前記検索集合Ｂを演算する。前記検索集合演算手段ＣＢ４は、具体的には、前記ハッシュ関数Ｈによる前記検索部分情報ｔ_ｑ１〜ｔ_ｑｍの出力値をＨ（ｔ_ｑ１）〜Ｈ（ｔ_ｑｍ）とし、前記検索数値をｂ_１〜ｂ_ｍとした場合に（ｂ_１，ｂ_２，…，ｂ_ｍ∈Ｆ）、Ｈ（ｔ_ｑ１）＝ｂ_１，Ｈ（ｔ_ｑ２）＝ｂ_２，…，Ｈ（ｔ_ｑｍ）＝ｂ_ｍを演算することにより、前記検索集合Ｂを演算する（Ｂ＝（ｂ_１，ｂ_２，…，ｂ_ｍ））。なお、実施例１の前記検索集合演算手段ＣＢ４では、前記検索集合Ｂは、前記検索数値ｂ_１〜ｂ_ｍが、昇順に並び替えられた状態で出力される（演算される）。

ＣＢ５：検索集合記憶手段
検索集合記憶手段ＣＢ５は、前記検索集合演算手段ＣＢ４により演算された前記検索集合Ｂ（Ｂ＝（ｂ_１，ｂ_２，…，ｂ_ｍ））を記憶する。
ＣＢ６：秘匿検索情報演算手段
秘匿検索情報演算手段ＣＢ６は、自然数をＬとし、Ｌ＜ｍが成立するとした場合に、ｍ種類の前記検索数値ｂ_１〜ｂ_ｍのうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値（ｂ_１〜ｂ_ｍ）を要素とする前記検索集合Ｂの部分集合である検索部分集合を演算することにより、前記検索情報ｔが秘匿化された秘匿検索情報を演算する。実施例１の前記秘匿検索情報演算手段ＣＢ６は、前記検索部分集合をＢ^＊とした場合に、前記検索集合Ｂの検索数値ｂ_１〜ｂ_ｍからＬ種類の検索数値が除かれた、（ｍ−Ｌ）種類の前記検索数値（ｂ_１〜ｂ_ｍ）を要素とする前記検索部分集合（秘匿検索情報）Ｂ^＊を演算する。例えば、Ｌ＝２とし、変数ｉを１〜３およびｍ以外の数値とし、前記検索数値ｂ_１〜ｂ_ｍのうちのｂ_２およびｂ_ｉの２種類の数値が除かれた場合、（ｂ_１，０，ｂ_３，…，ｂ_ｉ−１，０，ｂ_ｉ＋１，…，ｂ_ｍ）→（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）＝Ｂ^＊を演算する。

ＣＢ７：秘匿検索情報送信手段
秘匿検索情報送信手段ＣＢ７は、前記秘匿検索情報演算手段ＣＢ６により演算された前記秘匿検索情報Ｂ^＊を、前記データベースサーバＤＳに対して送信する。
ＣＢ８：終了判別手段
終了判別手段ＣＢ８は、前記秘匿検索情報送信プログラムＡＰ２を終了する入力がされたか否かを判別する。

（秘匿類似情報復元プログラムＡＰ３）
また、前記秘匿類似情報復元プログラムＡＰ３は、下記の機能手段（プログラムモジュール）を有する。

ＣＢ９：秘匿類似情報受信手段
秘匿類似情報受信手段ＣＢ９は、後述する秘匿類似情報送信手段ＣＤ８により送信された前記類似情報ｔ′が秘匿化された秘匿類似情報を受信する。実施例１の前記秘匿類似情報受信手段ＣＢ９では、前記秘匿類似情報として、前記データベースサーバＤＳに登録済の複数の前記多項式点集合Ｒの一例としてのＭ個の候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭを要素とする集合である解候補集合Ｒ_Ａ（Ｒ_Ａ＝（Ｒ_Ａ１，Ｒ_Ａ２，…，Ｒ_ＡＭ））を前記秘匿類似情報として受信する。なお、前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭおよび前記解候補集合Ｒ_Ａについては後述する。

ＣＢ10：候補多項式点集合演算手段
候補多項式点集合演算手段ＣＢ10は、検索数値判別手段ＣＢ10Aと、数値抽出手段ＣＢ10Bとを有し、前記類似情報ｔ′を演算可能な多項式点集合の候補としての候補多項式点集合を演算する。実施例１の前記候補多項式点集合演算手段ＣＢ10は、前記各候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭの部分集合となる前記候補多項式点部分集合をＱ_１〜Ｑ_Ｍとした場合に、前記検索集合記憶手段ＣＢ５に記憶した前記検索集合Ｂに含まれる検索数値ｂ_１〜ｂ_ｍと、前記秘匿類似情報受信手段ＣＢ９により受信した前記秘匿類似情報（解候補集合Ｒ_Ａ）に含まれる各候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭとに基づいて、前記各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍを演算する。

ＣＢ10A：検索数値判別手段
検索数値判別手段ＣＢ10Aは、前記検索数値ｂ_１〜ｂ_ｍが、前記各候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭに含まれる登録数値ａ_１〜ａ_ｎまたは前記擬似数値ａ_ｎ＋１〜ａ_ｒと同値であるか否かを判別する。実施例１の前記検索数値判別手段ＣＢ10Aは、ｍ個の前記検索数値ｂ_１〜ｂ_ｍが、前記各数値ａ_１〜ａ_ｒと同値であるか否かを、Ｍ個の前記各候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭについて全て判別する。なお、前記検索数値判別手段ＣＢ10Aでは、ｍ個の前記検索数値ｂ_１〜ｂ_ｍと、ｒ個の前記各数値ａ_１〜ａ_ｒとが昇順に並べられているため、例えば、ｂ_１＝ａ_３が成立する場合には、検索数値ｂ_２は数値ａ_４以降の数値と比較してゆくことにより、処理を高速化できる。
ＣＢ10B：数値抽出手段
数値抽出手段ＣＢ10Bは、前記検索数値ｂ_１〜ｂ_ｍと同値となる前記登録数値ａ_１〜ａ_ｎおよび前記擬似数値ａ_ｎ＋１〜ａ_ｒを抽出することにより、同値となる各数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））を抽出する。

実施例１の前記数値抽出手段ＣＢ10Bは、ｉ＝１，２，…，ｍとし、ｊ＝１，２，…，Ｍとし、変数をｘ_ｉ，ｙ_ｉとし、変数ｘ_ｉ，ｙ_ｉにより構成された点を（ｘ_ｉ，ｙ_ｉ）とした場合に、まず、前記検索情報Ｂに含まれるｉ番目の検索数値ｂ_ｉが、ｊ番目の候補多項式点集合Ｒ_Ａｊに含まれる数値ａ_１〜ａ_ｒのいずれかと同値である場合には、前記同値の数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））を点（ｘ_ｉ，ｙ_ｉ）にセットする（代入する）。例えば、ｂ_ｉ＝ａ_１となる場合には、点（ｘ_ｉ，ｙ_ｉ）に多項式点（ａ_１，ｆ（ａ_１））をセットする。また、ｉ番目の検索数値ｂ_ｉが、ｊ番目の候補多項式点集合Ｒ_Ａｊの数値ａ_１〜ａ_ｒと同値でない場合には、点（ｘ_ｉ，ｙ_ｉ）に何もセットしない。例えば、ｂ_ｉ≠ａ_１，ａ_２，…，ａ_ｒとなる場合には、点（ｘ_ｉ，ｙ_ｉ）に点（ｏ，ｏ）をセットする（（ｘ_ｉ，ｙ_ｉ）＝（ｏ，ｏ）＝φ）。

すなわち、以下の式（４）に示すように、ｊ番目の候補多項式点集合Ｒ_Ａｊについてのｉ番目の検索数値ｂ_ｉの射影を演算する。
（ｂ_ｉ，ｏ）
（ｘ_ｉ，ｙ_ｉ）←−−−−−Ｒ_Ａｊ …（４）
そして、前記射影である点（ｘ_ｉ，ｙ_ｉ）を、ｊ番目の候補多項式点部分集合Ｑ_ｊの要素とする（Ｑ_ｊ←Ｑ_ｊ∪（ｘ_ｉ，ｙ_ｉ））。
したがって、実施例１の前記候補多項式点集合演算手段ＣＢ10は、変数ｉ，ｊの全ての値について、上記の処理を繰り返して、全ての候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭの候補多項式点部分集合Ｑ_１〜Ｑ_Ｍを演算する。

ＣＢ11：解集合演算手段
解集合演算手段ＣＢ11は、類似情報復元判別手段ＣＢ11Aを有し、前記類似情報ｔ′を復元可能な各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍのみを要素とする集合である解集合を演算する。実施例１の前記解集合演算手段ＣＢ11は、０を除いた自然数をｃとし、前記各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍの要素数、すなわち、抽出された多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））の総数をそれぞれ‖Ｑ_１‖〜‖Ｑ_Ｍ‖とし、前記解集合をＲ_Ｂとした場合に、前記要素数‖Ｑ_１‖〜‖Ｑ_Ｍ‖がｃ個以上であると判別された前記各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍのみを要素とする前記解集合Ｒ_Ｂを演算する。

ＣＢ11A：類似情報復元判別手段
類似情報復元判別手段ＣＢ11Aは、０を除いた自然数をｃとした場合に、前記数値抽出手段ＣＢ10Aにより抽出された前記登録数値ａ_１〜ａ_ｎおよび前記擬似数値ａ_ｎ＋１〜ａ_ｒがｃ個以上であるか否かを判別することにより、前記各秘匿類似情報が、前記検索情報ｂ_１〜ｂ_ｍに対する前記類似情報ｔ′として復元可能であるか否かを判別する。実施例１の前記類似情報復元判別手段ＣＢ11Aは、前記要素数‖Ｑ_１‖〜‖Ｑ_Ｍ‖がｃ個以上であるか否かを判別することにより、抽出された前記数値ａ_１〜ａ_ｒがｃ個以上であるか否かを判別する。なお、実施例１の前記類似情報復元判別手段ＣＢ12では、前記自然数ｃの値が、以下の式（５）により設定されている。
ｃ＝ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１ …（５）

ＣＢ12：類似情報復元手段
類似情報復元手段ＣＢ12は、前記解集合演算手段ＣＢ11により演算された前記解集合Ｒ_Ｂに含まれる前記登録数値ａ_１〜ａ_ｎおよび前記擬似数値ａ_ｎ＋１〜ａ_ｒに基づいて、前記多項式ｆ（ｘ）を演算して前記類似情報ｔ′を復元する。なお、実施例１の前記類似情報復元手段ＣＢ12では、前記解集合Ｒ_Ｂの各候補多項式点部分集合（Ｑ_１〜Ｑ_Ｍ）に含まれる前記登録数値ａ_１〜ａ_ｎに対応する登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））が｛（ｎ＋ｋ）／２｝個以上既知である場合には、従来公知の誤り訂正符号の復号化アルゴリズムに基づいて、前記解集合Ｒ_Ｂから前記多項式ｆ（ｘ）を復元できる。すなわち、ｋ個の前記係数ｓ_０〜ｓ_ｋ−１が前記解集合Ｒ_Ｂの各候補多項式点部分集合（Ｑ_１〜Ｑ_Ｍ）ごとに演算される。このため、前記類似情報復元手段ＣＢ12では、まず、前記復号化アルゴリズムに基づいて、前記解集合Ｒ_Ｂの各候補多項式点部分集合（Ｑ_１〜Ｑ_Ｍ）を順番に前記多項式ｆ（ｘ）に復元する（係数ｓ_０〜ｓ_ｋ−１を演算する）。そして、前記多項式ｆ（ｘ）を復元できた場合には、演算された前記係数ｓ_０〜ｓ_ｋ−１については、前記逆関数Ｔ^−１により、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}に逆変換することにより、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}に基づく前記類似情報ｔ′（ｔ′＝ｓ）を演算する。

この場合、例えば、ｊ番目の候補多項式点部分集合Ｑ_ｊから前記多項式ｆ（ｘ）を復元できない場合には、前記候補多項式点部分集合Ｑ_ｊには｛（ｎ＋ｋ）／２｝個の前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））が存在しなかったものとみなして、次のｊ＋１番目の候補多項式点部分集合Ｑ_ｊ＋１の復元処理を実行する。すなわち、｛（ｎ＋ｋ）／２｝個の前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））が存在するか否かの判別ができないため、前記多項式ｆ（ｘ）を復元できた場合のみ、前記類似情報ｔ′を復元する。したがって、例えば、前記多項式ｆ（ｘ）を復元できる候補多項式点部分集合Ｑ_ｊが前記解集合Ｒ_Ｂに１個も含まれていない場合には、前記類似情報ｔ′を１つも復元せずに終了する場合もあり得る。

なお、実施例１の前記類似情報復元手段ＣＢ12では、実装が容易であり且つ効率的な前記復号化アルゴリズムの一例としてのＢＭアルゴリズム（Berlekamp-Masseyアルゴリズム、バーレカンプ・マッシィ法、ＢＭ法）により、前記多項式ｆ（ｘ）を演算する。なお、前記ＢＭアルゴリズムについては、例えば、非特許文献６、７等に記載されており、公知であるため、詳細な説明を省略する。
ＣＢ13：編集距離演算手段
編集距離演算手段ＣＢ13は、前記検索情報入力部３ａに入力された前記検索情報ｔと、前記類似情報復元手段ＣＢ12により復元された前記類似情報ｔ′との前記編集距離ｄを演算する。実施例１の前記編集距離演算手段ＣＢ13は、前記検索情報ｔと、復元された前記解集合Ｒ_Ｂの各候補多項式点部分集合に対応する各類似情報ｔ′との各編集距離ｄを全て演算する。

ＣＢ14：類似情報表示手段
類似情報表示手段ＣＢ14は、編集距離判別手段ＣＢ14Aを有し、前記検索情報入力部３ａに入力された前記検索情報ｔと、前記類似情報復元手段ＣＢ12により復元された前記類似情報ｔ′との前記編集距離ｄが予め設定された前記最大値ｄ_ｍａｘ以下である場合に（ｄ≦ｄ_ｍａｘ）、前記各類似情報ｔ′を前記類似情報出力部３ｃに表示する（図４参照）。実施例１の前記類似情報表示手段ＣＢ14は、前記編集距離ｄが前記最大値ｄ_ｍａｘ以下となる、前記解集合Ｒ_Ｂの各候補多項式点部分集合に対応する各類似情報ｔ′を一覧表示する。
ＣＢ14A：編集距離判別手段
編集距離判別手段ＣＢ14Aは、前記検索情報ｔと、前記解集合Ｒ_Ｂの各候補多項式点部分集合に対応する各類似情報ｔ′との各編集距離ｄが、前記最大値ｄ_ｍａｘ以下であるか否かを判別する。

（データベースサーバＤＳの制御部の説明）
前記データベースサーバＤＳのハードディスクドライブには、前記データベースサーバＤＳの基本動作を制御する基本ソフト（オペレーティングシステム）ＯＳや、アプリケーションプログラムとしての秘匿類似情報検索プログラム（類似情報検索プログラム）ＡＰ４、その他の図示しないソフトウェアが記憶されている。

（秘匿類似情報検索プログラムＡＰ４）
前記秘匿類似情報検索プログラムＡＰ４は、下記の機能手段（プログラムモジュール）を有する。

ＣＤ１：秘匿登録情報受信手段
秘匿登録情報受信手段ＣＤ１は、前記秘匿登録情報送信手段ＣＡ10により送信された前記秘匿登録情報Ｒを受信する。
ＣＤ２：秘匿登録情報記憶手段
秘匿登録情報記憶手段ＣＤ２は、前記秘匿登録情報受信手段ＣＤ１により受信した前記秘匿登録情報Ｒを記憶する。実施例１の前記秘匿登録情報記憶手段ＣＤ２は、０を除いた自然数をＮとし、受信した前記秘匿登録情報ＲがＮ番目に記憶される秘匿登録情報とし、記憶される前記秘匿登録情報（ボールト、多項式点集合）をＲ_１，Ｒ_２，…，Ｒ_Ｎ，…とした場合に、受信した前記秘匿登録情報ＲをＲ_Ｎとして記憶する。

ＣＤ３：秘匿検索情報受信手段
秘匿検索情報受信手段ＣＤ３は、前記秘匿検索情報送信手段ＣＢ７により送信された前記秘匿検索情報Ｂ^＊（例えば、Ｂ^＊＝（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）、Ｌ＝２）を受信する。
ＣＤ４：検索数値判別手段
検索数値判別手段ＣＤ４は、前記秘匿登録情報受信手段ＣＤ１により受信した前記秘匿検索情報Ｂ^＊に含まれる（ｍ−Ｌ）種類の前記検索数値（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）が、前記秘匿登録情報記憶手段ＣＤ２に記憶した前記各秘匿登録情報（各多項式点集合）Ｒ_１〜Ｒ_Ｎに含まれる前記登録数値ａ_１〜ａ_ｎまたは前記擬似数値ａ_ｎ＋１〜ａ_ｒと同値であるか否かを判別する。実施例１の前記検索数値判別手段ＣＤ４は、前記検索数値判別手段ＣＢ10Aと同様に、前記検索数値（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）が、前記各多項式点集合Ｒ_１〜Ｒ_Ｎに含まれる数値ａ_１〜ａ_ｒと同値であるか否かを、Ｎ個の前記各多項式点集合Ｒ_１〜Ｒ_Ｎについて全て判別する。

ＣＤ５：多項式点部分集合演算手段
多項式点部分集合演算手段ＣＤ５は、（ｍ−Ｌ）種類の前記検索数値（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）と同値となる前記登録数値ａ_１〜ａ_ｎの前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））および前記擬似数値ａ_ｎ＋１〜ａ_ｒの前記擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））を抽出することにより、前記多項式点集合（Ｒ_１〜Ｒ_Ｎ）における前記検索数値（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）の前記射影の集合であって、前記多項式点集合Ｒ_１〜Ｒ_Ｎの部分集合である多項式点部分集合を演算する。実施例１の前記多項式点部分集合演算手段ＣＤ５は、前記各多項式点集合Ｒ_１〜Ｒ_Ｎに対応する前記各多項式点部分集合をＱ_１ ^＊〜Ｑ_Ｎ ^＊とした場合に、前記各多項式点集合Ｒ_１〜Ｒ_Ｎから、（ｍ−Ｌ）種類の前記検索数値（ｂ_１，ｂ_３，…，ｂ_ｉ−１，ｂ_ｉ＋１，…，ｂ_ｍ）と同値となる数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））が抽出された前記各多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊を演算する。

具体的には、前記多項式点部分集合演算手段ＣＤ５は、前記数値抽出手段ＣＢ10Bと同様に、ｉ＝１，２，…，（ｍ−Ｌ）とし、ｊ＝１，２，…，Ｎとし、（ｍ−Ｌ）種類の前記検索数値をｂ_１〜ｂ_ｍ−Ｌとした場合に、まず、前記検索情報Ｂに含まれるｉ番目の検索数値ｂ_ｉが、ｊ番目の多項式点集合Ｒ_ｊに含まれる数値ａ_１〜ａ_ｒのいずれかと同値である場合には、前記同値の数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））を点（ｘ_ｉ，ｙ_ｉ）にセットする（代入する）。例えば、ｂ_ｉ＝ａ_１となる場合には、点（ｘ_ｉ，ｙ_ｉ）に多項式点（ａ_１，ｆ（ａ_１））をセットする。また、ｉ番目の検索数値ｂ_ｉが、ｊ番目の多項式点集合Ｒ_ｊの数値ａ_１〜ａ_ｒと同値でない場合には、点（ｘ_ｉ，ｙ_ｉ）に何もセットしない。例えば、ｂ_ｉ≠ａ_１，ａ_２，…，ａ_ｒとなる場合には、点（ｘ_ｉ，ｙ_ｉ）に点（ｏ，ｏ）をセットする（（ｘ_ｉ，ｙ_ｉ）＝（ｏ，ｏ）＝φ）。

すなわち、以下の式（４）′に示すように、ｊ番目の多項式点集合Ｒ_ｊについてのｉ番目の検索数値ｂ_ｉの射影を演算する。
（ｂ_ｉ，ｏ）
（ｘ_ｉ，ｙ_ｉ）←−−−−−Ｒ_ｊ …（４）′
そして、前記射影である点（ｘ_ｉ，ｙ_ｉ）を、ｊ番目の多項式点部分集合Ｑ_ｊ ^＊の要素とする（Ｑ_ｊ ^＊←Ｑ_ｊ ^＊∪（ｘ_ｉ，ｙ_ｉ））。
したがって、実施例１の前記多項式点部分集合演算手段ＣＤ５は、変数ｉ，ｊの全ての値について、上記の処理を繰り返して、全ての多項式点集合Ｒ_１〜Ｒ_Ｎの多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊を演算する。

ＣＤ６：多項式点部分集合要素数判別手段
多項式点部分集合要素数判別手段ＣＤ６は、前記多項式点部分集合演算手段ＣＤ５により演算された前記各多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊の点が（ｃ−Ｌ）個以上であるか否かを判別する。実施例１の前記多項式点部分集合要素数判別手段ＣＤ６は、前記類似情報復元判別手段ＣＢ11Aと同様に、前記各多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊の多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））の総数をそれぞれ‖Ｑ_１ ^＊‖〜‖Ｑ_Ｎ ^＊‖とした場合に、前記要素数‖Ｑ_１ ^＊‖〜‖Ｑ_Ｎ ^＊‖が（ｃ−Ｌ）個以上であるか否かを判別する。

ＣＤ７：秘匿類似情報演算手段
秘匿類似情報演算手段ＣＤ７は、（ｃ−Ｌ）個以上の点を有する前記各多項式点部分集合（Ｑ_１ ^＊〜Ｑ_Ｎ ^＊）に対応する前記各秘匿登録情報（Ｒ_１〜Ｒ_Ｎ）を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する。実施例１の前記秘匿類似情報演算手段では、０を除いた自然数をＭとし、Ｍ≦Ｎとし、（ｃ−Ｌ）個以上の点を有する前記各多項式点部分集合（Ｑ_１ ^＊〜Ｑ_Ｎ ^＊）に対応するＭ個の前記秘匿登録情報（Ｒ_１〜Ｒ_Ｎ）を前記類似情報ｔ′が秘匿化された可能性がある候補の多項式点集合である候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭとし、前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭを要素とする集合である解候補集合をＲ_Ａとした場合に（Ｒ_Ａ＝（Ｒ_Ａ１，Ｒ_Ａ２，…，Ｒ_ＡＭ））、前記秘匿類似情報である前記解候補集合Ｒ_Ａを演算する。
ＣＤ８：秘匿類似情報送信手段
秘匿類似情報送信手段ＣＤ８は、前記秘匿類似情報演算手段ＣＤ７により演算された前記秘匿類似情報（解候補集合Ｒ_Ａ）を、前記検索用クライアントパソコンＰＣｂに対して送信する。

（実施例１のフローチャートの説明）
次に、実施例１の前記各プログラムＡＰ１〜ＡＰ４の処理の流れをフローチャートを使用して説明する。

（実施例１の秘匿登録情報送信プログラムＡＰ１の秘匿登録情報送信処理のフローチャートの説明）
図５は実施例１の秘匿登録情報送信プログラムの秘匿登録情報送信処理のフローチャートである。
図５のフローチャートの各ＳＴ（ステップ）の処理は、前記登録用クライアントパソコンＰＣａの制御部のＲＯＭ等に記憶されたプログラムに従って行われる。また、この処理は前記制御部の他の各種処理と並行してマルチタスクで実行される。

図５に示すフローチャートは、前記秘匿登録情報送信プログラムＡＰ１が起動した場合に開始される。
図５のＳＴ１０１において、登録画像２（図３参照）を表示する。そして、ＳＴ１０２に移る。
ＳＴ１０２において、登録情報入力部２ａに登録情報ｓの入力があったか否かを判別する。イエス（Ｙ）の場合はＳＴ１０３に移り、ノー（Ｎ）の場合はＳＴ１０４に移る。
ＳＴ１０３において、登録情報ｓの入力に応じて登録画像２を更新する。そして、ＳＴ１０２に戻る。
ＳＴ１０４において、登録ボタン２ｂが入力されたか否かを判別する。ノー（Ｎ）の場合はＳＴ１０５に移り、イエス（Ｙ）の場合はＳＴ１０６に移る。
ＳＴ１０５において、秘匿登録情報送信プログラムＡＰ１を終了する入力がされたか否かを判別する。ノー（Ｎ）の場合はＳＴ１０２に戻り、イエス（Ｙ）の場合は前記秘匿登録情報送信処理を終了する。

ＳＴ１０６において、登録情報入力部２ａに登録情報ｓが表示されているか否かを判別する。イエス（Ｙ）の場合はＳＴ１０７に移り、ノー（Ｎ）の場合はＳＴ１０２に戻る。
ＳＴ１０７において、登録情報ｓから（ｋ−１）次元１変数多項式ｆの係数ｓ_０〜ｓ_ｋ−１（式（１）参照）を演算する。すなわち、ｓ_ｋ−１＝１とし、且つ、予め設定された可逆関数Ｔにより、登録情報ｓから抽出された部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}を、係数ｓ_０〜ｓ_ｋ−２に変換する。そして、ＳＴ１０８に移る。
ＳＴ１０８において、登録情報ｓから登録部分情報ｓ_ｑ１〜ｓ_ｑｎを抽出する。そして、ＳＴ１０９に移る。
ＳＴ１０９において、登録部分情報ｓ_ｑ１〜ｓ_ｑｎと、ハッシュ関数Ｈとにより、登録集合Ａを演算する（Ａ＝（ａ_１，ａ_２，…，ａ_ｎ）、Ｈ（ｓ_ｑ１）＝ａ_１，Ｈ（ｓ_ｑ２）＝ａ_２，…，Ｈ（ｓ_ｑｎ）＝ａ_ｎ）。そして、ＳＴ１１０に移る。

ＳＴ１１０において、変数ｘ_ｉの値を要素とする集合をＸとした場合に、以下の（１）〜（３）の処理を実行し、ＳＴ１１１に移る。
（１）変数ｉ，ｘ_ｉ，ｙ_ｉに、１，０，０をセットする（ｉ＝１，ｘ_ｉ＝０，ｙ_ｉ＝０）。
（２）集合Ｘにφをセットする。すなわち、集合Ｘを空集合とする（Ｘ←φ）。
（３）多項式点集合Ｒにφをセットする。すなわち、多項式点集合Ｒを空集合とする（Ｒ←φ）。
ＳＴ１１１において、次の（１）〜（３）の処理を実行し、ＳＴ１１２に移る。
（１）ｉ番目の登録数値ａ_ｉおよび登録数値ａ_ｉに対応する登録代入値ｆ（ａ_ｉ）を一組とする登録多項式点（ａ_ｉ，ｆ（ａ_ｉ））を演算して、点（ｘ_ｉ，ｙ_ｉ）にセットする（（ｘ_ｉ，ｙ_ｉ）←（ａ_ｉ，ｆ（ａ_ｉ）））。
（２）変数（点（ｘ_ｉ，ｙ_ｉ）のｘ座標の値）ｘ_ｉを、集合Ｘの要素とする（Ｘ←Ｘ∪｛ｘｉ｝）。
（３）点（ｘ_ｉ，ｙ_ｉ）を、多項式点集合Ｒの要素とする（Ｒ←Ｒ∪（ｘ_ｉ，ｙ_ｉ））

ＳＴ１１２において、変数ｉに＋１を加算する（ｉ＝ｉ＋１）。そして、ＳＴ１１３に移る。
ＳＴ１１３において、変数ｉが登録多項式点（ａ_ｉ，ｆ（ａ_ｉ））の個数であるｎより大きくなったか否かを判別する。イエス（Ｙ）の場合はＳＴ１１４に移り、ノー（Ｎ）の場合はＳＴ１１１に戻る。
ＳＴ１１４において、次の（１），（２）の処理を実行し、ＳＴ１１５に移る。
（１）ｉ番目の擬似数値ａ_ｉおよび擬似数値ａ_ｉに対応する擬似代入値ｆ′（ａ_ｉ）を一組とする擬似多項式点（ａ_ｉ，ｆ′（ａ_ｉ））を演算して、点（ｘ_ｉ，ｙ_ｉ）にセットする（（ｘ_ｉ，ｙ_ｉ）←（ａ_ｉ，ｆ′（ａ_ｉ））、ｘ_ｉ∈Ｆ−Ｘ、ｙ_ｉ∈Ｆ−｛ｆ（ｘ_ｉ）｝）。
（２）点（ｘ_ｉ，ｙ_ｉ）を、多項式点集合Ｒの要素とする（Ｒ←Ｒ∪（ｘ_ｉ，ｙ_ｉ）））

ＳＴ１１５において、変数ｉが多項式点集合Ｒに含まれる点の個数であるｒになったか否かを判別する。ノー（Ｎ）の場合はＳＴ１１６に移り、イエス（Ｙ）の場合はＳＴ１１７に移る。
ＳＴ１１６において、変数ｉに＋１を加算する（ｉ＝ｉ＋１）。そして、ＳＴ１１４に戻る。
ＳＴ１１７において、多項式点集合Ｒの要素（ｘ_ｉ，ｙ_ｉ）を変数ｘ_ｉ（ｉ＝１，２，…，ｒ）の昇順に並び替える。
ＳＴ１１８において、秘匿登録情報である多項式点集合ＲをデータベースサーバＤＳに送信する。そして、ＳＴ１０２に戻る。

（実施例１の秘匿検索情報送信プログラムＡＰ２の秘匿検索情報送信処理のフローチャートの説明）
図６は実施例１の秘匿検索情報送信プログラムの秘匿検索情報送信処理のフローチャートである。
図６のフローチャートの各ＳＴ（ステップ）の処理は、前記検索用クライアントパソコンＰＣｂの制御部のＲＯＭ等に記憶されたプログラムに従って行われる。また、この処理は前記制御部の他の各種処理と並行してマルチタスクで実行される。

図６に示すフローチャートは、前記秘匿検索情報送信プログラムＡＰ２が起動した場合に開始される。
図６のＳＴ２０１において、検索画像３（図４参照）を表示する。そして、ＳＴ２０２に移る。
ＳＴ２０２において、検索情報入力部３ａに検索情報ｔの入力があったか否かを判別する。イエス（Ｙ）の場合はＳＴ２０３に移り、ノー（Ｎ）の場合はＳＴ２０４に移る。
ＳＴ２０３において、検索情報ｔの入力に応じて検索画像３を更新する。そして、ＳＴ２０２に戻る。
ＳＴ２０４において、検索開始ボタン３ｂが入力されたか否かを判別する。ノー（Ｎ）の場合はＳＴ２０５に移り、イエス（Ｙ）の場合はＳＴ２０６に移る。

ＳＴ２０５において、秘匿検索情報送信プログラムＡＰ２を終了する入力がされたか否かを判別する。ノー（Ｎ）の場合はＳＴ２０２に戻り、イエス（Ｙ）の場合は前記秘匿検索情報送信処理を終了する。
ＳＴ２０６において、検索情報入力部３ａに検索情報ｔが表示されているか否かを判別する。イエス（Ｙ）の場合はＳＴ２０７に移り、ノー（Ｎ）の場合はＳＴ２０２に戻る。
ＳＴ２０７において、検索情報ｔから検索部分情報ｔ_ｑ１〜ｔ_ｑｍを抽出する。そして、ＳＴ２０８に移る。
ＳＴ２０８において、検索部分情報ｔ_ｑ１〜ｔ_ｑｍと、ハッシュ関数Ｈとにより、検索集合Ｂを演算して記憶する（Ｂ＝（ｂ_１，ｂ_２，…，ｂ_ｍ）、Ｈ（ｔ_ｑ１）＝ｂ_１，Ｈ（ｔ_ｑ２）＝ｂ_２，…，Ｈ（ｔ_ｑｎ）＝ｂ_ｍ）。そして、ＳＴ２０９に移る。

ＳＴ２０９において、検索集合Ｂの検索数値ｂ_１〜ｂ_ｍのうちのＬ種類の検索数値を除いて、（ｍ−Ｌ）種類の検索数値ｂ_１〜ｂ_ｍ−Ｌを要素とする検索部分集合Ｂ^＊を演算する（Ｂ^＊＝（ｂ_１，ｂ_２，…，ｂ_ｍ−Ｌ））。そして、ＳＴ２１０に移る。
ＳＴ２１０において、秘匿検索情報である検索部分集合Ｂ^＊をデータベースサーバＤＳに送信する。そして、ＳＴ２１１に移る。
ＳＴ２１１において、データベースサーバＤＳから送信された各秘匿類似情報（解候補集合Ｒ_Ａ、Ｒ_Ａ＝（Ｒ_Ａ１，Ｒ_Ａ２，…，Ｒ_ＡＭ））から対応する各類似情報ｔ′を復元する秘匿類似情報復元処理（後述する図８のフローチャート参照）を実行する。そして、ＳＴ２０２に戻る。

（実施例１の秘匿類似情報検索プログラムＡＰ４の秘匿類似情報検索処理のフローチャートの説明）
図７は実施例１の秘匿類似情報検索プログラムの秘匿類似情報検索処理のフローチャートである。
図７のフローチャートの各ＳＴ（ステップ）の処理は、前記データベースサーバＤＳの制御部のＲＯＭ等に記憶されたプログラムに従って行われる。また、この処理は前記制御部の他の各種処理と並行してマルチタスクで実行される。

図７に示すフローチャートは、前記秘匿類似情報検索プログラムＡＰ４が起動した場合に開始される。
図７のＳＴ３０１において、秘匿登録情報である多項式点集合Ｒを受信したか否かを判別する。イエス（Ｙ）の場合はＳＴ３０２に移り、ノー（Ｎ）の場合はＳＴ３０３に移る。
ＳＴ３０２において、受信した多項式点集合Ｒを秘匿登録情報Ｒ_Ｎとして記憶する。そして、ＳＴ３０１に戻る。
ＳＴ３０３において、秘匿検索情報である検索部分集合Ｂ^＊を受信したか否かを判別する。イエス（Ｙ）の場合はＳＴ３０４に移り、ノー（Ｎ）の場合はＳＴ３０１に戻る。

ＳＴ３０４において、以下の（１）〜（３）の処理を実行し、ＳＴ３０５に移る。
（１）変数ｉ，ｊ，ｘ_ｉ，ｙ_ｉに、１，１，０，０をセットする（ｉ＝１，ｊ＝１，ｘ_ｉ＝０，ｙ_ｉ＝０）。
（２）各多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊にφをセットする。すなわち、各多項式点部分集合Ｑ_１ ^＊〜Ｑ_Ｎ ^＊を空集合とする（Ｑ_１ ^＊←φ，Ｑ_２ ^＊←φ，…，Ｑ_Ｎ ^＊←φ）。
（３）解候補集合Ｒ_Ａにφをセットする。すなわち、解候補集合Ｒ_Ａを空集合とする（Ｒ_Ａ←φ）。

ＳＴ３０５において、以下の（１），（２）の処理を実行し、ＳＴ３０６に移る。
（１）ｊ番目の秘匿登録情報Ｒ_ｊについて、ｉ番目の検索数値ｂ_ｉの射影を演算する（式（４）′参照）。すなわち、秘匿検索情報Ｂ^＊に含まれるｉ番目の検索数値ｂ_ｉが、ｊ番目の秘匿登録情報Ｒ_ｊに含まれる数値ａ_１〜ａ_ｒと同値である場合には、点（ｘ_ｉ，ｙ_ｉ）に、同値の数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））をセットし、ｂ_ｉ≠ａ_１，ａ_２，…，ａ_ｒとなる場合には、点（ｘ_ｉ，ｙ_ｉ）に、点（ｏ，ｏ）をセットする（（ｘ_ｉ，ｙ_ｉ）＝（ｏ，ｏ）＝φ）。
（２）点（ｘ_ｉ，ｙ_ｉ）を、ｊ番目の多項式点部分集合Ｑ_ｊ ^＊の要素とする（Ｑ_ｊ ^＊←Ｑ_ｊ ^＊∪（ｘ_ｉ，ｙ_ｉ））。

ＳＴ３０６において、変数ｉが秘匿検索情報Ｂ^＊に含まれる点の個数である（ｍ−Ｌ）になったか否かを判別する。ノー（Ｎ）の場合はＳＴ３０７に移り、イエス（Ｙ）の場合はＳＴ３０８に移る。
ＳＴ３０７において、変数ｉに＋１を加算する（ｉ＝ｉ＋１）。そして、ＳＴ３０５に戻る。
ＳＴ３０８において、ｊ番目の多項式点部分集合Ｑ_ｊ ^＊の点が（ｃ−Ｌ）個以上であるか否かを判別する（‖Ｑ_ｊ ^＊‖≧ｃ−Ｌ）。イエス（Ｙ）の場合はＳＴ３０９に移り、ノー（Ｎ）の場合はＳＴ３１０に移る。
ＳＴ３０９において、ｊ番目の秘匿登録情報Ｒ_ｊを、解候補集合Ｒ_Ａの要素とする（Ｒ_Ａ←Ｒ_Ａ∪Ｒ_ｊ）。そして、ＳＴ３１０に移る。

ＳＴ３１０において、変数ｊが秘匿登録情報Ｒ_１〜Ｒ_Ｎの個数であるＮになったか否かを判別する。ノー（Ｎ）の場合はＳＴ３１１に移り、イエス（Ｙ）の場合はＳＴ３１２に移る。
ＳＴ３１１において、次の（１），（２）の処理を実行し、ＳＴ３０５に戻る。
（１）変数ｉに１をセットする（ｉ＝１）。
（２）変数ｊに＋１を加算する（ｊ＝ｊ＋１）。
ＳＴ３１２において、秘匿類似情報である解候補集合Ｒ_Ａ（Ｒ_Ａ＝（Ｒ_Ａ１，Ｒ_Ａ２，…，Ｒ_ＡＭ），Ｍ≦Ｎ）を検索用クライアントパソコンＰＣｂに送信する。そして、ＳＴ３０１に戻る。

（実施例１の秘匿類似情報復元プログラムＡＰ３の秘匿類似情報復元処理のフローチャートの説明）
図８は実施例１の秘匿類似情報復元プログラムの秘匿類似情報復元処理のフローチャートであり、図６のＳＴ２１１のサブルーチンの説明図である。

図８のＳＴ４０１において、秘匿類似情報である解候補集合Ｒ_Ａを受信したか否かを判別する。イエス（Ｙ）の場合はＳＴ４０２に移り、ノー（Ｎ）の場合はＳＴ４０１を繰り返す。
ＳＴ４０２において、以下の（１）〜（３）の処理を実行し、ＳＴ４０３に移る。
（１）変数ｉ，ｊ，ｘ_ｉ，ｙ_ｉに、１，１，０，０をセットする（ｉ＝１，ｊ＝１，ｘ_ｉ＝０，ｙ_ｉ＝０）。
（２）各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍにφをセットする。すなわち、各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍを空集合とする（Ｑ_１←φ，Ｑ_２←φ，…，Ｑ_Ｍ←φ）。
（３）解集合Ｒ_Ｂにφをセットする。すなわち、解集合Ｒ_Ｂを空集合とする（Ｒ_Ｂ←φ）。

ＳＴ４０３において、以下の（１），（２）の処理を実行し、ＳＴ４０４に移る。
（１）ｊ番目の候補多項式点集合Ｒ_Ａｊについて、ｉ番目の検索数値ｂ_ｉの射影を演算する（式（４）参照）。すなわち、検索情報Ｂに含まれるｉ番目の検索数値ｂ_ｉが、ｊ番目の候補多項式点集合Ｒ_Ａｊに含まれる数値ａ_１〜ａ_ｒと同値である場合には、点（ｘ_ｉ，ｙ_ｉ）に、同値の数値ａ_１〜ａ_ｒに対応する多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ）），（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））をセットし、ｂ_ｉ≠ａ_１，ａ_２，…，ａ_ｒとなる場合には、点（ｘ_ｉ，ｙ_ｉ）に、点（ｏ，ｏ）をセットする（（ｘ_ｉ，ｙ_ｉ）＝（ｏ，ｏ）＝φ）。
（２）点（ｘ_ｉ，ｙ_ｉ）を、ｊ番目の候補多項式点部分集合Ｑ_ｊの要素とする（Ｑ_ｊ←Ｑ_ｊ∪（ｘ_ｉ，ｙ_ｉ））。

ＳＴ４０４において、変数ｉが検索情報Ｂに含まれる点の個数であるｍになったか否かを判別する。ノー（Ｎ）の場合はＳＴ４０５に移り、イエス（Ｙ）の場合はＳＴ４０６に移る。
ＳＴ４０５において、変数ｉに＋１を加算する（ｉ＝ｉ＋１）。そして、ＳＴ４０３に戻る。
ＳＴ４０６において、ｊ番目の候補多項式点部分集合Ｑ_ｊの点がｃ個以上であるか否かを判別する（‖Ｑ_ｊ‖≧ｃ）。イエス（Ｙ）の場合はＳＴ４０７に移り、ノー（Ｎ）の場合はＳＴ４０８に移る。
ＳＴ４０７において、ｊ番目の候補多項式点部分集合Ｑ_ｊを、解集合Ｒ_Ｂの要素とする（Ｒ_Ｂ←Ｒ_Ｂ∪Ｒ_Ａｊ）。そして、ＳＴ４０８に移る。

ＳＴ４０８において、変数ｊが秘匿登録情報Ｒ_１〜Ｒ_Ｎの個数であるＮになったか否かを判別する。ノー（Ｎ）の場合はＳＴ４０９に移り、イエス（Ｙ）の場合はＳＴ４１０に移る。
ＳＴ４０９において、次の（１），（２）の処理を実行し、ＳＴ４０３に戻る。
（１）変数ｉに１をセットする（ｉ＝１）。
（２）変数ｊに＋１を加算する（ｊ＝ｊ＋１）。
ＳＴ４１０において、解集合Ｒ_Ｂに含まれる各候補多項式点部分集合Ｑ_ｊ（‖Ｑｊ‖≧ｃ））から、ＢＭアルゴリズムによって前記各多項式ｆ（ｘ）を復元し（係数ｓ_０〜ｓ_ｋ−１を演算し）、前記逆関数Ｔ^−１によって各類似情報ｔ′（ｔ′＝ｓ）を復元する。そして、ＳＴ４１１に移る。
ＳＴ４１１において、復元が成功し、且つ、編集距離ｄが最大値ｄ_ｍａｘ以下となる各類似情報ｔ′を類似情報出力部３ｂに一覧表示する（図４参照）。

（実施例１の作用）
前記構成を備えた実施例１の前記類似情報検索システムＳでは、前記登録用クライアントパソコンＰＣａにおいて、前記登録画像２の登録情報入力部２ａに前記登録情報ｓの入力があり、且つ、前記登録ボタン２ｂが入力された場合に、前記登録情報ｓが秘匿化された前記秘匿登録情報（多項式点集合Ｒ）を演算して、前記データベースサーバＤＳに送信する前記秘匿登録情報送信処理が実行される（図３、図５のＳＴ１０１〜ＳＴ１１８参照）。
また、実施例１の前記類似情報検索システムＳでは、前記検索用クライアントパソコンＰＣｂにおいて、前記検索画像３の検索情報入力部３ａに前記検索情報ｔの入力があり、且つ、前記検索開始ボタン３ｂが入力された場合に、前記検索情報ｔが秘匿化された前記秘匿検索情報（検索部分集合Ｂ^＊）を演算して、前記データベースサーバＤＳに送信する前記秘匿検索情報送信処理が実行される（図４、図６のＳＴ２０１〜ＳＴ２１０参照）。

また、実施例１の前記類似情報検索システムＳでは、前記データベースサーバＤＳにおいて、前記秘匿登録情報（多項式点集合Ｒ）を受信した場合には、前記秘匿登録情報Ｒ_Ｎ（Ｎ＝１，２，…）として記憶する（図７のＳＴ３０１，ＳＴ３０２参照）。また、前記秘匿検索情報（検索部分集合Ｂ^＊）を受信した場合には、前記検索情報ｔおよび前記類似情報ｔ′を秘匿化した状態で検索する前記秘匿類似情報検索処理が実行される（図７のＳＴ３０３〜ＳＴ３１２参照）。
そして、実施例１の前記類似情報検索システムＳでは、前記検索用クライアントパソコンＰＣｂにおいて、検索検索結果としての前記秘匿類似情報（解候補集合Ｒ_Ａ）を受信し、前記類似情報ｔ′を復元して前記類似情報出力部３ｂに表示する前記秘匿類似情報復元処理が実行される（図６のＳＴ２１１、図８のＳＴ４０１〜ＳＴ４１１参照）。

したがって、実施例１の前記類似情報検索システムＳでは、前記インターネット１を介して、前記各クライアントパソコンＰＣａ，ＰＣｂと、前記データベースサーバＤＳとの間で送受信される各情報Ｒ，Ｂ^＊，Ｒ_Ａは、前記登録情報ｓ、前記検索情報ｔ、前記類似情報ｔ′が秘匿化された情報である。このため、前記各クライアントパソコンＰＣａ，ＰＣｂおよび前記データベースサーバＤＳのユーザ以外の第三者から前記各情報ｓ，ｔ，ｔ′を秘匿することができる。
また、前記秘匿類似情報検索処理では、前記登録情報ｓ、前記検索情報ｔ、前記類似情報ｔ′を復元することなく、秘匿化したままの状態で実行される。すなわち、前記秘匿類似情報検索処理では、受信した前記秘匿検索情報（検索部分集合Ｂ^＊）に含まれる検索数値ｂ_１〜ｂ_ｍ−Ｌと、記憶した前記各秘匿登録情報Ｒ_１〜Ｒ_Ｎに含まれる数値ａ_１〜ａ_ｒとが同値であるか否かを判別するため（図７のＳＴ３０５参照）、復元された各情報ｓ，ｔ，ｔ′を特定できないようになっている。

なお、前記データベースサーバＤＳ上では、記憶した前記秘匿登録情報（多項式点集合Ｒ_１〜Ｒ_Ｎ）と、受信した前記秘匿検索情報（検索部分集合Ｂ^＊）とを、前記登録情報ｓと、前記検索情報ｔとに復元できないようになっている。すなわち、前記多項式点集合Ｒには、前記チャフの一例としての前記擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））が含まれている。このため、前記登録集合Ａを知らない限り、前記（ｎ，ｋ）符号の一例としての登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））を完全に特定できない。なお、前記登録集合Ａに十分近い前記検索集合Ｂを知得した場合には（Ｂ≒Ａ）、前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））の一部を特定でき、｛（ｎ＋ｋ）／２｝個以上の点を特定できれば、前記多項式点集合Ｒから前記登録情報ｓを復元できる。よって、前記検索集合Ｂを知得していない限り、前記多項式点集合Ｒから前記登録情報ｓを復元できない。また、前記検索部分集合Ｂ^＊は、前記検索集合ＢからＬ種類の検索数値が除かれている、例えば、Ｂ＝（ｂ_１，ｂ_２，…，ｂ_ｍ），Ｂ^＊＝（ｂ_１，ｂ_２，…，ｂ_ｍ−Ｌ）とした場合、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍが除かれている（図６のＳＴ２０９参照）。このため、前記検索集合Ｂを知らない限り、前記検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍを特定できず、前記検索部分集合Ｂ^＊から前記検索情報ｔを復元できない。

したがって、実施例１の前記類似情報検索システムＳでは、前記データベースサーバＤＳのユーザである管理者からも前記各情報ｓ，ｔ，ｔ′を秘匿することができる。
この結果、実施例１の前記類似情報検索システムＳは、前記第三者および前記管理者から、前記各情報ｓ，ｔ，ｔ′が秘匿された状態で、前記登録情報ｓの所有者である登録者と、前記検索情報ｔの知得者である検索者と、前記データベースサーバＤＳの管理業務を委託された外部委託業者としての前記管理者とを有する前記ＤＡＳモデルを構成できる。すなわち、前記登録用クライアントパソコンＰＣａのユーザである前記登録者と、前記検索用クライアントパソコンＰＣｂのユーザである前記検索者と、前記管理者とにより、前記ＤＡＳモデルを構成できる。

また、前記構成を備えた実施例１の前記類似情報検索システムＳでは、前記登録情報ｓを秘匿化して登録する際に、まず、ｑ−ｇｒａｍの抽出処理により、前記登録情報ｓから前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}や前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎが抽出される（図５のＳＴ１０７，ＳＴ１０８参照）。次に、前記可逆関数Ｔや前記ハッシュ関数Ｈにより、前記多項式ｆ（ｘ）の係数ｓ_０〜ｓ_ｋ−１や前記登録集合（第１の集合）Ａ（Ａ＝（ａ_１，ａ_２，…，ａ_ｎ））が演算される（図５のＳＴ１０７，ＳＴ１０９参照）。そして、前記ファジーボールトにおける施錠処理と同様に、前記（ｎ，ｋ）符号の一例としての前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））と、前記チャフの一例としての前記擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））とを有する前記多項式点集合Ｒが演算される（図５のＳＴ１１０〜ＳＴ１１７）。したがって、前記抽出処理と、前記各関数Ｔ，Ｈと、前記施錠処理とを組み合わせることにより、前記登録者ごとの鍵を使用しなくても、前記登録情報ｓを秘匿化できる。

また、前記検索情報ｔの検索を行う場合、まず、前記登録集合Ａと同様に、前記抽出処理と、前記ハッシュ関数Ｈと、前記施錠処理とにより、前記検索集合（第２の集合）Ｂ（Ｂ＝（ｂ_１，ｂ_２，…，ｂ_ｍ））が演算される（図６のＳＴ２０７，ＳＴ２０８参照）。そして、ｍ種類の検索数値ｂ_１〜ｂ_ｍからＬ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍが除かれた前記検索部分集合Ｂ^＊が演算される（図６のＳＴ２０９参照）。したがって、前記抽出処理と、前記ハッシュ関数Ｈと、前記施錠処理とを組み合わせることにより、前記検索者ごとの鍵を使用しなくても、前記検索情報ｔを秘匿化できる。
この結果、実施例１の前記類似情報検索システムＳでは、前記インターネット１を介して前記データベースサーバＤＳが送受信する全ての情報Ｒ，Ｂ^＊，Ｒ_Ａ（Ｒ_Ａ＝（Ｒ_Ａ１，Ｒ_Ａ２，…，Ｒ_ＡＭ））が、前記鍵を使用せずに演算できる。なお、前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭは、受信した前記多項式点集合Ｒを記憶した前記多項式点集合Ｒ_１〜Ｒ_Ｎの全部または一部である。したがって、従来公知の暗号アルゴリズムで使用される鍵を、ユーザ（登録者、検索者）ごとに設定しなくても、前記第三者および前記管理者から前記各情報ｓ，ｔ，ｔ′を秘匿できる。よって、前記暗号化データベース（図９参照）における鍵管理の安全性（厳格性）やそれに伴う管理コスト等の問題を解決することができる。

（各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍから各類似情報ｔ′への復元について）
ここで、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍが除かれた前記検索部分集合Ｂ^＊によって検索された前記解候補集合Ｒ_Ａから前記類似情報ｔ′が確実に復元できるか否かが問題となる。すなわち、前記解候補集合Ｒ_Ａの各候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭから演算された各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍに対応する各類似情報ｔ′が演算できるか否かが問題となる。

ここで、前記ｑ−ｇｒａｍを用いた類似文字列検索手法において、長さ（文字数）ｎの文字列と、長さｍの文字列とは、少なくとも｛ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１｝個の前記ｑ−ｇｒａｍを共通に持つことが保証されている。このため、長さ（文字数）‖ｓ‖の文字列（登録情報ｓ）と、長さ‖ｔ‖の文字列（検索情報ｔ）とが、少なくとも｛ｍａｘ（‖ｓ‖，‖ｔ‖）−（ｄ−１）ｑ−１｝個の前記ｑ−ｇｒａｍを共通に持つことから、以下の式（６）が成立する。
ｍａｘ（‖ｓ‖，‖ｔ‖）−（ｄ−１）ｑ−１
＝ｍａｘ（ｎ＋ｑ−１，ｍ＋ｑ−１）−（ｄ−１）ｑ−１
≧ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１ …（６）
すなわち、前記ハッシュ関数Ｈによって前記登録情報のｑ−ｇｒａｍとしての前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎに対応付けられた前記登録数値ａ_１〜ａ_ｎと、前記検索情報のｑ−ｇｒａｍとしての前記検索部分情報ｔ_ｑ１〜ｔ_ｑｍに対応付けられた前記検索数値ｂ_１〜ｂ_ｍとの共有数が｛ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１｝個以上であることが明らかである。

また、前記ＲＳ符号を用いたファジーボールトの開錠処理において、前記ボールトＲから前記（ｎ，ｋ）符号の｛（ｎ＋ｋ）／２｝個以上の点が判明すれば前記多項式が復元できることが保証されている。
よって、前記各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍから各類似情報ｔ′が復元できるか否かを判別するための多項式点の個数の下限値である前記自然数ｃについて、以下の式（７）が常に成立すると仮定すれば、前記（ｎ，ｋ）符号の｛（ｎ＋ｋ）／２｝個以上の点から前記多項式ｆ（ｘ）の係数ｓ_０〜ｓ_ｋ−１を常に演算できる（図８のＳＴ４１０参照）。
ｃ≧（ｎ＋ｋ）／２ …（７）

ここで、前記自然数ｃ，ｋについて、前記式（２）′，（５）が成立し、且つ、ｎ≧ｍが成立すると仮定した場合、以下の式（８）が成立する。
‖Ｑ_ｊ‖≧ｃ（ｊ＝１，２，…，Ｍ）
≧（ｎ＋ｋ）／２
＝ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１
＝ｎ−（ｄ−１）ｑ−１
≧ｎ−（ｄ_ｍａｘ−１）ｑ−１
＝（ｎ＋ｋ）／２ …（８）

また、前記自然数ｃ，ｋについて、前記式（２）′，（５）が成立し、且つ、ｎ＜ｍが成立すると仮定した場合には、以下の式（８）′が成立する。
‖Ｑ_ｊ‖≧ｃ
＝ｍａｘ（ｎ，ｍ）−（ｄ−１）ｑ−１
＝ｍ−（ｄ−１）ｑ−１
＞ｎ−（ｄ−１）ｑ−１
≧ｎ−（ｄ_ｍａｘ−１）ｑ−１
＝（ｎ＋ｋ）／２ …（８）′

したがって、実施例１の前記類似情報検索システムＳでは、予め設定された前記自然数ｑ，ｎ，ｍ，ｄの値と、前記式（２）′，（５）とに基づいて、前記自然数ｃ，ｋの値が設定された場合、前記式（７）が常に成立する。このため、ｃ個以上の多項式点を有する前記各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍに、前記（ｎ，ｋ）符号の｛（ｎ＋ｋ）／２｝個以上の点が含まれていれば、前記開錠処理により、前記係数ｓ_０〜ｓ_ｋ−１を常に演算できる。すなわち、実施例１の前記類似情報検索システムＳは、前記自然数ｃ，ｋを、前記式（２）′，（５）に基づいて設定すれば、前記類似情報ｔ′を復元可能か否かを判別するフィルタリング処理（図７のＳＴ３０８、図８のＳＴ４０６参照）を適切に実行することができる。よって、前記類似情報ｔ′が前記検索情報ｔと完全一致する場合には必ず復元でき、前記類似情報ｔ′が前記検索情報ｔとの類似度が高いほど（編集距離ｄが小さいほど）復元できる可能性が高まり、前記類似情報ｔ′が前記検索情報ｔとの類似度が低いほど（編集距離ｄが大きいほど）復元できる可能性が低くなると共に、前記フィルタリング処理で除外される可能性が高くなる。

この結果、実施例１の前記類似情報検索システムＳでは、前記ｑ−ｇｒａｍを用いた類似文字列検索手法の技術のみでは実現できない情報の秘匿化の問題が解決されていると共に、前記ＲＳ符号を用いたファジーボールトの技術のみでは実現できない前記開錠処理のフィルタリング条件の設定についての問題が解決されている。

（秘匿類似情報検索処理の効率について）
また、前記構成を備えた実施例１の前記類似情報検索システムＳでは、前記秘匿類似情報（解候補集合Ｒ_Ａ）を検索する際に、前記秘匿検索情報（検索部分集合Ｂ^＊）に含まれる検索数値ｂ_１〜ｂ_ｍ−Ｌと、前記各秘匿登録情報Ｒ_１〜Ｒ_Ｎに含まれる数値ａ_１〜ａ_ｒとを照合する。このため、暗号化された登録情報や検索情報を復号化してから照合を行う場合に比べ、効率的に前記秘匿類似情報（解候補集合Ｒ_Ａ）を検索できる。
また、実施例１の前記類似情報検索システムＳでは、前記検索数値ｂ_１〜ｂ_ｍ−Ｌと、前記数値ａ_１〜ａ_ｒとが昇順に並べられている。このため、前記照合により各候補多項式点部分集合Ｑ_１〜Ｑ_Ｍを演算する前記計算量が、前記ランダウの記号を用いてＯ（ｎ＋ｍ）時間となる。したがって、総当りで照合して、計算量がＯ（ｎｍ）になる場合に比べ、効率的に前記秘匿類似情報検索処理を実行できる。

（秘匿類似情報復元処理の効率について）
また、実施例１の前記類似情報検索システムＳでは、前記秘匿類似情報（解候補集合Ｒ_Ａ）の復元について、前記ＢＭアルゴリズムを用いた前記開錠処理が実行される（図８のＳＴ４１０参照）。前記ＢＭアルゴリズムを用いた前記開錠処理は、誤り訂正可能な点の数をｚ（ｚ＝（ｎ−ｋ）／２）とした場合に、前記計算量が前記ランダウの記号を用いてＯ（ｚ^２）時間となることが知られている（例えば、特開２００３−１６８９８３号公報等参照）。このため、前記Ｏ（ｚ^２）時間以上の開錠処理（例えば、計算量がＯ（ｚ^３）時間となるピーターソン（Perterson）法を用いた開錠処理）に比べ、効率的に前記秘匿類似情報復元処理を実行できる。

（総当り攻撃に対する秘匿登録情報の安全性について）
また、前記構成を備えた実施例１の前記類似情報検索システムＳでは、例えば、前記第三者や前記管理人が、前記秘匿登録情報（多項式点集合Ｒ）から前記多項式ｆ（ｘ）を総当りで復元して、前記登録情報ｓの解読を試みる可能性がある。ここで、十分に小さい正の値の実数をμとし（μ＞０，μ≒０）、前記多項式ｆ（ｘ）の候補となる多項式の総数をＮ_ｆとした場合、前記多項式の総数Ｎ_ｆについて、少なくとも（１−μ）の確率で、以下の式（９）が成立することが知られている（例えば、非特許文献７参照）。
Ｎ_ｆ＝（μ／３）×ｐ^ｋ−ｎ×（ｒ／ｎ）^ｎ …（９）
よって、例えば、前記自然数ｒ，ｐ，ｎ，ｋについて、ｒ＝ｐ＝１０^４，ｎ＝２２，ｋ＝１４とし、前記実数μについて、μ≒２^−１８８とした場合、Ｎ_ｆ≒２^８６が成立する。すなわち、２^８６通りの多項式のうち、前記登録情報ｓに対応する１つの多項式ｆ（ｘ）を特定しなければならない。

また、実施例１の前記類似情報検索システムＳでは、前記自然数ｒの値が大きくなるに連れて、前記多項式点集合Ｒに含まれる前記擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））の総数が増えるため、前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））を特定される可能性が低くなる。また、前記自然数ｒの値が大きければ、前記多項式の総数Ｎ_ｆ自体が大きく、前記多項式ｆ（ｘ）として選択できる多項式の総数も大きくすることができる。この場合、前記秘匿登録情報（多項式点集合Ｒ）が解読される可能性がさらに低減され、安全性を高くすることができる。

また、前記編集距離ｄについて、前記最大値ｄ_ｍａｘが大きくなるに連れて、検索される前記解候補集合Ｒ_Ａの候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭの個数が多くなる可能性が高くなる。すなわち、自然数Ｍの値が大きくなる可能性が高くなる。このため、類似情報検索処理としての利便性が高くなる。しかしながら、この場合、前記自然数ｋ（ｋ＝ｎ−２（ｄ_ｍａｘ−１）ｑ−２）の値が小さくなる（式（２）′参照）。このため、前記多項式ｆ（ｘ）の次数（ｋ−１）の値が小さくなり、前記多項式ｆ（ｘ）として選択できる多項式の総数も小さくなり、前記秘匿登録情報（多項式点集合Ｒ）が解読される可能性が高くなるため、安全性が低くなってしまう。
すなわち、前記最大値ｄ_ｍａｘが大きくなるに連れて、類似情報検索処理としての利便性が向上するが、前記秘匿登録情報（多項式点集合Ｒ）の安全性は低くなる。

逆に、前記最大値ｄ_ｍａｘが小さくなるに連れて、検索される前記解候補集合Ｒ_Ａの候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭの個数が少なくなる可能性が高くなり（自然数Ｍの値が小さくなる可能性が低くなり）、類似情報検索処理としての利便性が低くなる。また、この場合、前記自然数ｋの値が大きくなり、前記多項式ｆ（ｘ）の次数（ｋ−１）の値が大きくなり、前記多項式ｆ（ｘ）として選択できる多項式の総数も大きくなり、前記秘匿登録情報が解読される可能性が低くなるため、安全性が高くなる。
すなわち、前記最大値ｄ_ｍａｘが大きくなるに連れて、類似情報検索処理としての利便性が低下するが、前記秘匿登録情報（多項式点集合Ｒ）の安全性は高くなる。
この結果、実施例１の前記類似情報検索システムＳでは、前記最大値ｄ_ｍａｘに基づいて、前記利便性と前記安全性とを調節することができる。

（総当り攻撃に対する秘匿検索情報の安全性について）
また、前記構成を備えた実施例１の前記類似情報検索システムＳでは、例えば、前記第三者や前記管理人が、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍを総当りで推測して、前記秘匿検索情報（検索部分集合Ｂ^＊）から前記検索集合Ｂを復元して、前記検索情報ｔの解読を試みる可能性がある。

ここで、前記自然数Ｌの値が大きくなるに連れて、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍを特定できる可能性が低くなる。よって、前記検索集合Ｂを復元して前記検索情報ｔの解読される可能性が低くなるため、安全性が高くなる。しかしながら、この場合、前記データベースサーバＤＳに記憶された前記秘匿登録情報Ｒ_１〜Ｒ_Ｎが前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭであるか否かを判別するための前記要素数‖Ｑ_ｊ ^＊‖（ｊ＝１，２，…，Ｎ）の判別値（ｃ−Ｌ）の値が小さくなる。このため、前記類似情報ｔ′が復元できる可能性が低いにも関わらず、前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭとして検出される個数が多くなる可能性が高くなる（自然数Ｍの値が大きくなる可能性が高くなる）。例えば、Ｌ＝ｃとした場合、（ｃ−Ｌ）＝０が成立し、前記データベースサーバＤＳに記憶された全ての前記秘匿登録情報Ｒ_１〜Ｒ_Ｎが前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＮとして検出されてしまう。
すなわち、前記自然数Ｌの値が大きくなるに連れて、前記秘匿検索情報（検索部分集合Ｂ^＊の安全性は高くなるが、誤検出が多くなり類似情報検索処理としての処理効率が低下する。

逆に、前記自然数Ｌの値が小さくなるに連れて、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍを特定できる可能性が高くなり、前記検索情報ｔの解読される可能性が高くなるため、安全性が低くなる。しかしながら、この場合、前記判別値（ｃ−Ｌ）の値が小さくなる。このため、前記類似情報ｔ′が復元できる可能性が低い前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭが検出される可能性が低くなる。例えば、Ｌ＝０とした場合、（ｃ−Ｌ）＝ｃが成立し、Ｑ_ｊ ^＊＝Ｑ_ｊ（ｊ＝１，２，…，Ｎ）が常に成立する前記候補多項式点集合Ｒ_Ａ１〜Ｒ_ＡＭが検出される。
すなわち、前記自然数Ｌの値が小さくなるに連れて、前記秘匿検索情報（検索部分集合Ｂ^＊の安全性は低くなるが、誤検出が低減され類似情報検索処理としての処理効率が向上する。
この結果、実施例１の前記類似情報検索システムＳでは、前記自然数Ｌの値に基づいて、前記安全性と前記処理効率とを調節することができる。

（登録情報の偏りに基づく攻撃に対する類似情報検索システムＳの安全性について）
また、前記構成を備えた実施例１の前記類似情報検索システムＳでは、例えば、前記登録情報ｓに文字列としての偏り、すなわち、文字列中の文字やｑ−ｇｒａｍの出現頻度に偏りが存在する場合がある。この場合、前記第三者や前記管理人が、前記偏りに基づいて、前記係数ｓ_０〜ｓ_ｋ−１を推測したり、前記登録数値ａ_１〜ａ_ｎや擬似数値ａ_ｎ＋１〜ａ_ｒを推測したり、これらの推測を組み合わせたりすることにより、総当りで前記多項式ｆ（ｘ）を復元する場合に比べ、前記多項式ｆ（ｘ）となる候補の多項式を絞り込むことができる可能性がある。

ここで、例えば、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}に偏りが存在しても、前記係数ｓ_０〜ｓ_ｋ−１（ｓ_０，ｓ_１，…，ｓ_ｋ−１∈Ｆ^ｋ）の分布が前記ｋ次拡大体Ｆ^ｋ内で一様となるように前記可逆関数Ｔを設定することにより、前記秘匿登録情報（多項式点集合Ｒ）が解読される可能性が低くなる。すなわち、前記部分文字列ｓ_ｋ（１）〜ｓ_{ｋ（ｋ−１）}と、前記係数ｓ_０〜ｓ_ｋ−１との相関性が低減されることにより、前記係数ｓ_０〜ｓ_ｋ−１が推測され難くなり、前記秘匿登録情報（多項式点集合Ｒ）の安全性が高くなる。また、例えば、前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎに偏りが存在しても、前記登録数値ａ_１〜ａ_ｎ（ａ_１，ａ_２，…，ａ_ｎ∈Ｆ^ｎ）の分布が前記ｎ次拡大体Ｆ^ｎ内で一様となるように前記ハッシュ関数Ｈを設定することにより、前記秘匿登録情報（多項式点集合Ｒ）が解読される可能性が低くなる。すなわち、前記登録部分情報ｓ_ｑ１〜ｓ_ｑｎと、前記登録数値ａ_１〜ａ_ｎとの相関性が低減されることにより、前記登録数値ａ_１〜ａ_ｎが推測され難くなり、前記秘匿登録情報（多項式点集合Ｒ）の安全性が高くなる。
この結果、実施例１の前記類似情報検索システムＳでは、前記各関数Ｔ，Ｈが各出力値ｓ_０〜ｓ_ｋ−１，ａ_１〜ａ_ｎを一様に分布させる能力、いわゆる、前記各関数Ｔ，Ｈの一様分布性に基づいて、前記秘匿登録情報（多項式点集合Ｒ）の安全性を高くすることができる。

また、例えば、前記第三者や前記管理人が、前記偏りに基づいて、前記登録情報ｓの一部のｑ−ｇｒａｍ等の情報を解読して、前記情報に前記検索情報ｔと同程度の類似度を有する情報、すなわち、前記編集距離ｄが最大値ｄ_ｍａｘ以下となる情報を作成して、前記登録情報ｓを解読しようとする可能性がある。

ここで、例えば、前記データベースサーバＤＳを、糖転移酵素や糖鎖修飾酵素等の糖鎖合成関連遺伝子、いわゆる、糖鎖遺伝子が前記登録情報ｓとして格納される糖鎖遺伝子データベース（ＧＧＤＢ：GlycoGene DataBase）とした場合、前記糖鎖遺伝子の種類が約３００種類となり、前記糖鎖遺伝子の平均配列長が既知のものに限れば約１２００塩基対（bp：base pair）となることが知られている。すなわち、前記データベースサーバＤＳを前記糖鎖遺伝子データベースとした場合には、Ｎ＝３００，ｎ＝１２００となることが知られている。なお、前記糖鎖遺伝子データベースについては、例えば、非特許文献９等に記載されており、公知である。
よって、前記偏りが存在しないものとした場合に、一遺伝子あたりの平均文字列空間の大きさ、すなわち、前記一遺伝子の文字列表現の数が、以下の数１の式（１０）により示された値以上となる。

…（１０）

なお、前記式（１０）における分子の底の値（４）は、塩基の種類数（「Ａ」、「Ｔ」、「Ｇ」、「Ｃ」）であり、分母の第２項（Σ演算子付きの項）は、前記編集距離ｄが最大値ｄ_ｍａｘ以下になる文字列の数（類似文字列の上限値）である。
よって、例えば、ｄ_ｍａｘ＝１００とした場合に、前記式（１０）により示された値は、約２^１７００（２^１７００≒２^２４００／２^７００）となり、前記秘匿登録情報（多項式点集合Ｒ）の安全性は、約１７００ビット以上の鍵の安全性に相当することがわかる。この結果、前記偏りが存在しても、最大で約１７００ビット以上の鍵の安全性を確保することができ、前記秘匿登録情報（多項式点集合Ｒ）の安全性を十分に確保できる。
したがって、実施例１の前記類似情報検索システムＳでは、前記自然数ｎ，Ｎの値および前記最大値ｄ_ｍａｘ，に基づいて、前記秘匿登録情報（多項式点集合Ｒ）の安全性を調節することができる。

（変更例）
以上、本発明の実施例を詳述したが、本発明は、前記実施例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内で、種々の変更を行うことが可能である。本発明の変更例（Ｈ01）〜（Ｈ011）を下記に例示する。
（Ｈ01）前記実施例の前記類似情報検索システムＳでは、前記各クライアントパソコンＰＣａ，ＰＣｂと、前記データベースサーバＤＳとを別体で構成したが、これに限定されず、例えば、前記各クライアントパソコンＰＣａ，ＰＣｂを一体的に構成したり、前記各クライアントパソコンＰＣａ，ＰＣｂおよび前記データベースサーバＤＳを一体的に構成することも可能である。

（Ｈ02）前記実施例では、前記インターネット１を介して、前記各クライアントパソコンＰＣａ，ＰＣｂと、前記データベースサーバＤＳとが情報の送受信が可能に接続されているが、これに限定されず、例えば、専用線や、有線・無線のＬＡＮ（Local Area Network、構内通信網）環境や、暗号通信網等のその他の通信回線を介して接続されることも可能である。なお、前記通信回線として、前記専用線や、前記暗号通信網等を使用した場合には、前記第三者や前記管理者が前記各情報ｓ，ｔ，ｔ′を解読し難くなる可能性がある。すなわち、内部解析（リバース・エンジニアリング）や改変に対する防護力、いわゆる、耐タンパ性が高くなる可能性がある。
（Ｈ03）前記実施例では、前記秘匿類似情報（解候補集合Ｒ_Ａ）の復元する前記秘匿類似情報復元処理（図５のＳＴ２１１、図８のＳＴ４０１〜ＳＴ４１１参照）を、前記検索用クライアントパソコンＰＣｂで実行して、前記類似情報ｔ′を前記第三者や前記管理者に取得されないようにしているが、これに限定されず、例えば、通信回線として前記専用線や前記暗号通信網等を使用して、前記耐タンパ性が高くなった場合には、前記秘匿類似情報復元処理を、前記データベースサーバＤＳで実行して、復元された前記類似情報ｔ′を前記検索用クライアントパソコンＰＣｂに送信することも可能である。

（Ｈ04）前記実施例において、設定された各数値については、前記安全性（厳格性、機密性、秘匿性）、前記処理効率、前記利便性等の条件・仕様・設計等に応じて、任意の数値に変更可能である。例えば、実施例１のように、ｒ＞ｎとして、前記チャフ（擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ）））を含む前記秘匿登録情報（多項式点集合Ｒ）を演算して、前記秘匿登録情報（多項式点集合Ｒ）の安全性を確保することが好ましいが、ｒ＝ｎとして、前記多項式点集合Ｒを、前記チャフを含まない前記（ｎ，ｋ）符号の符号語（登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））のみの集合）とすることも可能である。また、Ｌ＞０として、Ｌ種類の検索数値ｂ_{ｍ−Ｌ＋１}〜ｂ_ｍが除かれた前記秘匿検索情報（検索部分集合Ｂ^＊）を演算して、前記秘匿検索情報（検索部分集合Ｂ^＊）の安全性を確保することが好ましいが、Ｌ＝０として、前記検索部分集合Ｂ^＊を、前記検索集合Ｂそのものとすることも可能である（Ｂ^＊＝Ｂ）。なお、この場合、通信回線として前記専用線や前記暗号通信網等を使用し、前記耐タンパ性を高くしておくことが好ましい。
（Ｈ05）本発明において、一方向関数の一例としての前記ハッシュ関数Ｈにより、前記数値ａ_１〜ａ_ｎ，ｂ_１〜ｂ_ｍから前記各部分情報ｓ_ｑ１〜ｓ_ｑｎ，ｔ_ｑ１〜ｔ_ｑｍを復元して、前記各情報ｓ，ｔをできないようにすることが好ましいが、これに限定されず、例えば、前記秘匿登録情報（多項式点集合Ｒ）の安全性等に応じて、前記ハッシュ関数Ｈを双方向関数の一例としての可逆関数等に変更することも可能である。

（Ｈ06）前記実施例では、前記各情報ｓ，ｔ，ｔ′が、文字列情報により構成されているが、これに限定されず、例えば、順序付き木や、順序無し木、グラフ等の情報により構成することも可能である。ここで、順序付き木の情報とは、前記各情報ｓ，ｔ，ｔ′を、分岐の始点となる節点である根節点と、前記分岐の終点となる節点である葉節点と、前記根節点と前記葉節点との間に設けられた節点である内部節点と、前記根節点と前記内部節点と前記葉節点とを連結する枝となる前記分岐の情報により構成され、且つ、前記各分岐にはそれぞれ順序が付けられた情報のことである。また、順序無し木の情報とは、前記順序付き木の情報に比べ、前記各分岐には順序が付けられていない情報のことである。
これらの情報については、前記情報の構造に基づくヒストグラム（histogram、度数分布図、柱状グラフ）を演算した場合には、前記ヒストグラム間の距離（L₁ distance、Ｌ_１距離）に基づいて、解候補のフィルタリング処理を行うことができる。

例えば、順序付き木の情報は、前記根節点および前記内部節点から分岐する枝が２本に限定され、且つ、前記根節点から前記葉節点まで到達するまでの前記分岐の回数である高さが全て同一となる順序付きの完全二分木の構造の情報である順序付完全二分木構造情報に変換することにより、前記順序付完全二分木構造情報を、ｑ−ｌｅｖｅｌ二分岐の情報（操作単位情報）のヒストグラムのベクトル表現により示すことができる。なお、前記ｑ−ｌｅｖｅｌ二分岐とは、前記完全二分木の一部の前記節点と前記節点どうしを連結する枝となる前記分岐の情報とにより構成された部分木の構造の情報である部分木構造情報であって、前記部分木における前記高さが（ｑ−１）となる前記部分木構造情報をいう。また、前記ｑ−ｌｅｖｅｌ二分岐の情報のヒストグラムとは、前記完全二分木における同じ前記ｑ−ｌｅｖｅｌ二分岐の情報の出現頻度のことをいう。

ここで、２つの前記順序付完全二分木構造情報をＵ，Ｖとし、前記ｑ−ｌｅｖｅｌ二分岐の情報のヒストグラムの種類数（ベクトル空間の大きさ）を｜ΓＵ｜，｜ΓＶ｜とし、前記ｑ−ｌｅｖｅｌ二分岐の情報のヒストグラムをｕ_１〜ｕ_｜ΓＵ｜，ｖ_１〜ｖ_｜ΓＶ｜として、Ｕ＝（ｕ_１，ｕ_２，…，ｕ_｜ΓＵ｜），Ｖ＝（ｖ_１，ｖ_２，…，ｖ_｜ΓＶ｜）が成立するものとした場合に、前記Ｌ_１距離は、前記順序付完全二分木構造情報Ｕ，Ｖ間のベクトル距離になる。よって、前記Ｌ_１距離に基づいて、順序付完全二分木構造情報Ｕ，Ｖどうしが類似であるか否かを判別することができる。すなわち、解候補のフィルタリング処理を行うことができる。

なお、これらの情報のヒストグラム間のＬ_１距離に基づいて、解候補のフィルタリング処理を行う秘匿化なしの類似情報検索処理については、例えば、非特許文献１０〜１２に記載されており、公知である。また、前記順序付き木の情報を変換した前記順序付完全二分木構造情報Ｕ，Ｖについて、前記順序付完全二分木構造情報Ｕ，Ｖ間の編集距離をｄとした場合に、前記順序付完全二分木構造情報Ｕ，Ｖ間のＬ_１距離が｛４×（ｑ−１）＋１｝×ｄとなることが知られている（例えば、非特許文献１０等参照）。ここで、前記編集距離ｄとは、前記順序付完全二分木構造情報Ｖが、前記順序付完全二分木構造情報Ｕになるまでの前記ｑ−ｌｅｖｅｌ二分岐の情報の挿入・削除・置換の各編集操作の回数のことである。

よって、前記フィルタリング処理の条件となる前記Ｌ_１距離を、前記ファジーボールトの開錠処理のフィルタリング条件とすることにより、秘匿化された類似情報検索処理を実行することが可能である。例えば、順序付き木の情報は、前記順序付完全二分木構造情報Ｕ，Ｖに基づいて、前記各集合Ａ，Ｂを演算し、前記秘匿登録情報（多項式点集合Ｒ）や前記秘匿検索情報（検索部分集合Ｂ^＊）を演算することができる。なお、前記完全二分木構造情報Ｕ，Ｖが有する前記節点の個数、例えば、｜Ｕ｜，｜Ｖ｜とし、｜ΓＵ｜＝ｎ，｜ΓＶ｜＝ｍ，ｎ≧ｍが成立するものとし、前記自然数ｃ，ｋについて以下の式（１１），（１２）が成立する場合には、以下の式（１３）が成立する。

ｃ＝ｎ−｛４×（ｑ−１）＋１｝×ｄ …（１１）
（ｎ＋ｋ）／２＝ｎ−｛４×（ｑ−１）＋１｝×ｄ_ｍａｘ …（１２）
‖Ｑ_ｊ‖≧ｃ
＝ｎ−｛４×（ｑ−１）＋１｝×ｄ
≧ｎ−｛４×（ｑ−１）＋１｝×ｄ_ｍａｘ
＝（ｎ＋ｋ）／２ …（１３）

すなわち、ｃ≧（ｎ＋ｋ）／２が常に成立するため（式（７）参照）、前記実施例と同様に、前記次数（ｋ−１）を設定して前記多項式ｆ（ｘ）を演算できると共に、前記判別値ｃに基づいて、秘匿化されたフィルタリング処理を実行できる（図７のＳＴ３０８、図８のＳＴ４０６参照）。この結果、実施例１の前記類似情報検索システムＳと同様に、前記自然数ｃ，ｄ，ｋ，Ｌ，ｎ，ｍ，ｑ，ｒの各値に基づいて、前記秘匿類似情報検索処理（図７のＳＴ３０３〜ＳＴ３１２参照）を実行することができる。

（Ｈ07）本発明において、前記各情報ｓ，ｔを入力するための前記各画像２，３を表示することが好ましいが、これに限定されず、例えば、コマンド入力等により前記各情報ｓ，ｔを入力することにより、前記各画像２，３を省略することも可能である。
（Ｈ08）前記実施例では、前記誤り訂正符号の復号化アルゴリズムの一例としてのＢＭアルゴリズムを用いた前記開錠処理により、前記多項式ｆ（ｘ）の係数ｓ_０〜ｓ_ｋ−１を演算して前記類似情報ｔ′を復元するが（図８のＳＴ４１０参照）、これに限定されず、例えば、前記誤り訂正符号の復号化アルゴリズムの一例としてのピーターソン（Perterson）法やユークリッド法を用いた開錠処理により、前記類似情報ｔ′を復元することも可能である（例えば、特開２００３−１６８９８３号公報や非特許文献６等参照）。

（Ｈ09）本発明において、前記自然数ｃ，ｄ，ｋ，Ｌ，ｎ，ｍ，ｑ，ｒの各値について、予め設定されているか、前記各情報ｓ，ｔ，ｔ′に基づいて自動的に設定されているが、これに限定されず、ユーザが各画像３，４等により設定できるようにすることも可能である。例えば、前記編集距離ｄの最大値ｄ_ｍａｘについて、前記検索画像４に最大値入力部を設けて、前記検索者が設定できるようにすることも可能である。
（Ｈ010）本発明において、前記登録情報ｓに基づいて、前記登録情報ｓを復元するために必要な点が最小で｛（ｎ＋ｋ）／２｝個となることが保証された（ｋ−１）次元で１変数の多項式ｆ（ｘ）を演算されることが好ましいが（図５のＳＴ１０７参照）、これに限定されず、例えば、｛（ｎ＋ｋ）／２｝個存在しても前記登録情報ｓを復元できない多項式を演算することも可能である。この場合、前記多項式ｆ（ｘ）として選択できる多項式の総数も大きくすることができ、前記利便性や前記安全性が高くなるが、前記類似情報ｔ′を復元可能か否かを判別するフィルタリング処理（図７のＳＴ３０８、図８のＳＴ４０６参照）の精度が低減されるため、誤検出が多くなり類似情報検索処理としての処理効率が低下する可能性がある。このため、前記多項式ｆ（ｘ）における復元可能な点の個数を、前記利便性と前記安全性と、前記フィルタリング処理の精度に基づく前記処理効率とを、前記類似情報検索システムＳの許容範囲に応じて調節することができる。

（Ｈ011）本発明において、前記登録情報ｓに基づいて、前記登録情報ｓを復元するために必要な点が｛（ｎ＋ｋ）／２｝個以上となる（ｋ−１）次元で１変数の多項式ｆ（ｘ）を演算したが（図５のＳＴ１０７参照）、これに限定されず、例えば、｛（ｎ＋ｋ）／２｝個以下で前記登録情報ｓを復元可能であることが保証された多項式が存在すれば、そのような前記多項式を演算することも可能である。すなわち、前記誤り訂正符号として、｛（ｎ＋ｋ）／２｝個以上の点が判明すれば前記ＢＭアルゴリズム等により多項式の復元可能な前記（ｎ，ｋ）符号（（ｎ，ｋ）ＲＳ符号）を利用することに限定されず、｛（ｎ＋ｋ）／２｝個以下の点により多項式の復元可能なその他の前記誤り訂正符号を利用することも可能である。この場合、解読するために知得する必要がある前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））の数が少なくなるため、前記多項式点集合Ｒの安全性が低下するが、前記多項式点集合Ｒに含まれる前記登録多項式点（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））の総数ｒの値を大きくして、前記擬似多項式点（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））の総数を増加させることにより、前記安全性を確保することができる。

本発明は、例えば、登録する情報がＤＮＡの塩基配列情報（核酸配列情報）や、蛋白質のアミノ酸配列情報等の遺伝子情報が格納された遺伝子情報データベースの管理業務を、遺伝子解析の分野における研究機関等が外部委託業者に委託するＤＡＳモデルを構築する場合に有用である。

図１は本発明の実施例１の類似情報検索システムの全体説明図である。 図２は本発明の実施例１の類似情報検索システムを構成する各装置の機能をブロック図（機能ブロック図）で示した説明図である。 図３は実施例１の登録画像の説明図である。 図４は実施例１の登録画像の説明図である。 図５は実施例１の秘匿登録情報送信プログラムの秘匿登録情報送信処理のフローチャートである。 図６は実施例１の秘匿検索情報送信プログラムの秘匿検索情報送信処理のフローチャートである。 図７は実施例１の秘匿類似情報検索プログラムの秘匿類似情報検索処理のフローチャートである。 図８は実施例１の秘匿類似情報復元プログラムの秘匿類似情報復元処理のフローチャートであり、図６のＳＴ２１１のサブルーチンの説明図である。 図９はＤＡＳモデルにおける遺伝子情報データベースに従来公知の暗号化データベースの技術を適用した場合の説明図である。

符号の説明

Ａ…登録集合、ＡＰ４…類似情報検索プログラム、ａ_１〜ａ_ｎ…登録数値、ａ_ｎ＋１〜ａ_ｒ…擬似数値、（ａ_１，ｆ（ａ_１））〜（ａ_ｎ，ｆ（ａ_ｎ））…多項式上の点、登録多項式点、（ａ_ｎ＋１，ｆ′（ａ_ｎ＋１））〜（ａ_ｒ，ｆ′（ａ_ｒ））…擬似多項式点、Ｂ…検索集合、Ｂ^＊…検索部分集合、秘匿検索情報、ｂ_１〜ｂ_ｍ…検索数値、ｃ，ｄ，ｋ，Ｌ，ｎ，ｍ，ｑ，ｒ…自然数、ＣＡ３…多項式演算手段、ＣＡ４…登録部分情報抽出手段、ＣＡ５…登録集合演算手段、ＣＡ６…登録代入値演算手段、ＣＡ７…擬似数値演算手段、ＣＡ８…擬似代入値演算手段、ＣＡ９…秘匿登録情報演算手段、ＣＡ10…秘匿登録情報送信手段、ＣＢ３…検索部分情報抽出手段、ＣＢ４…検索集合演算手段、ＣＢ５…検索集合記憶手段、ＣＢ６…秘匿検索情報演算手段、ＣＢ７…秘匿検索情報送信手段、ＣＢ９…秘匿類似情報受信手段、ＣＢ10A…検索数値判別手段、ＣＢ10B…数値抽出手段、ＣＢ11A…類似情報復元判別手段、ＣＢ12…類似情報復元手段、ＣＤ１…秘匿登録情報受信手段、ＣＤ２…秘匿登録情報記憶手段、ＣＤ３…秘匿検索情報受信手段、ＣＤ４…検索数値判別手段、ＣＤ５…多項式点部分集合演算手段、ＣＤ６…多項式点部分集合要素数判別手段、ＣＤ７…秘匿類似情報演算手段、ＣＤ８…秘匿類似情報送信手段、ＤＳ…記憶装置、類似情報検索装置、ｆ（ｘ）…多項式、ｆ（ａ_１），ｆ（ａ_２），…，ｆ（ａ_ｎ）…登録代入値、ｆ′（ａ_ｎ＋１）〜ｆ′（ａ_ｒ）…擬似代入値、ＰＣａ…登録装置、ＰＣｂ…検索装置、Ｑ_１ ^＊〜Ｑ_Ｎ ^＊…多項式点部分集合、Ｒ…多項式点集合、秘匿登録情報、Ｒ_Ａ…秘匿類似情報、Ｈ…一方向関数、Ｓ…類似情報検索システム、ｓ…登録情報、文字列情報、ｓ_ｑ１〜ｓ_ｑｎ…登録部分情報、部分情報、ｔ…検索情報、文字列情報、ｔ_ｑ１〜ｔ_ｑｍ…検索部分情報、部分情報、ｔ′…類似情報、文字列情報。

Claims (4)

1. 登録対象の情報である登録情報を記憶する記憶装置と、
   前記記憶装置と情報の送受信が可能に接続され、前記記憶装置に対して、前記登録情報を登録させる登録装置と、
   前記記憶装置と情報の送受信が可能に接続され、前記記憶装置に対して、記憶された前記登録情報のうち、検索対象の情報である検索情報と同一または類似する前記登録情報である類似情報を検索させる検索装置と、
   を有する類似情報検索システムであって、
   自然数をそれぞれｃ，ｄ，ｋ，Ｌ，ｎ，ｍ，ｑ，ｒとし、前記検索情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であり、且つ、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌ，ｒ≧ｎがそれぞれ成立するものとした場合に、
   前記登録装置は、
   前記登録情報に基づいて、（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式を演算する多項式演算手段と、
   前記登録情報に基づいて、前記登録情報を復元可能なｎ個の前記部分情報である登録部分情報を抽出する登録部分情報抽出手段と、
   抽出されたｎ個の前記登録部分情報に基づいて、ｎ種類の数値である登録数値を要素とする集合である登録集合を演算する登録集合演算手段と、
   前記登録数値が代入された前記多項式の数値である登録代入値を演算する登録代入値演算手段と、
   前記登録数値以外の数値である（ｒ−ｎ）種類の擬似数値を演算する擬似数値演算手段と、
   前記擬似数値が代入された前記多項式の数値以外の数値である擬似代入値を演算する擬似代入値演算手段と、
   前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、前記擬似数値および前記擬似数値に対応する前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を演算することにより、前記登録情報が秘匿化された秘匿登録情報を演算する秘匿登録情報演算手段と、
   演算された前記秘匿登録情報を、前記記憶装置に対して送信する秘匿登録情報送信手段と、
   を有し、
   前記記憶装置は、
   前記秘匿登録情報送信手段により送信された前記秘匿登録情報を受信する秘匿登録情報受信手段と、
   受信した前記秘匿登録情報を記憶する秘匿登録情報記憶手段と、
   を有し、
   前記検索装置は、
   前記検索情報に基づいて、前記検索情報を復元可能なｍ個の前記部分情報である検索部分情報を抽出する検索部分情報抽出手段と、
   抽出されたｍ個の前記検索部分情報に基づいて、ｍ種類の数値である検索数値を要素とする集合である検索集合を演算する検索集合演算手段と、
   演算された前記検索集合を記憶する検索集合記憶手段と、
   ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を演算することにより、前記検索情報が秘匿化された秘匿検索情報を演算する秘匿検索情報演算手段と、
   演算された前記秘匿検索情報を、前記記憶装置に対して送信する秘匿検索情報送信手段と、
   を有し、
   前記記憶装置は、
   前記秘匿検索情報送信手段により送信された前記秘匿検索情報を受信する秘匿検索情報受信手段と、
   受信した前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
   前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段と、
   演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段と、
   （ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段と、
   演算された前記秘匿類似情報を、前記検索装置に対して送信する秘匿類似情報送信手段と、
   を有し、
   前記検索装置は、
   前記秘匿類似情報送信手段により送信された前記秘匿類似情報を受信する秘匿類似情報受信手段と、
   記憶した前記検索集合に含まれる前記検索数値が、受信した前記各秘匿類似情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
   前記検索数値と同値となる前記登録数値および前記擬似数値を抽出する数値抽出手段と、
   抽出された前記登録数値および前記擬似数値がｃ個以上であるか否かを判別することにより、前記各秘匿類似情報が、前記検索情報に対する前記類似情報として復元可能であるか否かを判別する類似情報復元判別手段と、
   抽出された前記登録数値および前記擬似数値がｃ個以上である場合に、前記登録数値および前記擬似数値に基づいて、前記多項式を演算して前記類似情報を復元する類似情報復元手段と、
   を有する
   ことを特徴とする類似情報検索システム。
2. 前記自然数ｃ，ｋ，ｎについて、ｃ≧（ｎ＋ｋ）／２が成立するものとした場合に、
   前記登録装置は、
   前記登録情報に基づいて、（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元するために必要な前記多項式上の点が｛（ｎ＋ｋ）／２｝個以上となる前記多項式を演算する多項式演算手段と、
   を有する
   ことを特徴とする請求項１に記載の類似情報検索システム。
3. 登録対象の情報を登録情報とし、
   前記登録情報と同一または類似する情報を類似情報とし、
   自然数をそれぞれｄ，ｋ，ｎ，ｑ，ｒとし、
   前記登録情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記登録情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、ｒ≧ｎが成立するものとし、
   前記登録情報に基づいて抽出された前記登録情報を復元可能なｎ個の前記部分情報を登録部分情報とし、
   抽出されたｎ個の前記登録部分情報に基づいて演算されたｎ種類の数値である登録数値を要素とする集合を登録集合とし、
   前記登録情報に基づいて演算された（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式に前記登録数値が代入されて演算された数値を登録代入値とし、
   前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、
   前記登録数値以外の数値である擬似数値および前記擬似数値に対応する擬似代入値であって、前記擬似数値が代入された前記多項式の数値以外の数値である前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、
   ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を、前記登録情報が秘匿化された秘匿登録情報として記憶する秘匿登録情報記憶手段と、
   検索対象の情報を検索情報とし、
   自然数をそれぞれｃ，Ｌ，ｍとし、
   前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であり、且つ、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌがそれぞれ成立するものとし、
   前記検索情報のうちの前記操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記検索情報に基づいて抽出された前記検索情報を復元可能なｍ個の前記部分情報を検索部分情報とし、
   抽出されたｍ個の前記検索部分情報に基づいて演算されたｍ種類の数値である検索数値を要素とする集合を検索集合とし、
   ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を、前記検索情報が秘匿化された秘匿検索情報とした場合に、
   前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段と、
   前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段と、
   演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段と、
   （ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段と、
   を備えたことを特徴とする類似情報検索システム。
4. コンピュータを、
   登録対象の情報を登録情報とし、
   前記登録情報と同一または類似する情報を類似情報とし、
   自然数をそれぞれｄ，ｋ，ｎ，ｑ，ｒとし、
   前記登録情報のうちの操作対象となる単位の情報である操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記登録情報が前記類似情報に変換され、且つ、前記登録情報について、ｑ個の前記操作単位情報を有する部分情報をｎ個以上演算可能であり、且つ、ｒ≧ｎが成立するものとし、
   前記登録情報に基づいて抽出された前記登録情報を復元可能なｎ個の前記部分情報を登録部分情報とし、
   抽出されたｎ個の前記登録部分情報に基づいて演算されたｎ種類の数値である登録数値を要素とする集合を登録集合とし、
   前記登録情報に基づいて演算された（ｋ−１）次元で１変数の多項式であって、前記登録情報を復元可能な前記多項式に前記登録数値が代入されて演算された数値を登録代入値とし、
   前記登録数値および前記登録数値に対応する前記登録代入値を一組とする前記多項式上の点を登録多項式点とし、
   前記登録数値以外の数値である擬似数値および前記擬似数値に対応する擬似代入値であって、前記擬似数値が代入された前記多項式の数値以外の数値である前記擬似代入値を一組とする前記多項式以外の点を擬似多項式点とした場合に、
   ｎ個の前記登録多項式点と、（ｒ−ｎ）個の前記擬似多項式点とを有するｒ個の点の集合である多項式点集合を、前記登録情報が秘匿化された秘匿登録情報として記憶する秘匿登録情報記憶手段、
   検索対象の情報を検索情報とし、
   自然数をそれぞれｃ，Ｌ，ｍとし、
   前記検索情報について、ｑ個の前記操作単位情報を有する部分情報をｍ個以上演算可能であれば、ｃがｄ，ｑ，ｎ，ｍに基づいて演算され、且つ、ｃ≧Ｌ，ｍ≧Ｌがそれぞれ成立するものとし、
   前記検索情報のうちの前記操作単位情報について、ｄ回の挿入・削除・置換の操作を行うことにより、前記検索情報が前記類似情報に変換され、且つ、前記検索情報に基づいて抽出された前記検索情報を復元可能なｍ個の前記部分情報を検索部分情報とし、
   抽出されたｍ個の前記検索部分情報に基づいて演算されたｍ種類の数値である検索数値を要素とする集合を検索集合とし、
   ｍ種類の前記検索数値のうち、Ｌ種類の前記検索数値を除く（ｍ−Ｌ）種類の前記検索数値を要素とする前記検索集合の部分集合である検索部分集合を、前記検索情報が秘匿化された秘匿検索情報とした場合に、
   前記秘匿検索情報に含まれる前記検索数値が、記憶した前記各秘匿登録情報に含まれる前記登録数値または前記擬似数値と同値であるか否かを判別する検索数値判別手段、
   前記検索数値と同値となる前記登録数値の前記登録多項式点および前記擬似数値の前記擬似多項式点を抽出することにより、前記多項式点集合における前記検索数値の射影集合であって、前記多項式点集合の部分集合である多項式点部分集合を演算する多項式点部分集合演算手段、
   演算された前記多項式点部分集合の点が（ｃ−Ｌ）個以上であるか否かを判別する多項式点部分集合要素数判別手段、
   （ｃ−Ｌ）個以上の点を有する前記多項式点部分集合に対応する前記各秘匿登録情報を演算することにより、前記類似情報が秘匿化された秘匿類似情報を演算する秘匿類似情報演算手段、
   として機能させることを特徴とする類似情報検索プログラム。