(57)【特許請求の範囲】
【請求項１】
Ｌが１以上の整数であり、εが２以上の整数であり、Ｆが有限体であり、Ｆεが前記有限体Ｆの拡大体であり、前記拡大体Ｆεの拡大次数がεであり、ｃｅｉｌ（ｘ）が実数ｘ以上の最小の整数であり、Ｍ＝ｃｅｉｌ（Ｌ／ε）であり、ｊ＝０，…、Ｌ−１であり、ｍ＝０，…，Ｍ−１であり、
認証情報ｗの秘密分散値である秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌを格納する記憶部と、
認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ∈［Ｆ］Ｌの入力を受け付ける入力部と、
前記秘匿化認証情報［ｗ］ｉおよび前記秘匿化認証情報［ω］ｉを用い、秘密計算によって第１秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉを得る第１演算部と、
拡大体乱数ｒｍの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］を得る乱数生成部と、
ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｍ＝０，…，Ｍ−１についてｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０であり、前記第１秘匿化検証値［ｚ］ｉを用い、秘密計算によってｙｍを秘匿化した第２秘匿化検証値［ｙｍ］ｉを得る第２演算部と、
前記秘匿化拡大体乱数［ｒｍ］ｉおよび前記第２秘匿化検証値［ｙｍ］ｉを用い、秘密計算によって第３秘匿化検証値［ｒｍｙｍ］ｉを得て出力する第３演算部と、
を有する秘密計算装置。
【請求項２】
請求項１の秘密計算装置であって、
Ｍが２以上の整数である、秘密計算装置。
【請求項３】
請求項１または２の秘密計算装置であって、
ＫおよびＮが２以上の整数であり、Ｋ≦Ｎであり、
前記秘匿化拡大体乱数［ｒｍ］ｉは、（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値であり、
前記第２演算部は、前記第１秘匿化検証値［ｚ］ｉを表す列の要素を結合して前記第２秘匿化検証値［ｙｍ］ｉを得、
前記第３演算部は、前記第２秘匿化検証値［ｙｍ］ｉを前記（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値として前記第３秘匿化検証値［ｒｍｙｍ］ｉを得、
前記第３秘匿化検証値［ｒｍｙｍ］ｉが（２Ｋ−１，Ｎ）シャミア秘密分散方式に則った秘密分散値となる、秘密計算装置。
【請求項４】
請求項３の秘密計算装置であって、
Ｋ＝２である、秘密計算装置。
【請求項５】
請求項４の秘密計算装置であって、
ｒｍ∈Ｆεであり、ｒｓｍ∈Ｆεであり、ｙｓｍ∈Ｆεであり、Ｒｓｍ∈Ｆεであり、Ｉ∈Ｆεであり、［ｒｍ］ｉ＝ｒｍ＋ｒｓｍ・Ｉ∈Ｆεであり、［ｙｍ］ｉ＝ｙｍ＋ｙｓｍ・Ｉ∈Ｆεであり、［ｒｍｙｍ］ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ）・Ｉ＋ｒｓｍ・ｙｓｍ・Ｉ２∈Ｆεであり、
当該秘密計算装置は、
第２拡大体乱数Ｒｍ∈Ｆεの秘密分散値である第２秘匿化拡大体乱数［Ｒｍ］ｉ＝Ｒｍ＋Ｒｓｍ・Ｉ∈Ｆεを得る第２乱数生成部と、
拡大体乗算値［Ｒｍ］ｉ・Ｉ＝Ｒｍ・Ｉ＋Ｒｓｍ・Ｉ２∈Ｆεを得る第４演算部と、
第４秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ＋Ｒｍ）・Ｉ＋（ｒｓｍ・ｙｓｍ＋Ｒｓｍ）・Ｉ２∈Ｆεを得て出力する第５演算部と、
をさらに有する秘密計算装置。
【請求項６】
複数の秘密計算装置と検証装置とを有し、
Ｌが１以上の整数であり、εが２以上の整数であり、Ｆが有限体であり、Ｆεが前記有限体Ｆの拡大体であり、前記拡大体Ｆεの拡大次数がεであり、ｃｅｉｌ（ｘ）が実数ｘ以上の最小の整数であり、Ｍ＝ｃｅｉｌ（Ｌ／ε）であり、ｊ＝０，…、Ｌ−１であり、ｍ＝０，…，Ｍ−１であり、
前記秘密計算装置のそれぞれは、
認証情報ｗの秘密分散値である秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌを格納する記憶部と、
認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ∈［Ｆ］Ｌの入力を受け付ける第１入力部と、
前記秘匿化認証情報［ｗ］ｉおよび前記秘匿化認証情報［ω］ｉを用い、秘密計算によって第１秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉを得る第１演算部と、
拡大体乱数ｒｍの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］を得る乱数生成部と、
ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｍ＝０，…，Ｍ−１についてｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０であり、前記第１秘匿化検証値［ｚ］ｉを用い、秘密計算によってｙｍを秘匿化した第２秘匿化検証値［ｙｍ］ｉを得る第２演算部と、
前記秘匿化拡大体乱数［ｒｍ］ｉおよび前記第２秘匿化検証値［ｙｍ］ｉを用い、秘密計算によって第３秘匿化検証値［ｒｍｙｍ］ｉを得て出力する第３演算部と、を含み、
前記検証装置は、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功と判定する、秘密計算認証システム。
【請求項７】
請求項６の秘密計算認証システムであって、
Ｎ個の前記秘密計算装置を有し、
Ｎが３以上の整数であり、
前記秘匿化拡大体乱数［ｒｍ］ｉは、（２，Ｎ）シャミア秘密分散方式に則った秘密分散値であり、
前記第２演算部は、前記第１秘匿化検証値［ｚ］ｉを表す列の要素を結合して前記第２秘匿化検証値［ｙｍ］ｉを得、
前記第３演算部は、前記第２秘匿化検証値［ｙｍ］ｉを前記（２，Ｎ）シャミア秘密分散方式に則った秘密分散値として前記第３秘匿化検証値［ｒｍｙｍ］ｉを得、
ｒｍ∈Ｆεであり、ｒｓｍ∈Ｆεであり、ｙｓｍ∈Ｆεであり、Ｒｓｍ∈Ｆεであり、Ｉ∈Ｆεであり、［ｒｍ］ｉ＝ｒｍ＋ｒｓｍ・Ｉ∈Ｆεであり、［ｙｍ］ｉ＝ｙｍ＋ｙｓｍ・Ｉ∈Ｆεであり、［ｒｍｙｍ］ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ）・Ｉ＋ｒｓｍ・ｙｓｍ・Ｉ２∈Ｆεであり、ｉ＝１，…，Ｎであり、
前記秘密計算装置のそれぞれは、
第２拡大体乱数Ｒｍ∈Ｆεの秘密分散値である第２秘匿化拡大体乱数［Ｒｍ］ｉ＝Ｒｍ＋Ｒｓｍ・Ｉ∈Ｆεを得る第２乱数生成部と、
拡大体乗算値［Ｒｍ］ｉ・Ｉ＝Ｒｍ・Ｉ＋Ｒｓｍ・Ｉ２∈Ｆεを得る第４演算部と、
第４秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ＋Ｒｍ）・Ｉ＋（ｒｓｍ・ｙｓｍ＋Ｒｓｍ）・Ｉ２∈Ｆεを得て出力する第５演算部と、をさらに含む、
前記検証装置は、（３，Ｎ）シャミア秘密分散方式に則って、｛φ（１），φ（２），φ（３）｝⊆｛１，…，Ｎ｝について、［ｒｍｙｍ］φ（１）＋［Ｒｍ］φ（１）・Ｉと［ｒｍｙｍ］φ（２）＋［Ｒｍ］φ（２）・Ｉと［ｒｍｙｍ］φ（３）＋［Ｒｍ］φ（３）・Ｉとに対する演算を行い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功と判定する、秘密計算認証システム。
【請求項８】
秘密計算装置の秘密計算方法であって、
Ｌが１以上の整数であり、εが２以上の整数であり、Ｆが有限体であり、Ｆεが前記有限体Ｆの拡大体であり、前記拡大体Ｆεの拡大次数がεであり、ｃｅｉｌ（ｘ）が実数ｘ以上の最小の整数であり、Ｍ＝ｃｅｉｌ（Ｌ／ε）であり、ｊ＝０，…、Ｌ−１であり、ｍ＝０，…，Ｍ−１であり、
入力部が、認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ∈［Ｆ］Ｌの入力を受け付ける入力ステップと、
第１演算部が、認証情報ｗの秘密分散値である秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌおよび前記秘匿化認証情報［ω］ｉを用い、秘密計算によって第１秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉを得る第１演算ステップと、
乱数生成部が、拡大体乱数ｒｍの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］を得る乱数生成ステップと、
ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｍ＝０，…，Ｍ−１についてｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０であり、第２演算部が、前記第１秘匿化検証値［ｚ］ｉを用い、秘密計算によってｙｍを秘匿化した第２秘匿化検証値［ｙｍ］ｉを得る第２演算ステップと、
第３演算部が、前記秘匿化拡大体乱数［ｒｍ］ｉおよび前記第２秘匿化検証値［ｙｍ］ｉを用い、秘密計算によって第３秘匿化検証値［ｒｍｙｍ］ｉを得る第３演算ステップと、
を有する秘密計算方法。
【請求項９】
請求項１から５の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算技術に関し、特に、秘密計算によって認証処理を行う秘密計算認証技術に関する。
【背景技術】
【０００２】
秘密計算技術（例えば、非特許文献１等参照）を用いれば、認証情報（例えば、パスワード）を秘密に保ったまま認証処理を行うことができる。単純な方法は、登録済みの認証情報ｗの秘匿化認証情報［ｗ］と入力された認証情報ωの秘匿化認証情報［ω］とを用い、秘密計算によってｗ−ωに対応する秘匿化検証値［ｗ−ω］を計算する方法である。ｗ−ω＝０であればｗ＝ω（認証成功）であり、ｗ−ω≠０であればｗ≠ω（認証失敗）であるため、秘匿化検証値［ｗ−ω］は認証結果の秘匿値を表す。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, Tomas Toft, “Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation”, TCC 2006, pp. 285-304.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、上述した方法では、なりすましに対する安全性が低いという問題点がある。すなわち、ｗ−ω≠０であるにもかかわらず０が復元されるような不正な秘匿化検証値が計算された場合には、ｗ−ω≠０であるにもかかわらず認証成功と判定されてしまう。また認証情報ｗ，ωが秘密に保たれているため、このような不正な秘匿化検証値を検知することも困難である。【０００５】
本発明の目的は、認証情報を秘密に保ったまま、なりすましに対する安全性が高い認証処理を行う技術を提供することである。
【課題を解決するための手段】
【０００６】
秘密計算装置は、認証情報ｗの秘密分散値である秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌを格納し、認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ∈［Ｆ］Ｌの入力を受け、秘匿化認証情報［ｗ］ｉおよび秘匿化認証情報［ω］ｉを用い、秘密計算によって第１秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉを得、拡大体乱数ｒｍの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］を得、第１秘匿化検証値［ｚ］ｉを用い、秘密計算によってｙｍを秘匿化した第２秘匿化検証値［ｙｍ］ｉを得、秘匿化拡大体乱数［ｒｍ］ｉおよび第２秘匿化検証値［ｙｍ］ｉを用い、秘密計算によって第３秘匿化検証値［ｒｍｙｍ］ｉを得て出力する。ただし、Ｌが１以上の整数であり、εが２以上の整数であり、Ｆが有限体であり、Ｆεが有限体Ｆの拡大体であり、拡大体Ｆεの拡大次数がεであり、ｃｅｉｌ（ｘ）が実数ｘ以上の最小の整数であり、Ｍ＝ｃｅｉｌ（Ｌ／ε）であり、ｊ＝０，…、Ｌ−１であり、ｍ＝０，…，Ｍ−１であり、ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｍ＝０，…，Ｍ−１についてｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）‐１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０である。
【発明の効果】
【０００７】
認証情報を秘密に保ったまま、なりすましに対する安全性が高い認証処理を行うことができる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の秘密計算認証システムの機能構成を例示したブロック図である。
【図２】図２は実施形態の秘密計算装置の機能構成を例示したブロック図である。
【図３】図３Ａは実施形態の利用者装置の機能構成を例示したブロック図である。図３Ｂは実施形態の検証装置の機能構成を例示したブロック図である。
【図４】図４は実施形態の利用者装置の処理を説明するためのフロー図である。
【図５】図５は実施形態の秘密計算装置の処理を説明するためのフロー図である。
【図６】図６は実施形態の検証装置の処理を説明するためのフロー図である。
【図７】図７は実施形態の処理を説明するための概念図である。
【発明を実施するための形態】
【０００９】
以下、図面を用いて本発明の実施形態を説明する。
［概要］
実施形態の秘密計算認証システムは、Ｎ個（複数個）の秘密計算装置Ｐ１，…，ＰＮと検証装置とを有する。検証装置はＮ個の秘密計算装置Ｐ１，…，ＰＮの外部の装置であってもよいし、何れかの秘密計算装置Ｐｉの内部に含まれた装置であってもよい。秘密計算装置Ｐｉのそれぞれは、認証情報ｗの秘密分散値である秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌを記憶部に格納する。ただし、ｉ＝１，…，Ｎであり、Ｎは２以上の整数である。「β１∈β２」はβ１がβ２に属することを表す。Ｆは有限体を表し、Ｌは１以上の整数を表す。有限体Ｆは、素体であってもよいし、拡大体であってもよい。例えばＬは２以上の整数である。［Ｆ］は有限体Ｆの元の秘密分散値を表し、［Ｆ］ＬはＬ個の［Ｆ］からなる集合を表す。［α］ｉは秘密計算装置Ｐｉに割り当てられたαの秘密分散値を意味する。認証情報ｗは正規の利用者に対して事前登録されたものである。認証情報ｗに限定はなく、例えば、パスワード、生体認証情報、音声認証情報、パターン認証情報等どのようなものであってもよい。秘密計算装置Ｐｉのそれぞれは、複数個の認証情報ｗにそれぞれ対応する秘匿化認証情報［ｗ］ｉを格納してもよいし、単数の認証情報ｗに対応する秘匿化認証情報［ｗ］ｉのみを格納してもよい。秘密分散値を得るための秘密分散方式に限定はなく、複製型秘密分散方式（例えば、参考文献１等参照）、シャミア秘密分散方式（例えば、参考文献２等参照）などの周知の（Ｋ，Ｎ）秘密分散方式（「K-out-of-Nしきい値秘密分散方式」ともいう）を用いればよい。ただし、Ｋは２以上の整数であり、Ｋ≦Ｎを満たす。例えばＫ＝２である。（Ｋ，Ｎ）秘密分散方式では、任意の相違なるＫ個の秘密分散値が与えられれば秘匿化されている秘密情報を復元できるが、任意のＫ−１個の秘密分散値が与えられても秘密情報の情報はまったく得られない。以下では（Ｋ，Ｎ）秘密分散方式であるシャミア秘密分散方式を「（Ｋ，Ｎ）シャミア秘密分散方式」と呼ぶ。
参考文献１：五十嵐大，千田浩司，濱田浩気，高橋克巳，“軽量検証可能３パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理，”ＩｎＳＣＩＳ２０１１，２０１１．
参考文献２：A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.
【００１０】
各秘密計算装置Ｐｉの入力部には、認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ∈［Ｆ］Ｌが入力される。各秘密計算装置Ｐｉの演算部は、秘匿化認証情報［ｗ］ｉおよび秘匿化認証情報［ω］ｉを用い、秘密計算によって第１秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉを得て出力する。［ｗ−ω］ｉはｗ−ωの秘密分散値を表す。秘密計算方法に限定はなく、例えば非特許文献１や参考文献３に記載された周知の秘密計算方法を用いればよい。以下の秘密計算についても同様である。
参考文献３：千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【００１１】
各秘密計算装置Ｐｉの乱数生成部は、拡大体乱数ｒｍ∈Ｆεの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］を得て出力する。ただし、εが２以上の整数であり、Ｆεが有限体Ｆの拡大体であり、拡大体Ｆεの拡大次数がεである。ｃｅｉｌは天井関数であり、ｃｅｉｌ（ｘ）は実数ｘ以上の最小の整数を表す。ｍ＝０，…，Ｍ−１であり、Ｍ＝ｃｅｉｌ（Ｌ／ε）を満たす。Ｍは１以上の整数である。例えば、Ｍは２以上の整数である。秘匿化拡大体乱数［ｒｍ］ｉの生成は、いずれの秘密計算装置Ｐｉからも拡大体乱数ｒｍが秘匿された状態で行われなければならない。このような方法はよく知られており、どのような方法が用いられてもよい。例えば、秘密計算装置Ｐ１，…，ＰＮが協調して秘匿化拡大体乱数［ｒｍ］ｉを生成できる。一例を挙げると、各秘密計算装置Ｐｉ’がそれぞれ拡大体乱数ｒｍ，ｉ’の秘密分散値［ｒｍ，ｉ’］ｉ∈［Ｆε］を計算して秘密計算装置Ｐｉに送り（ただし、ｉ＝１，…，Ｎ、ｉ’＝１，…，Ｎかつｉ’≠ｉ）、各秘密計算装置Ｐｉが秘密分散値［ｒｍ，１］ｉ，…，［ｒｍ，Ｎ］ｉを用いた秘密計算によって［ｒｍ］ｉ＝［ｒｍ，１＋…＋ｒｍ，Ｎ］ｉを得る。
【００１２】
各秘密計算装置Ｐｉの演算部は、第１秘匿化検証値［ｚ］ｉを用い、秘密計算によってｙｍを秘匿化した第２秘匿化検証値［ｙｍ］ｉを得て出力する。ただし、ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｊ＝０，…、Ｌ−１であり、ｍ＝０，…，Ｍ−１についてｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０である。ｑ＞Ｌ−１となるｚｑはｚｑ＝０とされてもよいし（すなわち、０がｚｑにパディングされてもよいし）、ｑ＞Ｌ−１となるｚｑが０であることを表す情報が付加されてもよい。各秘密計算装置Ｐｉの演算部は、第１秘匿化検証値［ｚ］ｉを表す列を分割して各第２秘匿化検証値［ｙｍ］ｉを得てもよい。例えば、ｑ＞Ｌ−１となるｚｑが存在しないのであれば、各秘密計算装置Ｐｉの演算部が第１秘匿化検証値［ｚ］ｉ＝［ｙ０］ｉ｜…｜［ｙＭ−１］ｉをＭ個に分割して［ｙ０］ｉ，…，［ｙＭ−１］ｉを得てもよい。ただし、α１｜α２はα１とα２との連結を表す。ｑ＞Ｌ−１となるｚｑが存在するのであれば、各秘密計算装置Ｐｉの演算部は、第１秘匿化検証値［ｚ］ｉ＝［ｙ０］ｉ｜…｜［ｙＭ−２］ｉ｜［ｙ’Ｍ−１］ｉを［ｙ０］ｉ，…，［ｙＭ−２］ｉ，［ｙ’Ｍ−１］ｉに分割するとともに、ｑ＞Ｌ−１についてのｚｑ＝０の秘密分散値［０，…，０］ｉまたはｑ＞Ｌ−１となるｚｑが０であることを表す情報の秘密分散値［０，…，０］ｉを得、［ｙＭ−１］ｉ＝［ｙ’Ｍ−１］ｉ｜［０，…，０］ｉとしてもよい。
【００１３】
第２秘匿化検証値［ｙｍ］ｉはε次拡大体Ｆε上の（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値として扱うことができる。Ｋ＝２の場合について説明する。ｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）をε次拡大体の元をベクトル表現したものとみなす。すなわち、ｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）∈Ｆεとして扱う。ε次拡大体Ｆε上の（２，Ｎ）シャミア秘密分散方式に則ってｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）∈Ｆεを秘密分散して得られる秘密分散値［ｙｍ］ｉは、以下のようになる。
［ｙｍ］ｉ＝ｙｍ＋ｙｓｍ・Ｉ
＝（ｚεｍ＋ｙｓｍ，０・ｉ，…，ｚε（ｍ＋１）−１＋ｙｓｍ，ε−１・ｉ）    （１）
なぜなら、ε次拡大体Ｆε上の（２，Ｎ）シャミア秘密分散方式に則って秘密分散値を求めるための多項式をｇ（χ）＝ｙ０＋ｙｓｍ・χ∈Ｆεとみなせるからである。ただし、ｙｓｍ，０，…，ｙｓｍ，ε−１は拡大体乱数ｙｓｍ∈Ｆεのベクトル表現ｙｓｍ＝（ｙｓｍ，０，…，ｙｓｍ，ε−１）∈Ｆεの各要素であり、ｉに対応する座標軸Ｉ∈Ｆεのベクトル表現がＩ＝（ｉ，０，…，０）∈Ｆεである。座標軸χ＝（η，０，…，０）∈Ｆεであり、ηは整数変数である。χ＝Ｉ＝（ｉ，０，…，０）としたｇ（Ｉ）が［ｙｍ］ｉであり、χ＝０＝（０，０，…，０）としたｇ（０）がｙｍである。式（１）に示すように、この秘密分散値［ｙｍ］ｉはε次拡大体Ｆεの元となっている。なお、ｙｍ∈Ｆε，ｙｓｍ∈Ｆε，Ｉ∈Ｆεを多項式表現すると以下のようになる。
ｙｍ＝ｚεｍ＋ｚεｍ＋１・Ｘ＋…＋ｚε（ｍ＋１）−１・Ｘε−１
ｙｓｍ＝ｓｍ，０＋ｓｍ，１・Ｘ＋…＋ｙｓｍ，ε−１・Ｘε−１
Ｉ＝ｉ＋０・Ｘ＋…＋０・Ｘε−１
従って、ｙｍ＋ｙｓｍ・Ｉ∈Ｆεを多項式表現すると以下のようになる。
ｙｍ＋ｙｓｍ・Ｉ
＝ｚεｍ＋ｚεｍ＋１・Ｘ＋…＋ｚε（ｍ＋１）−１・Ｘε−１＋（ｓｍ，０＋ｓｍ，１・Ｘ＋…＋ｙｓｍ，ε−１・Ｘε−１）（ｉ＋０・Ｘ＋…＋０・Ｘε−１）
＝ｚεｍ＋ｚεｍ＋１・Ｘ＋…＋ｚε（ｍ＋１）−１・Ｘε−１＋ｓｍ，０・Ｉ＋ｓｍ，１・Ｉ・Ｘ＋…＋ｙｓｍ，ε−１・Ｉ・Ｘε−１
＝ｚεｍ＋ｓｍ，０・Ｉ＋（ｚεｍ＋１＋ｓｍ，１・Ｉ）・Ｘ＋…＋（ｚε（ｍ＋１）−１＋ｙｓｍ，ε−１・Ｉ）・Ｘε−１    （２）
ただし、Ｘは有限体Ｆ上の既約多項式ρ（Ｘ）についてρ（Ｘ）＝０を満たす。式（２）の各係数を要素とするベクトルは（ｚεｍ＋ｙｓｍ，０・ｉ，…，ｚε（ｍ＋１）−１＋ｙｓｍ，ε−１・ｉ）となる。このことから、ｙｍ＋ｙｓｍ・Ｉ∈Ｆεをベクトル表現すると式（１）のようになることが分かる。
【００１４】
Ｌ＝２、ε＝２、Ｋ＝２、Ｎ＝３、有限体Ｆが位数５の素体ＧＦ（５）であるの場合の簡単な例を示す。ｚ０＝０、ｚ１＝０を素体ＧＦ（５）上で（２，３）シャミア秘密分散方式によって秘密分散した場合、秘密計算装置Ｐｉに対応するｚ０、ｚ１秘密分散値の一例は、それぞれ、ｆ０（ｉ）＝ｚ０＋２ｉ  ｍｏｄ  ５、ｆ１（ｉ）＝ｚ１＋ｉ  ｍｏｄ  ５である。このときＭ＝ｃｅｉｌ（２／２）＝１であり、第２秘匿化検証値［ｙ０］ｉ＝［（ｚ０，ｚ１）］ｉは［ｙ０］ｉ＝［（ｚ０＋２ｉ  ｍｏｄ  ５，ｚ１＋ｉ  ｍｏｄ  ５）］ｉとなる。すなわち、［ｙ０］１＝［（２，１）］１、［ｙ０］２＝［（４，２）］２、［ｙ０］３＝［（１，３）］３となる。このとき、第２秘匿検証値［ｙ０］ｉは、ＧＦ（５）の２次拡大体Ｆε＝ＧＦ（５２）上でのシャミア秘密分散法に則った秘密分散値と扱っても構わない。これは、（２，Ｎ）シャミア秘密分散方式に則って秘密分散値を求めるための多項式をｇ（χ）＝ｙ０＋ｙｓｍ・χ∈ＧＦ（５２）とみなせるためである。ただし、秘密情報ｙ０＝（ｚ０，ｚ１）であり、乱数ｙｓｍ＝（２，１）であり、座標軸χ＝（η，０）とする。ηは整数変数であり、χ＝Ｉ＝（ｉ，０）としたｇ（Ｉ）が［ｙ０］ｉであり、χ＝（０，０）＝０としたｇ（０）がｙ０である。このように第２秘匿化検証値［ｙｍ］ｉはε次拡大体Ｆε上の（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値として扱うことができる。
【００１５】
各秘密計算装置Ｐｉの演算部は、秘匿化拡大体乱数［ｒｍ］ｉおよび第２秘匿化検証値［ｙｍ］ｉを用い、秘密計算によって第３秘匿化検証値［ｒｍｙｍ］ｉを得て出力する。上述のように、秘匿化認証情報［ｗ］ｉが（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値であり、秘匿化認証情報［ω］ｉが（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値であり、第１秘匿化検証値［ｚ］ｉを表す列の要素を結合して各第２秘匿化検証値［ｙｍ］ｉが得られ、秘匿化拡大体乱数［ｒｍ］ｉが（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値である場合、各秘密計算装置Ｐｉの演算部は、第２秘匿化検証値［ｙｍ］ｉを（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値として第３秘匿化検証値［ｒｍｙｍ］ｉを得ることができる。各秘密計算装置Ｐｉの演算部は、例えば、［ｒｍｙｍ］ｉ＝［ｒｍ］ｉ［ｙｍ］ｉの計算（拡大体Ｆε上での乗算）を行う。２個の（Ｋ，Ｎ）シャミア秘密分散方式に則った秘密分散値の乗算結果は（２Ｋ−１，Ｎ）シャミア秘密分散方式に則った秘密分散値となる。そのため、このように得られた第３秘匿化検証値［ｒｍｙｍ］ｉは（２Ｋ−１，Ｎ）シャミア秘密分散方式に則った秘密分散値となる。例えば、Ｋ＝２の場合、第３秘匿化検証値［ｒｍｙｍ］ｉは（３，Ｎ）シャミア秘密分散方式に則った秘密分散値となっている。すなわち、式（１）と同様、ε次拡大体Ｆε上の（２，Ｎ）シャミア秘密分散方式に則ってｒｍ∈Ｆεを秘密分散して得られる秘密分散値［ｒｍ］ｉは、以下のようになる。
［ｒｍ］ｉ＝ｒｍ＋ｒｓｍ・Ｉ    （３）
ただし、ｒｓｍ∈Ｆεは拡大体乱数である。式（２）および式（３）から、以下を満たすことが分かる。
［ｒｍｙｍ］ｉ＝［ｒｍ］ｉ［ｙｍ］ｉ
＝（ｙｍ＋ｙｓｍ・Ｉ）（ｒｍ＋ｒｓｍ・Ｉ）
＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓ＋ｒｓ・ｙｍ）・Ｉ＋ｒｓ・ｙｓ・Ｉ２∈Ｆε    （４）
これにより、［ｒｍｙｍ］ｉが（３，Ｎ）シャミア秘密分散方式に則ったｒｍｙｍの秘密分散値となっていることが分かる。なぜなら、ε次拡大体Ｆε上の（３，Ｎ）シャミア秘密分散方式に則って秘密分散値を求めるための多項式をｇ’（χ）＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓ＋ｒｓ・ｙｍ）・χ＋ｒｓ・ｙｓ・χ２∈Ｆεとみなせ、χ＝Ｉ＝（ｉ，０，…，０）としたｇ’（Ｉ）が［ｒｍｙｍ］ｉとなり、χ＝０＝（０，０，…，０）としたｇ’（０）がｒｍ・ｙｍとなるからである。
【００１６】
ここで、第３秘匿化検証値［ｒ０ｙ０］ｉ，…，［ｒＭ−１ｙＭ−１］ｉが認証結果の秘匿値として出力されてもよい（方式１）。しかし、各秘密計算装置Ｐｉがさらに以下の処理を行うことでさらに安全性を向上させることができる（方式２）。方式２の場合、さらに各秘密計算装置Ｐｉの乱数生成部が、ε次拡大体Ｆε上の（２，Ｎ）シャミア秘密分散方式に則って、第２拡大体乱数Ｒｍ∈Ｆεの秘密分散値である第２秘匿化拡大体乱数［Ｒｍ］ｉ＝Ｒｍ＋Ｒｓｍ・Ｉ∈Ｆεを得て出力する。前述した秘匿化拡大体乱数［ｒｍ］ｉの生成と同様、第２秘匿化拡大体乱数［Ｒｍ］ｉの生成は、いずれの秘密計算装置Ｐｉからも第２拡大体乱数Ｒｍが秘匿された状態で行われなければならない。このような方法はよく知られており、どのような方法が用いられてもよい。次に、各秘密計算装置Ｐｉの演算部が、第２秘匿化拡大体乱数［Ｒｍ］ｉとＩとを用い、拡大体乗算値［Ｒｍ］ｉ・Ｉ＝Ｒｍ・Ｉ＋Ｒｓｍ・Ｉ２∈Ｆεを得て出力する。さらに、各秘密計算装置Ｐｉの演算部が、第３秘匿化検証値［ｒｍｙｍ］ｉと拡大体乗算値［Ｒｍ］ｉ・Ｉとを用い、第４秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ＋Ｒｍ）・Ｉ＋（ｒｓｍ・ｙｓｍ＋Ｒｓｍ）・Ｉ２∈Ｆεを得て出力する。ここで［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉは、ε次拡大体Ｆε上の（３，Ｎ）シャミア秘密分散方式に則ったｒｍ・ｙｍの秘密分散値となっている。なぜなら、ε次拡大体Ｆε上の（３，Ｎ）シャミア秘密分散方式に則って秘密分散値を求めるための多項式をｇ”（χ）＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ＋Ｒｍ）・χ＋（ｒｓｍ・ｙｓｍ＋Ｒｓｍ）・χ２∈Ｆεとみなせ、χ＝Ｉ＝（ｉ，０，…，０）としたｇ’（Ｉ）が［ｒｍｙｍ］ｉとなり、χ＝０＝（０，０，…，０）としたｇ’（０）がｒｍ・ｙｍとなるからである。
【００１７】
検証装置は、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功と判定する。一方、検証装置は、何れかのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たさない場合に認証失敗と判定する。以下に、方式１，２に対する検証装置の処理を示す。
【００１８】
方式１の場合、第３秘匿化検証値［ｒｍｙｍ］ｉが（κ，Ｎ）シャミア秘密分散方式に則った秘密分散値である場合、互いに相違する少なくともκ個の第３秘匿化検証値［ｒｍｙｍ］φ（１），…，［ｒｍｙｍ］φ（κ）が検証装置の復元部に入力され、検証装置の復元部は、第３秘匿化検証値［ｒｍｙｍ］φ（１），…，［ｒｍｙｍ］φ（κ）を用いて検証値ｒｍｙｍを復元して出力する。ただし、κは１以上Ｎ以下の正整数であり、｛φ（１），…，φ（κ）｝⊆｛１，…，Ｎ｝である。例えば、第３秘匿化検証値［ｒｍｙｍ］ｉが（２Ｋ−１，Ｎ）シャミア秘密分散方式に則った秘密分散値である場合、検証装置の復元部は、少なくとも２Ｋ−１個の秘密計算装置から出力された第３秘匿化検証値［ｒｍｙｍ］φ（１），…，［ｒｍｙｍ］φ（２Ｋ−１）を用いて検証値ｒｍｙｍを復元して出力する。検証装置の判定部は、何れかの認証情報ｗに対し、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功とする。一方、すべての認証情報ｗに対し、何れかのｍについてｒｍｙｍ＝０を満たさない場合に認証失敗とする。あるいは、方式１において検証装置が［ｒ０ｙ０］ｉ，…，［ｒＭ−１ｙＭ−１］ｉの少なくとも一部を用いた秘密計算および復元を含む演算を行い、それによって得られた復元値を用い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすか否かを判定してもよい。例えば、検証装置が［ｒ０ｙ０］μ，…，［ｒＭ−１ｙＭ−１］μを用いた秘密計算によって秘密分散値［ｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１］μを得、これらから復元されるｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１が０である場合にすべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定し、ｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１が０でない場合にｍ＝０，…，Ｍ−１の何れかについてｒｍｙｍ＝０を満たさないと判定してもよい。ただし、μ＝φ（１），…，φ（κ）である。
【００１９】
方式２の場合、検証装置は、前述の第４秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉのうち、［ｒｍｙｍ］φ（１）＋［Ｒｍ］φ（１）・Ｉ、［ｒｍｙｍ］φ（２）＋［Ｒｍ］φ（２）・Ｉ、［ｒｍｙｍ］φ（３）＋［Ｒｍ］φ（３）・Ｉを用い、ε次拡大体Ｆε上の（３，Ｎ）シャミア秘密分散方式に則って、［ｒｍｙｍ］φ（１）＋［Ｒｍ］φ（１）・Ｉと［ｒｍｙｍ］φ（２）＋［Ｒｍ］φ（２）・Ｉと［ｒｍｙｍ］φ（３）＋［Ｒｍ］φ（３）・Ｉとに対する演算を行い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功と判定する。例えば、検証装置の復元部に［ｒｍｙｍ］φ（１）＋［Ｒｍ］φ（１）・Ｉと［ｒｍｙｍ］φ（２）＋［Ｒｍ］φ（２）・Ｉと［ｒｍｙｍ］φ（３）＋［Ｒｍ］φ（３）・Ｉが入力され、検証装置の復元部はこれらを用いて検証値ｒｍｙｍを復元して出力する。検証装置の判定部は、何れかの認証情報ｗに対し、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たす場合に認証成功とする。一方、すべての認証情報ｗに対し、何れかのｍについてｒｍｙｍ＝０を満たさない場合に認証失敗とする。あるいは、方式２において検証装置が［ｒ０ｙ０］ｉ”＋［Ｒ０］ｉ”・Ｉ”，…，［ｒＭ−１ｙＭ−１］ｉ”＋［ＲＭ−１］ｉ”・Ｉ”の少なくとも一部を用いた秘密計算および復元を含む演算を行い、それによって得られた復元値を用い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすか否かを判定してもよい。ただし、ｉ”＝φ（１），φ（２），φ（３）であり、Ｉ”＝（ｉ”，０，…，０）∈Ｆεである。例えば、検証装置が［ｒ０ｙ０］ｉ”＋［Ｒ０］ｉ”・Ｉ”，…，［ｒＭ−１ｙＭ−１］ｉ”＋［ＲＭ−１］ｉ”・Ｉ”を用いた秘密計算によって秘密分散値［ｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１］ｉ”を得、秘密分散値［ｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１］ｉ”を復元して得られるｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１が０である場合にすべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定し、ｒ０ｙ０＋…＋ｒＭ−１ｙＭ−１が０でない場合にｍ＝０，…，Ｍ−１の何れかについてｒｍｙｍ＝０を満たさないと判定してもよい。
【００２０】
以上の手法では、秘匿化拡大体乱数［ｒｍ］ｉを用いることで、ｗ−ω≠０であるにもかかわらずｒｍｙｍ＝０が復元されるような不正な秘匿化検証値が生成され、認証成功と判定されることを防止できる。また、ｗ−ω＝０である場合には拡大体乱数ｒｍの値にかかわらずｒｍｙｍ＝０となるため、ｗ−ω＝０であるにもかかわらず認証失敗と判定されることはない。また各処理が秘密計算によって行われるため、認証情報を秘密に保ったまま認証処理を行うことができる。このように、認証情報を秘密に保ったまま、なりすましに対する安全性が高い認証処理を行うことができる。
【００２１】
［第１実施形態］
次に図面を用いて本発明の第１実施形態を説明する。第１実施形態は方式１の一例である。
＜構成＞
図１に例示するように、本実施形態の秘密計算認証システム１は、利用者装置１１、複数個の秘密計算装置１２−１，…，１２−Ｎ、および検証装置１３を有し、これらはネットワークを通じて通信可能に構成されている。本実施形態のＮは２以上の整数である。なお、説明の簡略化のため、図１の秘密計算認証システム１は利用者装置１１および検証装置１３をそれぞれ１個含むが、秘密計算認証システム１が２個以上の利用者装置１１および／または検証装置１３を含んでいてもよい。
【００２２】
図２に例示するように、本実施形態の秘密計算装置１２−ｉは、入力部１２１−ｉ、出力部１２２−ｉ、制御部１２４−ｉ、演算部１２５−ｉ，１２６−ｉ，１２７−ｉ、乱数生成部１２８−ｉ、判定部１２９−ｉ、および記憶部１２３−ｉを有する。秘密計算装置１２−ｉは、制御部１２４−ｉの制御下で各処理を実行し、各部が得たデータは記憶部１２３−ｉに格納され、必要に応じて読み出されて他の処理に用いられる。図３Ａに例示するように、本実施形態の利用者装置１１は、入力部１１１、出力部１１２、制御部１１４、秘匿化部１１５、および表示部１１６を有する。利用者装置１１は、制御部１１４の制御下で各処理を実行し、各部が得たデータは記憶部（図示せず）に格納され、必要に応じて読み出されて他の処理に用いられる。図３Ｂに例示するように、本実施形態の検証装置１３は、入力部１３１、出力部１３２、制御部１３４、復元部１３６、および判定部１３７を有する。検証装置１３は、制御部１３４の制御下で各処理を実行し、各部が得たデータは記憶部（図示せず）に格納され、必要に応じて読み出されて他の処理に用いられる。
【００２３】
＜事前処理＞
各秘密計算装置１２−ｉ（ただし、ｉ＝１，…，Ｎ）の記憶部１２３−ｉには、事前登録された単数または複数の秘匿化認証情報［ｗ］ｉ∈［Ｆ］Ｌが格納される。認証情報ｗ自体は各秘密計算装置１２−ｉに公開されない。なお、秘密計算認証システム１で使用される秘密分散方式は予め定められており、利用者装置１１、複数個の秘密計算装置１２−１，…，１２−Ｎ、および検証装置１３は、この秘密分散方式に則った秘密分散値に対する秘密計算を行う。
【００２４】
＜秘密計算認証処理＞
図４に例示するように、まず利用者が利用者装置１１（図３Ａ）の入力部１１１に認証情報ωを入力する（ステップＳ１１１１）。認証情報ωは秘匿化部１１５に送られ、秘匿化部１１５は当該認証情報ωの秘密分散値である秘匿化認証情報［ω］ｉ（ただし、ｉ＝１，…，Ｎ）を得て出力する（ステップＳ１１５）。秘匿化認証情報［ω］ｉは出力部１１２に送られ、出力部１１２は各秘匿化認証情報［ω］ｉを各秘密計算装置１２−ｉに対して出力する（ステップＳ１１２１）。
【００２５】
図５に例示するように、各秘匿化認証情報［ω］ｉはネットワーク経由で各秘密計算装置１２−ｉ（図２）に送信され、入力部１２１−ｉに入力される（ステップＳ１２１−ｉ）。秘匿化認証情報［ω］ｉは判定部１２９−ｉに入力される。判定部１２９−ｉは記憶部１２３−ｉから何れかの秘匿化認証情報［ｗ］ｉ（例えば、ステップＳ１２９１−ｉ以降の処理が行われていない何れかの秘匿化認証情報［ｗ］ｉ）を読み出し（ステップＳ１２３−ｉ）、秘匿化認証情報［ω］ｉのサイズと秘匿化認証情報［ｗ］ｉのサイズとが互いに同一であるかを判定する（ステップＳ１２９１−ｉ）。これらが互いに同一でないと判定された場合には「失敗」を表す情報を出力し（ステップＳ１２２１−ｉ）、ステップＳ１２９２−ｉの処理に進む。
【００２６】
一方、秘匿化認証情報［ω］ｉのサイズと秘匿化認証情報［ｗ］ｉのサイズとが互いに同一であると判定された場合、演算部１２５−ｉ（第１演算部）はこれらの秘匿化認証情報［ω］ｉおよび秘匿化認証情報［ｗ］ｉを入力とし、秘密計算によって秘匿化検証値［ｚ］ｉ＝［ｗ−ω］ｉ（第１秘匿化検証値）を得て出力する（ステップＳ１２５−ｉ、図７）。乱数生成部１２８−ｉは、拡大体乱数ｒｍの秘密分散値である秘匿化拡大体乱数［ｒｍ］ｉ∈［Ｆε］（ただし、ｍ＝０，…，Ｍ−１，Ｍ＝ｃｅｉｌ（Ｌ／ε））を得て出力する（ステップＳ１２８−ｉ、図７）。演算部１２６−ｉ（第２演算部）は、秘匿化検証値［ｚ］ｉを入力とし、秘密計算によってｙｍを秘匿化した秘匿化検証値［ｙｍ］ｉ（第２秘匿化検証値）を得て出力する。ただし、ｚ＝（ｚ０，…，ｚＬ−１）＝ｗ−ωであり、ｚｊ∈Ｆであり、ｊ＝０，…、Ｌ−１であり、ｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｑ＝ε（Ｍ−１），…，εＭ−１のうちｑ＞Ｌ−１となるｚｑが０である。すなわち、図７に例示するように、Ｍε−Ｌ＝０であればｚ０，…，ｚＬ−１の列をＭ等分して得られる各列がｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）である。Ｍε−Ｌ≠０であれば、ｍ＝０，…，Ｍ−２についてはｙｍ＝（ｚεｍ，…，ｚε（ｍ＋１）−１）であり、ｍ＝Ｍ−１についてはｚε（Ｍ−１），…，ｚＬ−１とＭε−Ｌ個の０とからなる（ｚε（Ｍ−１），…，ｚＬ−１，０，…，０）がｙＭ−１である（ステップＳ１２６−ｉ）。演算部１２７−ｉ（第３演算部）は、秘匿化拡大体乱数［ｒｍ］ｉおよび秘匿化検証値［ｙｍ］ｉを入力とし、秘密計算によって秘匿化検証値［ｒｍｙｍ］ｉ（第３秘匿化検証値）を得て出力し、ステップＳ１２９２−ｉの処理に進む（ステップＳ１２７−ｉ）。
【００２７】
ステップＳ１２９２−ｉでは、記憶部１２３−ｉに格納されたすべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行されたかを判定する（ステップＳ１２９２−ｉ）。すべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行されていない場合、処理がステップＳ１２３−ｉに戻される。一方、すべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行された場合、ステップＳ１２２２−ｉの処理が実行される。
【００２８】
ステップＳ１２２２−ｉでは、ステップＳ１２７−ｉで得られた秘匿化検証値［ｒｍｙｍ］ｉが出力部１２２−ｉに入力される。ステップＳ１２７−ｉで得られた秘匿化検証値［ｒｍｙｍ］ｉが存在しない場合には「失敗」を表す情報が出力部１２２−ｉに入力される。出力部１２２−ｉは秘匿化検証値［ｒｍｙｍ］ｉまたは「失敗」を表す情報を検証装置１３に対して出力する（ステップＳ１２２２−ｉ）。
【００２９】
図６に例示するように、秘匿化検証値［ｒｍｙｍ］ｉまたは「失敗」を表す情報はネットワーク経由で検証装置１３に送信され、検証装置１３（図３Ｂ）の入力部１３１に入力される（ステップＳ１３１）。ここで「失敗」を表す情報が入力された場合、ステップＳ１３２２の処理が実行される。一方、秘匿化検証値［ｒｍｙｍ］ｉを表す情報が入力された場合、ステップＳ１３６以降の処理が実行される（ステップＳ１３７０）。
【００３０】
ステップＳ１３６では、復元部１３６は同一のｗに対応する秘匿化検証値［ｒｍｙｍ］φ（１），…，［ｒｍｙｍ］φ（Ｋ）を用いて検証値ｒｍｙｍを復元して出力する。ただし、｛φ（１），…，φ（Ｋ）｝⊆｛１，…，Ｎ｝である（ステップＳ１３６）。判定部１３７はｒ０ｙ０，…，ｒＭ−１ｙＭ−１を入力とし、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすかを判定する（ステップＳ１３７１）。すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定された場合、判定部１３７は「認証が成功したことを表す情報」を出力する（ステップＳ１３２１）。一方、何れかのｍについてｒｍｙｍ＝０を満たさないと判定された場合、次に判定部１３７はすべてのｗについてステップＳ１３６の処理を行ったかを判定する（ステップＳ１３７２）。何れかのｗについてステップＳ１３６の処理を行っていないと判定された場合、処理がステップＳ１３６に戻る。一方、すべてのｗについてステップＳ１３６の処理を行ったと判定された場合、ステップＳ１３２２の処理が実行される。ステップＳ１３２２では、判定部１３７が「認証が失敗したことを表す情報」を出力する（ステップＳ１３２２）。
【００３１】
ステップＳ１３２１で出力された「認証が成功したことを表す情報」またはステップＳ１３２２で出力された「認証が失敗したことを表す情報」である認証結果は出力部１３２に入力される。出力部１３２は認証結果を利用者装置１１に対して出力する。認証結果は利用者装置１１（図３Ａ）の入力部１１１に入力され（ステップＳ１１１２）、表示部１１６から表示される（ステップＳ１１６）。
【００３２】
［第１実施形態の変形例］
検証装置１３が［ｒ０ｙ０］ｉ，…，［ｒＭ−１ｙＭ−１］ｉの少なくとも一部を用いた秘密計算および復元を含む演算を行い、それによって得られた復元値を用い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすか否かを判定してもよい。前述した一例の他、例えば、検証装置１３が［ｒ０ｙ０］μ，…，［ｒＭ−１ｙＭ−１］μを用いた秘密計算によって秘密分散値［ｒ０ｙ０＋ｒ１ｙ１］μ，［ｒ２ｙ２＋ｒ３ｙ３］μ，…，［ｒＭ−２ｙＭ−２＋ｒＭ−１ｙＭ−１］μを得、これらから復元されるｒ０ｙ０＋ｒ１ｙ１，ｒ２ｙ２＋ｒ３ｙ３，…，ｒＭ−２ｙＭ−２＋ｒＭ−１ｙＭ−１がすべて０である場合にすべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定し、そうでない場合にｍ＝０，…，Ｍ−１の何れかについてｒｍｙｍ＝０を満たさないと判定してもよい。
【００３３】
［第２実施形態］
次に図面を用いて本発明の第２実施形態を説明する。第２実施形態は方式２の一例である。以下では第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については同じ参照番号を用いて説明を簡略化する。また、以下では逐一説明しないが、特に断りのない限り、本実施形態では、秘密分散方式として（２，Ｎ）シャミア秘密分散方式が用いられる。
【００３４】
＜構成＞
図１に例示するように、本実施形態の秘密計算認証システム２は、利用者装置１１、複数個の秘密計算装置２２−１，…，２２−Ｎ、および検証装置２３を有し、これらはネットワークを通じて通信可能に構成されている。本実施形態のＮは３以上の整数である。なお、説明の簡略化のため、図１の秘密計算認証システム２は利用者装置１１および検証装置２３をそれぞれ１個含むが、秘密計算認証システム２が２個以上の利用者装置１１および／または検証装置２３を含んでいてもよい。
【００３５】
図２に例示するように、本実施形態の秘密計算装置２２−ｉは、入力部１２１−ｉ、出力部１２２−ｉ、制御部１２４−ｉ、演算部１２５−ｉ，１２６−ｉ，１２７−ｉ，２２３−ｉ，２２４−ｉ、乱数生成部１２８−ｉ，２２８−ｉ、判定部１２９−ｉ、および記憶部１２３−ｉを有する。秘密計算装置２２−ｉは、制御部１２４−ｉの制御下で各処理を実行し、各部が得たデータは記憶部１２３−ｉに格納され、必要に応じて読み出されて他の処理に用いられる。図３Ｂに例示するように、本実施形態の検証装置２３は、入力部１３１、出力部１３２、制御部１３４、復元部２３６、および判定部１３７を有する。検証装置２３は、制御部１３４の制御下で各処理を実行し、各部が得たデータは記憶部（図示せず）に格納され、必要に応じて読み出されて他の処理に用いられる。
【００３６】
＜事前処理＞
第１実施形態と同じである。
【００３７】
＜秘密計算認証処理＞
図４に例示するように、第１実施形態で説明したステップＳ１１１１，Ｓ１１５，Ｓ１１２１の処理が実行される。これによって利用者装置１１から出力された各秘匿化認証情報［ω］ｉは各秘密計算装置２２−ｉ（図２）の入力部１２１−ｉに入力される（ステップＳ１２１−ｉ）。その後、第１実施形態で説明したステップＳ１２３−ｉ，Ｓ１２９１−ｉの処理が実行され、ステップＳ１２９１−ｉで秘匿化認証情報［ω］ｉのサイズと秘匿化認証情報［ｗ］ｉのサイズとが互いに同一でないと判定された場合には「失敗」を表す情報を出力し（ステップＳ１２２１−ｉ）、ステップＳ１２９２−ｉの処理に進む。一方、秘匿化認証情報［ω］ｉのサイズと秘匿化認証情報［ｗ］ｉのサイズとが互いに同一であると判定された場合には第１実施形態で説明したステップＳ１２５−ｉ，Ｓ１２８−ｉ，Ｓ１２６−ｉ，Ｓ１２７−ｉの処理が実行される。本実施形態では、ｒｍ∈Ｆεであり、ｒｓｍ∈Ｆεであり、ｙｓｍ∈Ｆεであり、Ｉ∈Ｆεであり、［ｒｍ］ｉ＝ｒｍ＋ｒｓｍ・Ｉ∈Ｆεであり、［ｙｍ］ｉ＝ｙｍ＋ｙｓｍ・Ｉ∈Ｆεであり、［ｒｍｙｍ］ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ）・Ｉ＋ｒｓｍ・ｙｓｍ・Ｉ２∈Ｆεである。
【００３８】
その後、乱数生成部２２８−ｉ（第２乱数生成部）が、拡大体乱数（第２拡大体乱数）Ｒｍ∈Ｆεの秘密分散値である秘匿化拡大体乱数（第２秘匿化拡大体乱数）［Ｒｍ］ｉ＝Ｒｍ＋Ｒｓｍ・Ｉ∈Ｆεを得て出力する（ステップＳ２２８−ｉ）。次に、演算部２２３−ｉ（第４演算部）が、秘匿化拡大体乱数［Ｒｍ］ｉとＩとをε次拡大体Ｆε上で乗算し、拡大体乗算値［Ｒｍ］ｉ・Ｉ＝Ｒｍ・Ｉ＋Ｒｓｍ・Ｉ２∈Ｆεを得て出力する。ただし、Ｒｓｍ∈Ｆεである（ステップＳ２２３−ｉ）。さらに、演算部２２４−ｉ（第５演算部）が、秘匿化検証値［ｒｍｙｍ］ｉと拡大体乗算値［Ｒｍ］ｉ・Ｉとを用い、秘匿化検証値（第４秘匿化検証値）［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉ＝ｒｍ・ｙｍ＋（ｒｍ・ｙｓｍ＋ｒｓｍ・ｙｍ＋Ｒｍ）・Ｉ＋（ｒｓｍ・ｙｓｍ＋Ｒｓｍ）・Ｉ２∈Ｆεを得て出力する（ステップＳ２２４−ｉ）。
【００３９】
ステップＳ１２９２−ｉでは、記憶部１２３−ｉに格納されたすべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行されたかを判定する（ステップＳ１２９２−ｉ）。すべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行されていない場合、処理がステップＳ１２３−ｉに戻される。一方、すべての秘匿化認証情報［ｗ］ｉについてステップＳ１２３−ｉ以降の処理が実行された場合、ステップＳ２２２２−ｉの処理が実行される。
【００４０】
ステップＳ２２２２−ｉでは、ステップＳ２２４−ｉで得られた秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉが出力部１２２−ｉに入力される。ステップＳ２２４−ｉで得られた秘匿化検証値が存在しない場合には「失敗」を表す情報が出力部１２２−ｉに入力される。出力部１２２−ｉは秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉまたは「失敗」を表す情報を検証装置１３に対して出力する（ステップＳ２２２２−ｉ）。
【００４１】
図６に例示するように、秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉまたは「失敗」を表す情報はネットワーク経由で検証装置２３に送信され、検証装置２３（図３Ｂ）の入力部１３１に入力される（ステップＳ２３１）。ここで「失敗」を表す情報が入力された場合、ステップＳ１３２２の処理が実行される。一方、秘匿化検証値［ｒｍｙｍ］ｉ＋［Ｒｍ］ｉ・Ｉを表す情報が入力された場合、ステップＳ２３６以降の処理が実行される。
【００４２】
ステップＳ２３６では、復元部２３６が（３，Ｎ）シャミア秘密分散方式に則って、［ｒｍｙｍ］Ｋ（１）＋［Ｒｍ］Ｋ（１）・Ｉと［ｒｍｙｍ］Ｋ（２）＋［Ｒｍ］Ｋ（２）・Ｉと［ｒｍｙｍ］Ｋ（３）＋［Ｒｍ］Ｋ（３）・Ｉとを用いて検証値ｒｍｙｍを復元して出力する。ただし、｛Ｋ（１），Ｋ（２），Ｋ（３）｝⊆｛１，…，Ｎ｝である（ステップＳ２３６）。判定部１３７はｒ０ｙ０，…，ｒＭ−１ｙＭ−１を入力とし、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすかを判定する（ステップＳ１３７１）。すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定された場合、判定部１３７は「認証が成功したことを表す情報」を出力する（ステップＳ１３２１）。一方、何れかのｍについてｒｍｙｍ＝０を満たさないと判定された場合、次に判定部１３７はすべてのｗについてステップＳ２３６の処理を行ったかを判定する（ステップＳ１３７２）。何れかのｗについてステップＳ２３６の処理を行っていないと判定された場合、処理がステップＳ２３６に戻る。一方、すべてのｗについてステップＳ２３６の処理を行ったと判定された場合、ステップＳ１３２２の処理が実行される。ステップＳ１３２２では、判定部１３７が「認証が失敗したことを表す情報」を出力する（ステップＳ１３２２）。それ以降の処理は第１実施形態と同じである。
【００４３】
［第２実施形態の変形例］
検証装置２３が［ｒ０ｙ０］ｉ”＋［Ｒ０］ｉ”・Ｉ”，…，［ｒＭ−１ｙＭ−１］ｉ”＋［ＲＭ−１］ｉ”・Ｉ”の少なくとも一部を用いた秘密計算および復元を含む演算を行い、それによって得られた復元値を用い、すべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすか否かを判定してもよい。ただし、ｉ”＝φ（１），φ（２），φ（３）であり、Ｉ”＝（ｉ”，０，…，０）∈Ｆεである。前述した一例の他、例えば、検証装置２３が［ｒ０ｙ０］ｉ”＋［Ｒ０］ｉ”・Ｉ”，…，［ｒＭ−１ｙＭ−１］ｉ”＋［ＲＭ−１］ｉ”・Ｉ”を用いた秘密計算によって、ｒ０ｙ０＋ｒ１ｙ１，ｒ２ｙ２＋ｒ３ｙ３，…，ｒＭ−２ｙＭ−２＋ｒＭ−１ｙＭ−１それぞれの秘密分散値を生成し、これらから復元されるｒ０ｙ０＋ｒ１ｙ１，ｒ２ｙ２＋ｒ３ｙ３，…，ｒＭ−２ｙＭ−２＋ｒＭ−１ｙＭ−１がすべて０である場合にすべてのｍ＝０，…，Ｍ−１についてｒｍｙｍ＝０を満たすと判定し、そうでない場合にｍ＝０，…，Ｍ−１の何れかについてｒｍｙｍ＝０を満たさないと判定してもよい。
【００４４】
［変形例等］
本発明は上述の実施形態に限定されるものではない。例えば、秘密計算装置１２−１〜１２−Ｎの少なくとも一部（例えば、すべての秘密計算装置１２−１〜１２−Ｎ）が利用者装置１１を含んでいてもよいし、検証装置１３を含んでいてもよい。また、各装置の各部で扱われる秘密分散値がすべて同じ秘密分散方式に則ったものであってもよいし、そうでなくてもよい。後者の場合、公知の秘密分散値の変換方法によって、特定の秘密分散方式に則った秘密分散値が他の秘密分散方式に則った秘密分散値に変換されてもよい。また、「αを用いてβを得る」とは、αを用いた計算によってβを算出することであってもよいし、αを用いた検索処理により、事前計算されていたβを抽出することであってもよい。
【００４５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４６】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００４７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４８】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５０】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００５１】
１，２  秘密計算認証システム
１１  利用者装置
１２−ｉ，２２−ｉ  秘密計算装置
１３，２３  検証装置
【図１】
0006933290.tif 000002
【図２】
0006933290.tif 000003
【図３】
0006933290.tif 000004
【図４】
0006933290.tif 000005
【図５】
0006933290.tif 000006
【図６】
0006933290.tif 000007
【図７】
0006933290.tif 000008