情報処理装置、情報処理方法、プログラム、及び記録媒体
【課題】高い安全性を有する効率的な公開鍵認証方式を実現すること。
【解決手段】
多次多変数多項式の組F=(f1,…,fm)及びベクトルsに基づいてメッセージを生成し、前記多次多変数多項式の組F及びベクトルy=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供し、k通りの検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する情報処理装置が提供される。但し、前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成される。また、ベクトルxl=(xl1,…,xln)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成される。
【解決手段】
多次多変数多項式の組F=(f1,…,fm)及びベクトルsに基づいてメッセージを生成し、前記多次多変数多項式の組F及びベクトルy=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供し、k通りの検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する情報処理装置が提供される。但し、前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成される。また、ベクトルxl=(xl1,…,xln)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成される。
Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298
【特許請求の範囲】
【請求項1】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、
前記検証者に前記第3の情報を提供する中間情報提供部と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理装置。
【請求項2】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
請求項1に記載の情報処理装置。
【請求項3】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成すると共に、N回分の前記メッセージから1つのハッシュ値を生成し、
前記メッセージ提供部は、前記ハッシュ値を前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報、及び、前記公開鍵及び前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行しても得られない一部のメッセージを1回の対話で前記検証者に提供する、
請求項2に記載の情報処理装置。
【請求項4】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持部と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理装置。
【請求項5】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項4に記載の情報処理装置。
【請求項6】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージから生成された1つのハッシュ値を取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択した検証パターンに対応する回答情報、及び、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行しても得られない一部のメッセージを前記証明者から取得し、
前記検証部は、前記ハッシュ値、前記一部のメッセージ、前記公開鍵、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証し、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項5に記載の情報処理装置。
【請求項7】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するステップと、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するステップと、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、
前記検証者に前記第3の情報を提供するステップと、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理方法。
【請求項8】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報処理装置が、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理方法。
【請求項9】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、
前記検証者に前記第3の情報を提供する中間情報提供機能と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
プログラム。
【請求項10】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持機能と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
プログラム。
【請求項11】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、
前記検証者に前記第3の情報を提供する中間情報提供機能と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
記録媒体。
【請求項12】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持機能と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
記録媒体。
【請求項1】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、
前記検証者に前記第3の情報を提供する中間情報提供部と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理装置。
【請求項2】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
請求項1に記載の情報処理装置。
【請求項3】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成すると共に、N回分の前記メッセージから1つのハッシュ値を生成し、
前記メッセージ提供部は、前記ハッシュ値を前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報、及び、前記公開鍵及び前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行しても得られない一部のメッセージを1回の対話で前記検証者に提供する、
請求項2に記載の情報処理装置。
【請求項4】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持部と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理装置。
【請求項5】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項4に記載の情報処理装置。
【請求項6】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージから生成された1つのハッシュ値を取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択した検証パターンに対応する回答情報、及び、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行しても得られない一部のメッセージを前記証明者から取得し、
前記検証部は、前記ハッシュ値、前記一部のメッセージ、前記公開鍵、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証し、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項5に記載の情報処理装置。
【請求項7】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するステップと、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するステップと、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、
前記検証者に前記第3の情報を提供するステップと、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理方法。
【請求項8】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報処理装置が、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
情報処理方法。
【請求項9】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、
前記検証者に前記第3の情報を提供する中間情報提供機能と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
プログラム。
【請求項10】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持機能と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
プログラム。
【請求項11】
多次多変数多項式の組F=(f1,…,fm)及びベクトルs∈Knに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組F及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成機能と、
前記検証者に前記第3の情報を提供する中間情報提供機能と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
記録媒体。
【請求項12】
多次多変数多項式の組F=(f1,…,fm)及びベクトルy=(y1,…,ym)=(f1(s),…,fm(s))を保持する情報保持機能と、
前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供機能と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得機能と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記多次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルsは秘密鍵であり、
前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Fは、標数q及び位数qkの環R上で定義される多項式f1,…,fmで構成され、ベクトルxl=(xl1,…,xln)(l=1,2)についてG(x1,x2)=F(x1+x2)−F(x1)−F(x2)で定義される多項式G(x1,x2)が、(x1i)q(z)(但し、1≦i≦n、q(z)=qz、1≦z≦k)に比例する項で構成されるように設定されている、
記録媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【公開番号】特開2013−42295(P2013−42295A)
【公開日】平成25年2月28日(2013.2.28)
【国際特許分類】
【出願番号】特願2011−177071(P2011−177071)
【出願日】平成23年8月12日(2011.8.12)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
【公開日】平成25年2月28日(2013.2.28)
【国際特許分類】
【出願日】平成23年8月12日(2011.8.12)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
[ Back to top ]