(57)【特許請求の範囲】
【請求項１】
サービス提供者サーバ、ユーザ端末および判定サーバを有する判定システムにおける暗号化値判定方法であって、
前記サービス提供者サーバは、
（ａ０）暗号化すべき値が所定のグループに属する値である第１の値か、前記グループには属さない値である第２の値かを判定し、
（ａ１）前記第１の値に対しては、第１の暗号鍵による暗号化処理を行って、第１の暗号化値を算出し、
（ａ２）前記第１の暗号化値に対し、第２の暗号鍵による第２の暗号化処理を行って、第２の暗号化値を算出し、前記第１の値と、前記第２の暗号化値と、を含んだ判定用データを、記憶部に格納し、
（ａ３）前記第２の値に対しては、ランダムな値を第２の暗号化値として算出し、当該第２の値と、当該第２の暗号化値と、を含んだ判定用データを、前記記憶部に格納し、
（ａ４）前記判定用データと、前記第１の暗号鍵を前記ユーザ端末へ送信し、
（ａ５）前記第２の暗号鍵を、前記判定サーバへ送信し、
前記ユーザ端末は、
（ａ６）入力部を介して任意の値が入力されると、前記任意の値に対し、前記第１の暗号鍵による暗号化処理を行って、第３の暗号化値を算出し、
（ａ７）前記任意の値が前記第１の値に該当する場合、前記サービス提供者サーバより送信された前記第１の値における前記判定用データから前記第１の値に対応する前記第２の暗号化値を取得し、前記任意の値が前記第２の値に該当する場合、前記サービス提供者サーバより送信された前記第２の値における前記判定用データから前記第２の値に対応する前記第２の暗号化値を取得し、
（ａ９）前記第３の暗号化値と、当該取得した第２の暗号化値と、を対とした通信データを前記判定サーバへ送信し、
前記判定サーバは、
（ａ１０）前記ユーザ端末から送信された第２の暗号化値を、前記第２の暗号鍵を用いて、復号化した復号値を算出し、
（ａ１１）前記復号値と、前記第３の暗号化値と、が一致するか否かを判定し、該判定結果を前記サービス提供者サーバへ送信する
ことを特徴とする暗号化値判定方法。
【請求項２】
前記第１の値は、所定のしきい値を超えていない値であり、前記第２の値は、所定のしきい値を超えている値であり、
前記サービス提供者サーバは、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ａ０）〜（ａ５）の処理を行い、
前記ユーザ端末は、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記判定サーバは、
前記しきい値から１減算した値である減算しきい値を前記しきい値として、
前記桁毎に、
処理対象となっている桁に関する前記判定用データと、前記通信データと、を基に、前記（ａ１０）および（ａ１１）の処理を行う
ことを特徴とする請求項１に記載の暗号化値判定方法。
【請求項３】
前記第１の値は、所定のしきい値を超えている値であり、前記第２の値は、所定のしきい値を超えていない値であり、
前記サービス提供者サーバは、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ａ０）〜（ａ５）の処理を行い、
前記ユーザ端末は、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記判定サーバは、
前記しきい値から１減算した値である減算しきい値を前記しきい値として、
前記桁毎に、
処理対象となっている桁に関する前記判定用データと、前記通信データと、を基に、前記（ａ１０）および（ａ１１）の処理を行う
ことを特徴とする請求項１に記載の暗号化値判定方法。
【請求項４】
前記第１の値は、所定のしきい値を超えていない値であり、前記第２の値は、所定のしきい値を超えている値であり、
前記サービス提供者サーバは、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ａ０）〜（ａ５）の処理を行い、
前記ユーザ端末は、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記桁の値を１加算した後、
前記桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記判定サーバは、
前記桁毎に、
処理対象となっている桁に関し、前記加算を行っていない桁および前記加算した桁のそれぞれについての前記判定用データと、前記通信データと、を基に、前記（ａ１０）の処理を行った後、前記（ａ１１）の処理を行う
ことを特徴とする請求項１に記載の暗号化値判定方法。
【請求項５】
前記第１の値は、所定のしきい値を超えている値であり、前記第２の値は、所定のしきい値を超えていない値であり、
前記サービス提供者サーバは、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ａ０）〜（ａ５）の処理を行い、
前記ユーザ端末は、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記桁の値を１加算した後、
前記桁毎に、
前記（ａ６）〜（ａ９）の処理を行い、
前記判定サーバは、
前記桁毎に、
処理対象となっている桁に関し、前記加算を行っていない桁および前記加算した桁のそれぞれについての前記判定用データと、前記通信データと、を基に、前記（ａ１０）の処理を行った後、前記（ａ１１）の処理を行う
ことを特徴とする請求項１に記載の暗号化値判定方法。
【請求項６】
サービス提供者サーバ、ユーザ端末および判定サーバを有する判定システムにおける暗号化値判定方法であって、
前記サービス提供者サーバは、
（ｂ０）暗号化すべき値が所定のグループに属する値である第１の値か、前記グループには属さない値である第２の値かを判定し、
（ｂ１）前記第１の値に対しては、第１の暗号鍵による暗号化処理を行って、第１の暗号化値を算出し、
（ｂ２）前記第１の暗号化値に対し、準同型暗号である第２の暗号鍵による第２の暗号化処理を行って、第２の暗号化値を算出し、当該第１の値と、当該第２の暗号化値と、を含んだ判定用データを、記憶部に格納し、
（ｂ３）前記第２の値に対しては、ランダムな値を第２の暗号化値として算出し、当該第２の値と、当該第２の暗号化値と、を含んだ判定用データを、前記記憶部に格納し、
（ｂ４）前記判定用データと、前記第１の暗号鍵と、前記第２の暗号鍵を前記ユーザ端末へ送信し、
（ｂ５）前記第２の暗号鍵に対応する復号鍵を、前記判定サーバへ送信し、
前記ユーザ端末は、
（ｂ６）入力部を介して任意の値が入力されると、前記任意の値に対し、前記第１の暗号鍵による暗号化処理を行って、第３の暗号化値を算出し、
（ｂ７）前記任意の値が前記第１の値に該当する場合、前記サービス提供者サーバより送信された前記第１の値における前記判定用データから前記第１の値に対応する前記第２の暗号化値を取得し、前記任意の値が前記第２の値に該当する場合、前記サービス提供者サーバより送信された前記第２の値における前記判定用データから前記第２の値に対応する前記第２の暗号化値を取得し、
（ｂ９）乱数を生成し、
（ｂ１０）前記乱数に対し、前記第２の暗号鍵による前記第２の暗号化処理を行って乱数暗号値を算出し、
（ｂ１１）前記乱数を、前記第３の暗号化値に乗算した第４の暗号化値を算出し、
（ｂ１２）前記乱数暗号化値を、前記取得した第２の暗号化値に乗算した第５の暗号化値を算出し、
（ｂ１３）前記第４の暗号化値と、前記第５の暗号化値と、を対とした通信データを前記判定サーバへ送信し、
前記判定サーバは、
（ｂ１４）前記ユーザ端末から送信された第５の暗号化値を、前記復号鍵を用いて、復号化した復号値を算出し、
（ｂ１５）前記復号値と、前記第４の暗号化値と、が一致するか否かを判定し、該判定結果を前記サービス提供者サーバへ送信する
ことを特徴とする暗号化値判定方法。
【請求項７】
前記第１の値は、所定のしきい値を超えていない値であり、前記第２の値は、所定のしきい値を超えている値であり、
前記サービス提供者サーバは、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ｂ０）〜（ｂ５）の処理を行い、
前記ユーザ端末は、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記判定サーバは、
前記しきい値から１減算した値である減算しきい値を前記しきい値として、
前記桁毎に、
処理対象となっている桁に関する前記判定用データと、前記通信データと、を基に、前記（ｂ１４）および（ｂ１５）の処理を行う
ことを特徴とする請求項６に記載の暗号化値判定方法。
【請求項８】
前記第１の値は、所定のしきい値を超えている値であり、前記第２の値は、所定のしきい値を超えていない値であり、
前記サービス提供者サーバは、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ｂ０）〜（ｂ５）の処理を行い、
前記ユーザ端末は、
前記しきい値および前記しきい値から１減算した減算しきい値のそれぞれを前記しきい値として、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記判定サーバは、
前記しきい値から１減算した値である減算しきい値を前記しきい値として、
前記桁毎に、
処理対象となっている桁に関する前記判定用データと、前記通信データと、を基に、前記（ｂ１４）および（ｂ１５）の処理を行う
ことを特徴とする請求項６に記載の暗号化値判定方法。
【請求項９】
前記第１の値は、所定のしきい値を超えていない値であり、前記第２の値は、所定のしきい値を超えている値であり、
前記サービス提供者サーバは、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ｂ０）〜（ｂ５）の処理を行い、
前記ユーザ端末は、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記桁の値を１加算した後、
前記桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記判定サーバは、
前記桁毎に、
処理対象となっている桁に関し、前記加算を行っていない桁および前記加算した桁のそれぞれについての前記判定用データと、前記通信データと、を基に、前記（ｂ１４）の処理を行った後、前記（ｂ１５）の処理を行う
ことを特徴とする請求項６に記載の暗号化値判定方法。
【請求項１０】
前記第１の値は、所定のしきい値を超えている値であり、前記第２の値は、所定のしきい値を超えていない値であり、
前記サービス提供者サーバは、
前記第１の値および前記第２の値を２進数展開し、所定のビット毎に区切った桁毎に、前記（ｂ０）〜（ｂ５）の処理を行い、
前記ユーザ端末は、
前記任意の値を２進数展開し、所定のビット毎に区切った桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記桁の値を１加算した後、
前記桁毎に、
前記（ｂ６）〜（ｂ１３）の処理を行い、
前記判定サーバは、
前記桁毎に、
処理対象となっている桁に関し、前記加算を行っていない桁および前記加算した桁のそれぞれについての前記判定用データと、前記通信データと、を基に、前記（ｂ１４）の処理を行った後、前記（ｂ１５）の処理を行う
ことを特徴とする請求項６に記載の暗号化値判定方法。
【請求項１１】
サービス提供者サーバ、ユーザ端末および判定サーバを有する判定システムであって、
前記サービス提供者サーバは、
（ａ０）暗号化すべき値が所定のグループに属する値である第１の値か、前記グループには属さない値である第２の値かを判定し、
（ａ１）前記第１の値に対しては、第１の暗号鍵による暗号化処理を行って、第１の暗号化値を算出し、
（ａ２）前記第１の暗号化値に対し、第２の暗号鍵による第２の暗号化処理を行って、第２の暗号化値を算出し、前記第１の値と、前記第２の暗号化値と、を含んだ判定用データを、記憶部に格納し、
（ａ３）前記第２の値に対しては、ランダムな値を第２の暗号化値として算出し、当該第２の値と、当該第２の暗号化値と、を含んだ判定用データを、前記記憶部に格納し、
（ａ４）前記判定用データと、前記第１の暗号鍵を前記ユーザ端末へ送信し、
（ａ５）前記第２の暗号鍵を、前記判定サーバへ送信し、
前記ユーザ端末は、
（ａ６）入力部を介して任意の値が入力されると、前記任意の値に対し、前記第１の暗号鍵による暗号化処理を行って、第３の暗号化値を算出し、
（ａ７）前記任意の値が前記第１の値に該当する場合、前記サービス提供者サーバより送信された前記第１の値における前記判定用データから前記第１の値に対応する前記第２の暗号化値を取得し、前記任意の値が前記第２の値に該当する場合、前記サービス提供者サーバより送信された前記第２の値における前記判定用データから前記第２の値に対応する前記第２の暗号化値を取得し、
（ａ９）前記第３の暗号化値と、当該取得した第２の暗号化値と、を対とした通信データを前記判定サーバへ送信し、
前記判定サーバは、
（ａ１０）前記ユーザ端末から送信された第２の暗号化値を、前記第２の暗号鍵を用いて、復号化した復号値を算出し、
（ａ１１）前記復号値と、前記第３の暗号化値と、が一致するか否かを判定し、該判定結果を前記サービス提供者サーバへ送信する
ことを特徴とする判定システム。
【請求項１２】
サービス提供者サーバ、ユーザ端末および判定サーバを有する判定システムであって、
前記サービス提供者サーバは、
（ｂ０）暗号化すべき値が所定のグループに属する値である第１の値か、前記グループには属さない値である第２の値かを判定し、
（ｂ１）前記第１の値に対しては、第１の暗号鍵による暗号化処理を行って、第１の暗号化値を算出し、
（ｂ２）前記第１の暗号化値に対し、準同型暗号である第２の暗号鍵による第２の暗号化処理を行って、第２の暗号化値を算出し、当該第１の値と、当該第２の暗号化値と、を含んだ判定用データを、記憶部に格納し、
（ｂ３）前記第２の値に対しては、ランダムな値を第２の暗号化値として算出し、当該第２の値と、当該第２の暗号化値と、を含んだ判定用データを、前記記憶部に格納し、
（ｂ４）前記判定用データと、前記第１の暗号鍵と、前記第２の暗号鍵を前記ユーザ端末へ送信し、
（ｂ５）前記第２の暗号鍵に対応する復号鍵を、前記判定サーバへ送信し、
前記ユーザ端末は、
（ｂ６）入力部を介して任意の値が入力されると、前記任意の値に対し、前記第１の暗号鍵による暗号化処理を行って、第３の暗号化値を算出し、
（ｂ７）前記任意の値が前記第１の値に該当する場合、前記サービス提供者サーバより送信された前記第１の値における前記判定用データから前記第１の値に対応する前記第２の暗号化値を取得し、前記任意の値が前記第２の値に該当する場合、前記サービス提供者サーバより送信された前記第２の値における前記判定用データから前記第２の値に対応する前記第２の暗号化値を取得し、
（ｂ９）乱数を生成し、
（ｂ１０）前記乱数に対し、前記第２の暗号鍵による前記第２の暗号化処理を行って乱数暗号値を算出し、
（ｂ１１）前記乱数を、前記第３の暗号化値に乗算した第４の暗号化値を算出し、
（ｂ１２）前記乱数暗号化値を、前記取得した第２の暗号化値に乗算した第５の暗号化値を算出し、
（ｂ１３）前記第４の暗号化値と、前記第５の暗号化値と、を対とした通信データを前記判定サーバへ送信し、
前記判定サーバは、
（ｂ１４）前記ユーザ端末から送信された第５の暗号化値を、前記復号鍵を用いて、復号化した復号値を算出し、
（ｂ１５）前記復号値と、前記第４の暗号化値と、が一致するか否かを判定し、該判定結果を前記サービス提供者サーバへ送信する
ことを特徴とする判定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化された値が所定の条件を満たす値か否かを判定する暗号化値判定方法および判定システムの技術に関する。
【背景技術】
【０００２】
情報システムの開発の効率化、運用管理費の低減などを目的に、近年、情報システムを自分で保持せず、外部業者に委託するクラウドと呼ばれる運用管理形態を用いることが脚光を浴びている。このようなクラウドによる運用は、効率化やコスト低減というメリットを有する反面、情報システムを管理する業者が情報システムを利用する者とは異なるため、機密情報を外部業者に預託することに不安が生じる。そのため、事前にデータの不正流出の予防策として暗号技術を活用し、データの機密性を確保する必要がある。
【０００３】
しかし、単純な暗号化ではデータに対する検索や値の大小判定、統計処理などは復号可能な者（預託業者）しか実行できず、クラウド業者などの外部の情報システム管理者では処理できなくなる。このことは当初の目的であるコスト低減などに反することになり、対策技術が求められる。
【０００４】
このような対策技術のうち、サーバ／クライアントモデルにおいて、クライアントが、サーバに秘匿化したデータを預託しながら、サーバに対し、情報の検索処理を依頼できる暗号化方式が知られている。例えば、非特許文献１や非特許文献２には、このような秘匿検索処理を実現する方式が記載されている。非特許文献１や非特許文献２に記載の技術では、平文と暗号値が一対一の単純な対応関係を有する決定的暗号化方式よりも安全な、平文と暗号値が一対ｍの複雑な対応関係を有する確率的暗号化方式を採用している。非特許文献１および非特許文献２に記載の技術では、このような確率的暗号化方式を用いることにより、クラウド業者などへの情報漏洩を防ぎながら、かつサーバに預託したデータを安全に検索するための技術が開示されている。
【０００５】
また、非特許文献３には、二者間で互いに値を隠したまま大小を比較するプロトコルが記載されている。非特許文献３に記載の技術を、具体値を秘匿したままのしきい値判定に応用する場合、ユーザが入力した値と、しきい値判定するサーバが保持するしきい値の大小比較を行う。その際、ユーザが取り得るすべての値について暗号処理や、通信を行う必要がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Dawn Xiaodong Song, David Wagner, Arian Perrig.“Practical Techniques for Searches on Encrypted Data”、［online］、[2011年1月11日検索］、インターネット＜URL：http://www.cs.berkeley.edu/~dawnsong/publication.html＞
【非特許文献２】Zhiqiang Yang, Sheng Zhong, Rebecca N. Wright.“Privacy-Preserving Queries on Encrypted Data”、［online］、[2011年1月11日検索］、インターネット＜URL：http://www.cs.rutgers.edu/~rwright1/Publications/＞
【非特許文献３】Yao,A.C.“Protocols for Secure Computation”、［online］、[2011年1月11日検索］、インターネット＜URL：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.7844&rep=rep1&type=pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、例えば、会社がある値に関する統計をとるために、ユーザから値に関する情報を取得したい場合がある。例えば、自動車会社が、ある車に関する値を、ユーザから取得して統計するために、まず、自動車整備会社にその値を集めさせ、その値があるしきい値を超えているか否かを自動車整備会社に判定させ、その結果を自動車会社で取得・統計したい場合がある。このような場合、自動車会社は、自動者整備会社にしきい値に関する情報を知られたくないことがある。
【０００８】
このような場合、非特許文献１および非特許文献２に記載された技術では、サービス提供者（前記した例では自動車会社）などはサーバに預託する暗号化したデータの完全一致検索しかできず、値の大小比較はできない。つまり、サービス提供者が、ユーザによって送信された値に対し、あるしきい値に対する大小で、その後の処理を決定したい場合、非特許文献１、非特許文献２の検索技術ではユーザから送信される値が取りうるすべての値に対する一致検索を実行することでしかしきい値に対する大小情報を決めることができず、非効率的である。
また、このような処理は判定者（前記した例では自動車整備会社）にユーザの値の情報の多く、またはすべてを開示してしまうことにつながり、安全性の観点から不適である。また、ユーザが送信しうる値の個数が少ない場合、決定性の暗号では通信データの頻度解析により、ユーザの傾向が露呈するおそれがある。
【０００９】
また、非特許文献３に記載された技術を、前記したしきい値判定に用いる場合、ユーザの値の情報が多く漏れてしまう。実際、しきい値判定サーバ（前記した例では自動車整備会社に設置されているサーバ）がしきい値を種々に変えながらユーザに比較プロトコルの要求をした場合、ユーザの値の特定まで可能になり、秘匿性が十分保てない。さらに、ユーザが取りうる値が大きくなり、その値の個数が比較的大きい場合、計算量や通信量が膨大になる（個数（または値の最大値）が２３２の場合、２３２回の暗号処理と、数ギガバイトのデータ送信が必要となる）。
【００１０】
このような背景に鑑みて本発明がなされたのであり、本発明は、暗号化対象値の条件に関する情報を他者に漏洩しないことを課題とする。
【課題を解決するための手段】
【００１１】
前記課題を解決するため、本発明は、サービス提供者サーバ、ユーザ端末および判定サーバを有する判定システムにおける暗号化値判定方法であって、
前記サービス提供者サーバは、
（ａ０）暗号化すべき値が所定のグループに属する値である第１の値か、前記グループには属さない値である第２の値かを判定し、
（ａ１）前記第１の値に対しては、第１の暗号鍵による暗号化処理を行って、第１の暗号化値を算出し、
（ａ２）前記第１の暗号化値に対し、第２の暗号鍵による第２の暗号化処理を行って、第２の暗号化値を算出し、前記第１の値と、前記第２の暗号化値と、を含んだ判定用データを、記憶部に格納し、
（ａ３）前記第２の値に対しては、ランダムな値を第２の暗号化値として算出し、当該第２の値と、当該第２の暗号化値と、を含んだ判定用データを、前記記憶部に格納し、
（ａ４）前記判定用データと、前記第１の暗号鍵を前記ユーザ端末へ送信し、
（ａ５）前記第２の暗号鍵を、前記判定サーバへ送信し、
前記ユーザ端末は、
（ａ６）入力部を介して任意の値が入力されると、前記任意の値に対し、前記第１の暗号鍵による暗号化処理を行って、第３の暗号化値を算出し、
（ａ７）前記任意の値が前記第１の値に該当する場合、前記サービス提供者サーバより送信された前記第１の値における前記判定用データから前記第１の値に対応する前記第２の暗号化値を取得し、前記任意の値が前記第２の値に該当する場合、前記サービス提供者サーバより送信された前記第２の値における前記判定用データから前記第２の値に対応する前記第２の暗号化値を取得し、
（ａ９）前記第３の暗号化値と、当該取得した第２の暗号化値と、を対とした通信データを前記判定サーバへ送信し、
前記判定サーバは、
（ａ１０）前記ユーザ端末から送信された第２の暗号化値を、前記第２の暗号鍵を用いて、復号化した復号値を算出し、
（ａ１１）前記復号値と、前記第３の暗号化値と、が一致するか否かを判定し、該判定結果を前記サービス提供者サーバへ送信することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、暗号化対象値の条件に関する情報を他者に漏洩しないことが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態に係る秘匿しきい値判定システムの構成例を示す図である。
【図２】第１実施形態に係るユーザ端末の構成例を示す図である。
【図３】第１実施形態に係るサービス提供者サーバの構成例を示す図である。
【図４】第１実施形態に係るしきい値判定サーバの構成例を示す図である。
【図５】ユーザ端末、サービス提供者サーバ、しきい値判定サーバのハードウェア構成を示す図である。
【図６】第１実施形態に係るしきい値判定用データ生成処理の手順を示すフローチャートである。
【図７】第１実施形態に係る通信データ生成処理の手順を示すフローチャートである。
【図８】第１実施形態に係るしきい値判定処理の手順を示すフローチャートである。
【図９】第２実施形態に係るユーザ端末の構成例を示す図である。
【図１０】第２実施形態に係るサービス提供者サーバの構成例を示す図である。
【図１１】第２実施形態に係るしきい値判定用データ生成処理の手順を示すフローチャートである。
【図１２】第２実施形態に係る通信データ生成処理の手順を示すフローチャートである。
【図１３】第２実施形態に係るしきい値判定処理の手順を示すフローチャートである。
【図１４】第３実施形態に係るしきい値判定用データ生成処理の手順を示すきフローチャートである。
【図１５】第３実施形態に係る通信データ生成処理の手順を示すフローチャートである。
【図１６】第３実施形態に係るしきい値判定処理の手順を示すフローチャートである。
【図１７】第４実施形態に係るしきい値判定用データ生成処理の手順を示すきフローチャートである。
【図１８】第４実施形態に係る通信データ生成処理の手順を示すフローチャートである。
【図１９】第４実施形態に係るしきい値判定処理の手順を示すフローチャートである。
【発明を実施するための形態】
【００１４】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１５】
《システム構成》
図１は、本実施形態に係る秘匿しきい値判定システムの構成例を示す図である。図１の構成は、後記する第１〜第４実施形態に共通の構成である。
秘匿しきい値判定システムＡは、ユーザ端末１と、サービス提供者サーバ（サーバ）２と、しきい値判定サーバ（判定サーバ）３とがネットワーク４を介して互いに接続された構成となっている。ここで、前記した例を用いると、サービス提供者サーバ２は自動車会社に設置され、しきい値判定サーバ３は自動車整備会社に設置され、ユーザ端末１は自動車のユーザが所有している端末である。
【００１６】
ユーザ端末１は、秘匿化した値をしきい値判定サーバ３へ送信する暗号データの生成および送信を行う。サービス提供者サーバ２は、後記する秘匿しきい値判定用の暗号化鍵、復号化鍵およびしきい値判定用データ（判定用データ）の生成、さらにしきい値判定サーバ３によるしきい値判定結果を受信する。しきい値判定サーバ３は、ユーザ端末１が送信した暗号化された通信データを受信し、しきい値判定を実行し、その結果をサービス提供者サーバ２へ送信する。
【００１７】
《第１実施形態》
次に、図２〜図８を参照して、本発明に係る第１実施形態を説明する。
（ユーザ端末）
図２は、第１実施形態に係るユーザ端末の構成例を示す図である。
ユーザ端末１は、制御部１１と、記憶部１２と、情報を入力する入力部１３と、情報を出力する出力部１４と、外部装置との情報の送受信を行う通信部１５とを有する。
【００１８】
制御部１１は、全体処理部１１１と、暗号化部１１２と、基本演算部１１３とを有する。
全体処理部１１１は、ユーザ端末１における処理を統括制御したり、入力部１３を介して、受け付けた情報を記憶部１２に格納したり、サービス提供者サーバ２や、しきい値判定サーバ３との情報を送受信を制御する。
また、全体処理部１１１は、平文データを、出力部１４に表示する処理を行ったり、記憶部１２に格納されている平文データを読み込み、それぞれ、暗号化部１１２や、基本演算部１１３に平文データの暗号化処理を行わせたり、暗号化された通信データや、ユーザ端末１の属性データや、一時情報を、通信部１５を介して、しきい値判定サーバ３（図１）へ送信する。
【００１９】
暗号化部１１２は、平文データと、秘密鍵が入力されると、秘密鍵を用いて暗号化を行い、出力された暗号化データを一時情報として記憶部１２に格納する。
なお、暗号化部１１２は、標準的な共通鍵暗号アルゴリズムの実装により実現可能である。
【００２０】
基本演算部１１３は、加算、減算、比較演算などの基本的な算術演算に関する処理を行う。
【００２１】
記憶部１２には、通信データと、秘密鍵と、しきい値判定用データと、一時情報が格納されている。
通信データは、平文データと、ユーザ端末１の属性データとを有している。
秘密鍵は、平文データを暗号化する際に用いられる。
しきい値判定用データは、しきい値判定サーバ３にしきい値判定を依頼する際に用いるデータを特定する情報であり、その詳細は後記する。なお、安全性の観点から、しきい値判定用データは、ユーザ端末１において秘密に管理されるべき情報である。
一時情報は、制御部１１での処理で一時的に必要となる情報が格納される。
【００２２】
（サービス提供者サーバ）
図３は、第１実施形態に係るサービス提供者サーバの構成例を示す図である。
サービス提供者サーバ２は、制御部２１と、記憶部２２と、情報を入力する入力部２３と、情報を出力する出力部２４と、外部装置との情報の送受信を行う通信部２５とを有する。
【００２３】
制御部２１は、全体処理部２１１と、暗号化部２１２と、復号化部２１３と、乱数生成部２１４と、基本演算部２１５とを有する。
全体処理部２１１は、サービス提供者サーバ２における処理を統括制御したり、入力部２０１を介して、入力を受け付けた情報を記憶部２２に格納したり、しきい値判定サーバ３や、ユーザ端末１との情報の送受信を制御する。
暗号化部２１２は、入力されたデータを暗号化する。
例えば、暗号化部２１２は、平文データと、秘密鍵が入力されたとき、秘密鍵を用いた暗号化処理を行い、暗号化されたデータを一時情報として記憶部２２に格納する。
また、例えば、暗号化部２１２は、暗号化された情報に対し、秘密鍵を用いて、さらに暗号化処理を行い、暗号化されたデータを一時情報として記憶部２２に格納する。
なお、暗号化部２１２は、例えば、標準的な共通鍵暗号アルゴリズムの実装により実現可能である。
【００２４】
復号化部２１３は、暗号化されたデータを復号化する。
例えば、復号化部２１３は、暗号化された情報と、秘密鍵が入力されたとき、対応する復号化を行い、出力されたデータを一時情報として記憶部２２に格納する。
乱数生成部２１４は、秘密鍵などを用いて擬似乱数を生成する。このとき、秘密鍵のデータ値は、乱数生成部２１４によって、新しいデータ値に更新され、再び、全体処理部２１１により記憶部２２に格納される。なお、乱数生成部２１４は、温度、時間、電力量などの物理現象や、乱数生成アルゴリズムを用いて乱数を生成・出力してもよい。
基本演算部２１５は、加算、減算、比較演算などの基本的な算術演算を行う。
【００２５】
記憶部２２には、通信データと、秘密鍵と、しきい値判定用データと、一時情報とが格納されている。
通信データは、平文データと、ユーザ端末１の属性データ（図２）を特定する情報であるユーザ属性データとを有している。
秘密鍵は、情報を暗号化する際に用いられる鍵であり、ユーザ端末１や、しきい値判定サーバ３へ送信されるものである。
しきい値判定用データは、しきい値判定サーバ３にしきい値判定を依頼する際に用いるデータを特定する情報であり、その詳細は後記する。なお、安全性の観点から、しきい値判定用データは、ユーザ端末１において秘密に管理されるべき情報である。
一時情報は、制御部２１での処理で一時的に必要となる情報が格納される。
【００２６】
（しきい値判定サーバ）
図４は、第１実施形態に係るしきい値判定サーバの構成例を示す図である。
しきい値判定サーバ３は、制御部３１と、記憶部３２と、情報を入力する入力部３３と、情報を出力する出力部３４と、外部装置との情報の送受信を行う通信部３５とを有する。
【００２７】
制御部３１は、全体処理部３１１と、暗号化部３１２と、復号化部３１３と、基本演算部３１４と、判定部３１５とを有する。
全体処理部３１１は、しきい値判定サーバ３における処理を統括制御したり、ユーザ端末１や、サービス提供者サーバ２との情報の送受信を制御する。
例えば、全体処理部３１１は、通信部３５を介して、ユーザ端末１からデータを受信する処理を行ったり、通信部３５を介して、判定部３１５の出力結果を、サービス提供者サーバ２へ送信する。
復号化部３１３は、暗号化されたデータを復号化する。
例えば、復号化部３１３は、暗号化された情報と、秘密鍵が入力されると、対応する復号化を行い、出力されたデータを一時情報として記憶部３２に格納する。
暗号化部３１２は、暗号化処理を行う。なお、しきい値判定サーバ３において、暗号化部３１２は省略可能である。
基本演算部３１４は、加算、減算、比較演算などの基本的な算術演算に関する処理を行う。
判定部３１５は、２つのデータ（値）の一致・不一致を判定し、この判定結果をデータとして出力する。
【００２８】
記憶部３２には、秘密鍵と、一時情報とが格納されている。
秘密鍵は、ユーザ端末１から送信された暗号化された情報を復号する際に用いられる。
一時情報は、制御部３１での処理で必要となる情報である。
【００２９】
（ハードウェア構成）
図５は、ユーザ端末、サービス提供者サーバ、しきい値判定サーバであるコンピュータのハードウェア構成を示す図である。
コンピュータ５（つまり、ユーザ端末１、サービス提供者サーバ２、しきい値判定サーバ３）は、ＣＰＵ（Central Processing Unit）５１、メモリ５２、ＨＤＤ（Hard Disk Drive）などの外部記憶装置５３、ＣＤ（Compact Disk）などのデータを読み取るＣＤＤ（Compact Disk Drive）などの読書装置５４、キーボードなどの入力装置５５、ディスプレイなどの出力装置５６、ＮＩＣ（Network Interface Card）などの通信装置５７を有する一般的なＰＣ（Personal Computer）で実現される。
図２〜図４の各部１１，１１１〜１１３，２１，２１１〜２１５，３１，３１１〜３１５は、外部記憶装置５３などに格納されているプログラムが、メモリ５２に展開され、ＣＰＵ５１によって実行されることにより具現化する。
【００３０】
《フローチャート》
（しきい値判定用データ生成処理）
図６は、第１実施形態に係るしきい値判定用データ生成処理の手順を示すフローチャートである。この処理は、サービス提供者サーバ２によって行われる処理である。
【００３１】
まず、サービス提供者サーバ２の基本演算部２１５が、インデックスｉを１にセットする（Ｓ１０１）。
次に、基本演算部２１５は、ｉが暗号化対象値であるか否かを判定する（Ｓ１０２）。ここで、暗号化対象値とは、サービス提供者が「Ｙｅｓ」と判定してほしい値である（つまり、サービス提供者が情報として取得したい値である）。例えば、ｎをしきい値としてｎ以下の値をサービス提供者が「Ｙｅｓ」の判定としてほしい場合は、ステップＳ１０２において、基本演算部２１５がｉ≦ｎの判定を行う。また、逆にｎをしきい値としてｎ以上の値をサービス提供者が「Ｙｅｓ」の判定としてほしい場合は、ステップＳ１０２において、基本演算部２１５がｉ≧ｎの判定を行う。あるいは、ｐからｑ（ｐ＜ｑ）の間の値をサービス提供者が「Ｙｅｓ」の判定としてほしい場合は、ステップＳ１０２において、基本演算部２１５がｐ≦ｉ≦ｑの判定を行う。または、偶数をサービス提供者が「Ｙｅｓ」の判定としてほしい場合は、ステップＳ１０２において、基本演算部２１５がｉ＝偶数であるか否かの判定を行う。
以下、第１実施形態および第２実施形態において、しきい値とは、暗号化対象値の条件とする。
【００３２】
ステップＳ１０２の結果、ｉが暗号化対象値（第１の値）である場合（ステップＳ１０２→Ｙｅｓ）、暗号化部２１２が記憶部２２から秘密鍵ｋ１（第１の暗号鍵）を読み出し、ｉを平文、ｋ１を秘密鍵とした暗号化処理Ｅ（ｋ１，ｉ）（第１の暗号化処理）を行って、暗号値ｅｉ（第１の暗号化値）を算出し（Ｓ１０３）、算出した暗号値ｅｉを一時情報として記憶部２２に格納する。なお、各装置１〜３において、算出された値は、一時情報として各記憶部１２，２２，３２に格納されるが、以降、この処理に関する記述を省略する。
次に、暗号化部２１２は、記憶部２２から秘密鍵ｋ２（第２の暗号鍵）を読み出すとともに、ステップＳ１０３で算出した暗号値ｅｉを読み出し、ｅｉを平文、ｋ２を秘密鍵とした暗号化処理Ｅ（ｋ２，ｅｉ）（第２の暗号化処理）を行って、暗号値Ｒｉ（第２の暗号化値）を算出する（Ｓ１０４）。つまり、暗号化部２１２は２重暗号を行う。
【００３３】
次に、暗号化部２１２は、ｉと、ステップＳ１０４で算出した暗号値Ｒｉの対（ｉ，Ｒｉ）を記憶部２２のしきい値判定用データに加える（Ｓ１０５）。
そして、基本演算部２１５はｉの値に１を加算したものをｉとして置き換え（Ｓ１０６）、ステップＳ１０２へ処理を戻す。
【００３４】
ステップＳ１０２の結果、ｉが暗号化対象値ではない（第２の値）場合（ステップＳ１０２→Ｎｏ）、基本演算部２１５が、ｉ＜ｍであるか否かを判定する（Ｓ１０７）。ここで、ｍはｉがとり得る最大値であり、予めサービス提供者サーバ２に登録されているものである。
ステップＳ１０７の結果、ｉ＜ｍである場合（Ｓ１０７→Ｙｅｓ）、乱数生成部２１４は乱数Ｒｉ（第２の暗号化値）を生成し（Ｓ１０８）、iとステップＳ１０８で生成した乱数Ｒｉの対（ｉ，Ｒｉ）をしきい値判定用データに加える（Ｓ１０９）。
そして、基本演算部２１５はｉの値に１を加算したものをｉとして置き換え（Ｓ１１０）、ステップＳ１０２へ処理を戻す。
【００３５】
ステップＳ１０７の結果、ｉ≧ｍである場合（Ｓ１０７→Ｎｏ）、全体処理部２１１はしきい値判定用データと、記憶部２２の秘密鍵ｋ１を、他者に情報が漏洩しない方法を用いて、ユーザ端末１へ送付する（Ｓ１１１）。しきい値判定用データおよび秘密鍵ｋ１の送付は、暗号化による送信でもよいし、しきい値判定用データおよび秘密鍵ｋ１を格納した媒体を物理的に送付してもよい。
【００３６】
サービス提供者サーバ２から送付されたしきい値判定用データおよび秘密鍵ｋ１を受け取ったユーザ端末１は、しきい値判定用データと秘密鍵ｋ１を記憶部２２に格納する。
【００３７】
次に、全体処理部２１１は秘密鍵ｋ２を、他者に情報が漏洩しない方法を用いて、しきい値判定サーバ３へ送付する（Ｓ１１２）。秘密鍵ｋ２の送付は、暗号化による送信でもよいし、秘密鍵ｋ２を格納した媒体を、物理的に送付してもよい。
サービス提供者サーバ２から送付された秘密鍵ｋ２を受け取ったしきい値判定サーバ３は、秘密鍵ｋ２を記憶部２２に格納する。
【００３８】
（通信データ生成処理）
図７は、第１実施形態に係る通信データ生成処理の手順を示すフローチャートである。この処理は、ユーザ端末１によって行われる処理である。
まず、入力部１３を介して、しきい値判定サーバ３で判定してもらう値（判定対象値）ｊがユーザ端末１に入力される（Ｓ２０１）。
そして、ユーザ端末１の暗号化部１１２は、記憶部１２から、図６のステップＳ１１１でサービス提供者サーバ２から送付された秘密鍵ｋ１を読み出し、ｊを平文、ｋ１を秘密鍵（第１の暗号鍵）とした暗号化処理Ｅ（ｋ１，ｊ）（第１の暗号化処理）を行って、暗号値ｅｊ（第３の暗号化値）を算出する（Ｓ２０２）。
次に、基本演算部１１３は、図６のステップＳ１１１でサービス提供者サーバ２から送付されたしきい値判定用データを参照して、ｊに対応する暗号値Ｒｊ（第２の暗号化値）を読み出す（Ｓ２０３）。このときの暗号値Ｒｊは、ステップＳ１０３，Ｓ１０４で算出されたものと、ステップＳ１０８で算出されたものの２種類のうち、どちらかの暗号値Ｒｊとなる。
そして、全体処理部１１１は、データの対（ｅｊ，Ｒｊ）と、記憶部１２の属性情報とを通信データとしてしきい値判定サーバ３へ送信する（Ｓ２０４）。
属性情報には、ユーザの識別情報（ＩＤ（Identification））や、判定対象値ｊの識別情報などが含まれる。なお、通信データに属性情報が含まれていなくてもよい。
【００３９】
（しきい値判定処理）
図８は、第１実施形態に係るしきい値判定処理の手順を示すフローチャートである。この処理は、しきい値判定サーバ３によって行われる処理である。
まず、しきい値判定サーバ３が、図７のステップＳ２０４で送信された通信データ（ｅｊ，Ｒｊ）を受信する（Ｓ３０１）。
次に、復号化部３１３は、記憶部３２から、図６のステップＳ１１２で送付された秘密鍵ｋ２を読み出し、Ｒｊを暗号値（第２の暗号化値）、ｋ２を復号鍵（第２の暗号鍵）として復号化処理Ｄ（ｋ２，Ｒｊ）を行い、復号値ｄｊを算出する（Ｓ３０２）。
そして、判定部３１５は、ｅｊ（第３の暗号化値）＝ｄｊであるか否かを判定する（Ｓ３０３）。
ステップＳ３０３の結果、ｅｊ＝ｄｊである場合（Ｓ３０３→Ｙｅｓ）、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信する（Ｓ３０４）。
ステップＳ３０３の結果、ｅｊ≠ｄｊである場合（Ｓ３０３→Ｎｏ）、全体処理部３１１は、判定対象値が暗号化対象値でないことを示す「Ｎｏ」をサービス提供者サーバ２へ送信する（Ｓ３０５）。
【００４０】
以上の処理を説明すると、図６のしきい値判定用データ生成処理において、暗号化対象値は、暗号化規則に基づいて暗号化している。従って、判定対象値が暗号化対象値であれば、ステップＳ３０２で復号された値は、図６のステップＳ１０３で算出された値と一致するはずである。
一方、図６のしきい値判定用データ生成処理において、暗号化対象値でない値はランダムな値が割り当てられる。従って、判定対象値が暗号化対象値でなければ、ステップＳ３０２で復号された値は、ランダムな値と比較されることになるので、ステップＳ３０３で不一致となる。
このようにして、しきい値判定サーバ３は、判定対象値が暗号化対象値であるか否かを判定する。
なお、ステップＳ３０４あるいはステップＳ３０５の処理において、ユーザ端末１などの属性情報を付加して送信してもよい。
【００４１】
（第１実施形態のまとめ）
第１実施形態によれば、ユーザ端末１は、しきい値判定処理のための秘密鍵ｋ２を知らないため、しきい値判定用データを用いても、ユーザ端末１はしきい値判定処理を行うことはできない。そのため、ユーザ端末１のユーザはしきい値（つまり、暗号化対象値となるための条件）を知ることはできない。
一方、しきい値判定サーバ３にはしきい値判定用データを送信されないため、しきい値判定サーバ３のユーザは、しきい値を知ることができない。また、ユーザ端末１が送信するデータの対（ｅｊ，Ｒｊ）のうち、ｅｊは判定対象値ｊを、しきい値判定サーバ３に送信されていない秘密鍵ｋ１で暗号化した値であるので、しきい値判定サーバ３のユーザは判定対象値ｊを知ることができない。
従って、サービス提供者（サービス提供者サーバ２のユーザ）は第３者にしきい値を知られることなく、ある値がしきい値以上なのか、以下なのかを知ることができる。
このようにすることで、暗号化対象値に関する情報漏洩のおそれなく外部委託できるため、ユーザ、またはサービス提供者の処理コスト軽減が可能となる。
【００４２】
《第２実施形態》
次に、図９〜図１３を参照して、本発明の第２実施形態を説明する。
第１実施形態に記載した方法は、しきい値判定が複数回発生する場合、判定対象値ｊが同じであれば、送信されるデータ対（ｅｊ，Ｒｊ）も同じとなる。このことが原因となって傾向情報が漏洩するおそれがある。そこで、第２実施形態では送信されるデータ対（ｅｊ，Ｒｊ）をランダム化した上で、公開鍵準同型暗号（準同型暗号）によって暗号化する。ここで、公開鍵準同型暗号とは、平文ｍ１と、ｍ２に対する暗号値が、それぞれｃ１、ｃ２である場合、ｃ１・ｃ２がｍ１＊ｍ２に対する暗号値となっている公開鍵暗号方式である。すなわち、暗号化処理Ｅｎｃに対し、Ｅｎｃ（ｍ１＊ｍ２）＝Ｅｎｃ（ｍ１）・Ｅｎｃ（ｍ２）となる暗号方式である。ここで、「・」と「＊」はそれぞれ暗号値空間、平文空間に定義されている、加法や乗法などの演算であり、各公開鍵準同型暗号に依存して決まる。
また、Ｅｎｃ（・）は公開鍵準同型暗号による暗号化処理を示す。公開鍵準同型暗号として、例えば、ＥｌＧａｍａｌ暗号や、楕円ＥｌＧａｍａｌ暗号などを利用することができる。
【００４３】
（ユーザ端末）
図９は、第２実施形態に係るユーザ端末の構成例を示す図である。
図９のユーザ端末１ａが、図２に示すユーザ端末１と異なる点は、制御部１１ａが公開鍵準同型暗号方式による暗号化処理を行う公開鍵準同型暗号化部１１４と、乱数を生成する乱数生成部１１５を有し、記憶部１２ａの通信データに、公開鍵準同型暗号化処理に用いる公開準同型暗号鍵を含んでいることである。
その他は、図２に示すユーザ端末１と同様の構成を有するため、図３と同一の符号を付して説明を省略する。
【００４４】
（サービス提供者サーバ）
図１０は、第２実施形態に係るサービス提供者サーバの構成例を示す図である。
図１０に示すサービス提供者サーバ２ａが、図３に示すサービス提供者サーバ２と異なる点は、制御部２１ａが公開鍵準同型暗号方式による暗号化処理を行う公開鍵準同型暗号化部２１６を有し、記憶部２２ａの通信データに、公開鍵準同型暗号化処理に用いる公開準同型暗号鍵を含んでいることである。
その他は、図３に示すサービス提供者サーバ２と同様の構成を有するため、図２と同一の符号を付して説明を省略する。
なお、しきい値判定サーバ３は、図４と同様の構成を有するので、同一の符号を付し、図示および説明を省略する。
【００４５】
なお、図９および図１０の各部１１ａ，１１１〜１１５，２１ａ，２１１〜２１６も図５における外部記憶装置５３などに格納されているプログラムが、メモリ５２に展開され、ＣＰＵ５１によって実行されることにより具現化する。
【００４６】
《フローチャート》
（しきい値判定用データ生成処理）
図１１は、第２実施形態に係るしきい値判定用データ生成処理の手順を示すフローチャートである。この処理は、サービス提供者サーバ２ａによって行われる処理である。
この処理が図６の処理と異なっている点は、図６のステップＳ１０４に相当する処理において、公開鍵準同型暗号化部２１６がｅｉを平文、ｐｋを公開準同型暗号鍵とした暗号化処理Ｅｎｃ（ｐｋ，ｅｉ）を行って、暗号値Ｒｉを算出している点である（Ｓ４０４）。
また、図６のステップＳ１１１に相当する処理において、全体処理部３１１が、秘密鍵ｋ１とともに、公開準同型暗号鍵ｐｋ（第２の暗号鍵）をユーザ端末１へ送付している（Ｓ４１１）点も、図６の処理と異なっている。
また、図６のステップＳ１１２の処理において、全体処理部３１１が、秘密鍵ｋ２の代わりに準同型暗号秘密鍵ｓｋ（復号鍵）を、他者に情報が漏洩しない方法を用いて、しきい値判定サーバ３へ送付する（Ｓ４１２）。
その他は、図６の処理と同様であるため、説明を省略する。
【００４７】
（通信データ生成処理）
図１２は、第２実施形態に係る通信データ生成処理の手順を示すフローチャートである。この処理は、ユーザ端末１ａによって行われる処理である。
図１２において、ステップＳ５０１〜Ｓ５０３の処理は、図７のステップＳ２０１〜Ｓ２０３と同様であるため、説明を省略する。
ステップＳ５０３の後、乱数生成部１１５は、乱数ｒを生成する（Ｓ５０４）。
公開鍵準同型暗号化部１１４は、図１１のステップＳ４１１でサービス提供者サーバ２から送付された公開準同型暗号鍵ｐｋを読み出し、乱数ｒを平文、ｐｋを公開準同型暗号鍵とした暗号化処理Ｅｎｃ（ｐｋ，ｒ）を行って、暗号値Ｒ（乱数暗号値）を算出しする（Ｓ５０５）。
次に、基本演算部１１３は、ｅｒｊ（第４の暗号化値）＝ｅｊ＊ｒと、Ｒｒｊ（第５の暗号化値）＝Ｒｊ・Ｒを計算する（Ｓ５０６）。ここで、「＊」は四則演算における乗算を示し、「・」は暗号空間で定義される乗法を示す。
そして、全体処理部１１１は、ステップＳ５０６で生成したデータの対（ｅｒｊ，Ｒｒｊ）と、記憶部１２ａの属性情報とを通信データとしてしきい値判定サーバ３へ送信する（Ｓ５０７）。
属性情報には、ユーザの識別情報（ＩＤ）や、判定対象値ｊの識別情報などが含まれる。なお、通信データに属性情報が含まれていなくてもよい。
【００４８】
（しきい値判定処理）
図１３は、第２実施形態に係るしきい値判定処理の手順を示すフローチャートである。この処理は、しきい値判定サーバ３によって行われる処理である。
まず、しきい値判定サーバ３が、図１１のステップＳ５０７で送信された通信データ（ｅｒｊ，Ｒｒｊ）を受信する（Ｓ６０１）。
次に、復号化部３１３は、記憶部３２から図１１のステップＳ４１２でサービス提供者サーバ２から送信された準同型暗号秘密鍵ｓｋを読み出し、Ｒｒｊを暗号値（第５の暗号化値）、ｓｋを復号鍵とした復号化処理Ｄｅｃ（ｓｋ、Ｒｒｊ）を行って、復号値ｄｒｊ（実際にはｊを暗号化した値）を算出する（Ｓ６０２）。ここで、Ｄｅｃ（・）は公開鍵準同型暗号による復号化処理を示す。
そして、判定部３１５は、ｅｒｊ（第４の暗号化値）＝ｄｒｊであるか否かを判定する（Ｓ６０３）。
ステップＳ６０３の結果、ｅｒｊ＝ｄｒｊである場合（Ｓ６０３→Ｙｅｓ）、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信する（Ｓ６０４）。
ステップＳ６０３の結果、ｅｒｊ≠ｄｒｊである場合（Ｓ６０３→Ｎｏ）、全体処理部３１１は、判定対象値が暗号化対象値でないことを示す「Ｎｏ」をサービス提供者サーバ２へ送信する（Ｓ６０５）。
なお、ステップＳ３０４あるいはステップＳ３０５の処理において、ユーザ端末１などの属性情報も付加して送信してもよい。
【００４９】
本実施形態では、しきい値判定を複数回行う場合であって、ユーザ端末１から送信される判定対象値ｊに、頻度などの統計的偏りがあったとしても、ユーザ端末１から送信されるデータ対（ｅｒｊ，Ｒｒｊ）は毎回、乱数によるマスクがかけられているため、しきい値判定サーバ３のユーザは、しきい値との比較結果以外の情報を得ることができないので、第１実施形態より、暗号化のレベルを向上することができる。
【００５０】
《第３実施形態》
第１実施形態および第２実施形態による方法では、ユーザ端末１による判定対象値ｊが取りうる値の個数に比例して、しきい値判定用データも大きくなってしまう。
これに対し、第３実施形態および第４実施形態では、判定対象値を適当な桁で分割して、桁ごとでしきい値判定を行い、その結果を基に判定対象値がしきい値より大きいか否か（あるいは、小さいか否か）を判定する方法である。
なお、第１実施形態および第２実施形態では、判定対象値があるグループ（しきい値より大きいや、しきい値より小さいや、ある範囲の値であるかや、偶数であるかなど）に属しているか否かを判定可能であったが、第３実施形態および第４実施形態では、しきい値より大きい、あるいは、しきい値より小さいといった判定のみ可能となる。
【００５１】
以下、第３実施形態および第４実施形態における処理手順をフローチャートで説明する。なお、第３実施形態および第４実施形態におけるユーザ端末１、サービス提供者サーバ２およびしきい値判定サーバ３の構成は、第１実施形態で示した構成と同様であるため、図示および説明を省略する。
【００５２】
＜フローチャート＞
（しきい値判定用データ生成処理）
図１４は、第３実施形態に係るしきい値判定用データ生成処理の手順を示すきフローチャートである。この処理は、サービス提供者サーバ２によって行われる処理である。
桁数の値としてｚが入力部２３を介して入力されている。
そして、基本演算部２１５は、桁のインデックスｂを０にセットする（Ｓ７０１）。ここで、桁数とは、判定対象値を２進展開して所定のビット毎に区切ったときの数である。ここで、２進数表現を「・」Ｂと表記し、１０進数表現を「・」Ｄと表記することとする。例えば、判定対象値が「１７８０」Ｄだとすると、この値を２進展開したものは「０１１０１１１１０１００」となる。秘匿しきい値判定システムＡが４ビット毎に値の判定を行うとすると、前記した値は「０１１０  １１１１  ０１００」Ｂと区切られることとなる。本実施形態では、先頭の桁から０桁目（ｂ＝０）、１桁目（ｂ＝１）、・・・と数えることを定義する。従って、この例において０桁目は「０１００」Ｂとなり、１桁目は「１１１１」Ｂとなり、２桁目は「０１１０」Ｂとなる。
【００５３】
次に、基本演算部２１５は、ｂ＝ｚである否かを判定する（Ｓ７０２）。
ステップＳ７０２の結果、ｂ≠ｚである場合（Ｓ７０２→Ｎｏ）、基本演算部２１５が、インデックスｉを１にセットする（Ｓ７０３）。
そして、基本演算部２１５はｉを２進展開する。
基本演算部２１５は、ｉが、処理対象となっている桁におけるしきい値ｎａ以下であるか否かを判定する（Ｓ７０４）。
ここで、ｎａは、各桁におけるしきい値である。しきい値が「１０００」Ｄであったとすると、このしきい値を２進展開した値は「００１１  １１１０  １０００」Ｂとなる。よって、０桁目（ｂ＝０）のｎａ＝「１０００」Ｂ＝「８」Ｄ、１桁目（ｂ＝１）のｎａ＝「１１１０」Ｂ＝「１４」Ｄ、２桁目（ｂ＝２）のｎａ＝「００１１」Ｂ＝「３」Ｄとなる。
その後、基本演算部２１５および暗号化部２１２がステップＳ７０５〜Ｓ７１２の処理を行う。
ステップＳ７０５〜Ｓ７１２の処理において、しきい値判定用データに現在処理している桁ｂが追加されること以外は、図６のステップＳ１０３〜Ｓ１１０と同様であるため説明を省略する。
なお、４ビット毎に桁を区切っている場合、ステップＳ７０９におけるｍは、ｍ＝「１１１１」Ｂ＝「１５」Ｄである。
【００５４】
ステップＳ７０９の結果、ｉ＞ｍである場合（Ｓ７０９→Ｎｏ）、基本演算部２１５は、ｎａ＜ｎｂであるか否かを判定する（Ｓ７１３）。ここで、ｎｂは各桁におけるしきい値から２を減算した値である。例えば、０桁目におけるしきい値がｎａ＝「８」Ｄであれば、ｎｂ＝「６」Ｄとなる。
ステップＳ７１３の結果、ｎａ≧ｎｂである場合（Ｓ７１３→Ｎｏ）、基本演算部２１５はｎａの値から１を減算したものをｎａとして置き換え（Ｓ７１４）、ステップＳ７０４へ処理を戻す。
ステップＳ７１３の結果、ｎａ＜ｎｂである場合（Ｓ７０９→Ｙｅｓ）、基本演算部２１５はｂの値に１を加算したものをｂとして置き換え（Ｓ７１５）、ステップＳ７０２へ処理を戻す。
ステップＳ７０２の結果、ｂ＝ｚである場合（Ｓ７０２→Ｙｅｓ）、全体処理部２１１は、各桁ｂのしきい値判定用データと、秘密鍵ｋ１と、桁数ｚを、他者に情報が漏洩しない方法を用いて、ユーザ端末１へ送付する（Ｓ７１６）。しきい値判定用データおよび秘密鍵ｋ１の送付は、暗号化による送信でもよいし、しきい値判定用データおよび秘密鍵ｋ１を格納した媒体を物理的に送付してもよい。
次に、全体処理部２１１は秘密鍵ｋ２と、桁数ｚを、他者に情報が漏洩しない方法を用いて、しきい値判定サーバ３へ送付する（Ｓ７１７）。秘密鍵ｋ２、桁数ｚの送付は、暗号化による送信でもよいし、秘密鍵ｋ２、桁数ｚを格納した媒体を、物理的に送付してもよい。
【００５５】
ここで、送付されるしきい値判定用データは、各桁毎に２つ送付されることになる。つまり、各桁におけるしきい値の初期値（つまり、ｎａの初期値）をｎとすると、ｎに対応したしきい値判定用データと、ｎ−１に対応したしきい値判定用データである。なお、しきい値判定用データには、どのしきい値に対応する情報が格納されている。例えば、しきい値ｎに対応するしきい値判定用データには「１」が対応付けられ、しきい値ｎ−１に対応するしきい値判定用データには「２」が対応付けられる。しきい値に対応する情報は、しきい値そのものでなければ、どのような情報でもよい。
【００５６】
（通信データ生成処理）
図１５は、第３実施形態に係る通信データ生成処理の手順を示すフローチャートである。この処理は、ユーザ端末１によって行われる処理である。
まず、入力部１３を介して、判定対象値ｈがユーザ端末１に入力される（Ｓ８０１）。
次に、基本演算部１１３がｈを２進展開し、ａビット毎に分割する（Ｓ８０２）。ａはサービス提供者サーバ２から送付されるデータなどに含まれる。
そして、基本演算部１１３は、桁数を示すインデックスｂを０にセットする（Ｓ８０３）。
【００５７】
次に、基本演算部１１３は、ｎｃ＜ｎｄであるか否かを判定する（Ｓ８０４）。ここで、ｎｃは現在処理している桁のしきい値に関する情報である。図１４で説明したように、しきい値判定用データには、桁毎のしきい値（図１４におけるｎａの初期値をｎとしたとき、ｎであるか、ｎ−１であるか）に関する情報が対応付けられているが、対応付けられている情報はしきい値そのものではない。例えば、しきい値ｎに対応する情報として「１」、しきい値ｎ−１に対応付けられている情報として「２」がしきい値判定用データに対応付けられているとすると、ｎｃのとり得る値は１，２であり、ｎｄ＝３となる。
ステップＳ８０４の結果、ｎｃ＜ｎｄである場合（Ｓ８０４→Ｙｅｓ）、基本演算部１１３は、ｂ＝ｚであるか否かを判定する（Ｓ８０５）。ｚは、図１４のステップＳ７１６でサービス提供者サーバ２から送られた桁数ｚである。
ステップＳ８０５の結果、ｂ＝ｚである場合（Ｓ８０５→Ｙｅｓ）、基本演算部１１３はｎｃの値から１を減算したものをｎｃとして置き換え（Ｓ８０６）、ステップＳ８０４へ処理を戻す。ここでは、送付されたしきい値判定用データに対応付けられている桁毎のしきい値の情報が「１」、「２」であることを前提として処理の説明を行っているが、その他の情報を対応付けている場合、ステップＳ８０６の処理はそれぞれの処理に対応した処理となる。
【００５８】
ステップＳ８０５の結果、ｂ≠ｚである場合（Ｓ８０５→Ｎｏ）、暗号化部１１２は、ｈのｂ桁目の値をｊとして、ステップＳ８０７、Ｓ８０８の処理を行う。例えば、判定対象値ｈが「１７８０」Ｄだとすると、この値を２進展開した値は、前記したように「０１１０  １１１１  ０１００」Ｂとなる。４ビットごとで桁分けして処理している場合、ｂ＝１であれば、ｊ＝「１１１１」Ｂ＝「１５」Ｄとなる。
ステップＳ８０７、Ｓ８０８の処理は、図７のステップＳ２０２、Ｓ２０３と同様であるため説明を省略する。
ステップＳ８０８の処理の後、基本演算部１１３は、ｂの値に１を加算したものをｂとして置き換え（Ｓ８０９）、ステップＳ８０４へ処理を戻す。
【００５９】
ステップＳ８０４の結果、ｎｃ≧ｎｂである場合（Ｓ８０４→Ｎｏ）、全体処理部１１１は、データの対（ｂ，ｅｊ，Ｒｊ）と、記憶部１２の属性情報とを通信データとしてしきい値判定サーバ３へ送信する（Ｓ８１０）。
また、ｂ＝０，１，・・・，ｚ−１である。
【００６０】
なお、しきい値判定用データには、桁毎のしきい値に関する情報が付与される。ここで付与される情報は、しきい値そのものでなければ、どのような情報でもよいが、ここではしきい値ｎに対応する情報として「１」、しきい値ｎ−１に対応する情報として「２」を使用することとする。
属性情報には、ユーザの識別情報（ＩＤ）や、判定対象値ｈの識別情報などが含まれる。なお、通信データに属性情報が含まれていなくてもよい。
【００６１】
（しきい値判定処理）
図１６は、第３実施形態に係るしきい値判定処理の手順を示すフローチャートである。この処理は、しきい値判定サーバ３によって行われる処理である。
まず、しきい値判定サーバ３が、図１５のステップＳ８１０で送信された通信データ（ｂ，ｅｊ，Ｒｊ）を受信する（Ｓ９０１）。ここで、ｂ＝０，１，・・・，ｚ−１である。
まず、基本演算部３１４は、桁数を示すインデックスｆを０にセットする（Ｓ９０２）。ｚは、図１４のステップＳ７１４でサービス提供者サーバ２から送られた桁数ｚである。
続いて、基本演算部３１４は、ｆ＝ｚであるか否かを判定する（Ｓ９０３）。
ステップＳ８０４の結果、ｆ≠ｚである場合（Ｓ９０３→Ｎｏ）、復号化部３１３は、ステップＳ９０１で受信した通信データのうち、しきい値ｎに対応する通信データから現在の桁数のインデックスｆに対応している（ｂ＝ｆ）Ｒｊを抽出し、これをＲｊ（１）とし、図８のステップＳ３０２と同様の手順で平文ｄｊ（１）を算出する（Ｓ９０４）。
次に、復号化部３１３は、しきい値ｎ−１に対応する通信データから現在の桁数のインデックスｆに対応している（ｂ＝ｆ）Ｒｊを抽出し、これをＲｊ（２）とし、図８のステップＳ３０２と同様の手順で平文ｄｊ（２）を算出する（Ｓ９０５）。
【００６２】
そして、判定部３１５が、Ｒｊ（１）の抽出元の通信データからｅｊを抽出し、これをｅｊ（１）とするとともに、Ｒｊ（２）の抽出元の通信データからｅｊを抽出し、これをｅｊ（２）とする。
そして、判定部３１５は、ｅｊ（１）＝ｄｊ（１）の判定と、ｅｊ（２）＝ｄｊ（２）の判定とを行う（Ｓ９０６）。
ｅｊ（１）＝ｄｊ（１）かつｅｊ（２）＝ｄｊ（２）であった場合を（ＯＫ，ＯＫ）と記載し、ｅｊ（１）≠ｄｊ（１）かつｅｊ（２）≠ｄｊ（２）であった場合を（ＮＧ，ＮＧ）と記載する。また、ｅｊ（１）＝ｄｊ（１）かつｅｊ（２）≠ｄｊ（２）であった場合を（ＯＫ，ＮＧ）と記載する。なお、後記して説明するように（ＮＧ，ＯＫ）となることはない。
【００６３】
ステップＳ９０６の結果、（ＯＫ，ＯＫ）であった場合（Ｓ９０６→（ＯＫ，ＯＫ））、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信して（Ｓ９０７）、処理を終了する。
ステップＳ９０６の結果、（ＮＧ，ＮＧ）であった場合（Ｓ９０６→（ＮＧ，ＮＧ））、全体処理部３１１は、判定対象値がが暗号化対象値でないことを示す「Ｎｏ」をサービス提供者サーバ２へ送信して（Ｓ９０８）、処理を終了する。
【００６４】
ステップＳ９０６の結果、（ＯＫ，ＮＧ）であった場合（Ｓ９０６→（ＯＫ，ＮＧ））、基本演算部３１４はｆの値に１を加算したものをｆとして置き換え（Ｓ９０９）、ステップＳ９０３へ処理を戻す。
ステップＳ９０３の結果、ｆ＝ｚである場合（Ｓ９０３→Ｙｅｓ）、すべての桁において、ｅｊ＝ｄｊであることになるため、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信して（Ｓ９１０）、処理を終了する。
なお、ステップＳ９０９あるいはステップＳ９１０の処理において、ユーザ端末１などの属性情報も付加して送信してもよい。
【００６５】
以上の内容を具体例を使用して説明する。
例として、「１７９１」Ｄ（「０１１０  １１１１  １１１１」Ｂ）が全体のしきい値であるものとする。
なお、ここでは、理解を容易にするため、平文で説明するが、実際には暗号化された値で比較が行われる。
、判定対象値がｈを２進展開したときの最初の桁の各値ｊについて、ステップＳ９０６の判定結果のパターンを示すと、以下のようになる。ここで、しきい値ｎは、「１７９１」Ｄ（「０１１０  １１１１  １１１１」Ｂ）における最初の桁の値（この例では「０１１０」Ｂ＝「６」Ｄ）であるものとする。
【００６６】
【表１】
0005416734.tif 000002
【００６７】
ここで、最初の桁が「００００〜０１０１」Ｂである場合（つまり、ステップＳ９０６の判定結果が（ＯＫ，ＯＫ）である場合）、判定対象値がｈは明らかにしきい値より小さい。従って、これ以降の処理を行うことなく、しきい値判定サーバ３は「Ｙｅｓ」を送信して、処理を終了する（図１６のＳ９０７に相当）。
また、最初の桁が「０１１１〜１１１１」Ｂである場合（つまり、ステップＳ９０６の判定結果が（ＮＧ，ＮＧ）である場合）、、判定対象値がｈは明らかにしきい値より大きい。従って、これ以降の処理を行うことなく、しきい値判定サーバ３は「Ｎｏ」を送信して、処理を終了する（図１６のＳ９０８に相当）。
最初の桁が「０１１０」Ｂの場合（つまり、ステップＳ９０６の判定結果が（ＯＫ，ＮＧ）である場合）は、しきい値判定サーバ３は、この桁だけでは、、判定対象値がｈが全体のしきい値より大きいか、小さいかを判定することができないので、次の桁について同様の判定を行う（図１６のＳ９０９に相当）。
なお、この表に示すように、しきい値ｎによる判定が「ＮＧ」となり、しきい値ｎ−１による判定が「ＯＫ」となることはない。
【００６８】
ここでは、しきい値より小さい値を「Ｙｅｓ」と判定する場合を示したが、しきい値より大きい値を「Ｙｅｓ」と判定したい場合、サービス提供者サーバ２は図１４のステップＳ７０４の不等号を反転させればよい。また、ある範囲内の値を「Ｙｅｓ」と判定したい場合は、サービス提供者サーバ２はステップＳ７０４で、その範囲内にｉが入っている場合に図１４のステップＳ７０４→Ｙｅｓとし、それ以外はステップＳ７０４→Ｎｏとすればよい。
【００６９】
＜第３実施形態のまとめ＞
第３実施形態によれば、各桁ごとにしきい値判定用データを用意する必要があるが、各桁での取りうる値の個数を低く抑えられるため（各桁におけるしきい値判定用データが小さいため）、大きな範囲の値を扱う場合でも、しきい値判定用データのデータサイズを小さくすることができる。
【００７０】
《第４実施形態》
《フローチャート》
（しきい値判定用データ生成処理）
図１７は、第４実施形態に係るしきい値判定用データ生成処理の手順を示すきフローチャートである。この処理は、サービス提供者サーバ２によって行われる処理である。
桁数の値としてｚが入力部２３を介して入力されている。
そして、基本演算部２１５は、桁のインデックスｂを０にセットする（Ｓ１００１）。ここで、桁および桁数に関する定義は第３実施形態と同様のものである。
【００７１】
次に、基本演算部２１５は、ｂ＝ｚである否かを判定する（Ｓ１００２）。
ステップＳ１００２の結果、ｂ＝ｚである場合（Ｓ１００２→Ｙｅｓ）、基本演算部２１５が、インデックスｉを１にセットする（Ｓ１００３）。
そして、基本演算部２１５はｉを２進展開する。
基本演算部２１５は、ｉが、処理対象となっている桁におけるしきい値ｎａ以上であるか否かを判定する（Ｓ１００４）。ここで、ｎｂは、各桁におけるしきい値である。しきい値が「１０００」Ｄであったとすると、このしきい値を２進展開した値は「００１１  １１１０  １０００」Ｂとなる。よって、０桁目（ｂ＝０）のｎａ＝「１０００」Ｂ＝「８」Ｄ、１桁目（ｂ＝１）のｎａ＝「１１１０」Ｂ＝「１４」Ｄ、２桁目（ｂ＝２）のｎａ＝「００１１」Ｂ＝「３」Ｄとなる。
その後、基本演算部２１５および暗号化部２１２がステップＳ１００５〜Ｓ１０１２の処理を行う。
ステップＳ１００５〜Ｓ１０１２の処理において、しきい値判定用データに現在処理している桁ｂが追加されること以外は、図６のステップＳ１１３〜Ｓ１２０と同様であるため説明を省略する。
なお、４ビット毎に桁を区切っている場合、ステップＳ１００９におけるｍは、ｍ＝「１１１１」Ｂ＝「１５」Ｄである。
【００７２】
ステップＳ１００９の結果、ｉ＞ｍである場合（Ｓ１００９→Ｎｏ）、基本演算部２１５はｂの値に１を加算したものをｂとして置き換え（Ｓ１０１３）、ステップＳ１００２へ処理を戻す。
ステップＳ１００２の結果、ｂ＝ｚである場合（Ｓ１００２→Ｙｅｓ）、全体処理部２１１は、各桁ｂのしきい値判定用データと、秘密鍵ｋ１と、桁数ｚを、他者に情報が漏洩しない方法を用いて、ユーザ端末１へ送付する（Ｓ１０１４）。しきい値判定用データおよび秘密鍵ｋ１の送付は、暗号化による送信でもよいし、しきい値判定用データおよび秘密鍵ｋ１を格納した媒体を物理的に送付してもよい。
次に、全体処理部２１１は秘密鍵ｋ２と、桁数ｚを、他者に情報が漏洩しない方法を用いて、しきい値判定サーバ３へ送付する（Ｓ１０１５）。秘密鍵ｋ２、桁数ｚの送付は、暗号化による送信でもよいし、秘密鍵ｋ２、桁数ｚを格納した媒体を、物理的に送付してもよい。
【００７３】
（通信データ生成処理）
図１８は、第４実施形態に係る通信データ生成処理の手順を示すフローチャートである。この処理は、ユーザ端末１において行われる処理である。
図１８のステップＳ１１０１〜Ｓ１１０６は、図１５のステップＳ８０１〜Ｓ８０３，Ｓ８０５〜Ｓ８０８と同様であるので説明を省略する。
ステップＳ１１０６の後、暗号化部２１２は、ｊ＋１の場合についても、図１５のステップＳ８０７，Ｓ８０８と同様の処理を行って、しきい値判定用データからＲｊ＋１を読み出す（Ｓ１１０７，Ｓ１１０８）。ここで、ｊは、第３実施形態と同様、判定対象値におけるｂ桁目の値である。
【００７４】
次に、基本演算部１１３は、ｂの値に１を加算したものをｂとして置き換え（Ｓ１１０９）、ステップＳ１１０４へ処理を戻す。
ステップＳ１１０４の結果、ｂ＝ｚである場合（Ｓ１１０４→Ｙｅｓ）、全体処理部２１１は、（ｂ，ｅｊ，Ｒｊ）と、（ｂ，ｅｊ＋１，Ｒｊ＋１）と、記憶部１２の属性情報とを通信データとしてしきい値判定サーバ３へ送信する（Ｓ１１１０）。ここで、ｂ＝０，１，・・・，ｚ−１である。
【００７５】
（しきい値判定処理）
図１９は、第４実施形態に係るしきい値判定処理の手順を示すフローチャートである。この処理は、しきい値判定サーバ３によって行われる処理である。
まず、しきい値判定サーバ３が、図１８のステップＳ１１１０で送信された通信データ（ｂ，ｅｊ，Ｒｊ）および（ｂ，ｅｊ＋１，Ｒｊ＋１）を受信する（Ｓ１２０１）。ここで、ｂ＝０，１，・・・，ｚ−１である。
図１９のステップＳ１２０２，Ｓ１２０３は、図１６のステップＳ９０２，Ｓ９０３と同様の処理であるため、説明を省略する。
そして、復号化は、Ｒｊを暗号値、図１７のステップＳ１０１５で送付された秘密鍵ｋ２を復号鍵とした復号化処理Ｄ（ｋ２，Ｒｊ）を行い、平文ｄｊを算出する（Ｓ１２０４）。
さらに、復号化部３１３は、Ｒｊ＋１を暗号値、図１７のステップＳ１０１５で送付された秘密鍵ｋ２を復号鍵とした復号化処理Ｄ（ｋ２，Ｒｊ＋１）を行い、平文ｄｊ＋１を算出する（Ｓ１２０５）。
そして、判定部３１５は、ｅｊ＝ｄｊの判定と、ｅｊ＋１＝ｄｊ＋１の判定とを行う（Ｓ１２０６）。
【００７６】
ステップＳ１２０６の結果、ｅｊ＝ｄｊかつｅｊ＋１＝ｄｊ＋１であった場合を（ＯＫ，ＯＫ）と記載し、ｅｊ≠ｄｊかつｅｊ＋１≠ｄｊ＋１であった場合を（ＮＧ，ＮＧ）と記載する。また、ｅｊ＝ｄｊかつｅｊ＋１≠ｄｊ＋１であった場合を（ＯＫ，ＮＧ）と記載する
【００７７】
ステップＳ１２０６の結果、（ＯＫ，ＯＫ）であった場合（Ｓ１２０６→（ＯＫ，ＯＫ））、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信して（Ｓ１２０７）、処理を終了する。
ステップＳ１２０６の結果、（ＮＧ，ＮＧ）であった場合（Ｓ１２０６→（ＮＧ，ＮＧ））、全体処理部３１１は、判定対象値が暗号化対象値でないことを示す「Ｎｏ」をサービス提供者サーバ２へ送信して（Ｓ１２０８）、処理を終了する。
【００７８】
ステップＳ１２０６の結果、（ＯＫ，ＮＧ）であった場合（Ｓ１２０６→（ＯＫ，ＮＧ））、基本演算部２１４は、桁数を示すインデックスｆの値に１を加算したものをｆとして置き換え（Ｓ１２０９）、ステップＳ１２０３へ処理を戻す。
ステップＳ１２０３の結果、ｆ＝ｚである場合（Ｓ１２０３→Ｙｅｓ）、すべての桁において、ｅｊ＝ｄｊであることになるため、全体処理部３１１は、判定対象値が暗号化対象値であることを示す「Ｙｅｓ」をサービス提供者サーバ２へ送信して（Ｓ１２１０）、処理を終了する。
なお、ステップＳ１２０７，Ｓ１２０８あるいはステップＳ１２１０の処理において、ユーザ端末１などの属性情報も付加して送信してもよい。
【００７９】
以上の内容を具体例を使用して説明する。
そして、「１７９１」Ｄ（「０１１０  １１１１  １１１１」Ｂが全体のしきい値であるものとする。
なお、ここでは、理解を容易にするため、平文で説明するが、実際には暗号化された値で比較が行われる。
判定対象値ｈを２進展開したときの最初の桁の各値ｊについて、ステップＳ１２０６の判定結果のパターンを示すと、以下のようになる。ここで、しきい値ｎは、「１７９１」Ｄ（「０１１０  １１１１  １１１１」Ｂ）における最初の桁の値（この例では「０１１０」Ｂ＝「６」Ｄ）である。
【００８０】
【表２】
0005416734.tif 000003
【００８１】
ここで、最初の桁の値ｊが「００００〜０１０１」Ｂである場合（つまり、ステップＳ１２０６の判定結果が（ＯＫ，ＯＫ）である場合）、判定対象値ｈは明らかにしきい値より小さい。従って、これ以降の処理を行うことなく、しきい値判定サーバ３は「Ｙｅｓ」を送信して、処理を終了する（図１９のＳ１２０７に相当）。
また、最初の桁の値ｊが「０１１１〜１１１１」Ｂである場合（つまり、ステップＳ１２０６の判定結果が（ＮＧ，ＮＧ）である場合）、判定対象値ｈは明らかにしきい値より大きい。従って、これ以降の処理を行うことなく、しきい値判定サーバ３は「Ｎｏ」を送信して、処理を終了する（図１９のＳ１２０８に相当）。
最初の桁が「０１１０」Ｂの場合（つまり、ステップＳ１２０６の判定結果が（ＯＫ，ＮＧ）である場合）は、しきい値判定サーバ３は、この桁だけでは、判定対象値ｈが全体のしきい値より大きいか、小さいかを判定することができないので、次の桁について同様の判定を行う（図１９のＳ１２０９）に相当。
なお、前記した表示示すように、ｊについての判定が「ＮＧ」で、ｊ＋１についての判定が「ＯＫ」となることはない。
【００８２】
ここでは、しきい値より小さい値を「Ｙｅｓ」と判定する場合を示したが、しきい値より大きい値を「Ｙｅｓ」と判定したい場合、サービス提供者サーバ２は図１７のステップＳ１００４の不等号を反転させればよい。また、ある範囲内の値を「Ｙｅｓ」と判定したい場合は、サービス提供者サーバ２はステップＳ１００４で、その範囲内にｉが入っている場合に図１４のステップＳ１００４→Ｙｅｓとし、それ以外はステップＳ１００４→Ｎｏとすればよい。
【００８３】
＜第４実施形態についてのまとめ＞
第３実施形態では、各桁のしきい値判定用データが、しきい値ｎに対応したものと、しきい値ｎ−１に対応したものとの２つが必要であるが、第４実施形態によれば、しきい値ｎに対応したしきい値判定用データ１つを各桁に関して用意すればよいので、第３実施形態の場合と比較して、しきい値判定用データを半分にすることができる。
【００８４】
なお、第３実施形態、第４実施形態では、第１実施形態に基づいた処理を説明したが、第２実施形態のように公開鍵準同型暗号（準同型暗号）を用いてもよい。
この場合、サービス提供者サーバ２は、図１０に示すサービス提供者サーバ２ａと同様の構成となり、ユーザ端末１は、図９に示すユーザ端末１ａと同様の処理となる。また、各処理は、以下に記載するような処理となる。
【００８５】
（第３実施形態に第２実施形態の公開鍵準同型暗号を用いた場合）
・図１４のステップＳ７０５〜Ｓ７０８の処理が、図１１のステップＳ４０３〜Ｓ４０６と同様の処理となり、ステップＳ７１１の処理がステップＳ４０９と同様の処理となり、、ステップＳ７１６，Ｓ７１７の処理がステップＳ４１１，Ｓ４１２と同様の処理となる。なお、しきい値判定用サーバに桁数ｂに関する情報と、しきい値ｎ，ｎ−１に関する情報が加えられるのは当然である。
・図１５のステップＳ８０７，Ｓ８０８の処理が、図１２のステップＳ５０２〜Ｓ５０６と同様の処理となり、ステップＳ８１０の処理がステップＳ５０７において桁数ｂの情報が加わった処理となる。
・図１６のステップＳ９０１が、図１３のステップＳ６０１と同様の処理となり、ステップＳ９０４，Ｓ９０５の処理が、それぞれステップＳ６０２と同様の処理となる。
【００８６】
（第４実施形態に第２実施形態の公開鍵準同型暗号を用いた場合）
・図１７のステップＳ１００５〜Ｓ１００８の処理が、図１１のステップＳ４０３〜Ｓ４０６と同様の処理となり、ステップＳ１０１１の処理がステップＳ４０９と同様の処理となり、、ステップＳ１０１４，Ｓ１０１５の処理がステップＳ４１１，Ｓ４１２と同様の処理となる。なお、しきい値判定用サーバに桁数ｂに関する情報が加えられるのは当然である。
・図１８のステップＳ１１０７，Ｓ１１０８の処理が、図１２のステップＳ５０２〜Ｓ５０６と同様の処理となり、ステップＳ１１１０の処理がステップＳ５０７において桁数ｂの情報が加わった処理となる。
・図１９のステップＳ１２０１が、図１３のステップＳ６０１と同様の処理となり、ステップＳ１２０４，Ｓ１２０５の処理が、それぞれステップＳ６０２と同様の処理となる。
【００８７】
なお、それぞれの処理は、暗号化対象数値が、しきい値より大きい（以上）場合、あるいはしきい値より小さい（以下）場合のそれぞれに適用可能である。
【００８８】
《適用例１》
例えば、第１〜第４実施形態に記載の技術を自動車メーカが、自動車購入者の保持する車両の状態把握のために車両の内部に蓄積している種々の制御データを定期的に収集し、各データについてしきい値判定を行うことに適用することができる。
自動車メーカは、整備や修理について、自動車整備会社に委託し、整備マニュアルなどの情報は提供しているとする。しかし、状態把握のために必要な制御データは自動車メーカにとっては、重要なノウハウであり、そのデータが漏洩することはノウハウを蓄積するために行った投資を無駄にすることになるため、秘匿化して守る必要がある。そのため、車両のデータとしきい値をともに秘匿化しつつ、自動車整備会社において、あるしきい値を超えているか否か判定可能であるような方式が必要となる。
【００８９】
この適用例１では、ユーザ端末１は自動車購入者の保持する車両に設置され、サービス提供者サーバ２は自動車メーカに設置され、しきい値判定サーバ３が自動車整備会社に設置されることになる。
自動車メーカに設置されたサービス提供者サーバ２は、第１〜第４実施形態に記載されたいずれかの方法によるしきい値判定用データ生成方法で、制御データに対するしきい値判定用データや、暗号用の各鍵を生成する。
【００９０】
車両に設置されているユーザ端末１には販売時にしきい値判定用データや、暗号化のための各鍵などを格納しておき、自動車整備会社に対しては、要請に従って必要なデータ（復号化のための各鍵など）を安全に送信する。このとき、同一の車種について同一の鍵で実施してもよいし、自動車購入者ごとに鍵を変えてもよい。
整備の際には、自動車整備会社のしきい値判定サーバ３は車両のユーザ端末１に対して、しきい値判定に必要な制御データ（通信データ）の生成を要求し、車両のユーザ端末１は第１〜第４実施形態におけるいずれかの通信データ生成処理の手順に従い、制御データ（通信データ）を生成して、自動車整備会社のしきい値判定サーバ３へ通信データを送信する。
【００９１】
通信データ送信の方法は、有線／無線による専用回線を介してもよいし、インターネットなどのネットワーク４を介してもよい。
自動車整備会社のしきい値判定サーバ３は第１〜第４実施形態のいずれかのしきい値判定処理を実行し、その結果が「ＮＯ」の場合（例えば、しきい値を超えている場合）は、整備マニュアルに従い整備、修理を行うようにする。また、制御データの種類によっては、自動車メーカに連絡してもよい。
【００９２】
《適用例２》
また、例えば、第１〜第４実施形態に記載の技術を電力会社が、各家庭における消費電力や、太陽電池パネルなどの発電量に関するデータを収集するために適用してもよい。
この場合、ユーザ端末１は各家庭に設置され、サービス提供者サーバ２は電力会社に設置され、しきい値判定サーバ３は変電所などに設置される。
【符号の説明】
【００９３】
１，１ａ  ユーザ端末
２，２ａ  サービス提供者サーバ（サーバ）
３      しきい値判定サーバ（判定サーバ）
１２    記憶部（ユーザ端末）
１３    入力部（ユーザ端末）
２２    記憶部（サービス提供者サーバ）
３２    記憶部（しきい値判定サーバ）
１１１  全体処理部（ユーザ端末）
１１２  暗号化部（ユーザ端末）
１１３  基本演算部（ユーザ端末）
１１４  公開鍵準同型暗号化部（ユーザ端末）
１１５  乱数生成部（ユーザ端末）
２１１  全体処理部（サービス提供者サーバ）
２１２  暗号化部（サービス提供者サーバ）
２１４  乱数生成部（サービス提供者サーバ）
２１５  基本演算部（サービス提供者サーバ）
２１６  公開鍵準同型暗号化部（サービス提供者サーバ）
３１１  全体処理部（しきい値判定サーバ）
３１３  復号化部（しきい値判定サーバ）
３１４  基本演算部（しきい値判定サーバ）
３１５  判定部（しきい値判定サーバ）
Ａ      しきい値判定システム（判定システム）
【図１】
0005416734.tif 000004
【図２】
0005416734.tif 000005
【図３】
0005416734.tif 000006
【図４】
0005416734.tif 000007
【図５】
0005416734.tif 000008
【図６】
0005416734.tif 000009
【図７】
0005416734.tif 000010
【図８】
0005416734.tif 000011
【図９】
0005416734.tif 000012
【図１０】
0005416734.tif 000013
【図１１】
0005416734.tif 000014
【図１２】
0005416734.tif 000015
【図１３】
0005416734.tif 000016
【図１４】
0005416734.tif 000017
【図１５】
0005416734.tif 000018
【図１６】
0005416734.tif 000019
【図１７】
0005416734.tif 000020
【図１８】
0005416734.tif 000021
【図１９】
0005416734.tif 000022