(57)【要約】  ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用可能とする。認証システムはユーザ装置と、ユーザ装置のユーザを認証するユーザ認証およびユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、ユーザ装置との間で機器認証を行う機器認証サーバ装置とを備え、ユーザサイド補助装置は検証情報の分散シェアを用いてユーザ装置との間でユーザ認証のためのマルチパーティ計算を行うとともに、ユーザ装置が生成した秘密鍵の分散シェアを用いて、ユーザ装置との間で機器認証のためのマルチパーティ計算を行う。
2017195886.tif 000002
【特許請求の範囲】
【請求項１】
ユーザ装置と、
前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、
前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備え、
前記ユーザサイド補助装置は、検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行うとともに、前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行う、
認証システム。
【請求項２】
ユーザ認証事前準備、ユーザ認証、検証情報分散シェア生成、機器認証事前準備および機器認証を行うように構成され、
前記ユーザ認証事前準備では前記ユーザ認証に先立って必要情報を準備し、
前記機器認証準備では前記機器認証に先立って必要情報を準備し、
前記ユーザ認証事前準備では、前記ユーザ装置を所有するユーザの固有情報である検証用ユーザ固有情報を取得し、
前記検証情報分散シェア生成では、前記検証用ユーザ固有情報から前記ユーザ認証で取得した情報と照合するための検証情報の分散シェアである検証情報分散シェアを計算し、前記ユーザサイド補助装置は前記検証情報分散シェアを取得し、前記検証情報分散シェア生成の一部または全部は前記ユーザ認証事前準備で行われ、前記検証情報分散シェア生成の残部は前記ユーザ認証で行われ、
前記機器認証事前準備では、前記ユーザ装置の秘密鍵を作成し、前記ユーザ装置は前記秘密鍵を秘密分散し、前記秘密分散により生成された複数ある秘密鍵分散シェアのいくつかを前記ユーザサイド補助装置に送り、前記ユーザサイド補助装置は前記秘密鍵分散シェアを保管し、
前記ユーザ認証では、前記ユーザの固有情報である認証用ユーザ固有情報を取得し、前記認証用ユーザ固有情報または前記認証用ユーザ固有情報から計算される情報を用いてユーザ認証マルチパーティ計算を実行することで前記ユーザを認証し、前記ユーザサイド補助装置は前記検証情報分散シェアを用いて前記ユーザ認証マルチパーティ計算に参加し、前記ユーザサイド補助装置は前記ユーザ認証マルチパーティ計算の結果として前記ユーザが受理されたのか拒否されたのかを示すデータの分散シェアであるユーザ認証結果分散シェアを取得し、
前記機器認証では、前記ユーザ装置が前記機器認証サーバ装置と通信することで前記機器認証サーバ装置から認証を受け、前記ユーザ装置および前記機器認証サーバ装置は一回または複数回の通信を行い、前記機器認証サーバ装置は前記機器認証の検証に必要なデータを作成して前記ユーザ装置に送信し、前記ユーザ装置は前記機器認証サーバから送られてきた前記検証に必要なデータを受信し、前記ユーザ装置は前記ユーザサイド補助装置と通信することで前記機器認証の証明に必要なデータを作成し、
前記ユーザ装置は前記証明に必要なデータを作成するために、前記機器認証サーバから送られてきた前記検証に必要なデータを必要に応じて加工して得られたデータを前記ユーザサイド補助装置に送信し、前記ユーザサイド補助装置は前記ユーザ装置から送られてきた前記必要に応じて加工された前記検証に必要なデータと前記秘密鍵分散シェアを用いて機器認証マルチパーティ計算を行い、前記ユーザ装置は前記機器認証マルチパーティ計算の結果として得られた分散シェアを複数用いて復元されたデータを必要に応じて加工したものを前記証明に必要なデータとして前記機器認証サーバに送る、
請求項１に記載の認証システム。
【請求項３】
前記ユーザ認証では、前記認証用ユーザ固有情報の分散シェアである認証情報分散シェアを作成する認証情報分散シェア生成を実行し、
前記ユーザサイド補助装置は前記認証情報分散シェアを取得し、
前記ユーザサイド補助装置は前記ユーザ認証マルチパーティ計算において前記認証情報分散シェアを用いる、
請求項２に記載の認証システム。
【請求項４】
前記ユーザ装置は前記検証情報分散シェア生成の出力である前記検証情報分散シェアの一つを保持し、
前記ユーザ装置は前記認証情報分散シェア生成の出力である前記認証情報分散シェアの一つを保持し、
前記ユーザ装置は前記ユーザ認証マルチパーティ計算に参加し、
前記ユーザ装置は自身の保持する前記検証情報分散シェアと前記認証情報分散シェアを前記ユーザ認証マルチパーティ計算で用い、
前記ユーザ装置は前記ユーザ認証マルチパーティ計算の結果として前記ユーザ認証結果分散シェアを取得する、
請求項３に記載の認証システム。
【請求項５】
前記ユーザ認証マルチパーティ計算において、
前記ユーザ装置のみが自身の送信したデータの正当性を示す正当性証明を作成し、
前記ユーザサイド補助装置が前記正当性証明を検証する、
請求項４に記載の認証システム。
【請求項６】
前記ユーザ認証マルチパーティ計算において前記ユーザ装置が作成する前記正当性証明はゼロ知識証明（ＺＫＩＰ：Zero-Knowledge Interactive Proof）である、
請求項５に記載の認証システム。
【請求項７】
前記ユーザ認証マルチパーティ計算において前記ユーザ装置が作成する前記正当性証明はメッセージ認証子（ＭＡＣ：Message Authentication Code）である、
請求項５に記載の認証システム。
【請求項８】
前記ユーザ認証マルチパーティ計算として依頼計算（Secure Function Evaluation）法を利用する、
請求項２に記載の認証システム。
【請求項９】
前記ユーザ認証マルチパーティ計算で用いる前記依頼計算法はガーブルドサーキット（ＧＣ：Garbled Circuit）法である、
請求項８に記載の認証システム。
【請求項１０】
前記ユーザ認証マルチパーティ計算としてガーブルドサーキット（ＧＣ：Garbled Circuit）法またはその他の依頼計算法を利用し、
前記依頼計算法は前記ユーザサイド補助装置が２つの変数aとbを引数として持つ関数f(a,b)の計算を前記ユーザ装置に依頼するものであり、
前記ユーザ装置は前記ユーザサイド補助装置からの計算依頼に対し、前記aとして前記ユーザ装置が保有する前記認証情報分散シェアを用い、前記bとして前記ユーザ装置が保有する前記検証情報分散シェアを用い、
前記関数f(a,b)は前記aと前記ユーザサイド補助装置が保有する前記認証情報分散シェアとを使用して認証情報xを復元し、前記bと前記ユーザサイド補助装置が保有する前記検証情報分散シェアとを使用して検証情報yを復元し、前記認証情報xと前記検証情報yを用いてユーザ認証を行い、認証結果を出力する関数である、
請求項３に記載の認証システム。
【請求項１１】
前記ユーザ装置は前記ユーザ認証において前記認証用ユーザ固有情報から前記ユーザの認証情報を計算し、
前記ユーザサイド補助装置は前記依頼計算において２つの変数aとbを引数として持つ関数g(a,b)の計算を前記ユーザ装置に依頼し、
前記ユーザ装置は前記ユーザサイド補助装置からの計算依頼に対し、前記aとして前記ユーザ装置が保有する前記認証情報を用い、前記bとして前記ユーザ装置が保有する前記検証情報分散シェアを用い、
前記関数g(a,b)が前記bと前記ユーザサイド補助装置が保有する前記検証情報分散シェアとを使用して検証情報yを復元し、前記認証情報aと前記検証情報yを使用してユーザ認証を行い、認証結果を出力する関数である、
請求項８または９に記載の認証システム。
【請求項１２】
前記ユーザ装置は前記検証情報分散シェアを保持せず、
前記ユーザ装置は前記ユーザ認証マルチパーティ計算に参加しない、
請求項３に記載の認証システム。
【請求項１３】
前記機器認証事前準備において、
前記ユーザ装置は公開鍵認証方式の鍵生成を実行することで、前記ユーザ装置の前記秘密鍵と前記ユーザの公開鍵を作成し、
前記ユーザ装置は前記公開鍵を前記サーバサイド補助装置と前記機器認証サーバ装置に送信し、
前記サーバサイド補助装置および前記機器認証サーバ装置は受信した公開鍵を保管し、
前記機器認証において、
前記機器認証サーバ装置は前記公開鍵認証方式に基づいたデータを送受信することで前記ユーザ装置の前記機器認証を検証し、
前記ユーザ装置は前記公開鍵認証方式に基づいたデータを送受信することで前記機器認証サーバ装置から前記機器認証を受ける、
請求項２ないし１２のいずれか１項に記載の認証システム。
【請求項１４】
前記ユーザ装置は前記機器認証事前準備で生成された前記秘密鍵分散シェアの一つを保持し、
前記ユーザ装置は前記機器認証マルチパーティ計算に参加し、
前記ユーザ装置は前記機器認証マルチパーティ計算で自身の保持する前記秘密鍵分散シェアを用い、
前記ユーザ装置は前記機器認証マルチパーティ計算の結果である前記分散シェアの１つを取得する、
請求項１３に記載の認証システム。
【請求項１５】
前記機器認証マルチパーティ計算において、
前記ユーザ装置のみが自身の送信したデータの正当性を示す正当性証明を作成し、
前記ユーザサイド補助装置が前記正当性証明を検証する、
請求項１４に記載の認証システム。
【請求項１６】
前記機器認証マルチパーティ計算において前記ユーザ装置が作成する前記正当性証明はゼロ知識証明（ＺＫＩＰ：Zero-Knowledge Interactive Proof）である、
請求項１５に記載の認証システム。
【請求項１７】
前記機器認証マルチパーティ計算において前記ユーザ装置が作成する前記正当性証明はメッセージ認証子（ＭＡＣ：Message Authentication Code）である、
請求項１５に記載の認証システム。
【請求項１８】
前記機器認証で行う前記公開鍵認証では、
前記機器認証サーバから前記ユーザ装置に送られてきたデータから前記ユーザ装置が前記機器認証サーバに送り返すデータを計算する返答計算過程において、
前記返答計算過程のうちの前記秘密鍵を利用しない演算は前記ユーザ装置または前記ユーザサイド補助装置の１台が実行し、
前記返答計算過程のうちの前記秘密鍵を利用する演算は前記機器認証マルチパーティ計算を実行することで計算する、
請求項１４ないし１７のいずれか１項に記載の認証システム。
【請求項１９】
前記ユーザ装置は、前記ユーザ認証マルチパーティ計算が終了すると、前記ユーザ認証結果分散シェアのいくつかを利用してユーザ認証結果を復元し、前記ユーザ認証結果が受理である場合、前記機器認証サーバ装置と前記サーバサイド補助装置とともに前記機器認証を実行し、前記ユーザ認証結果が拒否である場合、前記機器認証を実行することなく前記ユーザに認証が拒否された旨を通知する、
請求項２ないし１８のいずれか１項に記載の認証システム。
【請求項２０】
前記ユーザ認証マルチパーティ計算が終了すると、
前記ユーザサイド補助装置は前記ユーザ認証結果分散シェアを前記ユーザ装置に送り、
前記ユーザ装置は前記ユーザ認証結果分散シェアのいくつかを利用してユーザ認証結果を復元し、前記ユーザ認証結果が受理である場合、前記ユーザ装置は前記機器認証サーバ装置と前記サーバサイド補助装置とともに前記機器認証を実行し、前記ユーザ認証結果が拒否である場合、前記サーバサイド補助装置とともに機器認証シミュレートＭＰＣを実行し、
前記機器認証シミュレートＭＰＣにおいて、
前記ユーザ装置は前記機器認証における前記ユーザ装置が行う処理と、前記機器認証における前記機器認証サーバ装置が行う処理の双方を行い、
前記サーバサイド補助装置は前記機器認証における処理と同一の処理を行う、
請求項２ないし７および１３ないし１８のいずれか１項に記載の認証システム。
【請求項２１】
前記ユーザサイド補助装置は、前記ユーザが前記ユーザ認証で拒否された回数をカウントし、
前記ユーザ装置は、前記ユーザ認証の結果が拒否である場合、前記機器認証を実行することなく前記ユーザに認証が拒否された旨を通知し、
前記ユーザサイド補助装置は、前記ユーザ認証で拒否された回数が一定値を超えた後、前記ユーザを認証することを拒否する、
請求項１９または２０に記載の認証システム。
【請求項２２】
前記認証情報分散シェア生成では前記認証用ユーザ固有情報から認証情報を計算し、前記認証情報から前記認証情報分散シェアを計算する、
請求項３に記載の認証システム。
【請求項２３】
前記ユーザ装置は前記認証情報分散シェア生成を実行する、
請求項２２に記載の認証システム。
【請求項２４】
前記認証情報分散シェア生成を実行するユーザ認証分散シェア生成装置を備える、
請求項２２に記載の認証システム。
【請求項２５】
前記認証情報分散シェア生成では、前記認証用ユーザ固有情報を秘密分散して得られた認証用ユーザ固有情報分散シェアを前記ユーザサイド補助装置に送信し、
前記ユーザサイド補助装置は前記認証用ユーザ固有情報分散シェアを用いて認証情報分散シェア生成マルチパーティ計算を実行して前記認証情報分散シェアを得る、
請求項３に記載の認証システム。
【請求項２６】
前記ユーザ装置は前記認証情報分散シェア生成マルチパーティ計算に参加しない、
請求項２５に記載の認証システム。
【請求項２７】
前記検証情報分散シェア生成では、前記検証用ユーザ固有情報から検証情報を計算し、前記検証情報を秘密分散して前記検証情報分散シェアを取得する、
請求項２ないし２６のいずれか１項に記載の認証システム。
【請求項２８】
前記ユーザ装置は前記ユーザ認証事前準備において前記検証情報分散シェア生成を実行する、
請求項２７に記載の認証システム。
【請求項２９】
前記ユーザ認証事前準備において前記検証情報分散シェア生成を実行する検証情報分散シェア生成装置を備える、
請求項２７に記載の認証システム。
【請求項３０】
前記検証情報分散シェア生成では、検証情報分散シェア作成マルチパーティ計算を実行することで前記検証情報分散シェアを作成し、前記検証情報分散シェア作成マルチパーティ計算を行う前に、
前記検証用ユーザ固有情報から検証用ユーザ固有情報の分散シェアであるＭＰＣ入力検証用ユーザ固有情報分散シェアを作り、前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを前記検証情報分散シェア作成マルチパーティ計算に参加する装置に配り、
前記検証情報分散シェア作成マルチパーティ計算に参加する装置は前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを前記検証情報分散シェア作成マルチパーティ計算に用いる、
請求項２ないし２６のいずれか１項に記載の認証システム。
【請求項３１】
前記ユーザサイド補助装置は前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを受け取り、
前記ユーザサイド補助装置は前記検証情報分散シェア作成マルチパーティ計算に参加し、
前記ユーザ装置は前記検証情報分散シェア作成マルチパーティ計算に参加せず、
前記ユーザサイド補助装置は前記検証情報分散シェア作成マルチパーティ計算の出力として前記検証情報分散シェアを取得する、
請求項３０に記載の認証システム。
【請求項３２】
前記検証情報分散シェア生成では、前記検証情報分散シェア作成マルチパーティ計算を実行するとともに、事前準備時入力検証用ユーザ固有情報分散シェア作成と、ＭＰＣ入力検証用ユーザ固有情報分散シェア作成を実行し、
前記ユーザ認証事前準備では、前記事前準備時入力検証用ユーザ固有情報分散シェア作成を実行し、
前記ユーザ認証では、前記ＭＰＣ入力検証用ユーザ固有情報分散シェア作成と前記検証情報分散シェア作成マルチパーティ計算を実行し、
前記事前準備時入力検証用ユーザ固有情報分散シェア作成では、前記検証用ユーザ固有情報を入力として受け取り、前記検証用ユーザ固有情報の分散シェアである事前準備時検証用ユーザ固有情報分散シェアを出力して、前記事前準備時検証用ユーザ固有情報分散シェアを必要とする装置に送り、前記ユーザ装置および前記ユーザサイド補助装置は前記事前準備時検証用ユーザ固有情報分散シェアを保管し、
前記ＭＰＣ入力検証用ユーザ固有情報分散シェア作成では、前記ユーザ装置は自身の保有する前記事前準備時検証用ユーザ固有情報分散シェアから求まるデータを前記ユーザサイド補助装置に送り、前記ユーザサイド補助装置は自身の保有する前記事前準備時検証用ユーザ固有情報分散シェアと前記ユーザ装置から送られてきた前記事前準備時検証用ユーザ固有情報分散シェアから求めた前記データとを用いて前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを作る、
請求項３０または３１に記載の認証システム。
【請求項３３】
前記事前準備時入力検証用ユーザ固有情報分散シェア作成では、Mをユーザサイド補助装置の台数とするとき、前記検証用ユーザ固有情報を前記M個に秘密分散して分散シェアe[1],...,e[M]を作り、i=1,...,Mに対して前記分散シェアe[i]を２つに秘密分散して分散シェアc[i]とd[i]を作り、前記分散シェアd[i]をi番目の前記ユーザサイド補助装置の事前準備時入力検証用ユーザ固有情報分散シェアとし、前記分散シェアc[1],...,c[M]を前記ユーザ装置の事前準備時入力検証用ユーザ固有情報分散シェアとし、
前記ＭＰＣ入力検証用ユーザ固有情報分散シェア作成では、i=1,...,Mに対し、前記(c[1],...,c[M])から求まるデータであるc[i]を前記ユーザ装置がi番目の前記ユーザサイド補助装置に送り、i番目の前記ユーザサイド補助装置は自身が保有する前記分散シェアd[i]と前記ユーザ装置から送られてきた前記分散シェアc[i]とを用いて秘密分散の復元を実行することで前記分散シェアe[i]を計算し、前記分散シェアe[i]を前記ＭＰＣ入力検証用ユーザ固有情報分散シェアとして用いる、
請求項３２に記載の認証システム。
【請求項３４】
前記検証情報分散シェア生成では、前記検証情報分散シェア作成マルチパーティ計算を実行するとともに、ＭＰＣ入力検証用ユーザ固有情報分散シェア作成と保存用分散シェア作成と検証情報分散シェア復元を実行し、
前記ユーザ認証事前準備では、前記ＭＰＣ入力検証情報分散シェア作成と前記検証情報分散シェア作成マルチパーティ計算と前記保存用分散シェア作成を実行し、
前記ユーザ認証では、前記検証情報分散シェア復元を実行し、
前記ＭＰＣ入力検証用ユーザ固有情報分散シェア作成では、前記検証用ユーザ固有情報を秘密分散して分散シェアである前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを作成し、前記ＭＰＣ入力検証用ユーザ固有情報分散シェアを前記ユーザサイド補助装置に送り、
前記保存用分散シェア作成では、前記検証情報分散シェア作成マルチパーティ計算の出力として前記ユーザサイド補助装置が保有する前記検証情報分散シェアを用いて保存用分散シェアを作成し、前記保存用分散シェアを前記ユーザ装置と前記ユーザサイド補助装置が保管し、
前記検証情報分散シェア復元では、前記ユーザ装置は自身が保持する保存用分散シェアから求まるデータを前記ユーザサイド補助装置に送信し、前記ユーザサイド補助装置は自身が保管している前記保存用分散シェアと前記ユーザ装置が送信した前記ユーザ装置の前記保存用分散シェアから求まる前記データとを用いて前記検証情報分散シェアを計算する、
請求項３０または３１に記載の認証システム。
【請求項３５】
前記保存用分散シェア作成では、Mをユーザサイド補助装置の台数とするとき、i=1,...,Mに対し、i台目の前記ユーザサイド補助装置は前記検証情報分散シェア作成マルチパーティ計算の出力である前記検証情報分散シェアv[i]を２つに秘密分散することで前記検証情報分散シェアv[i]の分散シェアu[i]とw[i]を求め、i台目の前記ユーザサイド補助装置は前記分散シェアw[i]を自身の前記保存用分散シェアとして保管し、前記分散シェアu[i]を前記ユーザ装置に送り、前記ユーザ装置はi=1,...,Mに対し、前記分散シェアu[1],...,u[M]を受信して前記分散シェアu[1],...,u[M]を自身の前記保存用分散シェアとして保管し、
前記検証情報分散シェア復元では、i=1,...,Mに対し、前記ユーザ装置は自身が保持する前記保存用分散シェアu[1],...,u[M]から求まるデータu[i]をi番目の前記ユーザサイド補助装置に送信し、i=1,...,Mに対し、i番目の前記ユーザサイド補助装置は自身が保持する保存用シェアであるw[i]と前記ユーザ装置から送信された前記データu[i]とを用いて秘密分散の復元処理を行うことで、前記検証情報分散シェアv[i]を復元する、
請求項３４に記載の認証システム。
【請求項３６】
請求項１ないし３５のいずれか１項に記載の認証システムにおける前記ユーザ装置。
【請求項３７】
請求項１ないし３５のいずれか１項に記載の認証システムにおける前記ユーザサイド補助装置。
【請求項３８】
ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、
前記ユーザ装置が、秘密鍵の分散シェアを生成するステップと、
検証情報の分散シェアを用いて前記ユーザサイド補助装置との間で前記ユーザ認証のためのマルチパーティ計算を行うステップと、
前記秘密鍵の分散シェアを用いて、前記ユーザサイド補助装置との間で前記機器認証のためのマルチパーティ計算を行うステップと、を含む、
認証方法。
【請求項３９】
ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、
前記ユーザサイド補助装置が、検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行うステップと、
前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行うステップと、を含む、
認証方法。
【請求項４０】
ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、
秘密鍵の分散シェアを生成する処理と、
検証情報の分散シェアを用いて前記ユーザサイド補助装置との間で前記ユーザ認証のためのマルチパーティ計算を行う処理と、
前記秘密鍵の分散シェアを用いて、前記ユーザサイド補助装置との間で前記機器認証のためのマルチパーティ計算を行う処理と、を前記ユーザ装置に設けられたコンピュータに実行させる、
プログラム。
【請求項４１】
ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、
検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行う処理と、
前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行う処理と、を前記ユーザサイド補助装置に設けられたコンピュータに実行させる、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１６−０９７４２２号（２０１６年  ５月１３日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。本発明は、認証システム、認証方法およびプログラムに関し、特にユーザおよびユーザ装置をそれぞれ認証するユーザ認証および機器認証を行う認証システム、認証方法およびプログラムに関する。
【背景技術】
【０００２】
ウェブサービスの一例として、金銭の授受を伴うウェブバンキングの利用が拡大している。かかるウェブサービスを利用する際には、サービスを提供するサーバがユーザを認証することで、ユーザはサービスを利用可能となる。かかる認証を行うサーバを、以下「認証サーバ」と呼ぶ。【０００３】
既存のウェブサービスでは、主に、パスワードや生体情報などのユーザ固有の認証情報をユーザが自身の端末からウェブサービスを提供する認証サーバに送ることでユーザを認証する。【０００４】
これらの既存の認証方法では、認証の際にユーザが認証サーバに送信してきた認証情報を、ユーザが事前に認証サーバに登録した情報（以下「検証情報」という）と比較することでユーザの当人性を確認する。【０００５】
例えば単純なパスワード認証の場合、ユーザは事前に認証サーバにパスワードPを検証情報として登録しておく。後日認証を行う際、ユーザは再び認証サーバにパスワードP'を送る。認証サーバはP=P'である場合にはユーザ当人であると判断して認証を受理し、それ以外の場合には認証を棄却する。【０００６】
一方、生体認証の場合、ユーザは顔、指紋、光彩などの生体情報の特徴量Cを検証情報として認証サーバに登録しておく。後日認証を行う際、ユーザは再び生体情報の特徴量C'を認証サーバに送る。認証サーバは特徴量CとC'の「距離」（例えばハミング距離）が定められた閾値以下である場合には認証を受理し、それ以外の場合には棄却する。【０００７】
関連技術として、非特許文献１には、ＦＩＤＯ（Fast Identify Online）方式が記載されている。また、非特許文献２には、暗号化通信方式が記載されている。さらに、非特許文献３には、ゼロ知識証明（ＺＫＩＰ：Zero-Knowledge Interactive Proof）法およびメッセージ認証子（ＭＡＣ：Message Authentication Code）法以外のマルチパーティ計算（ＭＰＣ：Multi-Party Computation）が記載されている。また、非特許文献４には、ＺＫＩＰ法が記載されている。さらに、非特許文献５〜７には、ＭＡＣ法が記載されている。また、非特許文献８には、依頼計算（Secure Function Evaluation）が記載されている。さらに、非特許文献９には、ガーブルドサーキット（ＧＣ：Garbled Circuit）法が記載されている。また、非特許文献１０には、Shamirの秘密分散法が記載されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】FIDO UAF Architectural Overview. FIDO Alliance Proposed Standard 08 December 2014.
【非特許文献２】肥後春菜、一色寿幸、森健吾、尾花賢、「テンプレートサイズの小さい秘匿指紋認証方式」 2015年暗号と情報.セキュリティシンポジウム(SCIS2015), IEICE, 2015.
【非特許文献３】Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation,” (Extended Abstract), STOC 1988 1-10.
【非特許文献４】O. Goldreich, S. Micali and A. Wigderson, "How to play any mental game or a completeness theorem for protocols with honest majority," STOC 1987.
【非特許文献５】J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra, “A New Approach To Practical Active-Secure Two-Party Computation,” In CRYPTO 2012, Springer (LNCS 7417), pages 681-700, 2012.
【非特許文献６】I. Damgard and S. Zakarias, “Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing,” In TCC, pages 621-641, 2013.
【非特許文献７】Ivan Damgard, Valerio Pastro, Nigel P. Smart, Sarah Zakarias, “Multiparty Computation from Somewhat Homomorphic Encryption,” CRYPTO 2012: 643-662.
【非特許文献８】A. Yao, “How to generate and exchange secrets,” In Foundations of Computer Science, 1986, 27th Annual Symposium on, pages 162-167, IEEE, 1986.
【非特許文献９】D. Beaver, S. Micali, and P. Rogaway, “The round complexity of secure protocols,” In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 503-513, ACM, 1990.
【非特許文献１０】Shamir, Adi (1979), "How to share a secret," Communications of the ACM 22 (11): 612-613.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【００１０】
上述の既存の認証方法によると、認証サーバ側が情報漏えいを起こした際、ユーザ固有の検証情報が不正者の手に渡ってしまうという危険を伴う。パスワード認証など多くの認証システムでは検証情報から認証情報を再現することが容易である。したがって、不正者は再現された認証情報を用いることで、ユーザに成りすまして認証サーバの提供するウェブサービスを利用できてしまう。【００１１】
また、ユーザは複数のウェブサービスで同一の認証情報を利用している可能性が高い。このとき、１つのウェブサービスで検証情報が漏えいすると、不正者はユーザの利用しているすべてのウェブサービスで成りすましが可能となるという問題がある。【００１２】
特に認証情報として生体情報を利用していた場合、重大な問題が生じ得る。なぜなら、ユーザの生体情報は終生不変であるため、一度の情報漏えいで未来永劫にユーザが成りすましの危険にさらされるからである。【００１３】
また、ウェブサービスを提供する認証サーバの管理者は、ユーザの検証情報を含めた認証サーバ内の全データを閲覧することができる。したがって、認証サーバ管理者は、ユーザの検証情報を入手することで容易に成りすましができてしまう。【００１４】
［単純な問題回避策］
こうした問題を回避する方法は、いくつか提案されているものの、いずれも決定的な解決策にはなっていない。例えば、パスワード認証においてこの問題を回避する古典的な方法として、認証サーバ側にユーザのパスワードPそのものではなく、パスワードPのハッシュ値h=Hash(P)を保管するというものがある。これにより、不正者が認証サーバ側のデータを読むことで直接認証情報Pを手に入れることが不可能となる。【００１５】
しかし、かかる方法は上述の問題を完全に解決するものではない。なぜなら、認証サーバ側のデータを読むことに成功した場合、不正者はハッシュ値hを手に入れることができる。パスワードや生体情報といった認証情報はエントロピーが小さいため、h=Hash(P)を満たすパスワードPを全数探索することで特定できてしまう。特に不正者が認証サーバ管理者当人である場合、ハッシュ値hの入手は容易であるため、認証サーバ管理者には認証情報の秘密を保つことができない。【００１６】
上述の攻撃手法のように、ユーザ側の装置と通信することなく、サーバ側の装置のみを不正利用して認証情報を特定する攻撃手法を、以下「サーバサイド・オフライン攻撃」と呼ぶ。Pの探索の度にユーザ側の装置との通信が必要となるタイプの攻撃の場合、ユーザ側の装置で通信回数に上限を定めることで、不正者に全数攻撃をさせないように防御することができる。しかしながら、サーバサイド・オフライン攻撃の場合、ユーザ側の装置とは一切通信しない。この場合、不正者はユーザに気付かれることなくPの全数探索ができてしまうため、大きな問題となる。【００１７】
別の解決手法として、検証情報Pを直接認証サーバに保管する代わりに、Pを暗号化した暗号文Enc(P)を認証サーバに保管する方法が知られている。この方法によれば、認証サーバに保管された暗号文を不正者に奪われたとしても、Pの情報を秘匿することができる。【００１８】
しかし、この解決手法の場合、Enc(P)を復号するための秘密鍵をどこに保管すべきかという問題が生じる。秘密鍵を認証サーバ自身に保管すると、認証サーバに侵入した不正者は、Enc(P)と秘密鍵の両方を取得することができ、検証情報Pを容易に復元できてしまう。さらに、上述のように、不正者はPからユーザの認証情報を再現することができる。このことは、かかる解決手法がサーバサイド・オフライン攻撃に弱いことを意味する。【００１９】
以上に述べたように、サーバサイド・オフライン攻撃に対して安全性を保証することは容易ではない。特に、不正者が認証サーバの管理者自身である場合、不正者はサーバサイド・オフライン攻撃を簡単に実行でき、非常に大きな問題となる。【００２０】
［既存の暗号技術］
認証に関して既にいくつかの発明が提案されている。これらの既存発明について述べるための準備として、既存の暗号技術である秘密分散、マルチパーティ計算（ＭＰＣ：Multi-Party Computation）、および、依頼計算について述べる。【００２１】
［秘密分散］
秘密分散とは、秘密のデータを複数の装置で「分散シェア」することで、データの秘匿性を高める技術である。【００２２】
秘密分散には、１台の「分散装置」と、複数台の「シェア保有装置」と、１台の「復元装置」が関与する。なお、分散装置と復元装置とが同一である場合、または、シェア保有装置のうちの１台と分散装置もしくは復元装置とが同一である場合もある。以下では、分散装置、シェア保有装置および復元装置は、別個の装置である場合について説明する。【００２３】
ここで、シェア保有装置の台数をMとする。【００２４】
分散装置は秘密のデータKを入力として受け取り、K（とM）を使用して「分散手段」を実行し、分散手段の出力として「シェア」s[1],...,s[M]を得る。i=1,...,Mに対し、分散装置はシェアs[i]をi台目のシェア保有装置に送信する。【００２５】
秘密のデータKが必要になった場合、復元装置はシェア保有装置の何台かからシェアを受け取り、これらのシェアを入力して「復元手段」を実行することで秘密のデータKを復元することができる。【００２６】
秘密分散には「秘密分散安全性条件」と呼ばれている条件が存在し、以下を満たす。
不正者に乗っ取られた装置の集合が秘密分散安全性条件を満たしている限り、不正者は秘密のデータKの情報を一切知ることができない。
不正者に乗っ取られた装置の集合が秘密分散安全性条件を満たしている限り、不正者に乗っ取られていない装置のシェアを復元装置に送ることで復元装置は復元手段により秘密のデータKを復元することができる。【００２７】
［Shamir秘密分散］
秘密分散の代表的な方法の１つとして、Shamir秘密分散がある（非特許文献１０）。
Shamir秘密分散では、値t≦Mを１つ固定し、t+1個以上の元を持つ有限体Fを１つ固定し、さらにFの元a[0],...,a[M]を固定する。【００２８】
Shamir秘密分散法において、秘密Kは有限体Fの元である。Shamir秘密分散法の分散手段では、f(a[0])=Kを満たすt次多項式fをランダムに選び、s[1]=f(a[1]),...,s[M]=f(a[M])とする。【００２９】
復元装置が、これらのシェアのうちのt個のシェアs[i1],....,s[it]を得たとする。すると、復元装置は任意のj=1,...,tに対してs[ij]=f(a[ij])を満たす多項式fを一意に決定できるため、多項式fを用いて秘密K=f(a[0])を復元することができる。【００３０】
Shamir秘密分散法において、秘密分散安全性条件は「不正者に乗っ取られた装置の台数はt-1台以下である」という条件である。したがって、Shamir秘密分散法では以下が満たされる。
不正者に乗っ取られた装置の台数がt-1台以下であれば、不正者は秘密Kの情報を一切得ることができない。
不正者に乗っ取られた装置の台数がt-1台以下であれば、不正者に乗っ取られていない装置のシェアを復元装置に送ることで復元装置は復元手段により秘密Kを復元することができる。【００３１】
［マルチパーティ計算（ＭＰＣ：Multi-Parti Computation）］
認証の安全性を高める方式は、他にもいくつか提案されている。これらを説明するために、これらの要素技術であるマルチパーティ計算（ＭＰＣ：Multi-Party Computation）を説明する。【００３２】
ＭＰＣとは、複数台の装置（以下、ＭＰＣ装置）が相互に通信することで、与えられたデータx[1],...,x[M]の秘匿性を保ちつつ、計算結果のデータf(x[1],...,x[M])を計算する手法である。ここでfは事前に定められた関数である。本明細書では以下、関数fのことをＭＰＣの「計算関数」と呼ぶ。【００３３】
マルチパーティ計算として、様々な手法が知られている。これらの手法の多くは、装置が複数台結託して不正を行った場合に対しても安全である。すなわち、結託した装置の集合が事前に定められた条件（以下、「ＭＰＣ安全性条件」という。例えば「結託した装置の台数が閾値kよりも小さい」という条件）を満たしている限り、次のことが保証される。すなわち、データx[1],...,x[N]の秘匿性が保証され、かつ、ＭＰＣの計算結果として出力されるデータyがf(x[1],...,x[N])と等しいことが保証される。【００３４】
一方、結託した装置の集合がＭＰＣ安全性条件を満たさない場合、結託した装置に対してデータx[1],...,x[N]の情報が漏れる可能性があり、さらに、ＭＰＣの計算結果として出力されるデータyがf(x[1],...,x[N])とは異なる値になる可能性がある。【００３５】
特に、ＭＰＣに参加するすべての装置が結託した場合、結託した装置にデータx[1],...,x[N]の情報が完全に漏れてしまう。【００３６】
［秘密分散を利用したＭＰＣ］
既存のＭＰＣの多くでは、秘密分散をサブルーチンとして用いる。このようなＭＰＣでは、上述したＭＰＣ装置以外に、秘密分散の「分散装置」と「復元装置」がある。ＭＰＣ装置は、秘密分散のシェア保有装置に対応する。なお、分散装置と復元装置が同一である場合、分散装置とＭＰＣ装置が同一である場合、または、復元装置とＭＰＣ装置が同一である場合も考えられる。ただし、以下では、分散装置、ＭＰＣ装置および復元装置が別個の装置である場合について説明する。それ以外の場合も、同様である。【００３７】
ＭＰＣは以下の手段で行われる。以下、ＭＰＣ装置の台数をMとする。【００３８】
各ＭＰＣ装置には、事前に関数fを計算する手段が（回路図やアルゴリズムの形で）入力されているものとする。【００３９】
まず、分散装置はi=1,...,Nに対して秘密のデータx[i]を入力として受け取り、秘密分散の「分散手段」を実行することで、秘密のデータx[i]の「シェア」s[i,1],...,s[i,M]を作成する。次に、分散装置は、j=1,...,Mに対し、シェアs[1,j],...,s[N,j]をj番目のＭＰＣ装置に送信する。【００４０】
次に、ＭＰＣ装置は相互に通信しながら「ＭＰＣ手段」を実行し、計算結果として「出力のシェア」を得る。j番目のＭＰＣ装置が得た出力のシェアをt[j]とする。1番目,...,M番目のＭＰＣ装置は、それぞれ出力のシェアt[1],....,t[M]を復元装置に送る。【００４１】
復元装置は、t[1],....,t[M]を用いて「復元手段」を実行することで「ＭＰＣの出力」yを得る。【００４２】
分散装置、ＭＰＣ装置および復元装置のいずれも不正を行っていない場合、ＭＰＣの出力yはf(x[1],...,x[N])と一致する。【００４３】
以上で述べたＭＰＣには、サブルーチンとして用いた秘密分散法が定める秘密分散安全性条件がある。ＭＰＣの安全性を保証するＭＰＣ安全性条件は、秘密分散安全性条件とは必ずしも一致しない。ただし、秘密分散安全性条件はＭＰＣ安全性条件の必要条件である。すなわち、ＭＰＣ安全性条件が成り立てば秘密分散安全性条件が成り立つが、逆は必ずしも成り立たない。【００４４】
例えば、秘密分散安全性条件が「結託した装置の台数が閾値kよりも小さい」という条件とし、ＭＰＣ安全性条件が「結託した装置の台数が閾値tよりも小さい」という条件とする。このとき、k≧tは成り立つものの、k=tは成り立つとは限らない。【００４５】
［事前計算を利用したＭＰＣ］
非特許文献５〜７では、ＭＰＣの計算に必要となるデータの一部を事前計算しておくことでＭＰＣの効率化を図る。【００４６】
本明細書では、事前計算について詳述しない。ただし、何らかの方法（例えば非特許文献５〜７の方法）で事前計算データが用意されている場合も考慮して、「事前計算データがもしあれば、それを用いる」という趣旨の文言を実施形態の説明に加えた。【００４７】
［ＺＫＩＰ法、ＭＡＣ法］
秘密分散を利用した既存のＭＰＣには、不正者に乗っ取られたＭＰＣ装置が不正を働くことで秘密の情報を盗んだり、計算結果を偽ったりできないような仕組みを持っているものが多い。【００４８】
このような仕組みとして、ゼロ知識証明（ＺＫＩＰ：Zero-Knowledge Interactive Proof）法（非特許文献４）とメッセージ認証子（ＭＡＣ：Message Authentication Code）法（非特許文献５〜７）が知られている。いずれの方法も、ＭＰＣ装置が行った計算が不正なものではないことを示すための「正当性証明」を作成する「正当性証明作成部」と正当性証明を検証する「正当性検証部」を備えている。ただし、正当性証明の作り方やその検証方法については、ＺＫＩＰ法とＭＡＣ法とで相違する。また、「正当性証明作成部」と「正当性検証部」を備えた装置構成自体は、ＺＫＩＰ法とＭＡＣ法の間で共通する。【００４９】
ＺＫＩＰ法およびＭＡＣ法のＭＰＣ装置の装置構成は、以下のとおりである。
入力部
通信部
計算部
ＭＰＣ実行部
正当性証明部
正当性証明検証部
出力部【００５０】
ＺＫＩＰ法およびＭＡＣ法では秘密分散をサブルーチンとして用いており、ＭＰＣ装置以外に秘密分散のための「分散装置」と「復元装置」が用いられる。【００５１】
ＺＫＩＰ法およびＭＡＣ法では、各ＭＰＣ装置に事前に関数fを計算する手段が回路図の形で入力されているものとする。関数fの回路図はANDゲートやORゲートのような「素子」から構成され、各素子には「素子番号」が振られているものとする。以下では、説明を簡単にするため、入力ゲートに近い素子ほど小さい素子番号が割り振られていると仮定して説明する。ただし、かかる仮定は必須のものではない。【００５２】
また、以下では、何らかの事前計算データが用意されていることを仮定して説明する。ただし、以下の記述の中から事前計算データに関する記述を無視することで、事前計算のないＭＰＣに対しても同様の説明が当てはまる。【００５３】
ＺＫＩＰ法およびＭＡＣ法は、いずれも以下のように動作する。
j=1,...,Mに対し、j番目のＭＰＣ装置は、分散装置から秘密x[1],...,x[N]のシェアs[1,j],...,s[N,j]を入力部を用いて受け取る。
関数fの回路図を構成する各素子Rに対し、素子番号が小さいものから順に以下を実行する。
各ＭＰＣ装置は素子R、素子Rの入力端子に対応するシェア、および、事前計算データ（もしあれば）をＭＰＣ実行部に入力する。そして、通信部を用いることで相互通信しながらＭＰＣ実行部の処理を実行する。
各ＭＰＣ装置は素子R、素子Rの入力端子に対応するシェア、事前計算データ（もしあれば）、および、ＭＰＣ実行部の実行に使用した乱数（もしあれば）を入力として正当性証明部の処理を実行することで正当性証明を作成し、他のＭＰＣ装置に正当性証明を送信する。
各ＭＰＣ装置は素子Rと正当性証明を正当性証明検証部に入力することで、他のＭＰＣ装置の正当性証明の正当性を検証する。
関数fの回路図の出力端子に対応するシェアを、出力部を用いて出力する。
出力されたシェアは、復元装置に送られる。復元装置は、送られてきたシェアからＭＰＣの出力を復元する。【００５４】
上記の説明では、ＭＰＣ装置の正当性証明部が生成した正当性証明を別のＭＰＣ装置が受け取った上で正当性証明検証部を使って正当性証明を検証することを仮定して説明した。ただし、既存のＭＰＣ方式の中には、非特許文献４に記載された方式のように、正当性証明部と正当性証明検証部の間で複数回の相互通信を伴うものもある。【００５５】
また、非特許文献６に記載された方式のように、最後に一括して正当性証明を検証することでＭＰＣを効率化するものもある。【００５６】
しかし、いつどのような方法で正当性証明部と正当性証明検証部の処理を実行するのかという点を除くと、いずれの方式も上述のフローに当てはまる。【００５７】
［ＺＫＩＰ法とＭＡＣ法の問題点］
ＺＫＩＰ方式とＭＡＣ方式には、以下の問題点がある。
実行速度が遅く、サーバ同士、ユーザ・サーバ間双方の通信量が多い。
認証システムにおいては、数多くのユーザがシステムを利用する。したがって、これらのユーザの処理をすべて実行するために、システムには高い性能が求められる。既存方式は、実行速度や通信量の点で難がある。したがって、認証システムに求められる性能を出すためには、システムで用いるサーバを高性能なものにしたり、回線を高速度のものにしたりすることが求められる。このとき、システム構築に必要となる費用が嵩むという問題が生じる。
ユーザ端末として、スマートフォンのような計算能力および通信性能が低い端末が用いられることが想定される。したがって、ＺＫＩＰ方式またはＭＡＣ方式のように高い実行速度と多くの通信量を必要とする方式は、利用できない可能性もある。【００５８】
［依頼計算とガーブルドサーキット（ＧＣ：Garbled Circuit）法］
依頼計算(Secure Function Evaluation)とは、２つの装置を利用した方式である。具体的には、１つ目の装置が関数f（の回路図）を保持し、２つ目の装置が秘密の情報x[1],....,x[N]を保持する状態からスタートして、１つ目の装置が関数値f(x[1],...,x[N])を得ることを目標に行われる（非特許文献８）。【００５９】
依頼計算では２つ目の装置は関数fの情報を完全には知ることはできず、１つ目の装置は秘密の情報x[1],....,x[N]の情報を一切知ることはできない。【００６０】
ガーブルドサーキット（ＧＣ：Garbled Circuit）法（非特許文献９）は、依頼計算の代表的な方法である。ＧＣ法では、関数fを保有する側の装置が「ＧＣ（Garbled Circuit）」というデータを作成し、秘密の情報x[1],....,x[N]を保有する側の装置がＧＣを計算する。以下では、前者の装置を「ＧＣ作成装置」と呼び、後者の装置を「ＧＣ実行装置」と呼ぶ。【００６１】
ＧＣ作成装置は、以下のユニットを備えている。
入力部
ＧＣ生成部
ＧＣ出力生成部
送信部
出力部【００６２】
一方、ＧＣ実行装置は、以下のユニットを備えている。
入力部
ＧＣ実行部
送信部【００６３】
ＧＣは、以下のように動作する。
ＧＣ作成装置は、関数fを入力としてＧＣ生成部の処理を実行することでＧＣと鍵データKを作成し、ＧＣをＧＣ実行装置に送信する。
ＧＣ実行装置はＧＣと秘密の情報x[1],...,x[N]を入力としてＧＣ実行部の処理を実行することで、「ＧＣの出力」Eを取得し、ＧＣの出力EをＧＣ作成装置に送信する。
ＧＣ作成装置はＧＣの出力Eと鍵データKとを入力としてＧＣ出力生成部の処理を実行することで、出力yを得て、出力yを出力する。【００６４】
ＧＣ法においては、以下の性質が成立する。
（たとえＧＣ実行装置が不正者に乗っ取られたとしても）ＧＣ作成装置が不正者に乗っ取られない限り、出力yはf(x[1],...,x[N])に一致する。【００６５】
［ＧＣ法の問題点］
後述するように、本願開示ではＧＣ法に適切に改良を施した上でＭＰＣとして用いる。しかし、ＧＣ法それ自身には以下の問題があるため、そのままでは本願開示には適用することができない。
ＧＣ法自身はあくまで依頼計算を実現するための方式であり、ＭＰＣを実現するための方式ではない。したがって、ＧＣ実行装置が秘密の情報x[1],...,x[N]を知っていることを前提にしている。しかし、本願開示ではＧＣ法をＭＰＣとして用いるため、秘密のデータx[1],...,x[N]の秘匿性も担保する必要がある。
ＧＣ法ではＧＣ作成装置が不正者に乗っ取られないかぎり、出力yがf(x[1],...,x[N])に一致することが保証できる。しかしながら、ＧＣ作成装置が不正者に乗っ取られた場合に関しては何ら保証がない。【００６６】
［既存の認証技術とその問題点］
以上で本願開示および既存方式において利用する技術に関する説明を終了する。以下では、認証に関する既存方式を説明する。【００６７】
［ＦＩＤＯ方式］
前述した認証に関する問題を解決する一手法として、オンライン認証技術の標準化を行っている標準化団体ＦＩＤＯ（Fast Identify Online）は、ＵＡＦ（Universal Authentiation Framework）標準と呼ばれる認証手法を提案している（非特許文献１）。以下では、この認証手法を「ＦＩＤＯ方式」と呼ぶ。【００６８】
ＦＩＤＯ方式の特徴は、ユーザ装置に「セキュア領域」と呼ばれる安全性の高い領域の存在を仮定した点にある。ＦＩＤＯ方式では、ユーザの本人性を認証する「ユーザ認証」とユーザの機器を認証する「機器認証」が別個に行われる。ユーザの本人認証に用いる検証情報およびユーザの機器認証に使う秘密鍵は、このセキュア領域に格納される。【００６９】
図１は、ＦＩＤＯ方式の構成を例示するブロック図である。【００７０】
認証を行うには、以下の事前準備を行う必要がある。【００７１】
ユーザ装置11はユーザ情報取得部111を有する。ユーザ情報取得部111は、顔情報、指紋情報、光彩情報などの１つまたは複数のユーザ認証情報を取得する取得部1111を提供する。ユーザ装置11は、認証におけるこれらの検証情報を登録するため、ユーザ13からユーザ固有情報（顔情報、指紋情報、光彩情報など）を、取得部1111を用いて取得する。また、ユーザ装置11は取得したユーザ固有情報を検証情報導出部11211に入力することで検証情報を得る。登録された検証情報は、セキュア領域112（非特許文献１の「FIDO AUTHENTICATOR」）の記憶部1122に保管される。【００７２】
ユーザ装置11は、セキュア領域112の鍵ペア生成部11214を用いて（事前に定められた何らかの公開鍵認証方式の）鍵生成を行う。また、ユーザ装置11は生成された公開鍵pkと秘密鍵skをセキュア領域112の記憶部1122に保管し、公開鍵pkを機器認証サーバ装置12に送信する。機器認証サーバ装置12は、受信した公開鍵pkを自身の公開鍵データベース1221に保存する。【００７３】
認証を行う際、まず機器認証サーバ装置12はユーザ認証方法選択部1211を用いていずれの認証方法を用いて認証するのかを指定する。【００７４】
ユーザ装置11は、指定された認証方法におけるユーザ固有情報を、取得部1111を用いてユーザ13から受け取る。ユーザ装置11は、受け取ったユーザ固有情報を認証情報導出部11212に入力することで認証情報を得る。【００７５】
ユーザ装置11は、入力された認証情報と記憶部1122に保管された検証情報とを用いて、セキュア領域112のユーザ認証部11213の処理を実行する。これにより、ユーザ装置11はユーザ13の当人性を確認する。【００７６】
ユーザ認証部11213がユーザ13の認証を拒否した場合、ユーザ装置11は通知部114を用いて認証が拒否された旨をユーザ13に伝えて動作を終了する。【００７７】
一方、ユーザ認証部11213がユーザ13の認証を受理した場合、ユーザ装置11はセキュア領域112の記憶部1122に保管された秘密鍵skと公開鍵pkを用いて機器認証部11215の処理を実行する。機器認証サーバ装置12は、これを受けて公開鍵データベース1221に保管されたユーザ装置11の公開鍵pkを用いて機器認証検証部1212の処理を実行する。これにより、機器認証サーバ装置12はユーザ装置11の認証を受理または拒否する。最後に、ユーザ装置11は認証が受理または拒否された旨を通知部114を用いてユーザ13に伝えて動作を終了する。【００７８】
なお、機器認証部11215と機器認証検証部1212が通信する際には、ユーザ装置フロントエンド1131とサーバ装置フロントエンド1231を経由する。これらのフロントエンドはＦＩＤＯにより通信方法の標準化がなされているフロントエンドであり、広く普及している。【００７９】
［ＦＩＤＯ方式の問題点］
ＦＩＤＯ方式には、ユーザ装置11にセキュア領域112が存在することを仮定している（ないし前提としている）という問題がある。【００８０】
例えばマルウェア感染などによりセキュア領域112が侵された場合、そこに保存されている検証情報や秘密鍵が漏えいしてしまう可能性がある。【００８１】
特に、不正者は漏えいした検証情報や秘密鍵を用いることでユーザ13に成りすましてウェブサービスを行うことができるため、深刻な問題が生じ得る。【００８２】
また、ＦＩＤＯ方式の認証を利用したユーザアプリを開発した企業にとっては、企業イメージの悪化、これに伴う収益の減少、さらにはユーザ13に対する損害賠償費用の負担といったリスクも生じ得る。【００８３】
さらに、認証として生体認証を用いた場合、検証情報は生体情報という最高度に機微な情報であることから、重大な危険が生じ得る。【００８４】
以上の理由により、ＦＩＤＯ方式のようにユーザ装置11にセキュア領域112の存在を仮定する方式は望ましくない。【００８５】
［サーバサイドＭＰＣ方式］
ＭＰＣを利用した認証方式の一形態について、説明する。以下では、この認証方式を「サーバサイドＭＰＣ方式」と呼ぶ。【００８６】
図２は、サーバサイドＭＰＣ方式の装置構成を例示するブロック図である。以下、サーバサイドユーザ認証ＭＰＣ装置22の台数をMとする。【００８７】
サーバサイドＭＰＣ方式の基本的なアイデアは、通常の認証方式であればサーバ装置１台で認証の正当性を検証するところを、M台の「サーバサイドユーザ認証ＭＰＣ装置22」を使ってＭＰＣを行いながら認証の正当性を検証するところにある。【００８８】
サーバサイドユーザ認証ＭＰＣ装置22は、全部でM台ある。そこで、以下j番目のサーバサイドユーザ認証ＭＰＣ装置22に含まれるユニットの符号には、末尾に「[j]」を付すことで装置を区別する。例えば、「サーバサイドユーザ認証ＭＰＣ装置22[j]の分散ユーザ検証情報データベース2221[j]」といった表現を用いる。【００８９】
図２は、１つの認証方法のみを提供する場合を図示した。なお、ＦＩＤＯ方式の場合と同様、複数の認証方法を提供して、それらの中から認証方法を選ぶように拡張することも可能である。【００９０】
ＦＩＤＯ方式では、ユーザ認証と機器認証が行われる。一方、サーバサイドＭＰＣ方式ではユーザ認証のみが行われる。なお、サーバサイドＭＰＣ方式を機器認証も行うように改良することも可能である。ただし、このように改良しても、後述するようにサーバサイドＭＰＣ方式の問題点は解決されない。以下では、サーバサイドＭＰＣ方式において機器認証を行う場合についての説明を省略する。【００９１】
サーバサイドＭＰＣ方式では、ユーザ装置21がＭＰＣにおける分散装置の役割を果たす。ユーザ装置21は、ユーザ23の認証情報を分散する認証情報分散部2123と検証情報を分散する検証情報分散部2124を備えている。【００９２】
サーバサイドユーザ認証ＭＰＣ装置22は、ＭＰＣにおけるＭＰＣ装置である。しかし、１台目のサーバサイドユーザ認証ＭＰＣ装置22[1]のみは復元装置の役割も担っており、ＭＰＣの出力である認証結果を復元するための認証結果復元部2212[1]を有する。【００９３】
サーバサイドＭＰＣ方式におけるＭＰＣの計算関数fは、ユーザ認証の認証関数である。すなわち、関数fはユーザ23の認証情報と検証情報を入力として受け取り、認証を受理または拒否したことを示す何らかのデータ（例えば受理なら1、拒否なら0）を出力する。サーバサイドＭＰＣ方式は、以下のように行われる。【００９４】
まず事前準備として、ユーザ装置21はユーザ情報取得部211の取得部2111を用いてユーザ23からユーザ固有情報を受け取る。次に、ユーザ装置21は検証情報導出部2121を用いてユーザ固有情報から検証情報を導出し、導出した検証情報を検証情報分散部2124に入力して検証情報のシェアv[1],...,v[M]を得る。次に、ユーザ装置21は独自仕様通信部2131を用いることでシェアv[1]をサーバサイドユーザ認証ＭＰＣ装置22[1]に送り、...、シェアv[M]をサーバサイドユーザ認証ＭＰＣ装置22[M]に送る。【００９５】
サーバサイドユーザ認証ＭＰＣ装置22[1]、...、サーバサイドユーザ認証ＭＰＣ装置22[M]は、それぞれ独自仕様通信部2231[1],...,独自仕様通信部2231[M]を用いることでシェアv[1],...,v[M]を受信し、それぞれ分散ユーザ検証情報データベース2221[1],...,分散ユーザ検証情報データベース2221[M]に保管する。【００９６】
認証を受けるには、ユーザ装置21はユーザ情報取得部211の取得部2111を用いてユーザ23からユーザ固有情報を受け取る。次に、ユーザ装置21は認証情報導出部2122を用いてユーザ固有情報から認証情報を導出し、導出した認証情報を認証情報分散部2123に入力することで認証情報のシェアs[1],...,s[M]を作る。次に、ユーザ装置21は独自仕様通信部2131を用いることで、シェアs[1]をサーバサイドユーザ認証ＭＰＣ装置22[1]に送り、...、シェアs[M]をサーバサイドユーザ認証ＭＰＣ装置22[M]に送る。【００９７】
サーバサイドユーザ認証ＭＰＣ装置22[1]、...、サーバサイドユーザ認証ＭＰＣ装置22[M]は、それぞれ独自仕様通信部2231[1],...,独自仕様通信部2231[M]を用いることでシェアs[1],...,s[M]を受信する。次に、サーバサイドユーザ認証ＭＰＣ装置22[1]、...、サーバサイドユーザ認証ＭＰＣ装置22[M]は、それぞれ分散ユーザ検証情報データベース2221[1],...,分散ユーザ検証情報データベース2221[M]からユーザ23の検証情報のシェアv[1],...,v[M]を読み出し、そしてシェアv[1],...,v[M]およびシェアs[1],...,s[M]を使用して相互に通信しながらユーザ認証ＭＰＣ部2211[1],...,ユーザ認証ＭＰＣ部2211[M]の処理を実行する。これにより、サーバサイドユーザ認証ＭＰＣ装置22[1]、...、サーバサイドユーザ認証ＭＰＣ装置22[M]は、それぞれＭＰＣの出力のシェアt[1],...,t[M]を得る。【００９８】
サーバサイドユーザ認証ＭＰＣ装置22[2]、...、サーバサイドユーザ認証ＭＰＣ装置22[M]は、それぞれ独自仕様通信部2231[2],...,独自仕様通信部2231[M]を用いることで、それぞれシェアt[2],...,t[M]をサーバサイドユーザ認証ＭＰＣ装置22[1]に送信する。サーバサイドユーザ認証ＭＰＣ装置22[1]は、独自仕様通信部2231[1]を用いてこれらのシェアを受け取り、シェアt[1],...,t[M]を入力して認証結果復元部2212[1]の処理を実行することで、認証結果が受理なのか拒否なのかを把握する。【００９９】
［サーバサイドＭＰＣ方式の問題点］
通常のユーザ認証における通信プロトコルには、様々な標準がある。しかしながら、いずれの通信プロトコルもユーザ装置とサーバ装置の１対１の通信を前提としたものである。実際、ＦＩＤＯが提案している通信プロトコルもユーザ装置とサーバ装置の１対１の通信を前提としている。具体的には、図１におけるユーザ装置フロントエンド1131とサーバ装置フロントエンド1231がＦＩＤＯの提案する通信プロトコル標準に対応する箇所である。【０１００】
しかるに、サーバサイドＭＰＣ方式では、１台のユーザ装置21とM台のサーバサイドユーザ認証ＭＰＣ装置22による１対多の通信を利用する。しかし、１対１の通信を前提とした通信プロトコルを利用したウェブサービスやインフラストラクチャーが普及している現状において、サーバサイドＭＰＣ方式のように１対多の通信を利用する方式を利用することは現実的ではない。【０１０１】
また前述のように、ＭＰＣは不正なＭＰＣ装置の集合がＭＰＣ安全性条件を満たしている場合に限って安全性を保つことができる。サーバサイドＭＰＣ方式では、ユーザ装置21はユーザ23の検証情報の特徴量のシェアをサーバ側に送出してしまう。したがって、ＭＰＣ安全性条件を超える台数のＭＰＣ装置が不正に結託した場合、サーバ側にユーザ23の検証情報の特徴量という最高度に機微な情報を知られてしまう危険が生じる。【０１０２】
［サーバサイドＭＰＣ方式の変形例とその問題点］
上述したサーバサイドＭＰＣ方式では、ユーザの認証情報のみを用いて認証を行うことを想定している。ここで、サーバサイドＭＰＣ方式の変形例として、ＦＩＤＯ方式のようにユーザの認証情報とユーザ秘密鍵情報の両方を用いて認証するものが考えられる。【０１０３】
しかしながら、かかる変形例によると、ユーザ秘密鍵をどのように保管するべきかという問題を抱える。【０１０４】
ここでＦＩＤＯ方式と同様に、ユーザ装置21にセキュア領域の存在を仮定した上で、セキュア領域にユーザ秘密鍵を保存した場合、ＦＩＤＯ方式と同様にマルウェアなどによりセキュア領域が侵される危険性が生じる。【０１０５】
また、M台のサーバサイドユーザ認証ＭＰＣ装置22にユーザ秘密鍵を分散した場合、サーバサイドＭＰＣ装置側がＭＰＣ条件を超えて結託したときにユーザ秘密鍵の秘匿性を担保できないという問題が生じる。【０１０６】
［暗号化通信方式］
最後に暗号化通信を利用した認証方式の一形態について説明する。以下では、この方式を「暗号化通信方式」と呼ぶ。暗号化通信方式の例として、例えば非特許文献２に記載されたものがある。ここでは、非特許文献２のものよりも簡略化したものを紹介する。【０１０７】
暗号化通信方式の基本的なアイデアは、ユーザの認証情報および検証情報をサーバ装置の公開鍵で暗号化した上でサーバ装置に送信するというものである。これにより、サーバ装置には、認証情報や検証情報が暗号化された形でしか保管されない。したがって、サーバ装置のデータが不正者に見られたとしても安全性を保つことができる。【０１０８】
しかし、サーバ装置の秘密鍵もサーバ装置上に置いた場合、サーバ装置のデータを不正者に見られたときに、認証情報や検証情報の暗号文のみならず秘密鍵も不正者にとられてしまう。このとき、不正者は暗号文を復号することで、認証情報や検証情報という機微な情報を復元できてしまうという問題がある。【０１０９】
そこで暗号化通信方式では、サーバ装置とは別に「サーバ補助装置」という装置を設け、サーバ装置の秘密鍵をサーバ装置ではなくサーバ補助装置に保管する。【０１１０】
ＦＩＤＯ方式では、ユーザ認証と機器認証が行われる。一方、暗号化通信方式では、ユーザ認証しか行わない。なお、暗号化通信方式を機器認証も行うように改良することができる。しかしながら、そのように改良しても、後述するような暗号化通信方式の問題点は解決されない。そこで、以下では、暗号化通信方式において機器認証を行う場合に関する説明を省略する。【０１１１】
図３は、暗号化通信方式の構成を例示するブロック図である。【０１１２】
まず事前準備として、ユーザ認証サーバ補助装置33は、計算部331のサーバ補助装置鍵生成部3311の処理を実行することで（何らかの公開鍵暗号方式における）サーバ補助装置秘密鍵skとサーバ補助装置公開鍵pkを生成し、サーバ補助装置秘密鍵skを記憶部332に保管し、サーバ補助装置公開鍵pkを、通信部333を経由してユーザ装置31に送る。【０１１３】
ユーザ装置31は、サーバ補助装置公開鍵pkを受信して記憶部313に保管する。【０１１４】
次にユーザ装置31は、ユーザ情報取得部311の取得部3111を用いてユーザ34からユーザ固有情報を受け取る。ユーザ装置31は、ユーザ固有情報を検証情報導出部3122に入力することで検証情報を取得する。ユーザ装置31は、検証情報とサーバ補助装置公開鍵pkを検証情報暗号化部3124に入力することで検証情報の暗号文を作成する。ユーザ装置31は、ユーザ装置独自仕様フロントエンド3141を経由して暗号文をユーザ認証サーバ装置32に送る。ユーザ認証サーバ装置32は、サーバ装置独自仕様フロントエンド3231を経由して暗号文を受け取り、暗号文を暗号化ユーザ検証情報データベース3221に保管する。【０１１５】
認証の際、ユーザ装置31はユーザ情報取得部311の取得部3111を用いてユーザ34からユーザ固有情報を受け取る。ユーザ装置31は、ユーザ固有情報を認証情報導出部3121に入力することで認証情報を得る。ユーザ装置31は、認証情報とサーバ補助装置公開鍵を認証情報暗号化部3123に入力することで認証情報の暗号文を作成する。ユーザ装置31は、ユーザ装置独自仕様フロントエンド3141を経由して暗号文をユーザ認証サーバ装置32に送る。ユーザ認証サーバ装置32は、暗号化ユーザ検証情報データベース3221からユーザの暗号化された検証情報を探し出す。【０１１６】
次に、ユーザ認証サーバ装置32は暗号化された検証情報と暗号化された認証情報をサーバ装置暗号化認証検証部3211に入力する。また、ユーザ認証サーバ補助装置33は、サーバ補助装置秘密鍵skをサーバ補助装置暗号化認証検証部3312に入力する。ユーザ認証サーバ装置32とユーザ認証サーバ補助装置33は、補助通信部3232と補助通信部3331を利用して相互に通信しながら、それぞれサーバ装置暗号化認証検証部3211とサーバ補助装置暗号化認証検証部3312の処理を実行する。最終的に認証結果（受理するか拒否するか）を決定し、ユーザ認証サーバ装置32はサーバ装置独自仕様フロントエンド3231を用いて認証結果をユーザ装置31に通知する。ユーザ装置31は、ユーザ装置独自仕様フロントエンド3141を使って認証結果を受信する。また、ユーザ装置31は通知部315を使用して認証結果をユーザ34に通知する。【０１１７】
サーバ装置暗号化認証検証部3211とサーバ補助装置暗号化認証検証部3312をどのように実現するかには、様々な方法がある。一例として、ＭＰＣを実行することで認証の受理または拒否を決定する方法が考えられる。【０１１８】
［暗号化通信方式の問題点］
ユーザ認証サーバ装置32とユーザ認証サーバ補助装置33の両方が不正者に乗っ取られた場合、ユーザの認証情報という最高度に機微な情報が不正者の手に渡ってしまうという問題がある。【０１１９】
また、ユーザ認証サーバ装置32のみが不正者に乗っ取られた場合であっても、以下の方法によりサーバサイド・オフライン攻撃が可能である。
ユーザ認証サーバ装置32は、通常の手段でユーザ装置31の検証情報の暗号文Cを受け取る。
ユーザ認証サーバ装置32は、任意の情報Mを暗号化して暗号文C'を作成する。
ユーザ認証サーバ装置32は暗号文C、C'をサーバ装置暗号化認証検証部3211に入力し、ユーザ認証サーバ補助装置33と通信しながらサーバ装置暗号化認証検証部3211の処理を実行する。
サーバ装置暗号化認証検証部3211の出力が受理であるか拒否であるかに応じて、ユーザ認証サーバ装置32は任意の情報Mがユーザの認証情報と一致するか否かを判定することができる。【０１２０】
上述の攻撃は、ユーザ装置31と通信することなく実行可能である。したがって、ユーザ装置31（または、ユーザ装置31を保有するユーザ）に気付かれることなく、不正者は何度でも攻撃を実行することができる。ユーザの認証情報がパスワードや生体情報である場合、認証情報のエントロピーは小さい。したがって、上述の攻撃をMを変えつつ何度も実行することで、不正者はユーザの認証情報を特定することができる。【０１２１】
暗号化通信方式のもう１つの問題点は、ユーザ装置31とユーザ認証サーバ装置32の間の認証情報のやり取りが（暗号化された状態で）行われる点である。【０１２２】
ＦＩＤＯが標準化しているフロントエンドでは、ユーザ装置31とユーザ認証サーバ装置32の間で認証情報をやり取りしていることを想定していない。したがって、暗号化通信方式では、ＦＩＤＯのフロントエンドというすでに普及している標準を使うことができないという問題がある。【０１２３】
［暗号化通信方式の変形例とその問題点］
暗号化通信方式の変形例として、以下のものが考えられる。ただし、いずれの変形例も、上述した問題と同様の問題を抱える。
ユーザの検証情報や認証情報の暗号化において、公開鍵暗号ではなく共通鍵暗号を使う。
上述の方式では、ユーザサイド補助装置が１台であることを想定している。そこで、複数台のユーザサイド補助装置を用意し、ユーザサイド補助装置秘密鍵を分散シェアする。【０１２４】
次に、本発明が解決しようとする課題について、さらに詳細に説明する。これまで説明したように、既存の認証方式は、いずれも以下に挙げる１つ以上の問題をはらんでいる。
ユーザ装置にセキュア領域が存在することを仮定する必要がある。したがって、セキュア領域がマルウェアに侵されるなどした場合、ユーザの認証情報という最高度に機微な情報が不正者に漏えいする。
サーバ側の装置（サーバ装置やサーバ補助装置）がＭＰＣ条件以上に結託すると、ユーザの認証情報という最高度に機微な情報が不正者に漏えいする。
サーバサイド・オフライン攻撃に対して、安全でない。したがって、不正者がサーバの乗っ取りに成功すると、サーバサイド・オフライン攻撃によりユーザの認証情報という最高度に機微な情報が不正者に漏えいする。特にサーバの管理者自身が不正者である場合、一切安全を保てない。
ＦＩＤＯが標準化しているフロントエンドをはじめとする既存の通信標準を満たしていない。したがって、既存の通信標準を利用している大多数の装置との通信が不可能である。【０１２５】
なお、既存の認証方式の中には、ＭＰＣを使うものも存在する。しかしながら、既存のＭＰＣであるＺＫＩＰ法およびＭＡＣ法には、以下の問題点がある。
ＺＫＩＰやＭＡＣを生成、送受信および検証するのに計算コストと通信コストがかかるため、計算効率と通信効率が悪化する。特にユーザ装置がスマートフォンのような非力なデバイスである場合、計算効率と通信効率の悪さがネックとなる。したがって、既存の認証方式は実用性に乏しい。【０１２６】
さらに、ＧＣには以下の問題がある。
ＧＣ法自身はあくまで依頼計算を実現するための方式であり、ＭＰＣを実現するための方式ではない。したがって、ＧＣ法によると、入力データの秘密を担保できない。
ＧＣ作成装置が不正者に乗っ取られた場合に関して、何ら保証がない。【０１２７】
そこで、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用可能とすることが課題となる。本発明の目的は、かかる課題解決に寄与する認証システム、認証方法およびプログラムを提供することにある。その他の課題および解決手段は、以下の説明において明らかとなる。
【課題を解決するための手段】
【０１２８】
本発明の第１の態様に係る認証システムは、ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えている。前記ユーザサイド補助装置は、検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行うとともに、前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行う。【０１２９】
本発明の第２の態様に係る認証方法は、ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、前記ユーザ装置が、秘密鍵の分散シェアを生成するステップと、検証情報の分散シェアを用いて前記ユーザサイド補助装置との間で前記ユーザ認証のためのマルチパーティ計算を行うステップと、前記秘密鍵の分散シェアを用いて、前記ユーザサイド補助装置との間で前記機器認証のためのマルチパーティ計算を行うステップと、を含む。【０１３０】
本発明の第３の態様に係る方法は、ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、前記ユーザサイド補助装置が、検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行うステップと、前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行うステップと、を含む。【０１３１】
本発明の第４の態様に係るプログラムは、ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、秘密鍵の分散シェアを生成する処理と、検証情報の分散シェアを用いて前記ユーザサイド補助装置との間で前記ユーザ認証のためのマルチパーティ計算を行う処理と、前記秘密鍵の分散シェアを用いて、前記ユーザサイド補助装置との間で前記機器認証のためのマルチパーティ計算を行う処理と、を前記ユーザ装置に設けられたコンピュータに実行させる。【０１３２】
本発明の第５の態様に係るプログラムは、ユーザ装置と、前記ユーザ装置のユーザを認証するユーザ認証および前記ユーザ装置を認証する機器認証を補助するユーザサイド補助装置と、前記ユーザ装置との間で前記機器認証を行う機器認証サーバ装置と、を備えた認証システムにおいて、検証情報の分散シェアを用いて前記ユーザ装置との間で前記ユーザ認証のためのマルチパーティ計算を行う処理と、前記ユーザ装置が生成した秘密鍵の分散シェアを用いて、前記ユーザ装置との間で前記機器認証のためのマルチパーティ計算を行う処理と、を前記ユーザサイド補助装置に設けられたコンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【０１３３】
本発明に係る認証システム、認証方法およびプログラムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。
【図面の簡単な説明】
【０１３４】
【図１】ＦＩＤＯ方式の構成を例示するブロック図である。
【図２】サーバサイドＭＰＣ方式の構成を例示するブロック図である。
【図３】暗号化通信方式の構成を例示するブロック図である。
【図４】第１の実施形態に係る認証システムの構成を例示するブロック図である。
【図５】ユーザ認証事前準備（検証情報の登録）の動作を例示するフロー図である。
【図６】機器認証事前準備（公開鍵・秘密鍵ペアの生成と登録）の動作を例示するフロー図である。
【図７】ユーザ認証の動作を例示するフロー図である。
【図８】ユーザ装置ユーザ認証ＭＰＣ部の構成を例示するブロック図である。
【図９】ユーザサイド補助装置ユーザ認証ＭＰＣ部の構成を例示するブロック図である。
【図１０】ユーザ認証ＭＰＣの動作を例示するフロー図である。
【図１１】ユーザ装置機器認証ＭＰＣ部の構成を例示するブロック図である。
【図１２】ユーザサイド補助装置機器認証ＭＰＣ部の構成を例示するブロック図である。
【図１３】機器認証の動作を例示するフロー図である。
【図１４】ユーザサイド補助装置ユーザ認証ＭＰＣ部の構成を例示するブロック図である。
【図１５】ユーザ装置ユーザ認証ＭＰＣ部の構成を例示するブロック図である。
【図１６】第２の実施形態におけるユーザ認証ＭＰＣの動作を例示するフロー図である。
【図１７】機器認証シミュレートＭＰＣ部の構成を例示するブロック図である。
【図１８】機器認証シミュレートＭＰＣの動作を例示するフロー図である。
【図１９】一実施形態に係る認証システムの構成を例示する図である。
【発明を実施するための形態】
【０１３５】
＜一実施形態＞
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【０１３６】
図１９は、一実施形態に係る認証システムの構成を例示する図である。図１９を参照すると、認証システムは、ユーザ装置41と、ユーザ装置41のユーザを認証するユーザ認証およびユーザ装置41を認証する機器認証を補助するユーザサイド補助装置43[1]-43[M]（Mは自然数）と、ユーザ装置41との間で機器認証を行う機器認証サーバ装置42とを備えている。ユーザサイド補助装置43[1]-43[M]は、検証情報の分散シェアを用いてユーザ装置41との間でユーザ認証のためのマルチパーティ計算を行うとともに、ユーザ装置41が生成した秘密鍵の分散シェアを用いて、ユーザ装置41との間で機器認証のためのマルチパーティ計算を行う。
【０１３７】
一実施形態に係る認証システムでは、ユーザサイド補助装置とユーザ装置との間で検証情報の分散シェアを用いてマルチパーティ計算を行う。したがって、ユーザ装置は検証情報をそのまま保持する必要がなく、ＦＩＤＯ方式のようにユーザ装置内にセキュアな領域の存在を仮定する必要がなくなる。また、一実施形態では、ユーザ装置と機器認証サーバ装置の間でやり取りされるデータは既存のＦＩＤＯ方式と同様である。したがって、一実施形態によれば、サーバサイドＭＰＣ方式および暗号化通信方式のように独自仕様の通信フロントエンドを設けることなく、既存の機器認証サーバとの通信フロントエンドを利用することができる。さらに、一実施形態によると、ＦＩＤＯ方式と同様にユーザ認証および機器認証の双方の認証が可能となる。すなわち、一実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。
【０１３８】
＜第１ないし第８の実施形態の概要＞
はじめに、以下で詳述する第１ないし第８の実施形態の構成および効果について概説する。
【０１３９】
実施形態では、２種類のマシンを利用することを想定する。１つ目のマシンはユーザが自身のユーザ装置として用いられるマシンであり、具体的にはスマートフォン、タブレット、ＰＣ（Personal Computer）などである。２つ目のマシンは、サーバマシンである。サーバマシンはユーザ装置として使われるマシンよりも高性能であり、複数のユーザ装置と通信することが可能である。
【０１４０】
実施形態では、サーバとして用いられるマシンの方がユーザ装置として用いられるマシンよりも、以下の理由によりはるかにセキュリティの強度が高いことを利用する。安価であることが求められるユーザ装置は、セキュリティ保護機能が軽視される傾向にある上、ユーザ装置にはユーザが様々なアプリを自由にインストールできる。したがって、ユーザが不正なアプリをインストールしてしまうことなどにより、ユーザ装置は不正者に乗っ取られる可能性が高い。一方、サーバマシンであるユーザサイド補助装置は、ユーザ装置よりも高度なセキュリティ保護機能を備えることができ、しかもアプリのインストールなどは行われないため、ユーザ装置よりもはるかに安全性が高い。
【０１４１】
そこで、以下の実施形態では、ユーザ装置の認証を補助するサーバマシンである「ユーザサイド補助装置」を準備する。なお、ここで「ユーザサイド」とは、サーバサイド（例えば図１の機器認証サーバ装置１２の側）と対比する意味でのユーザサイド（例えば図１のユーザ装置１１の側）を意味するに過ぎない。すなわち、「ユーザサイド補助装置」はユーザ装置のユーザが保持する装置を意味するものではなく、むしろ複数の（多数の）ユーザ装置によって「ユーザサイド補助装置」が共有される使用形態が想定される。
【０１４２】
実施形態では、ＦＩＤＯ方式と同様、ユーザ認証と機器認証を分離する。ユーザ装置は、ユーザサイド補助装置の助けを借りながらユーザ認証を行う。その後、ユーザ装置はユーザサイド補助装置の助けを借りながら外部の「機器認証サーバ装置」から機器認証を受ける。
【０１４３】
具体的には、実施形態では（何らかの公開鍵認証方式における）ユーザ装置の秘密鍵と公開鍵を作成し、秘密鍵をユーザ装置とユーザサイド補助装置で分散シェアする。そしてユーザ装置とユーザサイド補助装置とがユーザの検証情報と認証情報の分散シェアを用いてＭＰＣを実行することでユーザ認証を行う。その後、ユーザ秘密鍵の分散シェアを用いてＭＰＣを実行することで、機器認証サーバ装置との公開鍵認証で必要な情報を作成する。
【０１４４】
なお、ユーザサイド補助装置は多数のユーザの検証情報の分散シェアを保管し、多数のユーザ装置とともにユーザ認証のＭＰＣを行うサーバであることを想定している。
【０１４５】
実施形態においては、機器認証の公開鍵認証方式のＭＰＣを効率的に実行するために、次のアイデアを用いる。既知の多くの公開鍵認証方式における認証は、秘密鍵を利用する「秘密鍵利用演算」と「それ以外」の部分に分けられる。以下、「それ以外」の部分を「秘密鍵不用演算」と呼ぶ。例えば、乱数cに対するHash-then-RSA署名H(c)d mod Nを計算するタイプの認証では、h=H(c)の計算が「秘密鍵不用演算」に相当する。一方、hd mod Nの計算が「秘密鍵利用演算」に相当する。
【０１４６】
秘密鍵利用演算に関しては、効率的なＭＰＣが知られている。
【０１４７】
例えば、xが秘密鍵であり、y=gx mod pを計算したいものとする。また、gの位数をqとする。
【０１４８】
M台のユーザサイド補助装置があり、i番目のユーザサイド補助装置がxの分散シェアx[i]∈{0,...,q-1}を保持し、x=x[1]+...+x[M] mod qが成り立つ場合、yは以下のＭＰＣによって計算することができる。
i=1,...,Mに対し、i番目のユーザサイド補助装置はy[i]=hx[i] mod qを計算し、y[i]を他のユーザサイド補助装置に送信する。
各ユーザサイド補助装置は、積y=y[1]…y[M] mod qを計算する。
【０１４９】
このように、秘密鍵利用演算に関しては効率的なＭＰＣが知られている。したがって、ユーザ装置はユーザサイド補助装置とともに、こうした効率的なＭＰＣを実行することで効率的に秘密鍵利用演算を実行する。一方、秘密鍵不用演算では秘密鍵を使用しない。そこで、ユーザ装置はユーザサイド補助装置の助けを借りることなく、ユーザ装置単独で秘密鍵不用演算を実行する。
【０１５０】
［第１の実施形態の概要］
第１の実施形態では、さらに以下のアイデアに基づいて問題点を解決する。
【０１５１】
前述のとおり、実施形態のユーザサイド補助装置はサーバマシンであることが想定されている。すなわち、ユーザサイド補助装置は通常のマシンよりもはるかにセキュアである。しかも、サーバマシンでは、通常ログ監視などが行われている。したがって、サーバマシンが不正者に乗っ取られたとしても、不正者が行った不正をログ監視により特定することができる。
【０１５２】
実施形態においては、不正者がユーザサイド補助装置を乗っ取ることに成功したとしても、定められたＭＰＣのプロトコルを逸脱した場合、ログ監視により不正者の存在が発覚してしまう。かかる場合には、不正者はＭＰＣのプロトコルを逸脱しないものと考えられる。
【０１５３】
既存のＭＰＣであるＺＫＩＰ法およびＭＡＣ法では、ＭＰＣ装置がＭＰＣのプロトコルを逸脱することを防ぐため、ＺＫＩＰやＭＡＣを生成し、これらを他のＭＰＣ装置に送信し、受信したＭＰＣ装置がＺＫＩＰやＭＡＣの正当性を検証する。これらの一連の手続きが、ＭＰＣの計算効率および通信効率を悪化させている。
【０１５４】
しかし、実施形態の装置構成においては、上述のようにユーザサイド補助装置はＭＰＣのプロトコルを逸脱しない。したがって、ユーザサイド補助装置はＺＫＩＰやＭＡＣを生成する必要がなくなる。一方、ＰＣやスマートフォンであることが想定されているユーザ装置にはログ監視機能がない。すなわち、ユーザ装置が不正者に乗っ取られた場合、不正者に操られたユーザ装置はＭＰＣのプロトコルを逸脱するおそれがある。
【０１５５】
以上の理由により、実施形態のユーザ認証においては、ユーザ装置のみがＺＫＩＰまたはＭＡＣを生成し、ユーザサイド補助装置はＺＫＩＰおよびＭＡＣを生成しないものとする。これにより、本実施形態によると、既存発明と比較してＺＫＩＰまたはＭＡＣの生成、送受信および検証に要するコストを削減することができる。
【０１５６】
また、既存発明ではＺＫＩＰまたはＭＡＣの生成、送受信および検証がＭＰＣの計算効率および通信効率において支配的である。したがって、実施形態によると、既存発明と比較してはるかに効率の良い処理が実現可能となる。
【０１５７】
［第２の実施形態の概要］
第２の実施形態では、ＭＰＣとしてＧＣ法を利用する。ＧＣ法には、前述した２つの問題点がある。第２の実施形態では、これらの問題点を以下のように解決する。
【０１５８】
第１の問題として、ＧＣ法にはＧＣを作成する装置が不正を行った場合に安全性が損なわれる。前述のように実施形態において、ユーザサイド補助装置はＭＰＣのプロトコルを逸脱しないと考えられる。そこで、第２の実施形態ではユーザサイド補助装置がＧＣを作成する装置として振る舞うことにより、かかる問題を回避することができる。
【０１５９】
第２の問題として、ＧＣ法は依頼計算でありＭＰＣではないため、入力データの秘密を守ることができない。この問題を解決するため、実施形態では入力データ（実施形態では認証情報や検証情報が入力データとして取り扱われる）をユーザ装置とユーザサイド補助装置の間で分散シェアする。以下、ユーザ装置が保持する認証情報および検証情報の分散シェアをそれぞれs[0],v[0]とする。一方、ユーザサイド補助装置が保持する認証情報および検証情報の分散シェアをそれぞれs[1],v[1]とする。
【０１６０】
また、f(a,b)を以下の関数とする。すなわち、関数f(a,b)はa,bをそれぞれ認証情報および検証情報の分散シェアとみなし、分散シェアaと分散シェアs[1]とを用いて認証情報xを復元し、分散シェアbと分散シェアv[1]を用いて検証情報yを復元し、認証情報xと検証情報yを用いてユーザ認証を行い、認証結果を出力する。
【０１６１】
ＧＣを作成する装置であるユーザサイド補助装置は、分散シェアs[1],v[1]を用いることでf(a,b)の回路図を作成し、その回路図をＧＣ生成部に入力することでＧＣと鍵データKを作成し、ＧＣをユーザ装置に送る。また、ユーザ装置はＧＣ実行部にＧＣと分散シェアs[0],v[0]を入力してＧＣの出力Eを得て、出力Eをユーザサイド補助装置に送る。最後に、ユーザサイド補助装置は出力Eと鍵データKから出力ansを得る。
【０１６２】
上述の方法に従って認証を行う場合、ユーザ装置が入手可能なデータは認証情報および検証情報自身ではなく、それらのシェアs[0],v[0]とＧＣのみである。したがって、本実施形態によると、秘密の情報である認証情報と検証情報がユーザ装置に漏れてしまうという問題が解決される。
【０１６３】
なお、実施形態では、安全性を高めるために以下の３つの手法を盛り込むことが可能である。
【０１６４】
［安全性を高める手法（その１）］
まず、１つ目の手法について述べる。この手法の詳細は、第３の実施形態として記載する。実施形態において、ユーザ装置とユーザサイド補助装置は、ＭＰＣでユーザ認証を終えた後、機器認証サーバとの機器認証プロトコルにおける返答をＭＰＣで作成する。このとき、ユーザ認証を通った場合に限って機器認証が行われる。すなわち、実施形態において、前者のＭＰＣで「拒否」が出た場合には、後者のＭＰＣを実行する必要はない。しかし、前者のＭＰＣで「拒否」の場合に後者のＭＰＣを行わないものとすると、後者のＭＰＣを行なったか否かという1ビット分の情報をユーザサイド補助装置が取得してしまう。
【０１６５】
ユーザの認証情報の秘匿性を高めるためには、ユーザ認証でユーザが受理されたのか否かという情報も、ユーザサイド補助装置から隠すことが好ましい。そこで、ユーザ認証でユーザが受理されたのか否かに関する情報をユーザサイド補助装置から隠したいケースでは、以下のような動作を行う。すなわち、ユーザ認証が受理された場合、ユーザ装置は通常通り機器認証に関するＭＰＣを行う。一方、それ以外の場合、機器認証に関するＭＰＣを行っているかのように偽装するためのプロトコル（以下「機器認証シミュレートＭＰＣ」という）を実行する。これにより、機器認証に関するＭＰＣを行ったか否かに関する1ビット分の情報をユーザサイド補助装置に対して隠ぺいすることができる。
【０１６６】
なお、「機器認証シミュレートＭＰＣ」は、ユーザ認証でユーザが受理されたのか否かという情報をユーザサイド補助装置から隠したいケースに対処するためのオプションである。したがって、かかる情報をユーザサイド補助装置に隠す必要がないケースでは、「機器認証シミュレートＭＰＣ」を実行する必要はない。
【０１６７】
［安全性を高める手法（その２）］
次に、安全性を高めるための２つ目の手法について述べる。この手法の詳細は、第４および第５の実施形態として記載する。
【０１６８】
この手法について説明するために、まず実施形態に係る認証システムに対する攻撃について述べる。実施形態の認証システムでは、ユーザ装置を乗っ取った不正者は、（実際にはユーザからユーザ認証の要求がないにも関わらず）、ユーザからユーザ認証の要求があったかのように偽ることで、ユーザサイド補助装置にユーザ認証ＭＰＣを実行させることが可能である。具体的には、任意に選んだ認証情報Mを用いてユーザサイド補助装置とともにユーザ認証ＭＰＣを実行し、結果が受理であるか拒否であるかを知ることができる。これにより、不正者は任意に選択した認証情報Mがユーザの認証情報と一致するか否かを知ることができる。認証情報のエントロピーは小さいため、認証情報Mをいろいろな値に変えつつ全数検索することで、不正者はユーザの認証情報を特定できてしまう。
【０１６９】
しかし、この攻撃手法は、ユーザ装置とユーザサイド補助装置の間の通信を伴う。そこで、ユーザ装置側でユーザサイド補助装置との通信回数に制限を課すことにより、不正者による解析を逃れることができ、安全性が保証される。
【０１７０】
［安全性を高める手法（その３）］
次に、安全性を高めるための３つ目の手法について述べる。この手法の詳細は、第６ないし第８の実施形態として記載する。第６ないし第８の実施形態では、構成に若干の差がある。そこで、最初に第６の実施形態について説明する。
【０１７１】
この手法について説明する前に、まず背後にある動機について説明する。これまでに説明した実施形態では、ユーザ認証のＭＰＣをユーザ装置とユーザサイド補助装置が共同で行う。このため、ユーザ装置とユーザサイド補助装置の双方がユーザ認証のアルゴリズムを保持することを前提としている。しかしながら、ユーザ認証、特に生体認証のアルゴリズムは企業秘密として保護すべき対象であることが多い。また、ユーザ認証に付随してユーザ固有情報（顔、光彩、指紋などの情報）から認証情報や検証情報を得るために特徴量を抽出する認証情報導出や検証情報導出も企業秘密として保護すべき対象であることが多い。したがって、企業秘密を保護するために、不特定多数のユーザの手に渡るおそれがあるユーザ装置に対して、認証情報導出のアルゴリズム、検証情報導出のアルゴリズム、および、ユーザ認証アルゴリズムを隠したいケースが考えられる。
【０１７２】
これらのアルゴリズムをユーザ装置から隠すための方法として、次の方法が考えられる。すなわち、ユーザ装置はユーザ固有情報の取得とその秘密分散のみを実行する。一方、ユーザサイド補助装置の側で、ユーザ固有情報の分散シェアを使用してＭＰＣにより検証情報や認証情報の分散シェアを計算し、ＭＰＣでユーザ認証アルゴリズムを実行する方法が考えられる。
【０１７３】
しかし、かかる方法によると、不正者がＭＰＣ安全性条件以上のユーザサイド補助装置と結託した場合、検証情報や認証情報という非常に機微な情報が不正者の手に渡ってしまうという問題がある。
【０１７４】
そこで、第６の実施形態では、まずユーザ装置がユーザからユーザ固有情報を取得し、ユーザ固有情報を秘密分散することで分散シェアe[1],...,e[M]を得る。ここで、Mはユーザサイド補助装置の台数である。そしてi=1,...,Mに対し、分散シェアe[i]をさらに秘密分散することで、「ユーザ固有情報の分散シェアの分散シェア」c[i],d[i]を得て、c[1],...,c[M]をユーザ装置自身が保管し、d[i]をi番目のユーザサイド補助装置が保管する。
【０１７５】
このように、第６の実施形態ではユーザ固有情報の分散シェアをユーザ装置とユーザサイド補助装置で分けて保管している。したがって、不正者がＭＰＣ安全性条件以上のユーザサイド補助装置を乗っ取った場合にも安全性を担保することができる。
【０１７６】
一方、認証情報導出のアルゴリズム、検証情報導出のアルゴリズム、および、ユーザ認証アルゴリズムはユーザ装置には秘密にし、ユーザサイド補助装置のみに記憶させる。
【０１７７】
ユーザ認証の際には、ユーザ装置は、自身が保持する「ユーザ固有情報の分散シェアの分散シェア」c[i]をi番目のユーザサイド補助装置に送り、i番目のユーザサイド補助装置はc[i]とd[i]からe[i]を復元する。
【０１７８】
さらに、ユーザ装置はユーザから取得したユーザ固有情報を秘密分散して分散シェアf[1],...,f[M]を得て、i=1,...,Mに対しf[i]をi番目のユーザサイド補助装置に送る。i番目のユーザサイド補助装置は、e[i]、f[i]、認証情報導出のアルゴリズム、検証情報導出のアルゴリズム、および、ユーザ認証アルゴリズムを使用して、他のユーザサイド補助装置と相互通信しながらＭＰＣを行うことでユーザ認証を行う。
【０１７９】
なお、第６の実施形態では、ユーザ認証の際にユーザ装置が「ユーザ固有情報の分散シェアの分散シェア」c[i]をユーザサイド補助装置に送付する。したがって、ユーザ認証の際に不正者にユーザサイド補助装置を乗っ取られた場合、不正者はユーザサイド補助装置に保管されているd[i]とユーザ装置から受け取ったc[i]を用いることで、e[i]を復元できてしまう。よって、この段階でＭＰＣ安全性条件以上のユーザサイド補助装置が不正者に乗っ取られていた場合、e[i]からユーザ固有情報や認証情報、検証情報が復元されてしまい、これら機微な情報の秘匿性を保つことができない。
【０１８０】
そこで、第６の実施形態では、ユーザ認証が終わり次第、ユーザサイド補助装置が「ユーザ固有情報のシェアのシェア」c[i]を消去することを義務化する。これにより、かかる危険を可能な限り回避する。
【０１８１】
一方、第７の実施形態は、第６の実施形態と同一の動機に基き、第６の実施形態と類似した方法で問題を解決する。しかし、第７の実施形態では、事前登録段階でユーザ装置がユーザ固有情報を取得すると、これを秘密分散した上でユーザサイド補助装置に送り、ユーザサイド補助装置間のＭＰＣを行う。これにより、i=1,...,Mに対し、i番目のユーザサイド補助装置はユーザ検証情報の分散シェアv[i]を得る。そしてi番目のユーザサイド補助装置はv[i]を秘密分散することで「検証情報の分散シェアの分散シェア」u[i]とw[i]を作り、u[i]をユーザ装置に送り、w[i]を自身で保管する。
【０１８２】
ユーザ認証の際、ユーザ装置はu[i]をi番目のユーザサイド補助装置に送り、i番目のユーザサイド補助装置はu[i]とw[i]から検証情報の分散シェアv[i]を復元する。さらに、ユーザ装置はユーザから得た固有情報を秘密分散することでユーザ固有情報の分散シェアf[1],...,f[M]を取得し、i=1,...,Mに対し、f[i]をi番目のユーザサイド補助装置に送る。i番目のユーザサイド補助装置は、v[i]、f[i]、認証情報導出のアルゴリズム、検証情報導出のアルゴリズム、および、ユーザ認証アルゴリズムを用いて他のユーザサイド補助装置と相互通信しながらＭＰＣを行うことでユーザ認証を行う。
【０１８３】
また、第８の実施形態では、ユーザの認証情報およびそのシェアを計算する専用のサーバマシンである「ユーザ認証情報分散シェア生成装置」と、ユーザの検証情報およびそのシェアを計算する専用のサーバマシンである「ユーザ検証情報分散シェア生成装置」を用意する。これらの装置は、認証情報、検証情報、および、これらのシェアの計算をユーザ装置の代わりに実行する。
【０１８４】
かかる方法により、ユーザ装置は認証情報や検証情報の計算を行わなくなる。したがって、認証情報や検証情報の導出アルゴリズムをユーザ装置に明かす必要がなくなる。
【０１８５】
＜実施形態によってもたらされる効果の概要＞
本発明の各実施形態によると、上述の各課題が解決される。
【０１８６】
第１に、ＦＩＤＯ方式では認証情報および検証情報をユーザ装置に保管しているため、ユーザ装置にはこれらの情報を守るセキュア領域の存在が必須とされ、セキュア領域が不正者に侵された場合、ユーザの認証情報および検証情報という最高度に機微な情報が不正者の手に渡ってしまうという問題点がある。しかし、本発明の実施形態では、ユーザ装置には（認証情報や検証情報の分散シェアは保存されているが）認証情報や検証情報自身は保存されていない。したがって、仮にユーザ装置が不正者に完全に乗っ取られたとしても、不正者に認証情報や検証情報を奪われる危険はなく、セキュア領域も必要とされない。
【０１８７】
なお、実施形態においても、ユーザ装置のみならずユーザサイド補助装置の側もＭＰＣ条件を超えて不正者に乗っ取られた場合、認証情報および検証情報が不正者に漏えいする。しかしながら、前述のように実施形態では、ユーザサイド補助装置としてサーバマシンを想定している。したがって、ユーザ装置と併せてユーザサイド補助装置も不正者に乗っ取られるという危険性は非常に小さい。
【０１８８】
また、実施形態では、ユーザ認証が通ったか否かをユーザサイド補助装置に隠す方法も第３の実施形態として提示している。かかる方法を用いれば、不正者にユーザサイド補助装置が乗っ取られた場合における安全性を高めることができる。
【０１８９】
さらに、ＦＩＤＯ方式では、ユーザ認証のアルゴリズム、認証情報導出のアルゴリズム、および、検証情報導出のアルゴリズムもセキュア領域に保管することで、これらのアルゴリズムが漏えいしないよう保護している。しかしながら、このことは、セキュア領域が不正者に侵された場合にこれらのアルゴリズムが流出することを意味する。ユーザ認証の方法として生体認証を用いている場合、これらのアルゴリズムは企業秘密であることが多い。したがって、アルゴリズムが不正者に流出することに対する懸念は大きい。
【０１９０】
そこで、実施形態では、これらのアルゴリズムをユーザ装置に秘匿しつつユーザ認証を実行する方法を第６および第７の実施形態として提示している。
【０１９１】
第２に、既存技術の中には、認証サーバ装置やこれを補助する装置がＭＰＣ条件を超えて不正者に乗っ取られると、認証情報または検証情報という最高度に機微な情報が不正者に漏えいしてしまう問題を抱えているものがある。しかし、本願開示の実施形態では、ＦＩＤＯ方式と同様にユーザ認証と機器認証を分離している。したがって、認証サーバ装置には、認証情報や検証情報を教えないのみならず、これらの分散シェアすらも教えない。したがって、認証サーバ装置やこれを補助する装置がＭＰＣ条件を超えて不正者に乗っ取られた場合であっても、不正者は認証情報や検証情報を一切知ることはできない。
【０１９２】
第３に、既存方式の中には、認証サーバ装置がユーザ装置と通信することなく認証情報を全数探索できてしまう「サーバサイド・オフライン攻撃」に対して脆弱性を抱えているものがある。しかし、本願開示の実施形態では、前述のように認証サーバ装置やその補助装置には認証情報や検証情報はもちろんそれらの分散シェアすら教えない。すなわち、本願開示の実施形態では、かかる攻撃は不可能である。
【０１９３】
また、実施形態では、ユーザ装置が不正者に乗っ取られた場合であっても、ユーザ認証回数を制限することで認証情報や検証方法の漏洩を防ぐ方法を第４および第５の実施形態として提示している。
【０１９４】
第４に、実施形態では、ユーザ装置とサーバ装置の間で通信するデータをＭＰＣで作成する。このとき、データの作り方については、実施形態とＦＩＤＯ方式などの既存の認証方式との間で相違する。しかしながら、通信するデータ自身は既存の認証方式のものと全く同一である。したがって、本願開示の実施形態によると、既存の認証方式の通信標準をそのまま利用することができる。すなわち、本願開示の実施形態によると、既存の認証方式の通信標準を満たすすべてのサーバ装置と通信可能であり、既存方式のような通信プロトコルの互換性の問題は生じない。
【０１９５】
＜実施形態１＞
次に、第１の実施形態に係る認証システムについて図面を参照して説明する。
【０１９６】
［構成］
図４を参照して、本実施形態の認証システムの構成を説明する。
【０１９７】
本実施形態の認証システムは、ユーザ装置41、ユーザサイド補助装置43、および、機器認証サーバ装置42を備えている。ユーザ44は、ユーザ装置41を保有するユーザである。
【０１９８】
ユーザ装置41はユーザ44が保有する装置であり、例えばスマートフォン、タブレット、ＰＣ（Personal Computer）などが想定される。
【０１９９】
ユーザサイド補助装置43および機器認証サーバ装置42は、何らかのサーバマシンであることが想定される。
【０２００】
ユーザ装置41、ユーザサイド補助装置43および機器認証サーバ装置42は、「計算部」、「記憶部」および「通信部」を備えている。計算部はＣＰＵ（Central Processing Unit）などのプロセッサである。記憶部は、メモリやハードディスクなどの記憶媒体である。通信部は、インターネットなどを介して装置同士が相互に通信することを可能にするための部分である。
【０２０１】
ユーザ装置41は、さらにユーザ情報取得部411および通知部415を備えている。ユーザ情報取得部411は、認証に使う情報をユーザ44から取得する。通知部415は、認証が受理されたのか拒否されたのかをユーザ44に伝える。通知部415は、例えばＰＣやスマートフォンのディスプレイである。
【０２０２】
本実施形態の認証システムでは、１人または複数のユーザ44が存在する。各ユーザ44は、１台以上のユーザ装置41を保有する。図４は、そのうちの１人のユーザ44と当該ユーザ44が保有する１台のユーザ装置41のみを示す。
【０２０３】
機器認証サーバ装置42は、ユーザ装置41を認証するサーバである。機器認証サーバ装置42は、例えばユーザ44がユーザ装置41を使用して何らかのウェブサービスを利用する際の認証に用いられる。本実施形態の認証システムにおいて、機器認証サーバ装置42は一般には複数台存在する。図４は、そのうちの１台のみを示す。
【０２０４】
機器認証サーバ装置42は、一般には複数台のユーザ装置41と通信する。機器認証サーバ装置42は、各装置の公開鍵を保存するためのデータベースである公開鍵データベース4221を記憶部422に保持する。なお、記憶部422は公開鍵データベース4221以外の領域も有し、そこに必要な情報を適時保存することもできる。
【０２０５】
ユーザサイド補助装置43は、認証においてユーザ装置41を補助する。図４にはM台のユーザサイド補助装置43を示す。これらのユーザサイド補助装置43は認証の際、ユーザ装置41や他のユーザサイド補助装置43と通信しながら、認証を遂行する。
【０２０６】
各ユーザサイド補助装置43は、一般に複数の認証を補助し、各認証において（認証ごとに異なるまたは同一の）ユーザ装置41と通信をする。
【０２０７】
以下、1台目,...,M台目のユーザサイド補助装置43をユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]と表記する。
【０２０８】
同様に、ユーザサイド補助装置43に含まれるユニットについても、末尾に「[i]」を付すことでi番目のユーザサイド補助装置43のものであることを明示する。例えば、ユーザサイド補助装置43[3]の計算部431を計算部431[3]のように表記する。
【０２０９】
各ユーザサイド補助装置43は、ユーザ44の検証情報の分散シェアや、ユーザ44の保有するユーザ装置41の秘密鍵の分散シェアを保有するためのデータベースである分散シェアデータベース4321を記憶部432に保持する。なお、記憶部432は分散シェアデータベース4321以外の領域も有し、そこに必要な情報を適時保存することもできる。
【０２１０】
［本実施形態における認証］
本実施形態では、認証として、ユーザ44を認証するための「ユーザ認証」とユーザ44が持っている装置であるユーザ装置41を認証する「機器認証」の２種類の認証がある。本実施形態において、ユーザ認証とはユーザ44がユーザ装置41に対して自身が事前登録されたユーザ44と同一であることを証明する行為を指す。一方、機器認証とは、ユーザ装置41が機器認証サーバ装置42に対して、自身が事前登録された装置と同一であることを証明することをいう。
【０２１１】
ユーザ44は、ユーザ装置41を利用してユーザ認証を行う。ユーザ装置41はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]と通信することでユーザ認証を行う。また、ユーザ認証が受理された場合、ユーザ装置41は機器認証サーバ装置42と通信することで機器認証を行う。この際、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]はユーザ装置41と通信することで、機器認証を手助けする。
【０２１２】
機器認証において、ユーザ装置41と機器認証サーバ装置42は事前に定められた何らかの通信プロトコル（例えばＦＩＤＯが提案しているＵＡＦ標準）に従って通信すべきデータを決定する。この通信プロトコルに従って通信するためのユニット（ないし手段）が、通信部414のユーザ装置フロントエンド4142と通信部423のサーバ装置フロントエンド4231である。
【０２１３】
上述したようにユーザ装置フロントエンド4142は、機器認証の通信プロトコルに従って機器認証サーバ装置42と通信するためのものである。一方、これとは別にユーザ装置41の通信部414は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]と通信するための補助通信部4141を有する。同様に、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の通信部433はユーザ装置41と通信するための補助通信部4331を有する。
【０２１４】
補助通信部4141および補助通信部4331は、認証情報や検証情報のシェアを送出するなど、ユーザ装置41とユーザサイド補助装置43の間の様々な通信を行う。
【０２１５】
ユーザ認証においては、ユーザ44を識別するための情報（以下「ユーザ固有情報」という）として、例えば以下の３種類のものが用いられる。
ユーザの記憶（暗証番号、パスワード、パスフレーズなど）
ユーザ生体情報（顔、指紋、光彩など）
ユーザの所有物（セキュリティトークン、ＩＣ（Integrated Circuit）カードなど）
【０２１６】
ユーザ装置41は、これらのユーザ固有情報の１つ以上を読み取るための手段を有するものとする。ユーザ装置41のユーザ情報取得部411は、読み取る認証情報ごとにその情報を読み取るための取得部4111を有する。
【０２１７】
取得部4111として、例えば以下のものが考えられる。
暗証番号、パスワード、パスフレーズなどを読み取るためのキーボード
顔、指紋、光彩などを読み取るためのカメラ
セキュリティトークンやＩＣカード内の情報を読み取るための読み取り機
【０２１８】
ユーザ装置41は、取得部4111が得たユーザ固有情報を加工して「認証情報」を得る認証情報導出部41211と、ユーザ固有情報を加工して「検証情報」を得る検証情報導出部41221を有する。
【０２１９】
「認証情報」とは、ユーザ認証においてユーザの当人性を示すための情報である。一方、「検証情報」とは、認証情報と比較するために事前に登録されている情報である。
【０２２０】
認証情報導出部41211および検証情報導出部41221の具体例をいくつか示す。
【０２２１】
例えば、認証情報および検証情報が生体情報である場合、取得部4111は画像データとして生体情報を取得する。また、認証情報導出部41211と検証情報導出部41221は、画像データから生体情報の特徴量を抽出し、抽出された特徴量を認証情報および検証情報として用いる。
【０２２２】
一方、認証情報がパスワードPである場合、安全性の観点から、検証情報としてパスワードPそのものではなくPのハッシュ値Hash(P)を使うことが考えられる。この場合、検証情報導出部41221は取得部4111が取得したパスワードPをハッシュ化する操作に対応する。一方、認証情報導出部41211は、取得部4111が取得したパスワードPをそのまま使用する。このとき、認証情報導出部41211は「取得部4111が得た情報Pをそのまま出力する」手段となる。
【０２２３】
図４に例示した構成によると、機器認証サーバ装置42の計算部421に設けられたユーザ認証方法選択部4211が、複数のユーザ認証の方法のうちのいずれを用いるのかを決定する。ただし、ユーザ認証方法選択部4211はユーザ装置41に実装されていてもよい。
【０２２４】
機器認証においては、ユーザ装置41が作成した（何らかの公開鍵認証方式における）公開鍵・秘密鍵ペアを利用して認証を行う。図４は、機器認証に用いられる公開鍵認証方式が事前に１通りに決定していることを前提に記載した。しかし、ユーザ認証の場合と同様に、複数の公開鍵認証方式から１つの方式を選ぶように拡張することも可能である。
【０２２５】
［予め装置に登録されているデータ］
ユーザ装置41は、事前に以下のデータを受け付けて記憶部413に保持するものとする。
ユーザサイド補助装置43の台数M
ユーザ認証の検証プロトコル（複数のユーザ認証が提供されている場合、それらすべての認証プロトコル）
機器認証の認証プロトコル
【０２２６】
ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]は、事前に以下のデータを受け付けて記憶部432に保持するものとする。
ユーザサイド補助装置43の台数M
ユーザ認証の検証プロトコル（複数のユーザ認証が提供されている場合、それらすべての認証プロトコル）
【０２２７】
機器認証サーバ装置42は、事前に以下のデータを受け付けて記憶部422に保持するものとする。
機器認証の検証プロトコル
【０２２８】
また、ユーザ認証や機器認証で行うＭＰＣが事前計算を必要とするものである場合、ユーザ装置41および機器認証サーバ装置42は、それぞれ記憶部413および記憶部432にＭＰＣの事前計算データを保管しておく。
【０２２９】
［全体の流れ］
本実施形態の認証システムの各部の詳細を述べる前に、全体の流れを概括する。
【０２３０】
本実施形態では、認証に先立って以下の事前準備を行う。
ユーザ認証事前準備
ユーザ認証で必要となるデータを事前準備する。本実施形態では、検証情報を計算しておく。
機器認証事前準備
機器認証で必要となるデータを事前準備する。本実施形態では、ユーザ装置の公開鍵および秘密鍵の生成を行う。
【０２３１】
認証において、以下の２つの動作を行う
ユーザ認証
ユーザ装置41がユーザサイド補助装置43の助けを借りながらユーザ44を認証する。
機器認証
ユーザ装置41がユーザサイド補助装置43の助けを借りながら機器認証サーバ装置42から認証を受ける。
【０２３２】
［ユーザ認証事前準備］
本実施形態では、ユーザ認証事前準備においてユーザ44が検証情報を事前登録する。検証情報を事前登録する方法として、様々な方法を用いることができる。図４は、ユーザ装置41の取得部4111を利用して検証情報を事前登録する場合を示す。しかし、例えば企業が新入社員全員を認証システムに一括登録するようなケースでは、検証情報を登録するための専用マシンを用意し、これを利用して検証部の事前登録を行ってもよい。以降、図４に記載した装置構成における検証情報の事前登録を説明する。
【０２３３】
ユーザ認証を複数用意している場合、すべての認証に対して以下の動作を行う。
【０２３４】
図５に従って検証情報の登録を説明する。
【０２３５】
ステップ51：まず、ユーザ装置41は以下を実行する。
ステップ511：取得部4111は、ユーザ44からユーザ固有情報を取得する。
ステップ512：検証情報導出部41221はユーザ固有情報を入力とし、検証情報を出力する。
ステップ513：検証情報分散部41222は検証情報とユーザサイド補助装置43の台数Mとを入力とし、検証情報の分散シェアv[0],v[1],...,v[M]を出力する。
ステップ514：記憶部413は分散シェアv[0]を保管する。
ステップ515：通信部414の補助通信部4141は、分散シェアv[1]をユーザサイド補助装置43[1]に送信し,...,分散シェアv[M]をユーザサイド補助装置43[M]に送信する。
ステップ516：ユーザ装置41は、ユーザ固有情報、検証情報および分散シェアv[1],...,v[M]を消去する。
【０２３６】
ステップ52：次に、i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
ステップ521：通信部433[i]の補助通信部4331[i]は、ユーザ装置41が送信した分散シェアv[i]を受信する。
ステップ522：分散シェアデータベース4321[i]は、分散シェアv[i]を保持する。
【０２３７】
［機器認証事前準備］
本実施形態では、機器認証の事前準備として、公開鍵・秘密鍵ペアの生成と登録を行う。
【０２３８】
図６に従って、公開鍵・秘密鍵ペアの生成と登録を説明する。
【０２３９】
ステップ61：ユーザ装置41は、以下を実行する。
ステップ611：鍵ペア生成部4125は、ユーザ装置41の公開鍵pkと秘密鍵skを生成する。
ステップ612：秘密鍵分散部4126は生成された秘密鍵skを入力とし、秘密鍵の分散シェアk[0],...,k[M]を出力する。
ステップ613：記憶部413は秘密鍵の分散シェアk[0]と公開鍵pkをに保管する。
ステップ614：i=1,...,Mに対し、通信部414の補助通信部4141は秘密鍵の分散シェアk[i]と公開鍵pkをユーザサイド補助装置43[1]に送信する。
ステップ615：ユーザ装置41は、秘密鍵skおよび秘密鍵の分散シェアk[1],...,k[M]を消去する。
ステップ616：ユーザ装置フロントエンド4142は、公開鍵pkを機器認証サーバ装置42に送信する。
【０２４０】
ステップ62：i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
ステップ621：通信部433[i]の補助通信部4331[i]は、秘密鍵の分散シェアk[i]と公開鍵pkを受信する。
ステップ622：分散シェアデータベース4321[i]は、秘密鍵の分散シェアk[i]と公開鍵pkを保持する。
【０２４１】
ステップ63：機器認証サーバ装置42は、以下を実行する。
ステップ631：サーバ装置フロントエンド4231は、ユーザ装置41の公開鍵pkを受信する。
ステップ632：公開鍵データベース4221は、受信した公開鍵pkを保持する。
【０２４２】
［ユーザ認証］
図７に従って、ユーザ認証を説明する。
【０２４３】
ステップ71：ユーザ装置41は、以下を実行する
ステップ711：取得部4111は、ユーザ44からユーザ固有情報を取得する。
ステップ712：認証情報導出部41211はユーザ固有情報を入力とし、認証情報を出力する。
ステップ713：認証情報分散部41212は認証情報とユーザサイド補助装置43の台数Mとを入力とし、認証情報の分散シェアs[0],s[1],...,s[M]を出力する。
ステップ714：i=1,...,Mに対し、通信部414の補助通信部4141は認証情報の分散シェアs[i]をユーザサイド補助装置43[i]に送信する。
ステップ715：ユーザ装置41は、ユーザ固有情報と認証情報の分散シェアs[1],...,s[M]を消去する。
ステップ716：ユーザ装置ユーザ認証ＭＰＣ部4123は、記憶部413からユーザ44の検証情報のシェアv[0]とユーザ認証の検証プロトコルと事前計算データp[0]（もしあれば）を読み込む。
【０２４４】
ステップ72：i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
ステップ721：通信部433[i]の補助通信部4331[i]は、認証情報の分散シェアs[i]を受信する。
ステップ722：ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、分散シェアデータベース4321[i]から、ユーザ装置41を保有するユーザ44の検証情報のシェアv[i]とユーザ認証の検証プロトコルを読み込み、記憶部432[i]から事前計算データp[i]（もしあれば）を読み込む。
【０２４５】
ステップ73：ユーザ装置41は、認証情報の分散シェアs[0]と検証情報の分散シェアv[0]と事前計算データp[0]（もしあれば）とユーザ認証の検証プロトコルをユーザ装置ユーザ認証ＭＰＣ部4123に入力する。また、i=1,...,Mに対し、ユーザサイド補助装置43[i]は認証情報の分散シェアs[i]と検証情報の分散シェアv[i]と事前計算データp[i]（もしあれば）とユーザ認証の検証プロトコルを、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]に入力する。これにより「ユーザ認証ＭＰＣ」を実行する。実行結果として、ユーザ装置41はユーザ認証結果のシェアa[0]を得る。また、i=1,...Mに対し、ユーザサイド補助装置43[i]はユーザ認証結果のシェアa[i]を得る。なお「ユーザ認証ＭＰＣ」の詳細については後述する。
【０２４６】
ステップ74：i=1,...,Mに対し、ユーザサイド補助装置43[i]の補助通信部4331[i]はユーザ認証結果のシェアa[i]をユーザ装置41に送る。
【０２４７】
ステップ75：ユーザ装置41は、以下を実行する。
ステップ751：補助通信部4141は、ユーザ認証結果のシェアa[1],...,a[M]を受信する。
ステップ752：ユーザ認証結果復元部4124はa[0],...,a[M]を入力とし、ユーザ認証の結果accを出力する。
ステップ753：ユーザ認証結果復元部4124は、ユーザ認証の結果accが「受理」か「拒否」かを判定する。
ステップ754：ユーザ認証の結果accが「受理」の場合、ユーザ装置41はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の助けを借りながら機器認証サーバ装置42から機器認証を受ける。なお「機器認証」の詳細については後述する。
ステップ755：ユーザ認証の結果が「拒否」の場合、ユーザ装置41は認証が拒否された旨を、通知部415を経由してユーザ44に伝えて終了する。
【０２４８】
［ユーザ認証ＭＰＣ］
ＺＫＩＰ法またはＭＡＣ法に基づいてユーザ認証ＭＰＣを実現する方法を述べる。
【０２４９】
図７に記載したユーザ認証のステップ73で行うユーザ認証ＭＰＣの詳細を述べる。ユーザ認証ＭＰＣでは、ユーザ装置41はユーザ装置ユーザ認証ＭＰＣ部4123を用いる。一方、ユーザサイド補助装置43はユーザサイド補助装置ユーザ認証ＭＰＣ部4311を用いる。
【０２５０】
まず、ユーザ装置ユーザ認証ＭＰＣ部4123およびユーザサイド補助装置ユーザ認証ＭＰＣ部4311の構成を説明する。
【０２５１】
図８は、ユーザ装置ユーザ認証ＭＰＣ部4123の構成を例示するブロック図である。
【０２５２】
図９は、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311の構成を例示するブロック図である。
【０２５３】
図８および図９を参照すると、ユーザ装置ユーザ認証ＭＰＣ部4123は正当性証明生成部84を有し、一方ユーザサイド補助装置ユーザ認証ＭＰＣ部4311は正当性証明検証部94を有する点で相違する。
【０２５４】
既存のＺＫＩＰ法およびＭＡＣ法においては、いずれも、ＭＰＣの各ステップを実行するたびに、各ＭＰＣ装置がそのステップの実行を正しく行ったことを証明する正当性証明を生成するステップと、他のＭＰＣ装置がそのステップの実行を正しく行ったことを確認するために他のＭＰＣ装置が生成した正当性証明を検証するステップがある。
【０２５５】
しかし、本実施形態の場合、［第１の実施形態の概要］で述べた理由により、ユーザ装置41のみに正当性証明を作成する正当性証明生成部84を設け、ユーザサイド補助装置43にはユーザ装置41の正当性証明を検証する正当性証明検証部94のみを設ける。
【０２５６】
図１０に従ってユーザ認証ＭＰＣを説明する。
【０２５７】
ステップ101：ユーザ装置41において、ユーザ装置ユーザ認証ＭＰＣ部4123の入力部81は認証情報の分散シェアs[0]と検証情報の分散シェアv[0]とユーザ認証の検証プロトコルを入力とし、認証情報の分散シェアs[0]と検証情報の分散シェアv[0]を一時記憶部82に保管する。i=1,...Mに対し、ユーザサイド補助装置43[i]におけるユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]の入力部91[i]は、認証情報の分散シェアs[i]と検証情報の分散シェアv[i]とユーザ認証の検証プロトコルを入力とし、一時記憶部92[i]に保管する。
【０２５８】
ステップ102：ユーザ認証の検証プロトコルの各素子Rに対し、素子番号が小さいものから順番に以下を実行する。
ステップ1021：素子Rの入力端子をc[1],...,c[N]とする。ここで、Nは素子Rの入力端子の個数である。ユーザ装置41は素子Rの入力端子c[1],...,c[N]に対応するシェアt[0,1],...,t[0,N]と事前計算データq[0,R]（もしあれば）を一時記憶部82から読み込み、素子Rとシェアt[0,1],...,t[0,N]をユーザ認証ＭＰＣ実行部83に入力する。i=1,...,Mに対し、ユーザサイド補助装置43[i]は素子Rの入力端子c[1],...,c[N]に対応するシェアt[i,1],...,t[i,N]を一時記憶部92[i]から読み込み、素子Rとシェアt[i,1],...,t[i,N]と事前計算データq[i,R]（もしあれば）をユーザ認証ＭＰＣ実行部93[i]に入力する。
ステップ1022：ユーザ認証ＭＰＣ実行部83およびユーザ認証ＭＰＣ実行部93[1],...,ユーザ認証ＭＰＣ実行部93[M]は、通信部414、通信部433[1],..,通信部433[M]を用いて通信し、素子Rに関するＭＰＣを実行する。
ステップ1023：ユーザ認証ＭＰＣ実行部83は、素子Rの出力端子のシェアu[0]をユーザ装置41に返す。i=1,...,Mに対し、ユーザ認証ＭＰＣ実行部93[i]は素子Rの出力端子のシェアu[i]をユーザサイド補助装置43[i]に返す。
ステップ1024：ユーザ装置41は、素子R、シェアt[0,1],...,t[0,N]、ユーザ認証ＭＰＣ実行部83の実行に利用した乱数（もしあれば）および事前計算データq[0,R]（もしあれば）を正当性証明生成部84に入力する。i=1,...,Mに対し、ユーザ装置41およびユーザサイド補助装置43[i]は、それぞれ、通信部414および通信部433[i]を用いて通信しながらは正当性証明生成部84および正当性証明検証部94の処理を実行する。
【０２５９】
ステップ103：実行結果として、ユーザ装置41はユーザ認証結果のシェアa[0]を得る。i=1,...,Mに対し、ユーザサイド補助装置43[i]はユーザ認証結果のシェアa[i]を得る。
【０２６０】
ステップ104：ユーザ装置41は、ユーザ認証結果のシェアa[0]を出力する。i=1,...,Mに対し、ユーザサイド補助装置43[i]はユーザ認証結果のシェアa[i]を出力する。
【０２６１】
［機器認証］
次に、本実施形態の機器認証の詳細について説明する。本実施形態の機器認証では、ユーザ装置41と機器認証サーバ装置42がＦＩＤＯのＵＡＦ標準で標準化されている認証などの何らかの公開鍵認証を実行する。既知の公開鍵認証では、ユーザ装置41は自身の秘密鍵を使用することで認証を行う。一方、機器認証サーバ装置42はユーザ装置41の公開鍵を使用することでユーザ装置41の認証を検証する。
【０２６２】
しかし、本実施形態の場合、ユーザ装置41は自身の秘密鍵を保有しておらず、ユーザ装置41の秘密鍵はユーザ装置41、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]で分散シェアされている。したがって、既知の公開鍵認証をそのまま本実施形態で使用することはできない。
【０２６３】
そこで、本実施形態では、公開鍵認証においてユーザ装置41が秘密鍵を使用して計算するデータは、ユーザ装置41、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]のＭＰＣで計算するように変更する。
【０２６４】
なお、以上で説明したように、本実施形態では、ユーザ装置41が必要データを計算する方法は通常の公開鍵認証とは異なる。しかし、ユーザ装置41と機器認証サーバ装置42の間でやり取りされる通信データは、通常の公開鍵認証と同一である。また、機器認証サーバ装置42の側で行う計算も、通常の公開鍵認証と同一である。したがって、本実施形態では、既存の認証方式の通信標準をそのまま利用することができる。すなわち、本実施形態によると、既存の認証方式の通信標準を満たしているすべてのサーバ装置と通信可能である。これにより、本実施形態では、既存技術のような通信プロトコルの互換性の問題は生じない。
【０２６５】
本実施形態における公開鍵認証に基づく機器認証は、以下の仮定を満たすものとする。
機器認証は「秘密鍵利用演算部」（ないし、ユニット名の一部に「秘密鍵利用演算」を含むユニット、以下同様）というサブルーチン（ないしユニット）を用いて行われ、秘密鍵は「秘密鍵利用演算部」でのみ用いられる。
【０２６６】
機器認証を行うサブルーチンのうちの「秘密鍵利用演算部」以外の部分を「秘密鍵不用演算部」と呼ぶ。
【０２６７】
本実施形態では、認証手段のうちの秘密鍵利用演算部の部分のみをユーザ装置41と機器認証サーバ装置42の間でのＭＰＣで実行する。一方、秘密鍵不用演算部の部分はユーザ装置41が単独で実行する。
【０２６８】
図１１は、ユーザ装置機器認証ＭＰＣ部4127の構成を例示するブロック図である。
【０２６９】
図１２は、ユーザサイド補助装置機器認証ＭＰＣ部4312の構成を例示するブロック図である。
【０２７０】
図１３は、機器認証の動作を例示するフロー図である。
【０２７１】
ステップ131：各装置は、以下のようにデータの入力を行う。
ステップ1311：ユーザ装置41は秘密鍵のシェアk[0]とユーザ装置41の公開鍵pkを記憶部413から読み込み、ユーザ装置機器認証ＭＰＣ部4127の入力部111に入力する。
ステップ1312：i=1,...,Mに対し、ユーザサイド補助装置43[i]は秘密鍵のシェアk[i]とユーザ装置41の公開鍵pkを分散シェアデータベース4321から読み込み、ユーザサイド補助装置機器認証ＭＰＣ部4312の入力部121に入力する。
ステップ1313：機器認証サーバ装置42はユーザ装置41の公開鍵pkを公開鍵データベース4221から読み込み、機器認証検証部4212に入力する。
【０２７２】
ステップ132：機器認証サーバ装置42およびユーザ装置41は、以下のようにデータの送受信を行う。
ステップ1321：機器認証サーバ装置42は機器認証検証部4212を実行し、機器認証検証部4212がユーザ装置41へのデータの送信要求を出した場合、サーバ装置フロントエンド4231を用いてユーザ装置41にデータを送信する。
ステップ1322：ユーザ装置41はユーザ装置フロントエンド4142を使って機器認証サーバ装置42から送られてきたデータを受信し、受信したデータを秘密鍵不用演算部115に入力し、以下を実行する。
ステップ13221：秘密鍵不用演算部115がサブルーチンとして秘密鍵利用演算を要求するたびに、秘密鍵不用演算部115がサブルーチンに投げたデータを秘密鍵利用演算ＭＰＣ実行部113に入力し、以下を実行する。
ステップ132211：秘密鍵利用演算ＭＰＣ実行部113はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の秘密鍵利用演算ＭＰＣ実行部122[1],...,秘密鍵利用演算ＭＰＣ実行部122[M]と相互通信してＭＰＣを実行し、必要データを計算し、計算されたデータを秘密鍵不用演算部115に返答する。
ステップ132212：i=1,...,Mに対し、ユーザ装置41およびユーザサイド補助装置43[i]は、それぞれ補助通信部4141および補助通信部4331[i]を用いて通信しながら、秘密鍵利用演算正当性証明生成部114および秘密鍵利用演算正当性証明検証部123[i]の処理を実行する。これにより、ステップ132211で行ったＭＰＣの正当性証明とその検証を行う。
ステップ13222：秘密鍵不用演算部115が機器認証サーバ装置42へのデータ送信要求を出した場合、ユーザ装置41はユーザ装置フロントエンド4142を用いて機器認証サーバ装置42にデータを送信する。
ステップ1323：最終的に、機器認証サーバ装置42の機器認証検証部4212が「受理」または「拒否」を意味するデータを出力した場合、機器認証サーバ装置42は機器認証検証部4212を終了する。
【０２７３】
本実施形態に係る認証システムでは、ユーザサイド補助装置とユーザ装置との間で検証情報および認証情報の分散シェアを用いてマルチパーティ計算を行う。したがって、ユーザ装置は検証情報および認証情報をそのまま保持する必要がなく、ＦＩＤＯ方式のようにユーザ装置内にセキュアな領域の存在を仮定する必要がなくなる。また、本実施形態では、ユーザ装置と機器認証サーバ装置の間でやり取りされるデータは既存のＦＩＤＯ方式と同様である。したがって、本実施形態によれば、サーバサイドＭＰＣ方式および暗号化通信方式のように独自仕様の通信フロントエンドを設けることなく、既存の機器認証サーバとの通信フロントエンドを利用することができる。さらに、本実施形態によると、ＦＩＤＯ方式と同様にユーザ認証および機器認証の双方の認証が可能となる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。したがって、本実施形態によると、ＦＩＤＯ方式、サーバサイドＭＰＣ方式および暗号化通信方式などの既存方式が抱える上述の問題を解消することが可能となる。
【０２７４】
また、本実施形態では、ユーザサイド補助装置としてサーバマシンを採用することで、ユーザサイド補助装置がＭＰＣのプロトコルを逸脱することを防ぐ。このとき、ユーザ装置のみが正当性証明を作成し、サーバサイド補助装置による正当性証明の生成を省略することができる。したがって、本実施形態によると、既存のＺＫＩＰ法およびＭＡＣ法と比較して計算効率および通信効率を大幅に改善することが可能となる。
【０２７５】
＜実施形態２＞
次に、第２の実施形態に係る認証システムについて図面を参照して説明する。本実施形態では、ガーブルドサーキット（ＧＣ：Garbled Circuit）法に基づくユーザ認証ＭＰＣを採用する。
【０２７６】
本実施形態の認証システムの構成は、第１の実施形態の構成（図４）と同様である。
【０２７７】
本実施形態のユーザ認証を示すフロー図は、第１の実施形態（図７）と同様である。ただし、本実施形態では、ステップ73のユーザ認証ＭＰＣが以下に説明するものに置換される。
【０２７８】
［ユーザ認証ＭＰＣ］
ＧＣ法に基づくユーザ認証ＭＰＣについて説明する。
【０２７９】
図７に示した認証手続きのステップ73で行うユーザ認証ＭＰＣの詳細について説明する。ユーザ認証ＭＰＣでは、ユーザ装置41はユーザ装置ユーザ認証ＭＰＣ部4123の処理を実行する。一方、ユーザサイド補助装置43はユーザサイド補助装置ユーザ認証ＭＰＣ部4311の処理を実行する。
【０２８０】
まず、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311およびユーザ装置ユーザ認証ＭＰＣ部4123の構成を説明する。
【０２８１】
図１４は、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311の構成を例示するブロック図である。
【０２８２】
なお、ここで述べるユーザ認証では、ユーザサイド補助装置43は1台のみである。図１４の装置構成は、この１台のみのユーザサイド補助装置43[1]について説明するためのものである。
【０２８３】
図１５は、ユーザ装置ユーザ認証ＭＰＣ部4123の構成を例示するブロック図である。
【０２８４】
図１６に従って、本実施形態におけるユーザ認証ＭＰＣを説明する。
【０２８５】
ステップ161：ユーザサイド補助装置43[1]は、認証情報の分散シェアs[1]と検証情報の分散シェアv[1]とユーザ認証の検証プロトコルをユーザサイド補助装置ユーザ認証ＭＰＣ部4311に入力する。ユーザサイド補助装置ユーザ認証ＭＰＣ部4311は、これらのデータを入力部141から受け取り、関数fの回路図をＧＣ生成部142に入力することでＧＣと鍵データKを作成する。ここで、関数f(a,b)は「a,bをそれぞれ認証情報、検証情報の分散シェアとみなし、aとs[1]とを使って認証情報xを復元し、bとv[1]を使って検証情報yを復元し、xとyを使ってユーザ認証を行い、認証結果を出力する」関数とする。ユーザサイド補助装置43[1]は、通知部433[1]を用いてユーザ装置41にＧＣを送信する。
【０２８６】
ステップ162：ユーザ装置41のユーザ装置ユーザ認証ＭＰＣ部4123は通信部414を使ってＧＣを受け取り、ＧＣを使用してＧＣ実行部152の処理を実行する。ユーザ装置41は、ＧＣ実行部152の出力Eを取得し、通信部414を用いて出力Eをユーザサイド補助装置43[1]に送る。
【０２８７】
ステップ163：ユーザサイド補助装置43[1]のユーザサイド補助装置ユーザ認証ＭＰＣ部4311は通知部415[1]を用いて出力Eを受信し、出力Eと鍵データKをＧＣ出力生成部143に入力し、その出力としてユーザ認証の結果が「受理」または「拒否」であることを意味するデータansを得る。
【０２８８】
ステップ164：ユーザ装置41は出力部144から何も出力しない。すなわち、ＭＰＣの出力のシェアs[0]は空文字列である。ユーザサイド補助装置43[1]はＭＰＣの出力のシェアs[1]としてansを出力する。次に、ユーザ装置41はユーザサイド補助装置43[1]からs[1]=ansを受信し、ユーザ認証結果復元部4124はansを出力する。
【０２８９】
上述したＭＰＣでは、第１の実施形態と同様にステップ713で行う認証情報分散部41212で認証情報が秘密分散され、結果として分散シェアs[0],s[1]が生成されることを前提として説明した。しかし、ステップ713において認証情報分散部41212を実行せず、s[0]を認証情報自身として、s[1]を空文字列とした場合にも、本実施形態は正しく動作し、安全性も担保することができる。
【０２９０】
本実施形態に係る認証システムにおいても、第１の実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、ユーザ装置は認証情報および検証情報そのものではなく、これらのシェアとＧＣしか入手できない。したがって、本実施形態によると、ユーザ装置に対して認証情報および検証情報が漏れるというＧＣ法の問題点を解消することができる。
【０２９１】
＜実施形態３＞
次に、第３の実施形態に係る認証システムについて図面を参照して説明する。
【０２９２】
第１および第２の実施形態においては、ユーザ認証が受理された場合、ユーザ装置41はユーザサイド補助装置43の助けを借りながら機器認証を行う。一方、ユーザ認証が拒否された場合、機器認証は行わず、ユーザ認証が拒否された旨をユーザ44に通知して終了する。このとき、ユーザサイド補助装置43は、ユーザ認証が受理されたのか拒否されたのかという1ビット分の情報を取得してしまう。
【０２９３】
本実施形態では、ユーザ認証が受理されたのか拒否されたのかという情報をユーザサイド補助装置43に対して隠す方法を説明する。
【０２９４】
本実施形態の認証システムの構成は、第１の実施形態（図４）と同様である。ただし、本実施形態では、ユーザ装置41はユーザ認証結果復元部4124の（「許否」の）後段にさらに機器認証シミュレートＭＰＣ部17を有する。
【０２９５】
また、本実施形態の動作は、ユーザ認証を示すフロー図（図７）のステップ755を除いて、第１の実施形態と同様である。
【０２９６】
本実施形態では、ステップ755の代わりに以下の動作を実行する。
ユーザ認証の結果が「拒否」の場合、ユーザ装置41はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の助けを借りながら、機器認証サーバ装置42の代わりに機器認証シミュレートＭＰＣを実行する。なお、機器認証シミュレートＭＰＣの詳細については、後述する。機器認証シミュレートＭＰＣが終了すると、ユーザ装置41は認証が拒否された旨を、通知部415を経由してユーザ44に伝えて終了する。
【０２９７】
図７のステップ73のユーザ認証ＭＰＣは、第１の実施形態で説明したＺＫＩＰ法またはＭＡＣ法を用いたものでもよいし、第２の実施形態で説明したＧＣ法を用いたものでもよい。
【０２９８】
図７のステップ754の機器認証は、第１の実施形態で説明したＲＳＡを用いたものでもよいし、第２の実施形態で説明した離散対数を用いたものでもよい。
【０２９９】
［機器認証シミュレートＭＰＣ］
機器認証シミュレートＭＰＣの基本的なアイデアは、通常の機器認証において機器認証サーバ装置42が実行していた機器認証検証部4212の動作を、ユーザ装置41が実行するというものである。このようにすると、図７のステップ754は、機器認証検証部4212の処理を実行するのが機器認証サーバ装置42なのかユーザ装置41なのかを除いて同一になる。
【０３００】
ユーザサイド補助装置43には、機器認証検証部4212を実行しているのが機器認証サーバ装置42なのかユーザ装置41なのかを判定する方法がない。したがって、ユーザサイド補助装置43には、ユーザ認証が受理された（すなわちステップ754を実行している）のか、それともユーザ認証が拒否された（すなわちステップ755を実行している）のかを判別する方法はない。
【０３０１】
図１７は、機器認証シミュレートＭＰＣ部17の構成を例示するブロック図である。
【０３０２】
機器認証シミュレートＭＰＣ部17は、ユーザ装置41が秘密鍵利用演算ＭＰＣ実行部173の処理を実行する際、ユーザサイド補助装置43の秘密鍵利用演算ＭＰＣ実行部122と相互通信しながらＭＰＣを実行する。
【０３０３】
図１７における秘密鍵利用演算ＭＰＣ実行部173、秘密鍵利用演算正当性証明生成部174および秘密鍵不用演算部175は、それぞれ、図１１におけるユーザ装置機器認証ＭＰＣ部4127の秘密鍵利用演算ＭＰＣ実行部113、秘密鍵利用演算正当性証明生成部114および秘密鍵不用演算部115と同一である。また、図１７における公開鍵認証検証部176は、図４における機器認証サーバ装置42の機器認証検証部4212と同一である。
【０３０４】
図１８は、機器認証シミュレートＭＰＣの動作を例示するフロー図である：
【０３０５】
ステップ181：各装置は、以下のようにデータ入力を行う。
ステップ1811：ユーザ装置41は秘密鍵のシェアk[0]を記憶部413から読み込み、機器認証シミュレートＭＰＣ部17の入力部171に入力する。ユーザ装置41は、さらに自身の公開鍵pkを記憶部413から読み込み、公開鍵認証検証部176に入力する。
ステップ1812：i=1,...,Mに対し、ユーザサイド補助装置43[i]は秘密鍵のシェアk[i]を分散シェアデータベース4321から読み込み、ユーザサイド補助装置機器認証ＭＰＣ部4312の入力部121に入力する。
【０３０６】
ステップ182：ユーザ装置41は以下を実行する。
ステップ1821：ユーザ装置41は公開鍵認証検証部176を実行し、公開鍵認証検証部176がデータの送信要求を出すと、送信要求されたデータを秘密鍵不用演算部175に入力する。
ステップ1822：ユーザ装置41は送信要求されたデータを秘密鍵不用演算部175に入力し、以下を実行する。
ステップ18221：秘密鍵不用演算部175がサブルーチンとして秘密鍵利用演算を要求するたびに、秘密鍵不用演算部175がサブルーチンに投げたデータを秘密鍵利用演算ＭＰＣ実行部173に入力し、以下を実行する。
ステップ182211：秘密鍵利用演算ＭＰＣ実行部173はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の秘密鍵利用演算ＭＰＣ実行部122[1],...,秘密鍵利用演算ＭＰＣ実行部122[M]と相互通信してＭＰＣを実行し、必要データを計算し、計算されたデータを秘密鍵不用演算部175に返答する。
ステップ182212：i=1,...,Mに対し、ユーザ装置41およびユーザサイド補助装置43[i]は、それぞれ補助通信部4141および補助通信部4331[i]を用いて通信しながら、秘密鍵利用演算正当性証明生成部174および秘密鍵利用演算正当性証明検証部123[i]の処理を実行する。これにより、ステップ182211で行ったＭＰＣの正当性証明とその検証を行う。
ステップ18222：秘密鍵利用演算正当性証明生成部174がデータ送信要求を出すと、ユーザ装置41は要求されたデータを公開鍵認証検証部176に入力する。
ステップ1823：最終的に公開鍵認証検証部176が「受理」または「拒否」を意味するデータを出力すると、ユーザ装置41は機器認証シミュレートＭＰＣを終了する。
【０３０７】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、ユーザ認証が許否された場合、ユーザ装置が機器認証シミュレートＭＰＣを実行することで、ユーザサイド補助装置に対して、ユーザに受理されたか否かに関する情報を一切与えないようにすることができる。したがって、本実施形態によると、上述の実施形態に係る認証システムの安全性をさらに高めることが可能となる。
【０３０８】
＜実施形態４＞
次に、第４の実施形態に係る認証システムについて図面を参照して説明する。
【０３０９】
本実施形態では、i=1,...,Mに対し、ユーザ認証で拒否された回数をカウントするカウンタを第１の実施形態のユーザサイド補助装置43[i]に付け加え、カウンタが定められたしきい値を超えた場合にはユーザ認証を拒絶する。
【０３１０】
本実施形態では、i=1,...,Mに対し、ユーザサイド補助装置43[i]にもユーザ装置41と同様、ユーザ認証結果復元部4124が備わっている。この点を除くと、本実施形態のシステム構成は第１の実施形態の構成と同様である。
【０３１１】
i=1,...,Mに対し、ユーザサイド補助装置43[i]の記憶部432[i]は、ユーザ装置41を用いたユーザ認証においてユーザ44が拒否された回数Cを（ユーザ装置41ごとに）保管しているものとする。ここでは、ユーザ44が拒否された回数Cを拒否回数カウンタと呼ぶ。拒否回数カウンタCは、予めゼロ（0）に初期化されている。また、しきい値Tが事前に定められ、ユーザサイド補助装置43[i]は、しきい値Tを記憶部432[i]に保管している。
【０３１２】
本実施形態の動作は、ユーザ認証を示すフロー図（図７）のステップ74とステップ75との間に以下のステップが挿入される点を除いて、第１の実施形態と同様である。
【０３１３】
i=1,...,M、j=1,...,Mに対し、ユーザサイド補助装置43[i]は補助通信部4331[i]を用いてユーザ認証結果のシェアa[i]をユーザサイド補助装置43[j]に送るi=1,...,Mに対し、ユーザ装置41は補助通信部4141を用いてユーザ認証結果のシェアa[0]をユーザサイド補助装置43[i]に送る。
【０３１４】
i=1,...,Mに対し、ユーザサイド補助装置43[i]は補助通信部4331[i]を用いてユーザ認証結果のシェアa[0],...,a[M]を受信し、ユーザ認証結果のシェアa[0],...,a[M]を入力してユーザ認証結果復元部の処理を実行する。これにより、ユーザサイド補助装置43[i]はユーザ認証の結果accを得る。ユーザ認証の結果accが「拒否」を表している場合、ユーザサイド補助装置43[i]は記憶部432[i]が保持するユーザ装置41の拒否回数カウンタCに1加える。拒否回数カウンタCの値が記憶部432[i]に保管されているしきい値T以上である場合、ユーザサイド補助装置43[i]は以後ユーザ装置41からのユーザ認証要求をすべて拒絶する。
【０３１５】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、ユーザ認証が許否された回数が所定のしきい値以上となると、ユーザサイド補助装置は以降のユーザ認証を許否する。したがって、本実施形態によると、不正者による解析を回避することができ、第１の実施形態に係る認証システムの安全性をさらに高めることが可能となる。
【０３１６】
＜実施形態５＞
次に、第５の実施形態に係る認証システムについて図面を参照して説明する。本実施形態では、ユーザ認証で拒否された回数をカウントするカウンタを実施形態２のユーザサイド補助装置43[1]に付け加え、カウンタが定められたしきい値を超えた場合にはユーザ認証を拒絶する。
【０３１７】
本実施形態の認証システムの構成は、第２の実施形態の構成と同様である。
【０３１８】
ユーザサイド補助装置43[1]の記憶部432[1]は、ユーザ装置41を用いたユーザ認証においてユーザ44が拒否された回数Cを（ユーザ装置41ごとに）保管しているものとする。ここでは、ユーザ44が拒否された回数Cを拒否回数カウンタと呼ぶ。拒否回数カウンタCは、予めゼロ（0）に初期化されている。また、しきい値Tが事前に定められており、ユーザサイド補助装置43[1]は、しきい値Tを記憶部432[1]に保管している。
【０３１９】
本実施形態の動作は、ユーザ認証ＭＰＣ部を示すフロー図（図１６）のステップ163とステップ164の間に以下のステップが追加される点を除いて、第２の実施形態と同様である。
【０３２０】
accが「拒否」を表す場合、ユーザサイド補助装置43[1]は記憶部432[1]が保持するユーザ装置41の拒否回数カウンタCに1加える。拒否回数カウンタCの値が記憶部432[1]に保管されているしきい値T以上である場合、ユーザサイド補助装置43[1]は以後ユーザ装置41からのユーザ認証要求を拒絶する。
【０３２１】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、ユーザ認証が許否された回数が所定のしきい値以上になると、ユーザサイド補助装置は以降のユーザ認証を許否する。したがって、本実施形態によると、不正者による解析を回避することができ、第２の実施形態に係る認証システムの安全性をさらに高めることが可能となる。
【０３２２】
＜実施形態６＞
次に、第６の実施形態に係る認証システムについて図面を参照して説明する。
【０３２３】
本実施形態の認証システムの構成は、第１の実施形態の構成と以下の点で相違する。
第１の実施形態では、ユーザ装置41は検証情報分散シェア生成部4122を備えている。一方、本実施形態における「検証情報分散シェア生成」には、ユーザ装置41およびユーザサイド補助装置43の双方が参加する。また、第１の実施形態とは異なり、本実施形態の検証情報分散シェア生成は第１の実施形態における検証情報導出部41221および検証情報分散部41222の機能を有していない。
第１の実施形態では、ユーザ装置41は認証情報分散シェア生成部4121を備えている。一方、本実施形態における「認証情報分散シェア生成」は、ユーザサイド補助装置43が参加するＭＰＣであり、ユーザ装置41はこのＭＰＣに参加しない。また、第１の実施形態と異なり、本実施形態の「認証情報分散シェア生成」は第１の実施形態における認証情報導出部41211および認証情報分散部41212の機能を有していない。
【０３２４】
本実施形態の「検証情報分散シェア生成」は、下記の３つの動作を含む。
事前準備時入力検証用ユーザ固有情報分散シェア作成
ＭＰＣ入力検証用ユーザ固有情報分散シェア作成
検証情報分散シェア作成マルチパーティ計算
【０３２５】
「事前準備時入力検証用ユーザ固有情報分散シェア作成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証事前準備で行われる。
この処理は、ユーザ装置41によって実行される。
この処理は、ユーザ固有情報とユーザサイド補助装置43の台数Mとを入力として受け取り、M+1個の「事前準備時検証用ユーザ固有情報分散シェア」を出力する。これらのうちの１つはユーザ装置41のためのものであり、他のM個はM台のユーザサイド補助装置43のためのものである。
【０３２６】
「事前準備時入力検証用ユーザ固有情報分散シェア作成」の詳細は、次のとおりである。
入力として受け取ったユーザ固有情報を秘密分散してM個のユーザ固有情報の分散シェアe[1],...,e[M]を得る。
i=1,...,Mに対し、ユーザ固有情報の分散シェアe[i]を秘密分散して2個の「ユーザ固有情報の分散シェアの分散シェア」c[i],d[i]を得る。
分散シェアe[1],...,e[M]を消去する。
ユーザ装置の「事前準備時検証用ユーザ固有情報分散シェア」はD=(c[1],...,c[M])である。i=1,...,Mに対し、ユーザサイド補助装置43[i]の「事前準備時検証用ユーザ固有情報分散シェア」はd[i]である。
【０３２７】
「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証時に実行される。
この処理は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]によって実行される。
この処理の入力は、以下の２つである。
ユーザ装置41が保管している「事前準備時検証用ユーザ固有情報分散シェア」から求められるデータ
ユーザサイド補助装置43[i]が保管している「事前準備時検証用ユーザ固有情報分散シェア」
この処理の出力は、ユーザ固有情報の分散シェア（以下「ＭＰＣ入力検証用ユーザ固有情報分散シェア」という）である。
【０３２８】
i=1,...,Mに対し、ユーザサイド補助装置43[i]が実行する「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成[i]」の詳細は、次のとおりである。
ユーザ装置41が保管している「事前準備時検証用ユーザ固有情報分散シェア」D=(c[1],...,c[M])から求められるデータc[i]と、自身の保持している「事前準備時検証用ユーザ固有情報分散シェア」d[i]を入力として受け取る。
c[i],d[i]を用いて秘密分散の復元を実行することで、ユーザ固有情報の分散シェア（すなわちＭＰＣ入力検証用ユーザ固有情報分散シェア）e[i]を得てe[i]を出力する。
【０３２９】
「検証情報分散シェア作成マルチパーティ計算」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証時に実行される。
この処理は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が参加するＭＰＣである。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は自身の持っているユーザ固有情報の分散シェアをＭＰＣで用い、ＭＰＣの出力として検証情報の分散シェアを得る。
【０３３０】
本実施形態における「認証情報分散シェア生成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証時に実行される。
この処理は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が参加するＭＰＣである。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は自身の持っているユーザ固有情報の分散シェアをＭＰＣで用い、ＭＰＣの出力として認証情報の分散シェアを得る。
【０３３１】
「検証情報分散シェア作成マルチパーティ計算」と「認証情報分散シェア生成のＭＰＣ」は、第１の実施形態の他のＭＰＣと同様に、事前計算データを入力として受け取る場合がある。
【０３３２】
また、第１の実施形態でも述べたように、サーバマシンであるユーザサイド補助装置43はユーザ装置41と比較してはるかに安全性が高く、ログ監視も行われている。このとき、たとえ不正者がユーザサイド補助装置43を乗っ取ったとしても、ユーザサイド補助装置43が定められた動作から外れた行動をとることは考えづらい。
【０３３３】
したがって、「検証情報分散シェア作成マルチパーティ計算」と「認証情報分散シェア生成」のＭＰＣでは、既存のＭＰＣであるＺＫＩＰ法やＭＡＣ法における正当性証明および検証が必要なくなる。このとき、これらのＭＰＣは高速に実行することができる。
【０３３４】
次に、第１の実施形態の動作のうちの、本実施形態とは詳細が異なるものに関して述べる。
ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、検証情報の分散シェアv[i]と認証情報の分散シェアs[i]と事前計算データ（もしあれば）を入力として受け取り、他のユーザサイド補助装置43のユーザサイド補助装置ユーザ認証ＭＰＣ部4311と相互通信しながらＭＰＣの計算を進め、認証結果の分散シェアa[i]を出力する。しかし、本実施形態では、第１の実施形態とは異なり、ユーザ装置41がこのＭＰＣに参加しない。第１の実施形態においては、サーバマシンであるユーザサイド補助装置43よりも安全性の劣るユーザ装置41と相互通信しながらＭＰＣを実行している。このため、第１の実施形態のユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、ユーザ装置41の動作の正当性を検証する正当性証明検証部94を備えている。しかし、本実施形態では、上述したように、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]の行うＭＰＣにユーザ装置41が参加しない。したがって、本実施形態では、ＭＰＣを行う際に、正当性証明検証部94の実行を省略することができる。
【０３３５】
第１の実施形態では、ユーザ認証結果復元部4124はM+1個の分散シェアを入力として受け取っている。一方、本実施形態では、ユーザ認証結果復元部4124は入力としてM個の分散シェアしか受け取らない。これは上述したように、ユーザ認証のＭＰＣにユーザ装置41が参加しないため、シェアがそもそもM個しか存在しないからである。
【０３３６】
［ユーザ認証事前準備］
本実施形態のユーザ認証事前準備は、以下のとおりである。
【０３３７】
まず、ユーザ装置41は以下を実行する。
取得部4111によりユーザ44からユーザ固有情報を取得する。
ユーザ固有情報とユーザサイド補助装置43の台数Mを用いて「事前準備時入力検証用ユーザ固有情報分散シェア作成」を実行し、M+1個の「事前準備時入力検証用ユーザ固有情報分散シェア」D=(c[1],...,c[M]),d[1],...,d[M]を得る。
D=(c[1],...,c[M])を記憶部413に保管する。
i=1,...,Mに対し、通信部414の補助通信部4141を用いてd[i]をユーザサイド補助装置43[i]に送信する。
ユーザ固有情報および分散シェアd[1],...,d[M]を消去する。
【０３３８】
次に、i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
ユーザ装置41が送信した分散シェアd[i]を通信部433[i]の補助通信部4331[i]を用いて受信する。
分散シェアd[i]を分散シェアデータベース4321[i]に保存する。
【０３３９】
［機器認証事前準備］
第１の実施形態と同一である。
【０３４０】
［ユーザ認証］
本実施形態のユーザ認証は、以下のとおりである。
【０３４１】
ユーザ装置41は、以下を実行する。
取得部4111によりユーザ44からユーザ固有情報を取得する。
ユーザ固有情報とユーザサイド補助装置43の台数Mとを用いてユーザ固有情報を秘密分散し、、認証情報の分散シェアf[1],...,f[M]を得る。
記憶部413から「事前準備時入力検証用ユーザ固有情報分散シェア」D=(c[1],...,c[M])を読み込む。
i=1,...,Mに対し、通信部414の補助通信部4141を用いてf[i]とc[i]をユーザサイド補助装置43[i]に送信する。
ユーザ固有情報と分散シェアf[1],...,f[M]を消去する。
【０３４２】
i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
f[i]とc[i]を通信部433[i]の補助通信部4331[i]を用いて受信する。
分散シェアデータベース4321[i]から「事前準備時入力検証用ユーザ固有情報分散シェア」d[i]を読み込む。
c[i]とd[i]を入力して「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成」を実行することで、ユーザ固有情報の分散シェア（ＭＰＣ入力検証用ユーザ固有情報分散シェア）e[i]を得る。
記憶部432から検証情報導出部のアルゴリズムと事前計算データp[i]（もしあれば）を読み込み、e[i]と事前計算データp[i]（もしあれば）と検証情報導出部のアルゴリズムを用いて、「検証情報分散シェア作成マルチパーティ計算[i]」を他のユーザサイド補助装置43と相互通信しながら実行し、出力として検証情報の分散シェアv[i]を得る。
記憶部432から認証情報導出部のアルゴリズムと事前計算データq[i]（もしあれば）を読み込み、f[i]と事前計算データq[i]（もしあれば）と認証情報導出部のアルゴリズムを用いて、「認証情報分散シェア生成[i]」を他のユーザサイド補助装置43の「認証情報分散シェア生成[j]」と相互通信しながらマルチパーティ計算により実行し、出力として認証情報の分散シェアs[i]を得る。
記憶部432からユーザ認証のアルゴリズムと事前計算データb[i]（もしあれば）を読み込み、v[i]とs[i]とb[i]（もしあれば）とユーザ認証のアルゴリズムをユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]に入力し、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]を他のユーザサイド補助装置43のユーザサイド補助装置ユーザ認証ＭＰＣ部4311と相互通信しながら実行し、実行結果としてユーザ認証結果の分散シェアa[i]を得る。
補助通信部4331[i]を用いてa[i]をユーザ装置41に送る。
f[i]、c[i]、v[i]、s[i]、a[i]を消去する。
【０３４３】
ユーザ装置41は、以下を実行する。
補助通信部4141を用いてa[1],...,a[M]を受信する。
a[1],...,a[M]をユーザ認証結果復元部4124に入力し、その出力としてユーザ認証の結果accを得る。
ユーザ認証の結果accが「受理」か「拒否」かを判定する。
ユーザ認証の結果accが「受理」である場合、ユーザ装置41はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の助けを借りながら、機器認証サーバ装置42から機器認証を受ける。
ユーザ認証の結果が「拒否」である場合、ユーザ装置41は認証が拒否された旨を、通知部415を経由してユーザ44に伝えて終了する。
【０３４４】
本実施形態では、第１の実施形態と同様、ユーザ認証の結果が「拒否」の場合にはその旨をユーザ44に伝えて終了するものとした。ただし、第３の実施形態と同様に、機器認証シミュレートＭＰＣを実行した後、ユーザ44に「拒否」された旨を通知してもよい。これにより、ユーザ認証の結果が「拒否」されたか否かがユーザサイド補助装置43には分からないようにすることもできる。
【０３４５】
また、本実施形態においても、第４の実施形態と同様に、ユーザ認証が拒否される回数の上限を定め、安全性を高めることも可能である。
【０３４６】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、認証情報導出、検証情報導出およびユーザ認証の各アルゴリズムをユーザサイド補助装置にのみ記憶させる。したがって、本実施形態によると、これらのアルゴリズムを不特定多数のユーザによって使用されるユーザ装置に対して隠蔽することが可能となる。
【０３４７】
＜実施形態７＞
次に、第７の実施形態に係る認証システムについて図面を参照して説明する。
【０３４８】
本実施形態の認証システムの構成は、以下の点を除いて第１の実施形態の構成と同一である。
第１の実施形態では、ユーザ装置41は検証情報分散シェア生成部4122を備えている。一方、本実施形態における「検証情報分散シェア生成」には、ユーザ装置41およびユーザサイド補助装置43の双方が参加する。また、第１の実施形態と異なり、本実施形態の「検証情報分散シェア生成」は、第１の実施形態における検証情報導出部41221と検証情報分散部41222の機能を有していない。
第１の実施形態では、ユーザ装置41は認証情報分散シェア生成部4121を備えている。一方、本実施形態における「認証情報分散シェア生成」は、ユーザサイド補助装置が参加するＭＰＣであり、ユーザ装置41はこのＭＰＣに参加しない。また、第１の実施形態と異なり、本実施形態の「認証情報分散シェア生成」は第１の実施形態における認証情報導出部41211と認証情報分散部41212の機能を有していない。
【０３４９】
本実施形態の「検証情報分散シェア生成」は、以下の４つの処理を含む。
ＭＰＣ入力検証用ユーザ固有情報分散シェア作成
検証情報分散シェア作成マルチパーティ計算
保存用分散シェア作成
検証情報分散シェア復元
【０３５０】
「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ装置が実行する。
この処理は、ユーザ認証事前準備で実行される。
この処理は、ユーザ固有情報とユーザサイド補助装置43の台数Mを入力として受け取り、ユーザ固有情報の分散シェアを出力する。
【０３５１】
「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成」の詳細は、以下のとおりである。
ユーザ固有情報Eとユーザサイド補助装置43の台数Mを入力として受け取る。
ユーザ固有情報EをM個に秘密分散してユーザ固有情報の分散シェア（ＭＰＣ入力検証用ユーザ固有情報分散シェア）e[1],...,e[M]を得る。
e[1],...,e[M]を出力する。
【０３５２】
「検証情報分散シェア作成マルチパーティ計算」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が参加するＭＰＣである。
この処理は、ユーザ認証事前準備で実行される。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は、自身の保持するユーザ固有情報の分散シェアe[i]をＭＰＣで用い、ＭＰＣの出力として検証情報の分散シェアv[i]を得る。
【０３５３】
「保存用分散シェア作成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証事前準備で実行される。
この処理は、検証情報の分散シェアを入力として受け取り、保存用分散シェアを出力する。
この処理は、まずi=1,...,Mに対し、ユーザサイド補助装置43[i]が実行することで自身の保存用分散シェアとユーザ装置41に送るデータを作成する。ユーザ装置41は、ユーザサイド補助装置43から送られてきたデータをもとに自身の保存用分散シェアを作成する。
【０３５４】
「保存用分散シェア作成」の詳細は以下のとおりである。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
検証情報の分散シェアv[i]を入力として受け取り、v[i]を2つに秘密分散することで「検証情報の分散シェアの分散シェア」u[i]とw[i]を得る。
w[i]をユーザサイド補助装置43[i]自身の保存用分散シェアとする。
u[i]をユーザ装置41に送る。
ユーザ装置41は、以下を実行する
i=1,...,Mに対し、u[i]をユーザサイド補助装置43[i]から受け取る。
W=(u[1],...,u[M])をユーザ装置41の保存用分散シェアとする。
【０３５５】
「検証情報分散シェア復元」を実行する装置、実行されるとき、および、入出力は以下のとおりである。
この処理は、ユーザ認証で実行される。
この処理は、保存用分散シェアを入力として受け取り、検証情報分散シェアを出力する。
この処理では、まずユーザ装置41が自身の保存用分散シェアから得られる情報をユーザサイド補助装置43に送り、ユーザサイド補助装置43は送られてきたデータと自身の保存用分散シェアからユーザ認証を計算する。
【０３５６】
「検証情報分散シェア復元」の詳細は、以下のとおりである。
i=1,...,Mに対し、ユーザ装置41は自身の保存用分散シェアW=(u[1],...,u[M])から求まるデータu[i]をユーザサイド補助装置43[i]に送る。
i=1,...,Mに対し、ユーザサイド補助装置43[i]はユーザから送られてきたデータu[i]と自身の保存用分散シェアw[i]を用いて秘密分散の復元部を行い、検証情報の分散シェアv[i]を得る。
【０３５７】
本実施形態における「認証情報分散シェア生成」を実行する装置、実行されるとき、および、入出力は、以下のとおりである。
この処理は、ユーザ認証時に実行される。
この処理は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が参加するＭＰＣである。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は自身が保持するユーザ固有情報の分散シェアをＭＰＣで用い、ＭＰＣの出力として認証情報の分散シェアを得る。
【０３５８】
「検証情報分散シェア作成マルチパーティ計算」と「認証情報分散シェア生成」のＭＰＣは、第１の実施形態の他のＭＰＣと同様に、事前計算データを入力として受け取る場合がある。
【０３５９】
また、第１の実施形態でも述べたように、サーバマシンであるユーザサイド補助装置43はユーザ装置41と比較してはるかに安全性が高く、ログ監視も行われている。このとき、たとえ不正者がユーザサイド補助装置43を乗っ取ったとしても、ユーザサイド補助装置43が定められた動作から外れた行動をとることは考えづらい。
【０３６０】
したがって、「検証情報分散シェア作成マルチパーティ計算」と「認証情報分散シェア生成」のＭＰＣでは、既存のＭＰＣであるＺＫＩＰ法やＭＡＣ法における正当性証明および検証が必要なくなる。したがって、これらのＭＰＣは高速に実行することができる。
【０３６１】
次に、第１の実施形態の構成および動作のうちの、本実施形態とは詳細が異なるものに関して述べる。
【０３６２】
ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、第６の実施形態のユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]と同様である。すなわち、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、検証情報の分散シェアv[i]と認証情報の分散シェアs[i]と事前計算データ（もしあれば）を入力として受け取り、他のユーザサイド補助装置43のユーザサイド補助装置ユーザ認証ＭＰＣ部4311と相互通信しながらＭＰＣの計算を進め、認証結果の分散シェアa[i]を出力する。しかし、第１の実施形態とは異なり、ユーザ装置41はこのＭＰＣに参加しない。また、第６の実施形態と同様の理由により、本実施形態の場合、ＭＰＣを行う際に正当性証明検証部94の実行を省略することができる。
【０３６３】
第６の実施形態と同様の理由により、ユーザ認証結果復元部4124は入力としてM個の分散シェアしか受け取らない。
【０３６４】
なお、第６の実施形態と同様の理由により、本実施形態でも、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]の行うＭＰＣで、正当性証明検証部94の実行を省略することができる。
【０３６５】
［ユーザ認証事前準備］
ユーザ認証事前準備は、以下のとおりである。
【０３６６】
まず、ユーザ装置41は以下を実行する。
取得部4111によりユーザ44からユーザ固有情報Eを取得する。
ユーザ固有情報Eを用いて「ＭＰＣ入力検証用ユーザ固有情報分散シェア作成」を実行し、出力としてユーザ固有情報の分散シェアe[1],...,e[M]を得る。
通信部414の補助通信部4141を用いてe[1]をユーザサイド補助装置43[1]に送信し,...,e[M]をユーザサイド補助装置43[M]に送信する。
ユーザ固有情報Eおよび分散シェアe[1],...,e[M]を消去する。
【０３６７】
次に、i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
ユーザ装置41が送信したe[i]を通信部433[i]の補助通信部4331[i]を用いて受信する。
記憶部432から検証情報導出部のアルゴリズムと事前計算データp[i]（もしあれば）を読み込み、e[i]と事前計算データp[i]（もしあれば）と検証情報導出部のアルゴリズムを用いて「検証情報分散シェア作成マルチパーティ計算」を他のユーザサイド補助装置43と相互通信しながら実行する。このマルチパーティ計算の出力として、検証情報の分散シェアv[i]を得る。
v[i]を入力して「保存用分散シェア作成」を実行する。結果として、ユーザサイド補助装置43[i]は自身の保存用シェアw[i]を得て分散シェアデータベース4321[i]に保管し、ユーザ装置41は自身の保存用シェアW=(u[1],...,u[M])を得る。
ユーザサイド補助装置43[i]は、v[i]、u[i]を消去する。
【０３６８】
ユーザ装置41は、以下を実行する。
保存用シェアW=(u[1],...,u[M])を記憶部413に保管する。
【０３６９】
［機器認証事前準備］
第１の実施形態と同一である。
【０３７０】
［ユーザ認証］
本実施形態のユーザ認証は、以下のとおりである。
【０３７１】
ユーザ装置41は、以下を実行する。
取得部4111によりユーザ44からユーザ固有情報を取得する。
ユーザ固有情報とユーザサイド補助装置43の台数Mとを用いて、ユーザ固有情報を秘密分散し、認証情報の分散シェアf[1],...,f[M]を得る。
記憶部413から保存用分散シェアW=(u[1],...,u[M])を読み込む。
i=1,...,Mに対し、通信部414の補助通信部4141を用いてf[i]とu[i]をユーザサイド補助装置43[i]に送信する。
ユーザ固有情報とf[1],...,f[M]を消去する。
【０３７２】
i=1,...,Mに対し、ユーザサイド補助装置43[i]は以下を実行する。
f[i]とu[i]を通信部433[i]の補助通信部4331[i]を用いて受信する。
分散シェアデータベース4321[i]から保存用シェアw[i]を読み込む。
保存用シェアu[i],w[i]を入力して「検証情報分散シェア復元」を実行することで検証情報の分散シェアv[i]を復元する。
記憶部432から認証情報導出部のアルゴリズムと事前計算データq[i]（もしあれば）を読み込み、f[i]と事前計算データq[i]（もしあれば）と認証情報導出部のアルゴリズムとを用いて、「認証情報分散シェア生成」を他のユーザサイド補助装置43の「認証情報分散シェア生成」と相互通信しながら実行し、出力として認証情報の分散シェアs[i]を得る。
記憶部432からユーザ認証のアルゴリズムと事前計算データb[i]（もしあれば）を読み込み、v[i]とs[i]とb[i]（もしあれば）とユーザ認証のアルゴリズムをユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]に入力し、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]を他のユーザサイド補助装置43のユーザサイド補助装置ユーザ認証ＭＰＣ部4311と相互通信しながら実行し、実行結果としてユーザ認証結果の分散シェアa[i]を得る。
補助通信部4331[i]を用いてa[i]をユーザ装置41に送る。
f[i]、u[i]、v[i]、s[i]、a[i]を消去する。
【０３７３】
ユーザ装置41は、以下を実行する。
補助通信部4141を用いてa[1],...,a[M]を受信する。
a[1],...,a[M]をユーザ認証結果復元部4124に入力し、その出力としてユーザ認証の結果accを得る。
ユーザ認証の結果accが「受理」か「拒否」かを判定する。
ユーザ認証の結果accが「受理」である場合、ユーザ装置41はユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]の助けを借りながら、機器認証サーバ装置42から機器認証を受ける。
ユーザ認証の結果が「拒否」である場合、ユーザ装置41は認証が拒否された旨を、通知部415を経由してユーザ44に伝えて終了する。
【０３７４】
本実施形態においても、第６の実施形態と同様に、第３の実施形態における機器認証シミュレートＭＰＣを実行した後、ユーザ44に「拒否」された旨を通知してもよい。これにより、ユーザ認証の結果が「拒否」されたか否かが、ユーザサイド補助装置43には分からないようにすることもできる。
【０３７５】
また、本実施形態においても、第４の実施形態と同様に、ユーザ認証が拒否される回数の上限を定め、安全性の向上を図ることも可能である。
【０３７６】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、認証情報導出、検証情報導出およびユーザ認証の各アルゴリズムをユーザサイド補助装置のみが使用する。したがって、本実施形態によると、これらのアルゴリズムを不特定多数のユーザによって使用されるユーザ装置に開示する必要がなくなり、これらのアルゴリズムを企業秘密（例えばサーバサイド補助装置を提供する企業の企業秘密）として保護することができる。
【０３７７】
＜実施形態８＞
次に、第８の実施形態に係る認証システムについて図面を参照して説明する。
【０３７８】
本実施形態の認証システムの構成は、以下の点を除いて、第１の実施形態の構成と同一である。
本実施形態には、「ユーザ認証情報分散シェア生成装置」、「ユーザ検証情報分散シェア生成装置」というサーバマシンがある。以下、これらが別個のサーバマシンであることを前提として話を進めるが、これらは同一のサーバマシンであってもよい。
第１の実施形態では、ユーザ装置41は検証情報分散シェア生成部4122を備えている。一方、本実施形態では、ユーザ装置41はこのユニットを有しておらず、ユーザ検証情報分散シェア生成装置にこのユニットを設ける。検証情報分散シェア生成部4122は、第１の実施形態と同様に、検証情報導出部41221と検証情報分散部41222を有する。
第１の実施形態では、ユーザ装置41は認証情報分散シェア生成部4121を備えている。一方、本実施形態では、ユーザ装置41はこのユニットを有しておらず、ユーザ認証情報分散シェア生成装置にこのユニットを設ける。本実施形態の認証情報分散シェア生成部は、第１の実施形態と同様に、認証情報導出部41211と認証情報分散部41212を有する。
【０３７９】
本実施形態では、第１の実施形態と異なり、ユーザ装置41用の検証情報分散シェアも認証情報分散シェアも作成しない。すなわち、検証情報分散部41222は、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が保有するM個のシェアしか生成しない。同様に、認証情報分散部41212も、ユーザサイド補助装置43[1],...,ユーザサイド補助装置43[M]が保有するM個のシェアしか生成しない。
【０３８０】
また、本実施形態では、ユーザ装置41はユーザ認証ＭＰＣに参加しない。したがって、ユーザ装置41はユーザ装置ユーザ認証ＭＰＣ部4123を備えていない。i=1,...,Mに対し、ユーザサイド補助装置43[i]のユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は、他のユーザサイド補助装置43と通信するものの、ユーザ装置41とは通信しない。
【０３８１】
本実施形態の詳細は、以下のとおりである。
【０３８２】
［ユーザ認証事前準備］
ユーザ装置41は、図５のステップ511と同様、ユーザ44からユーザ固有情報を取得する。次に、ユーザ装置41はユーザ固有情報をユーザ検証情報分散シェア生成装置に送る。その後、ユーザ装置41はユーザ固有情報を消去する。
ユーザ検証情報分散シェア生成装置は、ユーザ装置41の代わりに、図５のステップ512〜516を実行する。すなわち、ユーザ検証情報分散シェア生成装置は以下を実行する。
ユーザ検証情報分散シェア生成装置は、ユーザ装置41から受け取ったユーザ固有情報を検証情報導出部41221に入力して検証情報を得る。次に、検証情報と、ユーザサイド補助装置43の台数Mを検証情報分散部41222に入力し、その出力として検証情報の分散シェアv[1],...,v[M]を得る。i=1,...,Mに対し、ユーザ検証情報分散シェア生成装置は検証情報の分散シェアv[i]をユーザサイド補助装置43[i]に送る。その後、ユーザ検証情報分散シェア生成装置は、ユーザ固有情報、検証情報、および、検証情報の分散シェアv[1],...,v[M]を消去する。
i=1,...,Mに対し、ユーザサイド補助装置43[i]は検証情報の分散シェアv[i]を受信して分散シェアデータベース4321[i]に保存する。
【０３８３】
［機器認証事前準備］
第１の実施形態と同様である。
【０３８４】
［ユーザ認証］
第１の実施形態との相違点は、以下のとおりである。
ユーザ装置41は、図７のステップ711と同様、ユーザ44からユーザ固有情報を取得する。次に、ユーザ装置41は、ユーザ固有情報をユーザ検証情報分散シェア生成装置に送る。その後、ユーザ装置41はユーザ固有情報を消去する。そして、ユーザ認証情報分散シェア生成装置は、図７ステップ712〜715をユーザ装置41の代わりに実行する。すなわち、ユーザ認証情報分散シェア生成装置は以下を実行する。
・ユーザ認証情報分散シェア生成装置は、ユーザ装置41から受け取ったユーザ固有情報を認証情報導出部41211に入力して認証情報を得る。次に、認証情報と、ユーザサイド補助装置43の台数Mを認証情報分散部41212に入力し、その出力として、認証情報の分散シェアs[1],...,s[M]を得る。i=1,...,Mに対し、ユーザ認証情報分散シェア生成装置はs[i]をユーザサイド補助装置43[i]に送る。その後、ユーザ認証情報分散シェア生成装置はユーザ固有情報、認証情報、および、認証情報の分散シェアs[1],...,s[M]を消去する。
ユーザ装置ユーザ認証ＭＰＣ部4123が存在しないため、ユーザ装置ユーザ認証ＭＰＣ部4123の入力を読み込む図７のステップ716は不要となる。同様に、図７のステップ73においても、ユーザ装置ユーザ認証ＭＰＣ部4123に関連する処理がなくなる。図７のステップ73のユーザ認証ＭＰＣに対して、ユーザ装置41は参加しない。i=1,..,Mに対し、ユーザサイド補助装置ユーザ認証ＭＰＣ部4311[i]は他のユーザサイド補助装置43と通信するものの、ユーザ装置41とは通信しない。このとき、ユーザ装置41はユーザ認証ＭＰＣの出力としてa[0]を得ることもない。
a[0]がないため、図７のステップ752ではa[1],...,a[M]からユーザ認証の結果を復元する。
【０３８５】
なお、本実施形態では、ユーザ認証情報分散シェア生成装置およびユーザ検証情報分散シェア生成装置がそれぞれ１台の場合を想定した。ただし、これらの装置を複数台用意し、複数の装置間でＭＰＣを実行することで、ユーザ認証情報の分散シェアや検証情報の分散シェアを計算してもよい。
【０３８６】
本実施形態に係る認証システムにおいても、上記実施形態と同様の効果がもたらされる。すなわち、本実施形態の認証システムによると、ユーザ認証と機器認証を行う認証システムにおいて、ユーザ装置内にセキュアな領域を必要とせず、既存の機器認証サーバとの通信フロントエンドを利用することができる。また、本実施形態では、ユーザの認証情報および検証情報、ならびに、これらのシェアをユーザ装置の代わりに計算する専用のサーバマシンを設けた。したがって、本実施形態によると、認証情報および検証情報を導出するアルゴリズムを不特定多数のユーザによって使用されるユーザ装置に開示する必要がなくなり、これらのアルゴリズムを企業秘密（例えば専用のサーバマシンおよびユーザサイド補助装置を提供する企業の企業秘密）として保護することができる。
【０３８７】
本願開示は、さまざまな用途に適用可能である。例えば、決済システムをはじめとする多くのウェブサービスにおいて、認証が使われている。本願開示は、こうした認証を必要とする認証システムにおいて広く利用することができる。特に、本願開示は既存の認証方式のフロントエンドをそのまま利用できるため、ＦＩＤＯ方式をはじめとするすでにデファクト・スタンダードとして広まっている認証システムにおいて、ユーザ装置の内部の構成を変えるだけで利用可能である。
【０３８８】
（付記）
本発明の請求の範囲全記載が、実施形態として以下に繰り込み記載されているものとする。但し、「請求項」は「形態（mode）」と読み替えるものとし、その際、従属関係は単に好ましい関係を示しそれに限定されないものとする。
【０３８９】
なお、上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０３９０】
（図１）
11    ユーザ装置
111    ユーザ情報取得部
1111    取得部
112    セキュア領域
1121    計算部
11211    検証情報導出部
11212    認証情報導出部
11213    ユーザ認証部
11214    鍵ペア生成部
11215    機器認証部
1122    記憶部
113    通信部
1131    ユーザ装置フロントエンド
114    通知部
12    機器認証サーバ装置
121    計算部
1211    ユーザ認証方法選択部
1212    機器認証検証部
122    記憶部
1221    公開鍵データベース
123    通信部
1231    サーバ装置フロントエンド
13    ユーザ
（図２）
21    ユーザ装置
211    ユーザ情報取得部
2111    取得部
212    計算部
2121    検証情報導出部
2122    認証情報導出部
2123    認証情報分散部
2124    検証情報分散部
213    通信部
2131    独自仕様通信部
214    通知部
22    サーバサイドユーザ認証ＭＰＣ装置
221    計算部
2211    ユーザ認証ＭＰＣ部
2212    認証結果復元部（サーバサイドユーザ認証ＭＰＣ装置22[1]のみ）
222    記憶部
2221    分散ユーザ検証情報データベース
223    通信部
2231    独自仕様通信部
23    ユーザ
（図３）
31    ユーザ装置
311    ユーザ情報取得部
3111    取得部
312    計算部
3121    認証情報導出部
3122    検証情報導出部
3123    認証情報暗号化部
3124    検証情報暗号化部
313    記憶部
314    通信部
3141    ユーザ装置独自仕様フロントエンド
315    通知部
32    ユーザ認証サーバ装置
321    計算部
3211    サーバ装置暗号化認証検証部
322    記憶部
3221    暗号化ユーザ検証情報データベース
323    通信部
3231    サーバ装置独自仕様フロントエンド
3232    補助通信部
33    ユーザ認証サーバ補助装置
331    計算部
3311    サーバ補助装置鍵生成部
3312    サーバ補助装置暗号化認証検証部
332    記憶部
333    通信部
3331    補助通信部
34    ユーザ
（図４）
41    ユーザ装置
411    ユーザ情報取得部
4111    取得部
412    計算部
4121    認証情報分散シェア生成部
41211    認証情報導出部
41212    認証情報分散部
4122    検証情報分散シェア生成部
41221    検証情報導出部
41222    検証情報分散部
4123    ユーザ装置ユーザ認証ＭＰＣ部
4124    ユーザ認証結果復元部
4125    鍵ペア生成部
4126    秘密鍵分散部
4127    ユーザ装置機器認証ＭＰＣ部
413    記憶部
414    通信部
4141    補助通信部
4142    ユーザ装置フロントエンド
415    通知部
42    機器認証サーバ装置
421    計算部
4211    ユーザ認証方法選択部
4212    機器認証検証部
422    記憶部
4221    公開鍵データベース
423    通信部
4231    サーバ装置フロントエンド
43    ユーザサイド補助装置
431    計算部
4311    ユーザサイド補助装置ユーザ認証ＭＰＣ部
4312    ユーザサイド補助装置機器認証ＭＰＣ部
432    記憶部
4321    分散シェアデータベース
433    通信部
4331    補助通信部
44    ユーザ
（図８）
81    入力部
82    一時記憶部
83    ユーザ認証ＭＰＣ実行部
84    正当性証明生成部
85    出力部
（図９）
91    入力部
92    一時記憶部
93    ユーザ認証ＭＰＣ実行部
94    正当性証明検証部
95    出力部
（図１１）
111    入力部
112    受信部
113    秘密鍵利用演算ＭＰＣ実行部
114    秘密鍵利用演算正当性証明生成部
115    秘密鍵不用演算部
116    出力部
（図１２）
121    入力部
122    秘密鍵利用演算ＭＰＣ実行部
123    秘密鍵利用演算正当性証明検証部
124    出力部
（図１４）
141    入力部
142    ＧＣ生成部
143    ＧＣ出力生成部
144    出力部
（図１５）
151    入力部
152    ＧＣ実行部
153    出力部
（図１７）
17    機器認証シミュレートＭＰＣ部
171    入力部
172    受信部
173    秘密鍵利用演算ＭＰＣ実行部
174    秘密鍵利用演算正当性証明生成部
175    秘密鍵不用演算部
176    公開鍵認証検証部
177    出力部
【図１】
2017195886.tif 000003
【図２】
2017195886.tif 000004
【図３】
2017195886.tif 000005
【図４】
2017195886.tif 000006
【図５】
2017195886.tif 000007
【図６】
2017195886.tif 000008
【図７】
2017195886.tif 000009
【図８】
2017195886.tif 000010
【図９】
2017195886.tif 000011
【図１０】
2017195886.tif 000012
【図１１】
2017195886.tif 000013
【図１２】
2017195886.tif 000014
【図１３】
2017195886.tif 000015
【図１４】
2017195886.tif 000016
【図１５】
2017195886.tif 000017
【図１６】
2017195886.tif 000018
【図１７】
2017195886.tif 000019
【図１８】
2017195886.tif 000020
【図１９】
2017195886.tif 000021
【国際調査報告】
2017195886.tif 000022
2017195886.tif 000023
2017195886.tif 000024