JP5736816B2 - 認証装置、認証方法、プログラム、及び署名生成装置 - Google Patents
認証装置、認証方法、プログラム、及び署名生成装置 Download PDFInfo
- Publication number
- JP5736816B2 JP5736816B2 JP2011026401A JP2011026401A JP5736816B2 JP 5736816 B2 JP5736816 B2 JP 5736816B2 JP 2011026401 A JP2011026401 A JP 2011026401A JP 2011026401 A JP2011026401 A JP 2011026401A JP 5736816 B2 JP5736816 B2 JP 5736816B2
- Authority
- JP
- Japan
- Prior art keywords
- verification
- information
- algorithm
- message
- response
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/321—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving a third party or a trusted authority
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3093—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving Lattices or polynomial equations, e.g. NTRU scheme
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
- H04L9/3221—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs interactive zero-knowledge proofs
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
- H04L9/3255—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using group based signatures, e.g. ring or threshold signatures
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Analysis (AREA)
- General Physics & Mathematics (AREA)
- Algebra (AREA)
- Storage Device Security (AREA)
- Computer And Data Communications (AREA)
- Mobile Radio Communication Systems (AREA)
Description
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。なお、本実施形態に係る説明に先立ち、一般的なHFE署名方式についても簡単に説明する。
1:はじめに
1−1:公開鍵認証方式のアルゴリズム構成
1−2:電子署名方式のアルゴリズム構成
1−3:nパスの公開鍵認証方式
1−4:HFE電子署名方式
1−4−1:HFE関数の性質
1−4−2:HFE電子署名方式のアルゴリズム
2:第1実施形態
2−1:公開鍵認証方式のアルゴリズム
2−2:拡張アルゴリズム
2−3:並列化アルゴリズム
2−4:非対話型アルゴリズム
2−5:電子署名方式への変形
2−6:具体例
2−7:効率的なアルゴリズム
2−8:多次多変数連立方程式の形式
2−8−1:共通鍵ブロック暗号に関する形式
2−8−2:ハッシュ関数に関する形式
2−8−3:ストリーム暗号に関する形式
3:第2実施形態
3−1:公開鍵認証方式のアルゴリズム
3−2:拡張アルゴリズム
3−3:並列化アルゴリズム
3−4:非対話型アルゴリズム
3−5:電子署名方式への変形
3−6:具体例
3−7:効率的なアルゴリズム
4:効率的なアルゴリズムの一般化
5:ハードウェア構成例
6:まとめ
はじめに、本発明に係る実施形態について詳細に説明するに先立ち、一般的な公開鍵認証方式のアルゴリズム構成、一般的な電子署名方式のアルゴリズム構成、及びnパスの公開鍵認証方式について簡単に説明する。
まず、図1を参照しながら、一般的な公開鍵認証方式のアルゴリズム構成について説明する。図1は、一般的な公開鍵認証方式のアルゴリズム構成について説明するための説明図である。
公開鍵認証方式とは、ある人(証明者)が、公開鍵pk及び秘密鍵skを利用して、他の人(検証者)に本人であることを納得させるための認証方式である。例えば、証明者Aの公開鍵pkAは、検証者に公開される。一方、証明者Aの秘密鍵skAは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵pkAに対応する秘密鍵skAを知る者が証明者A本人であるとみなされる。
公開鍵認証方式のモデルには、図1に示すように、証明者と検証者という2つのエンティティが存在する。証明者は、鍵生成アルゴリズムGenを用いて、証明者固有の秘密鍵skと公開鍵pkの組を生成する。次いで、証明者は、鍵生成アルゴリズムGenを用いて生成した秘密鍵skと公開鍵pkの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムPを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムPを利用して、秘密鍵skを保有していることを検証者に証明する。
鍵生成アルゴリズムGenは、証明者により利用される。そして、鍵生成アルゴリズムGenは、証明者に固有の秘密鍵skと公開鍵pkの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された公開鍵pkは公開される。そして、公開された公開鍵pkは、検証者により利用される。一方、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵skは、検証者に対して公開鍵pkに対応する秘密鍵skを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λ(λは0以上の整数)を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式(1)のように表現される。
証明者アルゴリズムPは、証明者により利用される。そして、証明者アルゴリズムPは、公開鍵pkに対応する秘密鍵skを保有していることを証明するアルゴリズムである。証明者アルゴリズムPは、証明者の秘密鍵skと公開鍵pkを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。
検証者アルゴリズムVは、検証者により利用される。そして、検証者アルゴリズムVは、対話プロトコルの中で、公開鍵pkに対応する秘密鍵skを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムVは、証明者の公開鍵pkを入力とし、証明者との間で対話プロトコルを実行した後、0又は1(1bit)を出力するアルゴリズムとして定義される。なお、出力0の場合には証明者が不正なものであり、出力1の場合には証明者が正当なものであるとする。形式的に、検証者アルゴリズムVは、下記の式(2)のように表現される。
上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という2つの条件を満たすことが求められる。しかし、証明者が秘密鍵skを保有していることを証明者に証明させるためには、証明者が秘密鍵skに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵skに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵skの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVが設計されることが必要になる。
次に、図2を参照しながら、一般的な電子署名方式のアルゴリズム構成について説明する。図2は、一般的な電子署名方式のアルゴリズム構成について説明するための説明図である。
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果を奏する電子的な仕組みが必要とされる。このような仕組みが電子署名である。例えば、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを電子署名方式と呼ぶ。
電子署名方式のモデルには、図2に示すように、署名者と検証者という2つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerという3つのアルゴリズムにより構成される。
鍵生成アルゴリズムGenは、署名者により利用される。そして、鍵生成アルゴリズムGenは、署名者固有の署名鍵skと検証鍵pkの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された検証鍵pkは公開される。一方、鍵生成アルゴリズムGenにより生成された署名鍵skは、署名者により秘密に管理される。そして、署名者により秘密に管理されている署名鍵skは、文書Mに付与される電子署名σの生成に利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λ(λは0以上の整数)を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式(3)のように表現される。
署名生成アルゴリズムSigは、署名者により利用される。そして、署名生成アルゴリズムSigは、文書Mに対して付与される電子署名σを生成するアルゴリズムである。形式的に、署名生成アルゴリズムSigは、署名者の署名鍵skと文書Mを入力とし、下記の式(4)に示すように、電子署名σを出力するアルゴリズムとして表現される。
署名検証アルゴリズムVerは、検証者により利用される。そして、署名検証アルゴリズムVerは、電子署名σが文書Mに対する正当な電子署名であるか否かを検証するアルゴリズムである。形式的に、署名検証アルゴリズムVerは、下記の式(5)に示すように、署名者の検証鍵pk、文書M、電子署名σを入力とし、0又は1(1bit)を出力するアルゴリズムとして表現される。なお、0を出力する場合(公開鍵pkが文書Mと電子署名σを拒否する場合)、文書Mに対する電子署名σは不当である。1を出力する場合(公開鍵pkが文書Mと電子署名σを受理する場合)、文書Mに対する電子署名σは正当である。
次に、図3を参照しながら、nパスの公開鍵認証方式について説明する。図3は、nパスの公開鍵認証方式について説明するための説明図である。
ここで、多次多変数連立方程式を用いた電子署名方式の一例として、HFE電子署名方式について簡単に説明する。
まず、HFE関数Ftの定義、及びHFE関数Ftの性質について簡単に説明する。
K:q個の数を含む元で構成される有限環
Kn:Kのn個の直積
Ft:Kn→Kn
A:有限環Kのn次拡大(要素数qn)
B:有限環Kのm次拡大(要素数qm)
φ:線形写像A→Kn(下記の式(6)を参照)
S:Kn上での可逆的アフィン変換
T:Kn上での可逆的アフィン変換
f:中央写像(下記の式(7)を参照)
トラップドア:S、T、aij、bi、c
HFE関数Ftは、変換Sによる写像、中央写像F(F=φ−1*f*φ)、及び変換Tによる写像の合成写像Ft=T*F*Sにより表現される(この*は写像の合成)。そして、y=Ft(x)を計算するアルゴリズムは、次のようになる。
(Step.2)φ−1により、x’∈KnをX’∈Aに変換する。
(Step.3)中央写像fにより、X’∈AをY’=f(X’)∈Aに変換する。
(Step.4)φにより、Y’∈Aをy’=(y0’,…,yn−1’)∈Knに変換する。
(Step.5)変換Tにより、y’∈Knをy=(y0,…,yn−1)∈Knに変換する。
(Step.6)y∈Knを出力する。
HFE関数Ftに対する順方向の計算アルゴリズムは、与えられたx∈KnをHFE関数Ft(x)に代入してy=Ft(x)∈Knを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元xが1つ入力されると値域の元yが1つ出力される。
HFE関数Ftに関する逆方向の計算アルゴリズムは、次のStep.1〜Step.7により構成される。
(Step.2)φ−1により、y’=(y0’,…,yn−1’)∈KnをY’∈Aに変換する。
(Step.3)Y’を用いて、X’∈{Z∈A|f(Z)=Y’}の集合を計算する。但し、{Z∈A|f(Z)=Y’}が空集合の場合、例外値errを出力する。なお、X’∈{Z∈A|f(Z)=Y’}は、例えば、多項式f(X)−Y’を因数分解することにより求められる。また、終域の要素Y’をランダムに選択したとき、その要素Y’に対する原像{Z∈A|f(Z)=Y’}がm個の元を持つ確率は、近似的に1/(m!e)となる(但し、このeはネイピア数)。
(Step.4)X’∈{Z∈A|f(Z)=Y’}の集合から1つの要素X’を選択する。
(Step.5)φにより、Step.4で選択された1つの要素X’∈Aをx’=(x0’,…,xn−1’)∈Knに変換する。
(Step.6)変換Sの逆変換S−1により、x’∈Knをx=(x0,…,xn−1)∈Knに変換する。
(Step.7)x∈Knを出力する。
ここまでHFE関数Ftについて説明してきた。次に、HFE関数Ftを用いた電子署名方式(以下、HFE署名方式)の具体的なアルゴリズムについて説明する。但し、ここでは、HFE署名方式の一例として、HFE関数を用いたPFDH署名方式(以下、HFE+PFDH署名方式)について説明する。
まず、PFDH署名方式における鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。これらPFDH署名方式のアルゴリズムは、トラップドア付き一方向性関数Ft:A→B、ハッシュ関数H:{0,1}*→Bを利用する。
鍵生成アルゴリズムGenは、セキュリティパラメータを1λとし、署名鍵skをFtのトラップドアtとし、検証鍵pkをFtとして(sk,pk)を計算する((sk,pk)←Gen(1λ))。
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.4により電子署名σを計算する(σ←Sig(sk,M))。
(Step.2)y=H(M,r)∈Bを計算する。
(Step.3)トラップドアtを用いてFtの逆方向の計算アルゴリズムを実行し、y=Ft(x)となるxを算出する。但し、y=Ft(x)となるxが存在しない場合にはStep.1に戻る。
(Step.4)電子署名σ=(x,r)を出力する。
署名検証アルゴリズムVerは、検証鍵pk=Ft、メッセージM、電子署名σ=(x,r)を入力とし、次のStep.1及びStep.2によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
(Step.2)Ft(x)=H(M,r)の場合に1を出力し、Ft(x)≠H(M,r)の場合に0を出力する。
次に、HFE+PFDH署名方式における署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。HFE+PFDH署名方式は、HFE関数Ftを用いたPFDH署名方式である。なお、HFE+PFDH署名方式では、署名鍵sk、HFE関数FtのトラップドアS,T,aij、bi、c、検証鍵pkがFtに設定される。
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.9により電子署名σを計算する(σ←Sig(sk,M))。
(Step.2)乱数r、メッセージMを用いて、ハッシュ値y∈Kn←H(M,r)を計算する。
(Step.3)y=(y0,…,yn−1)∈Knを変換Tの逆変換T−1に適用してy’=(y0’,…,yn−1’)∈Knを得る。
(Step.4)φ−1により、y’=(y0’,…,yn−1’)∈KnをY’∈Aに変換する。
(Step.5)X’∈{Z∈A|f(Z)=Y’}の集合を計算する。
(Step.6)集合{Z∈A|f(Z)=Y’}から1つの要素X’を選択する。但し、集合{Z∈A|f(Z)=Y’}が空集合の場合、Step.1の処理へ戻る。
(Step.7)φにより、X’∈Aをx’=(x0’,…,xn−1’)∈Knに変換する。
(Step.8)変換Sにより、x’∈Knをx=(x0,…,xn−1)∈Knに変換する。
(Step.9)電子署名σ=(x,r)を出力する。
署名検証アルゴリズムVerは、検証鍵pk=Ft、メッセージM、電子署名σ=(x,r)を入力とし、次のStep.1〜Step.3によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
(Step.2)電子署名σに含まれるx∈KnをHFE関数Ft(x)に代入して、y”=Ft(x)∈Knを計算する。
(Step.3)y=y”ならば1を出力し、y≠y”ならば0を出力する。
ここで、本発明の第1実施形態について説明する。本実施形態は、HFE電子署名方式と同様、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、HFE電子署名方式などとは異なり、十分な安全性を確保するために、効率的に解く手段(トラップドア)を持たない多次多変数連立方程式を利用できるようにした公開鍵認証方式及び電子署名方式を提供するものである。
まず、図4を参照しながら、本実施形態に係る公開鍵認証方式(以下、本手法)のアルゴリズムについて説明する。図4は、本手法のアルゴリズムについて説明するための説明図である。なお、本手法は、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図4を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、(r,w’)←G1(w)を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してn変数多項式F’(x)=(f’1(x),…,f’m(x))を生成する。つまり、証明者アルゴリズムPは、F’←G2(w’)を計算する。
次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、F”(x)←F(x+r)+F’(x)を計算する。この計算は、xについての多項式の組F(x+r)を多項式の組F’(x)によりマスクする操作に相当する。
次いで、証明者アルゴリズムPは、F’(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F’(z),z)を計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w’)を計算する。さらに、証明者アルゴリズムPは、多項式の組F”のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(F”)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2,c3)はメッセージである。
検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=(w’,z)を生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=(F”(x),z)を生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
さて、上記Step.1において生成されたメッセージ(c1,c2,c3)を検証者に送った際、秘密鍵skに関する情報、rに関する情報、zに関する情報が検証者に一切漏れていないことに注意されたい。また、上記Step.3において生成された情報σを検証者に送った際、d=0のときにはzに関する情報が検証者に一切漏れておらず、d=1,2のときにはrに関する情報が検証者に一切漏れていないことに注意されたい。
本手法の健全性は、検証者の全ての要求d=0,1,2に対して、証明者がメッセージ(c1,c2,c3)に対する正しい情報σを回答したならば、その回答内容から、下記の式(8)及び式(9)を満たすF''''、F'''、r’、z’が計算できるということから保証されている。
上記の鍵生成アルゴリズムGenは、y←F(s)を計算し、公開鍵を(F,y)に設定している。しかし、鍵生成アルゴリズムGenは、(y1,…,ym)←F(s)として、(f1 *(x),…,fm *(x))←(f1(x)−y1,…,fm(x)−ym)を計算し、公開鍵を(f1 *,…,fm *)に設定するように構成されていてもよい。このように変形すると、証明者と検証者との間でy=0として対話プロトコルを実行することが可能になる。
次に、図5を参照しながら、本手法を拡張した公開鍵認証方式(以下、拡張手法)のアルゴリズムについて説明する。図5は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、1パス目に送信するメッセージ(c1,c2,c3)を1つのハッシュ値cに変換して検証者に送る方式である。また、この拡張手法では、1パス目にハッシュ値cを送るように対話プロトコルを構成するため、3パス目で送る情報σから復元できないメッセージを情報σと共に検証者に送る。このように拡張することで、対話プロトコルの中で検証者に送るハッシュ値の数を減らすことが可能になり、通信するデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図5を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、(r,w’)←G1(w)を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してn変数多項式F’(x)=(f’1(x),…,f’m(x))を生成する。つまり、証明者アルゴリズムPは、F’←G2(w’)を計算する。
次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、F”(x)←F(x+r)+F’(x)を計算する。この計算は、xについての多項式の組F(x+r)を多項式の組F’(x)によりマスクする操作に相当する。
次いで、証明者アルゴリズムPは、F”(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F”(z),z)を計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w’)を計算する。さらに、証明者アルゴリズムPは、多項式の組F”のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(F”)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2,c3)はメッセージである。
拡張方式の場合、証明者アルゴリズムPは、メッセージ(c1,c2,c3)をハッシュ関数Hに適用してハッシュ値cを生成する。そして、証明者アルゴリズムPは、生成したハッシュ値cを検証者に送る。
検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報(σ,c*)=(w,c1)を生成する。また、d=1の場合、証明者アルゴリズムPは、情報(σ,c*)=((w’,z),c3)を生成する。そして、d=2の場合、証明者アルゴリズムPは、情報(σ,c*)=((F”,z),c2)を生成する。このようにして生成された情報(σ,c*)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報(σ,c*)を利用して以下の検証処理を実行する。
さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(2/3)2以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は(2/3)Nとなり、Nを十分に大きい数(例えば、N=140)にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にN回実行するアルゴリズムは図6のようになる。以下、図6を参照しながら、並列的に対話プロトコルをN回実行する各アルゴリズムの内容について説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図6を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(8)を実行する。(処理(1))証明者アルゴリズムPは、任意に数wiを選択する。(処理(2))証明者アルゴリズムPは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数w’iを生成する。つまり、証明者アルゴリズムPは、(ri,w’i)←G1(wi)を計算する。(処理(3))証明者アルゴリズムPは、擬似乱数生成器G2に数w’iを適用してn変数多項式の組F’i(x)を生成する。つまり、証明者アルゴリズムPは、F’i←G2(w’i)を計算する。
(処理(4))証明者アルゴリズムPは、zi←si−riを計算する。この計算は、秘密鍵siをベクトルriによりマスクする操作に相当する。(処理(5))証明者アルゴリズムPは、F”i(x)←F(x+ri)+F’i(x)を計算する。この計算は、xについての多項式の組F(x+ri)を多項式の組F’i(x)によりマスクする操作に相当する。
(処理(6))証明者アルゴリズムPは、F”i(zi)とziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1(F”i(zi),zi)を計算する。(処理(7))証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2(w’i)を計算する。(処理(8))証明者アルゴリズムPは、多項式の組F”iのハッシュ値c3,iを生成する。つまり、証明者アルゴリズムPは、c3,i←H3(F”i)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1,i、c2,i、c3,i)はメッセージである。
検証者アルゴリズムVは、i=1〜Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1,2}(i=1〜N)を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(3)を実行する。(処理(1))di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。(処理(2))di=1の場合、証明者アルゴリズムPは、情報σi=(w’i,zi)を生成する。(処理(3))di=2の場合、証明者アルゴリズムPは、情報σi=(F”i,zi)を生成する。上記の処理(1)〜(3)の判定及び処理が実行された後、情報σi(i=1〜N)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σi(i=1〜N)を利用して以下の検証処理を実行する。なお、以下の処理は、i=1〜Nについて実行される。
さて、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性レベルを保証している。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性レベルが確実に保証されているということを保証するには、以下で説明するような条件が必要になる。
これまで3パスの公開鍵認証方式について説明してきた。しかし、本手法においては、2パス目で検証者から証明者に送られる情報が検証パターンを示す要求d(実際には単なる乱数を用いることが多い。)だけであるため、1パスの公開鍵認証方式(以下、非対話型方式)に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図7に示した。以下、図7を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図7を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(8)を実行する。(処理(1))証明者アルゴリズムPは、任意に数wiを選択する。(処理(2))証明者アルゴリズムPは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数w’iを生成する。つまり、証明者アルゴリズムPは、(ri,w’i)←G1(wi)を計算する。(処理(3))証明者アルゴリズムPは、擬似乱数生成器G2に数w’iを適用してn変数多項式の組F’i(x)を生成する。つまり、証明者アルゴリズムPは、F’i←G2(w’i)を計算する。
(処理(4))証明者アルゴリズムPは、zi←s−riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。(処理(5))証明者アルゴリズムPは、F”i(x)←F(x+ri)+F’i(x)を計算する。この計算は、xについての多項式の組F(x+ri)を多項式の組F’i(x)によりマスクする操作に相当する。
(処理(6))証明者アルゴリズムPは、F”i(zi)とziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1(F”i(zi),zi)を計算する。(処理(7))証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2(w’i)を計算する。(処理(8))証明者アルゴリズムPは、多項式の組F”iのハッシュ値c3,iを生成する。つまり、証明者アルゴリズムPは、c3,i←H3(F”i)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1,i、c2,i、c3,i)はメッセージである。
次に、証明者アルゴリズムPは、乱数Rを選択する。次いで、証明者アルゴリズムPは、i=1〜Nについて、乱数RとStep.1で生成したメッセージ(c1,i、c2,i、c3,i)をハッシュ関数Hに適用してd=(d1,…,dN)を生成する。
次に、証明者アルゴリズムPは、生成したdiに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜(3)を実行する。(処理(1))di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。(処理(2))di=1の場合、証明者アルゴリズムPは、情報σi=(w’i,zi)を生成する。(処理(3))di=2の場合、証明者アルゴリズムPは、情報σi=(F”i,zi)を生成する。上記の処理(1)〜(3)の判定及び処理が実行された後、乱数R、メッセージ(c1,i,c2,i,c3,i)及び情報σi(i=1〜N)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、まず、証明者から受け取った乱数R、メッセージ(c1,i,c2,i,c3,i)及び情報σi(i=1〜N)をハッシュ関数Hに適用してd=(d1,…,dN)を生成する。次いで、検証者アルゴリズムVは、情報σi(i=1〜N)を利用して以下の検証処理を実行する。なお、以下の処理は、i=1〜Nについて実行される。
ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと類似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
署名生成アルゴリズムSigは、i=1〜Nについて、以下の(処理1)〜(処理15)を実行する。なお、署名生成アルゴリズムSigには、署名鍵sk=(s1,…,sN)と文書Mが入力されているものとする。
署名検証アルゴリズムVerは、i=1〜Nについて、以下の全ての検証を通過すれば、電子署名σを受理し、1つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムVerには、電子署名σと文書Mが入力されているものとする。まず、署名検証アルゴリズムVerは、d=(d1,…,dN)←H(R,M,c1,1,…,c3,N)を計算する。次いで、署名検証アルゴリズムVerは、i=1〜Nについて、以下の(検証1)〜(検証3)を実行する。
次に、図8を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図8は、本手法の具体例を説明するための説明図である。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数2次多項式(f1(x),…,fm(x))をF(x)と表記する。但し、n変数2次多項式fi(x1,…,xn)は、下記の式(10)のように表現される。
次に、図8を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、(r,w’)←G1(w)を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用してm本の1次多項式の組f’1(x1,…,xn),…,f’m(x1,…,xn)を生成する。つまり、証明者アルゴリズムPは、(f’1,…,f’m)←G2(w’)を計算する。但し、1次多項式f’i(x1,…,xn)は、下記の式(11)のように表現される。また、m本の1次多項式の組(f’1(x),…,f’m(x))をF’(x)と表記する。
次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、F”(x)←F(x+r)+F’(x)を計算する。この計算は、xについての多項式F(x+r)を多項式F’(x)によりマスクする操作に相当する。ここで、F(x+r)の中にはrに関する情報がxの1次の項にしか現れないため、rに関する情報は全てF’(x)によりマスクされている点に注意されたい。
次いで、証明者アルゴリズムPは、F’(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F’(z),z)を計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w’)を計算する。さらに、証明者アルゴリズムPは、多項式F”のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(F”)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1、c2、c3)はメッセージである。
検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=(w’,z)を生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=(F”,z)を生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
m本のn変数2次多項式の組(f1(x),…,fm(x))は、下記の式(12)のように表現することができる。但し、x=(x1,…,xn)は、n個の変数を表すベクトルである。また、A1,…,Amは、n×n行列である。さらに、b1,…,bmはn×1ベクトルである。そして、cは、m×1ベクトルである。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数w’を生成する。つまり、証明者アルゴリズムPは、(r,w’)←G1(w)を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数w’を適用して2つのベクトルt∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、(t,e)←G2(w’)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t’←r+tを計算する。次いで、証明者アルゴリズムPは、e’←F(r)−c+eを計算する。
次いで、証明者アルゴリズムPは、上記の式(16)に基づいてFb(z,t)を算出し、Fb(z,t)+eとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(Fb(z,t)+e,z)を計算する。また、証明者アルゴリズムPは、数w’のハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w’)を計算する。さらに、証明者アルゴリズムPは、2つのベクトルt’とe’のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(t’,e’)を計算する。なお、上記のH1(…)、H2(…)、H3(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2,c3)はメッセージである。
検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1,2}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=(w’,z)を生成する。そして、d=2の場合、証明者アルゴリズムPは、情報σ=(t’,e’,z)を生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
さて、図9に示した本手法の効率的なアルゴリズムは、その計算効率を維持しながら、図10、図11に示すようなアルゴリズムに変形することが可能である。
例えば、図9に示した効率的なアルゴリズムのStep.1において、e’←F(r)−c+eという計算を行っているが、この計算を図10に示すようにe’←F(r)+eという計算に変形してもよい。但し、この変形を行う場合には、Step.4において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.4においてd=0の場合に検証者が行う検証内容のうち、c3=H3(r’+t”,F(r’)−c+e”)の検証をc3=H3(r’+t”,F(r’)+e”)の検証に置き換える必要がある。また、Step.4においてd=2の場合に検証者が行う検証内容のうち、c1=H1(F(z’)+Fb(z’,t’’’)+e’’’−y,z’)の検証をc1=H1(F(z’)+Fb(z’,t’’’)−c+e’’’−y,z’)の検証に置き換える必要がある。
また、図10に示したアルゴリズムのStep.3において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、(r,t,e)が復元できる情報であればどのような情報でもよい。例えば、図11に示すように、Step.3においてd=0の場合に設定されるσの内容を(w’,t’)にしてもよい。但し、この変形を行う場合には、Step.4において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.4においてd=0の場合に検証者が行う検証内容のうち、c3=H3(r’+t”,F(r’)+e”)の検証をc3=H3(t’,F(t’−t)+e”)の検証に置き換える必要がある。
これまで説明してきたように、本手法は、多次多変数連立方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式である。また、本手法は、複雑な多次多変数連立方程式を利用可能な点に特徴がある。ここまでの説明においては多次多変数連立方程式の形式に特別な限定を行ってこなかったが、例えば、十分に困難性が補償されている暗号要素技術を表現した多次多変数連立方程式を利用することが好ましい。以下、本手法に適用可能な多次多変数連立方程式の具体例を紹介する。
AES、DES、KATANなどの共通鍵ブロック暗号技術は、よく解析され、安全性及び信頼性が高い要素技術である。これらの共通鍵ブロック暗号は、共通鍵ブロック暗号の鍵、平文、暗号文を変数とする多次多変数連立方程式により表現することができる。この多次多変数連立方程式において平文と暗号文を表現する変数に値を与えると、この多次多変数連立方程式は、鍵を表現する変数だけを変数に持つ方程式になる。
同様に、SHA−1、SHA−256などのハッシュ関数に関する多次多変数連立方程式を本手法に適用することも可能である。これらのハッシュ関数は、ハッシュ関数の入力となるメッセージと出力となるハッシュ値を変数とする多次多変数連立方程式で表現することができる。この多次多変数連立方程式において、ハッシュ値を表現する変数に適当な値を与えると、対応する入力を表現した変数に関する多次多変数連立方程式が得られる。
同様に、Triviumなどのストリーム暗号に関する多次多変数連立方程式を本手法に適用することも可能である。これらのストリーム暗号は、ストリーム暗号の初期の内部状態を表現する変数と、出力されるストリームを表現する変数に関する多次多変数連立方程式で表現することが可能である。この場合、出力ストリームを表現する変数に適当な値を与えると、対応する初期の内部状態を表現するための変数に関する多次多変数連立方程式が得られる。
次に、本発明の第2実施形態について説明する。これまで3パスの公開鍵認証方式について説明してきた。本実施形態では、5パスの公開鍵認証方式(以下、本手法)について説明する。本手法は、検証者の検証パターンを2q通りにすることにより、公開鍵認証方式の健全性を確保する方式である。
以下、図12を参照しながら、5パスの公開鍵認証方式(本手法)に係るアルゴリズム構成について説明する。図12は、本手法に係るアルゴリズムの内容について説明するための説明図である。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←f1(s),…,fm(s)を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図12を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’(x)=(f’1(x),…,f’m(x))を生成する。つまり、証明者アルゴリズムPは、(r,F’)←G(w)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。
次いで、証明者アルゴリズムPは、F’(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F’(z),z)を計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w)を計算する。なお、上記のH1(…)、H2(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2)はメッセージである。
検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。
証明者アルゴリズムPは、F”(x)←αF(x+r)+F’(x)を計算する。この計算は、xについての多項式の組F(x+r)を多項式の組F’(x)によりマスクする操作に相当する。
検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
さて、上記Step.1及びStep.3において生成されたメッセージ(c1,c2)及び多項式の組F”を検証者に送った際、秘密鍵skに関する情報、rに関する情報、zに関する情報が検証者に一切漏れていないことに注意されたい。また、上記Step.5において生成された情報σを検証者に送った際、d=0のときにはzに関する情報が検証者に一切漏れておらず、d=1のときにはrに関する情報が検証者に一切漏れていないことに注意されたい。
本手法の健全性は、証明者アルゴリズムPが1組の(c1,c2)、及び、検証者アルゴリズムVが選択する2通りの(α1,α2)について、要求d=0,1に正しく回答した場合に、その回答内容から下記の式(17)〜式(19)を満たすF''''1、F''''2、F'''、r’、z’を計算できるということから保証されている。
上記の鍵生成アルゴリズムGenは、y←F(s)を計算し、公開鍵を(F,y)に設定している。しかし、鍵生成アルゴリズムGenは、(y1,…,ym)←F(s)として、(f1 *(x),…,fm *(x))←(f1(x)−y1,…,fm(x)−ym)を計算し、公開鍵を(f1 *,…,fm *)に設定するように構成されていてもよい。このように変形すると、証明者と検証者との間でy=0として対話プロトコルを実行することが可能になる。
次に、図13を参照しながら、本手法を拡張した公開鍵認証方式(以下、拡張手法)のアルゴリズムについて説明する。図13は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、3パス目に送信する多項式の組F”を1つのハッシュ値c3に変換して検証者に送る方式である。このように拡張することで、対話プロトコルの中で表現サイズの大きい多項式の組F”を検証者に送る確率を半減することが可能になり、通信する平均的なデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図13を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’(x)を生成する。つまり、証明者アルゴリズムPは、(r,F’)←G(w)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。
次いで、証明者アルゴリズムPは、F’(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F’(z),z)を計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w)を計算する。なお、上記のH1(…)、H2(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2)はメッセージである。
検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。
証明者アルゴリズムPは、F”(x)←αF(x+r)+F’(x)を計算する。この計算は、xについての多項式の組F(x+r)を多項式の組F’(x)によりマスクする操作に相当する。さらに、証明者アルゴリズムPは、多項式の組F”のハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(F”(x))を計算する。なお、上記のH3(…)は、ハッシュ関数である。また、ハッシュ値c3はメッセージである。
検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=(z,F”)を生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を(1/2+1/q)以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(1/2+1/q)2以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は(1/2+1/q)Nとなり、Nを十分に大きい数(例えば、N=80)にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にN回実行するアルゴリズムは図14のようになる。以下、図14を参照しながら、並列的に対話プロトコルをN回実行する各アルゴリズムの内容について説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図14を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(5)を実行する。(処理(1))証明者アルゴリズムPは、任意に数wiを選択する。(処理(2))証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’i(x)を生成する。つまり、証明者アルゴリズムPは、(ri,F’i)←G(wi)を計算する。(処理(3))証明者アルゴリズムPは、zi←s−riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。
(処理(4))証明者アルゴリズムPは、F’i(zi)とziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1(F’i(zi),zi)を計算する。(処理(5))証明者アルゴリズムPは、数w’iのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2(w’i)を計算する。
検証者アルゴリズムVは、q通り存在する環Kの元からN個の乱数α1,…,αNを選択する。そして、検証者アルゴリズムVは、選択した乱数α1,…,αNを証明者に送る。
検証者アルゴリズムVは、i=1〜Nについて、F”i(x)←αiF(x+ri)+F’i(x)を計算する。この計算は、xについての多項式の組F(x+ri)を多項式の組F’i(x)によりマスクする操作に相当する。そして、検証者アルゴリズムVは、多項式の組F”1,…,F”Nを検証者に送る。
検証者アルゴリズムVは、i=1〜Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1}(i=1〜N)を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1〜Nについて、以下の(処理1)又は(処理2)を実行する。(処理1)di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。(処理2)di=1の場合、証明者アルゴリズムPは、情報σi=ziを生成する。上記(処理1)又は(処理2)の判定及び処理が実行された後、情報σi(i=1〜N)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σi(i=1〜N)を利用して以下の検証処理を実行する。なお、以下の処理は、i=1〜Nについて実行される。
以下、図15を参照しながら、拡張方式に係る並列化アルゴリズムの内容について説明する。なお、鍵生成アルゴリズムGenの構成については本手法に係る並列化アルゴリズムと同じであるため、詳細な説明を省略する。
まず、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(5)を実行する。(処理(1))証明者アルゴリズムPは、任意に数wiを選択する。(処理(2))証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’i(x)を生成する。つまり、証明者アルゴリズムPは、(ri,F’i)←G(wi)を計算する。(処理(3))証明者アルゴリズムPは、zi←s−riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。
(処理(4))証明者アルゴリズムPは、F’i(zi)とziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1(F’i(zi),zi)を計算する。(処理(5))証明者アルゴリズムPは、数wiのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2(wi)を計算する。
検証者アルゴリズムVは、q通り存在する環Kの元からN個の乱数α1,…,αNを選択する。そして、検証者アルゴリズムVは、選択した乱数α1,…,αNを証明者に送る。
検証者アルゴリズムVは、i−1〜Nについて、F”i(x)←αiF(x+ri)+F’i(x)を計算する。この計算は、xについての多項式の組F(x+ri)を多項式の組F’i(x)によりマスクする操作に相当する。次いで、検証者アルゴリズムVは、多項式の組F”1,…,F”Nのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3(F”1,…,F”N)を計算する。なお、上記のH3(…)は、ハッシュ関数である。また、ハッシュ値c3はメッセージである。
検証者アルゴリズムVは、i=1〜Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求di∈{0,1}(i=1〜N)を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求diに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1〜Nについて、以下の(処理1)又は(処理2)を実行する。(処理1)di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。(処理2)di=1の場合、証明者アルゴリズムPは、情報σi=(zi,F”i)を生成する。上記(処理1)又は(処理2)の判定及び処理が実行された後、情報σi(i=1〜N)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σi(i=1〜N)を利用して以下の検証処理を実行する。なお、以下の処理は、i=1〜Nについて実行される。
さて、上記の第1実施形態に係る対話プロトコルと同様、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性レベルを保証している。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性レベルが確実に保証されているということを保証するには、以下で説明するような条件が必要になる。
これまで5パスの公開鍵認証方式について説明してきた。しかし、本手法においては、検証者から証明者に送られる情報が実際には単なる乱数だけであるため、1パスの公開鍵認証方式(以下、非対話型方式)に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図16に示した。以下、図16を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図16を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、i=1〜Nについて、以下の処理(1)〜処理(5)を実行する。(処理(1))証明者アルゴリズムPは、任意に数wiを選択する。(処理(2))証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Knと多項式の組F’i(x)を生成する。つまり、証明者アルゴリズムPは、(ri,F’i)←G(wi)を計算する。(処理(3))証明者アルゴリズムPは、zi←s−riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。
(処理(4))証明者アルゴリズムPは、Fi(zi)とziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1(Fi(zi),zi)を計算する。(処理(5))証明者アルゴリズムPは、数wiのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2(wi)を計算する。
次に、検証者アルゴリズムVは、乱数RA,RBを選択する。そして、検証者アルゴリズムVは、乱数RAと上記の処理(4)及び(5)で計算されたハッシュ値c1,i,c2,iをハッシュ関数HAに適用してハッシュ値α1,…,αNを生成する。つまり、検証者アルゴリズムVは、(α1,…,αN)←HA(RA,c1,1,…,c2,N)を計算する。
次に、検証者アルゴリズムVは、i=1〜Nについて、以下の処理(1)及び(2)を実行する。(処理(1))証明者アルゴリズムPは、F”i(x)←αiF(x+ri)+F’i(x)を計算する。この計算は、xについての多項式の組F(x+ri)を多項式の組F’i(x)によりマスクする操作に相当する。(処理(2))証明者アルゴリズムPは、i=1〜Nについて、乱数RA,RB、ハッシュ値(c1,i、c2,i)、αi,F”iをハッシュ関数HBに適用してd=(d1,…,dN)を生成する。つまり、証明者アルゴリズムPは、(d1,…,dN)←HB(RA,RB,c1,1,…,c2,N,α1,…,αN,F”1,…,F”N)を計算する。
次に、証明者アルゴリズムPは、生成したdiに応じて検証者に送り返す情報σiを生成する。ここで、証明者アルゴリズムPは、i=1〜Nについて、以下の(処理1)又は(処理2)を実行する。(処理1)di=0の場合、証明者アルゴリズムPは、情報σi=wiを生成する。(処理2)di=1の場合、証明者アルゴリズムPは、情報σi=ziを生成する。上記(処理1)又は(処理2)の判定及び処理が実行された後、RA、RB、c1,i、c2,i、σi(i=1〜N)は、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、まず、証明者から受け取ったRA、c1,i、c2,iをハッシュ関数HAに適用してαiを生成する。つまり、検証者アルゴリズムVは、(α1,…,αN)←HA(RA,c1,1,…,c2,N)を計算する。次いで、検証者アルゴリズムVは、d=(d1,…,dN)←HB(RA,RB,c1,1,…,c2,N,α1,…,αN,F”1,…,F”N)を計算する。次いで、検証者アルゴリズムVは、情報σi(i=1〜N)を利用して以下の検証処理を実行する。なお、以下の処理は、i=1〜Nについて実行される。
ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数多次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
署名生成アルゴリズムSigは、i=1〜Nについて、以下の(処理1)〜(処理11)を実行する。なお、署名生成アルゴリズムSigには、署名鍵sk=sと文書Mが入力されているものとする。
署名検証アルゴリズムVerは、i=1〜Nについて、以下の全ての検証を通過すれば、電子署名σを受理し、1つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムVerには、電子署名σと文書Mが入力されているものとする。まず、署名検証アルゴリズムVerは、α=(α1,…,αN)←HA(RA,M,c1,1,…,c3,N)を計算する。次いで、署名検証アルゴリズムVerは、d=(d1,…,dN)←H(R,M,c1,1,…,c3,N,α,F”1,…,F”N)を計算する。次いで、署名検証アルゴリズムVerは、i=1〜Nについて、以下の(検証1)〜(検証3)を実行する。
次に、図17を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図17は、本手法の具体例を説明するための説明図である。
鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f1(x1,…,xn),…,fm(x1,…,xn)と、ベクトルs=(s1,…,sn)∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=(y1,…,ym)←(f1(s),…,fm(s))を計算する。そして、鍵生成アルゴリズムGenは、(f1,…,fm,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x1,…,xn)をxと表記し、m本のn変数多次多項式(f1(x),…,fm(x))をF(x)と表記する。
次に、図17を参照しながら、対話プロトコルにおける証明者アルゴリズムPと検証者アルゴリズムVによる処理について説明する。この対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵sは、証明者により秘密に管理されているものとする。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組F’(x)=(f’1(x),…,f’m(x))を生成する。つまり、証明者アルゴリズムPは、(r,F’)←G(w)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。但し、多項式f’i(x)は、下記の式(20)のように表現される。
次いで、証明者アルゴリズムPは、F’(z)とzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(F’(z),z)を計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w)を計算する。なお、上記のH1(…)、H2(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2)はメッセージである。
検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。
証明者アルゴリズムPは、F”(x)←αF(x+r)+F’(x)を計算する。この計算は、xについての多項式の組F(x+r)を多項式の組F’(x)によりマスクする操作に相当する。
検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
ここで、上記の第1実施形態と同様、効率の良いアルゴリズムについて考える。例えば、xについての多項式の組F(x+r)をマスクするために用いた多項式の組F’(x)を、2つのベクトルt∈Kn、e∈Kmを用いてF’(x)=Fb(x、t)+eのように表現する方法について考える。この方法を用いると、xについての多項式の組F(x+r)は、下記の式(21)のように表現される。
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kn、t∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、(r,t,e)←G(w)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。
次いで、証明者アルゴリズムPは、Fb(z,t)+eとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1(Fb(z,t)+e,z)を計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2(w)を計算する。なお、上記のH1(…)、H2(…)は、ハッシュ関数である。また、ハッシュ値(c1,c2)はメッセージである。
検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、選択した乱数αを証明者に送る。
証明者アルゴリズムPは、t’←αr+tを計算する。さらに、証明者アルゴリズムPは、e’←α(F(r)−c)+eを計算する。そして、証明者アルゴリズムPは、t’,e’を検証者に送る。
検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムVは、選択した検証パターンを表す要求d∈{0,1}を証明者に送る。
証明者アルゴリズムPは、検証者から受けた要求dに応じて検証者に送り返す情報σを生成する。もしd=0の場合、証明者アルゴリズムPは、情報σ=wを生成する。また、d=1の場合、証明者アルゴリズムPは、情報σ=zを生成する。このようにして生成された情報σは、証明者アルゴリズムPにより検証者に送られる。
検証者アルゴリズムVは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
さて、図18に示した本手法の効率的なアルゴリズムは、その計算効率を維持しながら、図19〜図25に示すようなアルゴリズムに変形することが可能である。
例えば、図18に示した効率的なアルゴリズムのStep.3において、e’←α(F(r)−c)+eという計算を行っているが、この計算を図19に示すようにe’←αF(r)+eという計算に変形してもよい。但し、この変形を行う場合には、Step.6において検証者が行う検証内容の一部を変形する必要がある。具体的には、Step.6においてd=0の場合に検証者が行う検証内容のうち、e’=α(F(r’)−c)+e”の検証をe’=αF(r’)+e”の検証に置き換える必要がある。また、Step.6においてd=1の場合に検証者が行う検証内容のうち、c1=H1(α(F(z’)−y)+Fb(z’,t’’’)+e’’’,z’)の検証をc1=H1(α(F(z’)−c−y)+Fb(z’,t’’’)+e’’’,z’)の検証に置き換える必要がある。
また、図19に示したアルゴリズムのStep.5において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、(t’,e’’)に併せて用いることで(r,t,e)が復元できるような情報であればどのような情報でもよい。例えば、図20に示すように、Step.5においてd=0の場合に設定されるσの内容をrにしてもよい。但し、この変形を行う場合には、図19に示したアルゴリズムのStep.1における計算c2←H2(w)をc2←H2(r,t,e)に変形する必要がある。また、Step.6においてd=0の場合に検証者が行う検証内容をc2=H2(r,t’−αr,e’−αF(r))の検証に置き換える必要がある。
また、図20に示したアルゴリズムのStep.3において、t’←αr+tという計算を行っているが、この計算を図21に示すようにt’←α(r+t)という計算に変形してもよい。但し、この変形を行う場合には、図20に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2(r,α−1t’−r,e’−αF(r))の検証に置き換える必要がある。
また、図20に示したアルゴリズムのStep.3において、e’←αF(r)+eという計算を行っているが、この計算を図22に示すようにe’←α(F(r)+e)という計算に変形してもよい。但し、この変形を行う場合には、図20に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2(r,t’−αr,e’−α−1e’−F(r))の検証に置き換える必要がある。
また、図20に示したアルゴリズムのStep.5において、d=0の場合にσをrに設定しているが、d=0の場合に設定されるσは、(t’,e’’)に併せて用いることで(r,t,e)が復元できるような情報であればどのような情報でもよい。例えば、図23に示すように、Step.5においてd=0の場合に設定されるσの内容をtにしてもよい。但し、この変形を行う場合には、Step.2においてαがα∈RK\{0}から選ばれるようにすると共に、Step.6においてd=0の場合に検証者が行う検証内容をc2=H2(α−1(t’−t),t,e’−αF(α−1(t’−t)))の検証に置き換える必要がある。
また、図23に示したアルゴリズムのStep.3において、t’←αr+tという計算を行っているが、この計算を図24に示すようにt’←α(r+t)という計算に変形してもよい。但し、この変形を行う場合には、図23に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2(α−1t’−t,t,e’−αF(α−1t’−t))の検証に置き換える必要がある。
また、図23に示したアルゴリズムのStep.3において、e’←αF(r)+eという計算を行っているが、この計算を図25に示すようにe’←α(F(r)+e)という計算に変形してもよい。但し、この変形を行う場合には、図23に示したアルゴリズムのStep.6においてd=0の場合に検証者が行う検証内容をc2=H2(α−1(t’−t),t,α−1e’−αF(α−1(t’−t)))の検証に置き換える必要がある。
ところで、上記の第1及び第2実施形態に係る効率的なアルゴリズムは、下記の式(22)で表現される2次の多変数多項式を公開鍵(又はシステムパラメータ)として利用する構成であった。しかし、上記の効率的なアルゴリズムは、位数q=pkの体上で定義される3次以上の多次多変数多項式(下記の式(23)を参照)を公開鍵(又はシステムパラメータ)として利用する構成に拡張することができる。
上記の各アルゴリズムは、例えば、図26に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図26に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、Personal Handy−phone Systemの略である。また、上記のPDAは、Personal Digital Assistantの略である。
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。
上記の鍵生成アルゴリズムGenは、鍵設定部の一例である。上記の証明者アルゴリズムPは、メッセージ送信部、検証パターン受信部、回答送信部、応答受信部、多項式生成部、多項式送信部の一例である。上記の情報σは、回答情報の一例である。上記の検証者アルゴリズムVは、メッセージ受信部、検証パターン選択部、検証パターン送信部、回答受信部、検証部、応答送信部、多項式受信部の一例である。上記の署名生成アルゴリズムSigは、メッセージ生成部、検証パターン選択部、署名生成部の一例である。
P 証明者アルゴリズム
V 検証者アルゴリズム
Sig 署名生成アルゴリズム
Ver 署名検証アルゴリズム
Claims (23)
- s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定部と、
検証装置に対してメッセージcを送信するメッセージ送信部と、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信部と、
k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信部と、
を備え、
前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証装置。 - 前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証装置からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行し、前記検証装置により全ての回答情報で検証が成功した場合に認証が成功する、
請求項1に記載の認証装置。 - 前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証装置からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行する処理を繰り返し、
前記第1〜第3ステップを所定回数実行した結果、前記検証装置により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項2に記載の認証装置。 - 前記メッセージcがc=(c1,…,cm)である場合、
前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージc’=H(c)を算出して、前記検証装置に対してメッセージc’を送信し、
前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証装置が復元することができないメッセージcの要素を送信する、
請求項2又は3に記載の認証装置。 - s∈Knが秘密鍵に設定され、環K上の多次多項式fi(x1,…,xn)(i=1〜m)が公開鍵またはシステムパラメータ、及びyi=fi(s)が公開鍵に設定されており、
証明装置からメッセージcを受信するメッセージ受信部と、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明装置に対して送信する検証パターン送信部と、
k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明装置から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージc、及び前記回答受信部により受信された回答情報を用いて前記証明装置の正当性を検証する検証部と、
を備え、
前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証装置。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定部と、
検証装置に対してメッセージcを送信するメッセージ送信部と、
前記検証装置から応答αを受信する応答受信部と、
前記応答受信部により受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式f”を生成する多項式生成部と、
前記多項式生成部により生成された多項式f”を前記検証装置に送信する多項式送信部と、
1つの前記メッセージcに対するk通り(k≧2)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信部と、
k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信部と、
を備え、
前記回答情報は、2通りの前記応答α、前記多項式f”及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証装置。 - 前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式f”を生成し、前記多項式送信部により当該多項式f”を送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証装置からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行し、前記検証装置により全ての回答情報で検証が成功した場合に認証が成功する、
請求項6に記載の認証装置。 - 前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記応答受信部から応答αを受信する第2ステップ、当該第2ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式f”を生成し、前記多項式送信部により当該多項式f”を送信する第3ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証装置からそれぞれ検証パターンの情報を受信する第4ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第5ステップを実行する処理を繰り返し、
前記第1〜第5ステップを所定回数実行した結果、前記検証装置により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項7に記載の認証装置。 - s∈Knが秘密鍵に設定され、環K上の多次多項式fi(x1,…,xn)(i=1〜m)が公開鍵またはシステムパラメータ、及びyi=fi(s)が公開鍵に設定されており、
証明装置からメッセージcを受信するメッセージ受信部と、
前記証明装置に対して応答αを送信する応答送信部と、
前記応答送信部により送信された応答αを用いて前記証明装置により生成された、前記メッセージcに対する検証に利用される多項式f”を受信する多項式受信部と、
1つの前記メッセージcに対するk通り(k≧2)の検証パターンの中から1つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明装置に対して送信する検証パターン送信部と、
k通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明装置から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージc、前記多項式受信部により受信された多項式f”、及び前記回答受信部により受信された回答情報を用いて前記証明装置の正当性を検証する検証部と、
を備え、
前記回答情報は、2通りの前記応答α、前記多項式f”及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証装置。 - 前記m及びnは、m<nの関係を有する、
請求項1、5、6、9のいずれか1項に記載の認証装置。 - 前記m及びnは、2m−n≪1の関係を有する、
請求項10に記載の認証装置。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定ステップと、
検証装置に対してメッセージcを送信するメッセージ送信ステップと、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、
k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信ステップと、
を含み、
前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証方法。 - s∈Knが秘密鍵に設定され、環K上の多次多項式fi(x1,…,xn)(i=1〜m)が公開鍵またはシステムパラメータ、及びyi=fi(s)が公開鍵に設定されており、
証明装置からメッセージcを受信するメッセージ受信ステップと、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明装置に対して送信する検証パターン送信ステップと、
k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明装置から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージc、及び前記回答受信ステップで受信された回答情報を用いて前記証明装置の正当性を検証する検証ステップと、
を含み、
前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証方法。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定ステップと、
検証装置に対してメッセージcを送信するメッセージ送信ステップと、
前記検証装置から応答αを受信する応答受信ステップと、
前記応答受信ステップで受信された応答αを用いて、前記メッセージcに対する検証に利用される多項式f”を生成する多項式生成ステップと、
前記多項式生成ステップで生成された多項式f”を前記検証装置に送信する多項式送信ステップと、
1つの前記メッセージcに対するk通り(k≧2)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信ステップと、
k通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信ステップと、
を含み、
前記回答情報は、2通りの前記応答α、前記多項式f”及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証方法。 - s∈Knが秘密鍵に設定され、環K上の多次多項式fi(x1,…,xn)(i=1〜m)が公開鍵またはシステムパラメータ、及びyi=fi(s)が公開鍵に設定されており、
証明装置からメッセージcを受信するメッセージ受信ステップと、
前記証明装置に対して応答αを送信する応答送信ステップと、
前記応答送信ステップで送信された応答αを用いて前記証明装置により生成された、前記メッセージcに対する検証に利用される多項式f”を受信する多項式受信ステップと、
1つの前記メッセージcに対するk通り(k≧2)の検証パターンの中から1つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明装置に対して送信する検証パターン送信ステップと、
k通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明装置から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージc、前記多項式受信ステップで受信された多項式f”、及び前記回答受信ステップで受信された回答情報を用いて前記証明装置の正当性を検証する検証ステップと、
を含み、
前記回答情報は、2通りの前記応答α、前記多項式f”及び前記k通りの回答情報を用いて実施した前記メッセージcに対する計2k通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵sが計算可能となる情報である、
認証方法。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定機能と、
検証装置に対してメッセージcを送信するメッセージ送信機能と、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信機能と、
k通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信機能と、
をコンピュータに実現させるためのプログラムであり、
前記回答情報は、前記k通りの回答情報を用いて実施した前記メッセージcに対するk通りの検証パターンが全て成功した場合に秘密鍵sが計算可能となる情報である、
プログラム。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定部と、
前記多次多項式fi(x1,…,xn)及び前記秘密鍵sに基づいてN個のメッセージcを生成するメッセージ生成部と、
文書M及び前記メッセージcを一方向性関数に適用して得られた情報に基づいて、kN通り(k≧3)の検証パターンの中から検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージc及び前記文書Mを用いた検証を通過するような電子署名σを生成する署名生成部と、
を備え、
前記電子署名σは、前記(k−1)N+1通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵sが計算可能となる情報である、
署名生成装置。 - 前記メッセージ生成部により生成された単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン選択部により検証パターンを選択する第2ステップ、それぞれの検証パターンの情報に対して前記署名生成部により電子署名σを送信する第3ステップを実行し、電子署名σを用いて実施した検証が全て成功した場合に認証が成功する、
請求項17に記載の署名生成装置。 - 前記m及びnは、m<nの関係を有する、
請求項17に記載の署名生成装置。 - 前記多次多項式fiは2次多項式である、
請求項17に記載の署名生成装置。 - s∈Knを秘密鍵に設定し、環K上の多次多項式fi(x1,…,xn)(i=1〜m)を公開鍵またはシステムパラメータ、及びyi=fi(s)を公開鍵に設定する鍵設定部と、
検証装置に対してメッセージcを送信するメッセージ送信部と、
1つの前記メッセージcに対するk通り(k≧3)の検証パターンの中から前記検証装置により選択された1つの検証パターンの情報を受信する検証パターン受信部と、
k通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証装置に送信する回答送信部と、
を備え、
前記回答情報は、前記秘密鍵sをr∈Knによりマスクした情報z∈Knと、前記rをt∈Knによりマスクしたt’∈Knと、前記多次多項式fiに前記rを代入したfi(r)をei∈Kによりマスクしたei’∈Kを用いて計算される情報である、
認証装置。 - 前記メッセージ送信部により単数又は複数のメッセージcを送信する第1ステップ、それぞれのメッセージcに対して前記検証パターン受信部により前記検証装置からそれぞれ検証パターンの情報を受信する第2ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第3ステップを実行し、前記検証装置により全ての回答情報で検証が成功した場合に認証が成功する、
請求項21に記載の認証装置。 - 前記多次多項式fiは2次多項式である、
請求項1、5、6、9、21のいずれか1項に記載の認証装置。
Priority Applications (4)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2011026401A JP5736816B2 (ja) | 2010-05-31 | 2011-02-09 | 認証装置、認証方法、プログラム、及び署名生成装置 |
US13/111,696 US8522033B2 (en) | 2010-05-31 | 2011-05-19 | Authentication device, authentication method, program, and signature generation device |
CN201110145023.8A CN102263638B (zh) | 2010-05-31 | 2011-05-24 | 认证设备、认证方法和签名生成设备 |
US13/934,946 US8959355B2 (en) | 2010-05-31 | 2013-07-03 | Authentication device, authentication method, program, and signature generation device |
Applications Claiming Priority (5)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2010125026 | 2010-05-31 | ||
JP2010125026 | 2010-05-31 | ||
JP2010224753 | 2010-10-04 | ||
JP2010224753 | 2010-10-04 | ||
JP2011026401A JP5736816B2 (ja) | 2010-05-31 | 2011-02-09 | 認証装置、認証方法、プログラム、及び署名生成装置 |
Publications (3)
Publication Number | Publication Date |
---|---|
JP2012098690A JP2012098690A (ja) | 2012-05-24 |
JP2012098690A5 JP2012098690A5 (ja) | 2014-03-27 |
JP5736816B2 true JP5736816B2 (ja) | 2015-06-17 |
Family
ID=45010112
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2011026401A Active JP5736816B2 (ja) | 2010-05-31 | 2011-02-09 | 認証装置、認証方法、プログラム、及び署名生成装置 |
Country Status (3)
Country | Link |
---|---|
US (2) | US8522033B2 (ja) |
JP (1) | JP5736816B2 (ja) |
CN (1) | CN102263638B (ja) |
Families Citing this family (21)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP5790288B2 (ja) * | 2011-08-12 | 2015-10-07 | ソニー株式会社 | 情報処理装置、及び情報処理方法 |
JP2014048414A (ja) * | 2012-08-30 | 2014-03-17 | Sony Corp | 情報処理装置、情報処理システム、情報処理方法及びプログラム |
JP2014050064A (ja) * | 2012-09-04 | 2014-03-17 | Sony Corp | 情報処理装置、情報処理システム、情報処理方法、プログラム及びクライアント端末 |
JP2014090372A (ja) | 2012-10-31 | 2014-05-15 | Sony Corp | 情報処理装置、情報処理システム、情報処理方法及びコンピュータプログラム |
EP2930880A4 (en) | 2012-12-05 | 2016-08-03 | Sony Corp | INFORMATION PROCESSOR, VERIFICATION PROCESSOR, INFORMATION PROCESSING METHOD, VERIFICATION PROCESSING METHOD, AND PROGRAM |
CN103888256B (zh) * | 2012-12-24 | 2018-01-05 | 国民技术股份有限公司 | 一种密码钥匙的认证方法及系统 |
JP2015033038A (ja) | 2013-08-05 | 2015-02-16 | ソニー株式会社 | 情報処理装置、情報処理方法及びコンピュータプログラム |
JPWO2015019821A1 (ja) | 2013-08-05 | 2017-03-02 | ソニー株式会社 | 情報処理装置、情報処理方法及びコンピュータプログラム |
CN104348624B (zh) * | 2013-08-09 | 2018-02-02 | 阿里巴巴集团控股有限公司 | 一种哈希认证可信度的方法和装置 |
CN103780383B (zh) | 2014-01-13 | 2017-05-31 | 华南理工大学 | 一种基于超球面的多变量公钥签名/验证系统及方法 |
JP2015194947A (ja) | 2014-03-31 | 2015-11-05 | ソニー株式会社 | 情報処理装置及びコンピュータプログラム |
CN105100034B (zh) * | 2014-05-23 | 2018-09-11 | 阿里巴巴集团控股有限公司 | 一种网络应用中访问功能的方法和设备 |
CN105701392B (zh) * | 2015-12-31 | 2020-10-27 | 联想(北京)有限公司 | 信息处理方法及电子设备 |
CN105515754B (zh) * | 2016-01-06 | 2018-10-30 | 飞天诚信科技股份有限公司 | 一种rsa-crt签名方法及装置 |
WO2018076377A1 (zh) * | 2016-10-31 | 2018-05-03 | 华为技术有限公司 | 一种数据传输方法、终端、节点设备以及系统 |
JP6629466B2 (ja) * | 2017-01-20 | 2020-01-15 | 日本電信電話株式会社 | 秘密計算システム、秘密計算装置、秘密計算方法、プログラム |
JP7101031B2 (ja) * | 2018-04-13 | 2022-07-14 | 株式会社bitFlyer Blockchain | ブロックチェーン・ネットワーク及びそのための確定方法 |
CZ308885B6 (cs) * | 2019-09-26 | 2021-08-04 | Univerzita Tomáše Bati ve Zlíně | Systém ověření identity a licencí pro práci s vysoce citlivými daty |
KR102364047B1 (ko) * | 2019-11-19 | 2022-02-16 | 기초과학연구원 | 구조화된 행렬들에 기초한 공개키 암호를 위한 방법과 장치 |
JP7273742B2 (ja) * | 2020-02-07 | 2023-05-15 | 株式会社東芝 | 暗号化装置、復号装置、暗号方法、復号方法、暗号化プログラム及び復号プログラム |
WO2021262716A1 (en) * | 2020-06-23 | 2021-12-30 | Ntt Research Inc. | Tamper-resistant data encoding secure against unbounded polynomial size attack complexity |
Family Cites Families (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP3484069B2 (ja) * | 1998-02-27 | 2004-01-06 | 日本電信電話株式会社 | 秘密情報認証方法及び合同多項式認証方法並びに当該認証プログラムを記録した記録媒体 |
US7308097B2 (en) * | 2001-12-07 | 2007-12-11 | Ntru Cryptosystems, Inc. | Digital signature and authentication method and apparatus |
JP4575283B2 (ja) * | 2005-11-15 | 2010-11-04 | 株式会社東芝 | 暗号装置、復号装置、プログラム及び方法 |
FR2899702A1 (fr) * | 2006-04-10 | 2007-10-12 | France Telecom | Procede et dispositif pour engendrer une suite pseudo-aleatoire |
CN101277186B (zh) * | 2007-03-30 | 2011-06-15 | 北京握奇数据系统有限公司 | 利用非对称密钥算法实现外部认证的方法 |
-
2011
- 2011-02-09 JP JP2011026401A patent/JP5736816B2/ja active Active
- 2011-05-19 US US13/111,696 patent/US8522033B2/en active Active
- 2011-05-24 CN CN201110145023.8A patent/CN102263638B/zh active Active
-
2013
- 2013-07-03 US US13/934,946 patent/US8959355B2/en active Active
Also Published As
Publication number | Publication date |
---|---|
CN102263638B (zh) | 2016-08-10 |
US8959355B2 (en) | 2015-02-17 |
CN102263638A (zh) | 2011-11-30 |
US8522033B2 (en) | 2013-08-27 |
JP2012098690A (ja) | 2012-05-24 |
US20130297930A1 (en) | 2013-11-07 |
US20110296188A1 (en) | 2011-12-01 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP5736816B2 (ja) | 認証装置、認証方法、プログラム、及び署名生成装置 | |
JP5593850B2 (ja) | 認証装置、認証方法、プログラム、及び署名生成装置 | |
JP2013042315A (ja) | 情報処理装置、及び情報処理方法 | |
JP5790289B2 (ja) | 情報処理装置、情報処理方法、プログラム、及び記録媒体 | |
KR101986392B1 (ko) | 정보 처리 장치, 정보 처리 방법, 및 기록 매체 | |
JP5594034B2 (ja) | 認証装置、認証方法、及びプログラム | |
JP5790291B2 (ja) | 情報処理装置、署名提供方法、署名検証方法、プログラム、及び記録媒体 | |
JP5790286B2 (ja) | 情報処理装置、署名生成装置、情報処理方法、署名生成方法、及びプログラム | |
JP5790290B2 (ja) | 情報処理装置、情報処理方法、プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体 | |
JP5790288B2 (ja) | 情報処理装置、及び情報処理方法 | |
WO2013024628A1 (ja) | 情報処理装置、及び情報処理方法 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20140210 |
|
A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20140210 |
|
A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20141126 |
|
A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20150106 |
|
A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20150306 |
|
TRDD | Decision of grant or rejection written | ||
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20150324 |
|
A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20150406 |
|
R151 | Written notification of patent or utility model registration |
Ref document number: 5736816 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R151 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |