本人確認システム
【課題】秘密情報の漏洩の可能性が低く、低資源装置に好適な、有限回数の本人確認処理を実現する、本人確認システムを提供する。
【解決手段】ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、ｇのオーダー（位数）の倍数に設定した。応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【解決手段】ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、ｇのオーダー（位数）の倍数に設定した。応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本人確認システムに適用して好適な技術に関する。
より詳細には、ＲＦＩＤに代表される、演算能力及び記憶容量が限られるデバイスで、有限回数の本人確認動作を実現する技術に関する。
【背景技術】
【０００２】
現在、市場ではＩＣカードやＲＦＩＤ（Radio Frequency IDentification）等の、超小型の認証機能を備える装置が広く使われている。これらの装置はその認証機能によって、本人であることを確認した上で、次の動作へ移行する。ＩＣカードであれば、それは金銭の入出金であり、ＲＦＩＤであれば、貼付されている商品の流通の許可等である。
なお、これ以降、ＩＣカードやＲＦＩＤ等の、演算能力と記憶容量が限られている装置を「低資源装置」と呼ぶ。
【０００３】
情報技術の進歩により、これら電子的な認証機能を備える装置が広く流通していると共に、逆にその認証機能を破ろうとする、悪意ある者の脅威も増大しつつある。認証機能の根幹は暗号であり、コンピュータ等の情報処理装置の演算能力の進歩が、暗号を破る技術としても利用されるからである。
【０００４】
本発明に関連する先行技術文献を、非特許文献１、非特許文献２、非特許文献３及び非特許文献４に示す。
【非特許文献１】Schnorr, C.-P. Efficient Identification and Signatures for Smart Cards. In CRYPTO ’89 (1990), vol. 435 of Lecture Notes in Computer Science, Springer, pp. 235.251.
【非特許文献２】Girault, M. Self-certified public keys. In EUROCRYPT ’91 (1992), vol. 4547 of Lecture Notes on Computer Science, Springer, pp. 490.497.
【非特許文献３】Girault, M., Poupard, G., and Stern, J. On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order. Journal of Cryptology 19, 4 (October 2006), 463.487.
【非特許文献４】K.W.Campbell, M.J.Wiener, "DES is not a group", CRYPTO'92.
【非特許文献５】科学 第７８巻 第１０号『暗号への脅威「サイドチャネル攻撃」とその対策』崎山一男、太田和夫、pp.1080-1083(2008/10/1)
【非特許文献６】現代暗号 (シリーズ・情報科学の数学) 、岡本龍明、山本博資、pp.119-122(1997/6/30)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ＩＣカードの認証機能で使われる暗号は、非特許文献４で開示される、トリプルＤＥＳと呼ばれる共通鍵暗号が広く使われている。
一般に、共通鍵暗号方式は、秘密鍵を通信者同士（証明者装置と検証者装置）が保管しなければならず、通信者同士の通信から秘密鍵の漏洩を防ぐために、通信者同士の通信路に秘匿性を確保する必要がある。また、検証者装置の秘密鍵の管理を厳重にする必要がある。
そこで、通信路の秘匿性をなくしてもよく、検証者装置側の秘密鍵の管理が不要である公開鍵暗号方式を、ＩＣカードやＲＦＩＤに採用しようとする議論が、暗号の関係者で活発に行われている。
【０００６】
非特許文献１に開示される「Ｓｃｈｎｏｒｒ方式」は、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性は完全にない。しかしながら、装置の電流変化や演算時間の相違等から秘密鍵を類推するサイドチャネル攻撃に対抗するために、証明者装置で剰余演算と位数算出（オーダー関数）を実行する必要がある。つまり、証明者装置に対して高い演算能力を要求する。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
なお、サイドチャネル攻撃については例えば非特許文献５にその詳細が記されている。
【０００７】
非特許文献２及び非特許文献３に開示される「ＧＰＳ方式」は、Ｓｃｈｎｏｒｒ方式と比べると、証明者装置では剰余演算や位数算出を実行する必要がない。つまり、証明者装置に対して高い演算能力を要求しないので、演算能力の点ではＳｃｈｎｏｒｒ方式より有利である。
しかし、証明者装置と検証者装置との間の通信路から、秘密情報が漏洩する可能性が完全にない、とは言い切れない。また、証明者装置の内部の演算処理から秘密情報の漏洩の可能性を払拭するために、証明者装置の内部に保持する情報のビット数を大きくせざるを得ず、証明者装置に要求される記憶容量が大きくなってしまう。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【０００８】
本発明はかかる点に鑑みてなされたものであり、秘密情報の漏洩の可能性が低く、低資源装置に好適な、有限回数の本人確認処理を実現する、本人確認システムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明の本人確認システムは、秘密鍵ｓと秘密鍵に対応する公開鍵Ｉと定数Ａ及び定数Ｂとを生成すると共に、ハッシュ関数を利用してコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を生成するセンターと、生成された公開鍵Ｉと定数Ｂとセンターで利用されるハッシュ関数とを利用して証明処理を実行する検証者装置と、生成された秘密鍵ｓと定数Ａとコミットメント数列とを記憶する記憶部と、検証者装置にコミットメント値ｘを送信し、検証者装置からチャレンジ数ｃを受信し、検証者装置にレスポンス値ｙを送信する入出力制御部と、秘密鍵ｓと定数Ａと乱数ｒと、受信したチャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａをレスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、よりなるものである。
【００１０】
サイドチャネル攻撃を防ぐために、Ｓｃｈｎｏｒｒ方式では証明者装置で剰余演算と位数算出（オーダー関数）を実行することで対応していた。一方で、ＧＰＳ方式では証明者装置で演算する数値のビット数を多く取ることで対応していた。
本発明では、ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、群Ｇの元ｇのオーダー（位数）の倍数に設定した。
応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。
証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【発明の効果】
【００１１】
本発明により、秘密情報の漏洩の可能性が低く、低資源装置に好適な、有限回数の本人確認処理を実現する、本人確認システムを提供できる。
【発明を実施するための最良の形態】
【００１２】
本実施形態を説明する前に、本実施形態で説明する本人確認システムと、これに用いるＲＦＩＤ（Radio Frequency IDentification）の概略を説明する。
ＲＦＩＤは、その名の通り、電波を用いて本人識別を実行する装置である。およそ数ｍｍ乃至数ｃｍ程度の極小型にて形成され、電波そのものを駆動電源として利用する。また、大量生産され、使い捨てを容認する程度の低コストで作られる。このため、内部に形成される集積回路は、低コスト且つ超低消費電力を実現する必要があるため、その演算能力及び記憶容量は低く抑えられている。これ以降、本実施形態では、このように演算能力と記憶容量が限られている装置を「低資源装置」と呼ぶ。
本実施形態に係る本人確認システムは、ＲＦＩＤに代表される低資源装置に対し、実施回数を限定した（有限回数の）本人確認動作を実現する。
【００１３】
無線タグとも呼ばれるＲＦＩＤは、主に物流の現場で、商品に貼付されて利用される。物流の要所で、正規の物品であることを証明するための「本人確認動作」を実行するために利用される。このような利用状況から、本実施形態の本人確認システムでは、低資源装置に有限回数の本人確認動作を実現することを目的として構築されている。
【００１４】
前述の「有限回数」については、物流の現場の状況に応じて変化する。
例えば、ある物流システムでは、商品が生産拠点から三箇所の問屋を経て商店に到達するので、最低五回以上は証明処理ができなければならない。
しかし、別の物流システムでは、生産拠点から産地直送で商店に到達するので、最低二回の証明処理ができれば足りる、と考えることができる。
本実施形態では、このような現場の状況に柔軟に対応できる、有限回数の本人確認動作を実現する仕組みを提供する。
【００１５】
以下、本発明の実施の形態を、図１〜図１７を参照して説明する。なお、本実施形態の説明は、図面毎に以下の構成を採る。
［システム全体構成］図１
［システム全体の処理の流れ］図２、図３
［センター］図４
［センター：定数演算部］図５、図６
［センター：群生成器］図７、図８
［センター：応答定数生成器］図９、図１０
［センター：コミットメント数列生成部］図１１、図１２
［証明者装置］図１３
［証明者装置：演算処理部］図１４、図１５
［検証者装置］図１６、図１７
［証明処理］
［サイドチャネル攻撃に対する耐性］
［従来技術との比較］
【００１６】
［システム全体構成］
図１は、本発明の一実施形態の例である、本人確認システム１０１の概略図である。この本人確認システム１０１は、ＲＦＩＤを量産する図示しない工場と、工場で生産されたＲＦＩＤ（証明者装置）１０２と、生産されたＲＦＩＤが正しく製造された装置であるか否かを検証する、検証者装置１０３とで構成される。更に、工場内には、証明者装置１０２を生産する段階の途中で、発明者が発明した本人確認方式を実践するために必要な「定数」を生成し、記録する装置として、センター１０４が設けられている。
つまり、本人確認システム１０１は、センター１０４と、証明者装置１０２と、検証者装置１０３の三者で構成されている。
【００１７】
センター１０４は、最初に幾つかの定数を算出して、検証者装置１０３に送信する。図１では、「Ｉ」、「Ｂ」、「ｇ」、「ｐ」「Ｈａｓｈ（）」という定数と関数名が、センター１０４から検証者装置１０３に送られている。これら変数及び関数名の詳細は後述する。
検証者装置１０３は、センター１０４から受信した定数等を記憶する。
以上が、証明者装置１０２を生産する前の準備段階である。この段階は、後述する図２（ａ）に相当する。
【００１８】
次に、センター１０４は証明者装置１０２の生産処理を行う。この生産処理は、最初の段階で算出した幾つかの定数と、証明者装置１０２毎にユニークな数列を、入出力インターフェース１０５を通じて証明者装置１０２に記録する。図１では、生産工程の端的な表現として、センター１０４は、ベルトコンベア１０６上に並べられて移動する証明者装置１０２（ＲＦＩＤ）に対し、「Ａ」、「ｓ」という定数と、「｛（ｘ１，ｒ１），．．．（ｘｔ，ｒｔ）｝」という数列を記録する。これら変数及び数列の詳細は後述する。
以上が、証明者装置１０２の生産段階である。この段階は、後述する図２（ｂ）に相当する。
【００１９】
工場で生産された後の証明者装置１０２は、検証者装置１０３によって「本人確認処理」が行われる。例えば、証明者装置１０２がＲＦＩＤの場合は、当該ＲＦＩＤが貼付された商品が、物流の途中で検証者装置１０３による検証が行われる。
検証者装置１０３は、入出力インターフェース１０７を介して証明者装置１０２にアクセスし、証明者装置１０２が正しく工場で生産されたものなのか、つまり、悪意の第三者による改竄なく、センター１０４が生成した所定の定数が記憶されている、正規の物品であるか否かを検証する。検証の結果、正規の物品である、つまり「本人である」ことが確認できたら、検証者装置１０３は「本人である」旨の判定結果を出力する。逆に、検証の結果、正規の物品でない、つまり「本人でない」ことが確認できたら、検証者装置１０３は「本人でない」旨の判定結果を出力する。
以上が、検証者装置１０３による証明者装置１０２の本人確認段階である。この段階は、後述する図３に相当する。
【００２０】
［システム全体の処理の流れ］
図２（ａ）及び（ｂ）は、センター１０４と検証者装置１０３と証明者装置１０２との処理の大まかな流れを示すシーケンス図である。説明の便宜のため、図４を参照しつつ説明する。
図２（ａ）は、証明者装置１０２を生産する前の準備段階の流れを示すシーケンス図である。
先ず、センター１０４は、図４にて後述する定数演算部４０２を稼動して、定数演算処理を行う（Ｓ２０１）。
定数演算処理によって生成された定数Ｉ、Ｂ、ｇ、ｐは、検証者装置１０３に送信される（Ｓ２０２）。検証者装置１０３は、定数Ｉ、Ｂ、ｇ、ｐを受信すると、これを記憶する（Ｓ２０３）。
【００２１】
次に、センター１０４は、図４にて後述する検証仕様決定部４０３を稼動して、検証仕様決定処理を行う（Ｓ２０４）。
検証仕様決定処理によって決定されたハッシュ関数Ｈａｓｈの仕様（種類）は、検証者装置１０３に送信される（Ｓ２０５）。検証者装置１０３は、受信したハッシュ関数Ｈａｓｈの種類を内部に設定する（Ｓ２０６）。
【００２２】
周知のように、ハッシュ関数は任意長のデータ入力を受けて、固定長のデータを出力する関数である。現代の暗号技術は膨大なデータ量を扱うことが多いので、主にそのデータ量を削減しつつ、セキュリティを維持するために用いられる。データ量の削減は、暗号を扱う装置の記憶容量を削減するだけでなく、演算ステップ数を削減する効果がある。
多くの場合、ハッシュ関数はプログラムで実現される。特に、本実施形態のように、センター１０４と検証者装置１０３がハッシュ関数を交換可能な装置として構成するならば、殆どの場合、パソコンやワークステーション等の計算機に、所定のプログラムを実行させることで構築することが多い。したがって、センター１０４で選択したハッシュ関数Ｈａｓｈは、そのプログラムをモジュールとして検証者装置１０３に転送してもよい。
【００２３】
センター１０４と検証者装置１０３で利用されるハッシュ関数は、以下の条件を満たす必要がある。
（１）ハッシュ値が与えられたときにその入力を求めるのが困難であること。
（２）ある入力に対する出力と同じ値を出力するような異なる入力を求めるのが困難であること。
（３）同じ値を出力するような異なる入力の組を求めるのが困難であること。
以上の条件を満たす必要があるため、例えばハッシュ関数の入力を推測可能なＭＤ５等は、本実施形態における実装にはそぐわないといえる。
上記条件を満たすハッシュ関数は、例えば周知のＳＨＡ−１や、特開２００８−２３３６６１号公報に開示されているもの等が挙げられる。
【００２４】
なお、「ハッシュ関数を決定する」という行為は、必ずしも複数のハッシュ関数から一つを選択する、という動作を必要とする訳ではない。本人確認システム１０１の全体の仕様として、使用するハッシュ関数を最初から一つだけに固定化してしまっても一向に構わない。大事なことは、センター１０４の中（図４及び図１１にて後述するコミットメント数列生成部４０４）及び検証者装置１０３の中で使用するハッシュ関数器は、同じものでなければならない、ということである。
【００２５】
次に、図２（ｂ）は、証明者装置１０２の生産段階の流れを示すシーケンス図である。
センター１０４は、図４にて後述するコミットメント数列生成部４０４を稼動して、証明者装置１０２に記録させるためのコミットメント数列を生成する（Ｓ２０７）。その際、先の定数演算処理にて生成された定数Ａ、ｇ、ｐと、準備段階で実行した検証仕様決定処理（Ｓ２０４）にて決定されたハッシュ関数Ｈａｓｈと、コミットメント数列レコード数ｔを受け取り、これら定数等を用いてコミットメント数列を生成する。
コミットメント数列とは、乱数ｒとこれに対応するコミットメント値ｘの組（ｘ，ｒ）よりなるレコードがｔ個あるテーブル｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝である。
【００２６】
次に、センター１０４は、コミットメント数列生成部４０４によって生成されたコミットメント数列と、先の定数演算処理（Ｓ２０１）にて生成された定数Ａ、ｓとを、図４にて後述する定数記録部４０５を通じて、証明者装置１０２に記録する（Ｓ２０８）。一方、証明者装置１０２は、センター１０４から定数Ａ、ｓとコミットメント数列を受信すると、これを内部の後述するＲＯＭに記憶する（Ｓ２０９）。
上述のステップＳ２０７、Ｓ２０８及びＳ２０９の処理は、証明者装置１０２を一個生産する毎に繰り返される（Ｓ２１０、Ｓ２１１、Ｓ２１２）。
【００２７】
生産段階において、センター１０４から証明者装置１０２に転送される情報のうち、秘密鍵ｓとコミットメント数列｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝は、秘密情報である。これら情報は、外部に漏れてはならない。
一方、生産段階において、センター１０４から証明者装置１０２に転送される情報のうち、応答定数Ａは、公開情報である。つまり、外部に漏れても問題ない。
また、準備段階においてセンター１０４で生成される情報のうち、Ｂ、ｇ、ｐ、Ｉも公開情報である。
したがって、証明処理の段階では、秘密情報は証明者装置１０２の内部にのみ存在し、検証者装置１０３には存在しない。
【００２８】
図３は証明者装置１０２と検証者装置１０３との間で行われる、検証処理の流れを示すシーケンス図である。
検証者装置１０３は、証明者装置１０２に対してコミットメント値ｘを要求する（Ｓ３０１）。証明者装置１０２は、検証者装置１０３から送られたコミットメント要求に呼応して、コミットメント値ｘを送信する（Ｓ３０２）。検証者装置１０３は、コミットメント値ｘを受信すると、これを一旦内部に記憶する（Ｓ３０３）。
次に、検証者装置１０３はチャレンジ数ｃを生成し、これを証明者装置１０２に送信する（Ｓ３０４）。証明者装置１０２は、チャレンジ数ｃを受信すると、これを基に応答値ｙを生成し、検証者装置１０３に送信する（Ｓ３０５）。検証者装置１０３は受信した応答値ｙと、先に記憶していたコミットメント値ｘ、先に送信したチャレンジ数ｃ等を用いて、証明者装置１０２が正規の装置であるのかを検証する。検証した結果は、所定の処理機構等に出力する（Ｓ３０６）。
【００２９】
前述の「所定の処理機構」は、様々な態様が考えられる。
例えば、商品流通の仕組みにおいては、本実施形態に係るＲＦＩＤを貼付した商品をチェックしていて、もし当該ＲＦＩＤの改竄が認められた場合、当該商品の流通を緊急的に停止させ、悪意ある改竄がどこで行われたかを調査することが考えられる。単に対象品を除外する等の物理的な処理に留まらず、追跡調査を行う等の人間社会行動的な処理も含む。
つまり、検証者装置１０３の検証結果は、最低限アラームとして表示するか、何らかの稼動状態を停止させる等の処理のいずれかを実行し得るトリガとなる。
【００３０】
［センター１０４］
図４はセンター１０４のブロック図である。
定数演算部４０２は、図２（ａ）の準備段階で稼動する機能ブロックである。所定の演算処理を実行して、Ａ、Ｂ、ｇ、ｓ、ｐ、Ｉを出力する。
検証仕様決定部４０３は、図２（ａ）の準備段階で稼動する機能ブロックである。後述のコミットメント数列生成部４０４と検証者装置１０３で共通に使用するハッシュ関数の種類を決定すると共に、コミットメント数列生成部４０４で生成するコミットメント数列のレコード数ｔを決定する。
コミットメント数列生成部４０４は、図２（ｂ）の生産段階で稼動する機能ブロックである。定数演算部４０２からＡ、ｇ、ｐを受け取り、検証仕様決定部４０３にて決定されたハッシュ関数を用いて、ｔ個のレコード数のコミットメント数列を生成する。
定数記録部４０５は、図２（ｂ）の生産段階で稼動する機能ブロックである。定数演算部４０２からＡ、ｓを受け取り、コミットメント数列生成部４０４が生成したコミットメント数列を、証明者装置１０２に送信して、記録させる。
【００３１】
［センター１０４：定数演算部４０２］
図５はセンター１０４内部の定数演算部４０２のブロック図であり、図６は定数演算部４０２の処理の流れを説明するフローチャートである。
処理を開始すると（Ｓ６０１）、先ず、基礎定数生成器５０２は、初期基本定数ｑと、秘密鍵範囲Ｓと、チャレンジ数範囲Ｂを、以下の条件で作成する。
【００３２】
Ｓ＜ｑ≦ＢＳ 但し、ｑ，Ｓ：１６０ビット以上、Ｂ：３５ビット以上
【００３３】
作成されたｑ、Ｓ、Ｂは、それぞれｑ記憶部５０３、Ｓ記憶部５０４、Ｂ記憶部５０５に一時的に記憶される。各々の記憶部はＲＡＭやレジスタで構成される。
【００３４】
秘密鍵範囲Ｓは、後述する秘密鍵ｓを乱数で生成する際の最大値を規定するので、なるべく大きな値であることが望ましい。
【００３５】
次に、初期基本定数ｑを基に、群生成器５０６にて群Ｇの元ｇ及び剰余演算の法ｐを生成する（Ｓ６０３）。なお、ステップＳ６０３のｇ，ｐ生成処理は、群Ｇの全ての元を算出することなく、効率よくｇを算出する処理である。
次に、ｑ、Ｓ及びＢを基に、応答定数生成器５０７にて応答定数Ａを生成する（Ｓ６０４）。
次に、秘密鍵範囲Ｓを基に、秘密鍵生成器５０８にて秘密鍵ｓを生成する（Ｓ６０５）。秘密鍵生成器５０８の実体は乱数発生器であり、０〜Ｓ−１の範囲の乱数を指定する。
なお、ステップＳ６０３、Ｓ６０４及びＳ６０５は、順番を問わない。
【００３６】
作成されたｐ、ｇ、ｓ、Ａは、それぞれｐ記憶部５１４、ｇ記憶部５０９、ｓ記憶部５１０、Ａ記憶部５１１に一時的に記憶される。各々の記憶部はＲＡＭやレジスタで構成される。
【００３７】
次に、ｇ、ｐとｓを基に、公開鍵生成器５１２にて公開鍵Ｉを生成する（Ｓ６０６）。公開鍵Ｉは、以下の式で算出する。
【００３８】
Ｉ＝ｇ−ｓｍｏｄ ｐ
【００３９】
なお、「ｍｏｄ」は剰余演算を意味する。この、公開鍵Ｉの演算は、ｇ−ｓの値に対し、更に群演算を実行した結果である。本実施形態における群演算は、法ｐを用いた剰余演算である。
作成されたＩは、Ｉ記憶部５１３に一時的に記憶される。Ｉ記憶部５１３もＲＡＭやレジスタで構成される。
【００４０】
以上、作成された各定数は、それぞれ以下の三箇所に出力される。
先ず、ｇ、Ｉ、Ｂ、ｐは、検証者装置１０３に出力される（Ｓ６０７）。
次に、Ａ、ｇ、ｐが、コミットメント数列生成部４０４に出力される（Ｓ６０８）。
最後に、Ａとｓが、定数記録部４０５へ出力される（Ｓ６０９）。
これら出力処理が終わると、定数演算部４０２の処理が終了する（Ｓ６１０）。
【００４１】
［センター１０４：群生成器５０６］
図７は定数演算部４０２内の群生成器５０６のブロック図であり、図８は群生成器５０６の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ８０１）、先ず、乱数発生器７０２は乱数ωを生成する。
次に、乱数ωは素数判定器７０３によって素数であるか否かが判定される（Ｓ８０３）。素数でなければ、素数判定器７０３は再度乱数発生器７０２を起動させ、新たな乱数ωを生成させる。つまり、任意の素数を素数判定器７０３というフィルタを通じて出力する。
素数である乱数ωは、数値「２」７０４と、ｑ記憶部５０３内のｑと共に、乗算器７０５で乗算される。その後、加算器７０６で数値「１」７０７が加算される。つまり、以下の式を実行する（Ｓ８０４）：
【００４２】
ｐ＝２ｑω＋１
【００４３】
算出した値ｐは、素数判定器７０８で素数か否かが判定される（Ｓ８０５）。素数でなければ（Ｓ８０５のＮＯ）、再度ステップＳ８０２に戻り、乱数発生器７０２から処理のやり直しが行われる。素数であれば、一旦ｐ記憶部５１４に記憶される。
【００４４】
次に、数値「２」７０９とω記憶部７１０に記憶されているωを乗算器７１１で乗算した値で、数値「２」７１２をべき乗器７１３にてべき乗する。この値を、ステップＳ８０５で得たｐをｐ記憶部５１４から読み出して、剰余演算器７１５にて剰余を算出する。つまり、以下の式を実行する（Ｓ８０６）：
【００４５】
ｇ＝２２ωｍｏｄ ｐ
【００４６】
上述の式で算出した値が、群Ｇの元ｇと、本実施形態の群演算として用いる剰余演算の法ｐである。このｇ及びｐを出力して（Ｓ８０７）、処理を終了する（Ｓ８０８）。
【００４７】
なお、乱数発生器７０２は、任意の整数の乱数を作成すればよい。後述する他の乱数発生器（図１１の乱数発生器１１０３及び図１６の乱数発生器１６０４）とは異なり、乱数発生範囲は限定されない。
【００４８】
なお、群生成器５０６の演算処理により、ｇｑｍｏｄ ｐ＝１が必ず成立する。ｑは「ｇの位数」と呼ばれており、「ｏｒｄ（ｇ）」と記す。
【００４９】
［センター１０４：応答定数生成器５０７］
図９は定数演算部４０２内の応答定数生成器５０７のブロック図であり、図１０は応答定数生成器５０７の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１００１）、先ず、Ｂ記憶部５０５に格納されているＢと、Ｓ記憶部５０４に格納されているＳを、乗算器９０２で乗算する（Ｓ１００２）。この値をｕとする。
次に、カウンタ変数ｍ９０３を初期値「０」９０４で初期化する（Ｓ１００３）。
これ以降はループ処理である。
先ず、数値「２」９０５をべき乗器９０６により、カウンタ変数ｍ９０３から得られる変数ｍでべき乗し、乗算器９０７にてｑ記憶部５０３から得られるｑと乗算する。つまり、以下の式を実行する（Ｓ１００４）：
【００５０】
Ａ＝２ｍｑ
【００５１】
算出した値Ａを、比較器９０８で先のステップＳ１００２にて算出した値ｕと比較する（Ｓ１００５）。比較の結果、Ａがｕ以上でない、つまりＡがｕよりも小さい場合は（Ｓ１００５のＮＯ）、カウンタ変数ｍ９０３をインクリメントし（Ｓ１００６）、再度ステップＳ１００４の式を演算する。
ステップＳ１００５でＡがｕ以上であれば（Ｓ１００５のＹＥＳ）、この値を応答定数Ａとして出力し（Ｓ１００７）、処理を終了する（Ｓ１００８）。
【００５２】
図９の比較器９０８の出力は、真のときにカウンタ変数ｍ９０３をインクリメントする。これがステップＳ１００５のＮからステップＳ１００６に相当する。
比較器９０８の出力が偽のときには、ＮＯＴゲート９０９で反転され、スイッチ９１０をオン制御する。これがステップＳ１００５のＹからステップＳ１００７に相当する。
【００５３】
以上のような手順にて、応答定数生成器５０７で算出した応答定数Ａは、ｑに２ｍを乗算した数であるので、Ａはｑで割り切れる。また、ＢとＳとの乗算値ｕと比較しているため、Ａ≧ＢＳが保障される。
前述のように、ｑはｇの位数（オーダー）であるので、Ａはｏｒｄ（ｇ）で割り切れる。
【００５４】
［センター１０４：コミットメント数列生成部４０４］
図１１はセンター１０４内のコミットメント数列生成部４０４のブロック図であり、図１２はコミットメント数列生成部４０４の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１２０１）、先ず制御部１１０２内の図示しないカウンタ変数ｉを１に初期化する（Ｓ１２０２）。
次に、制御部１１０２によって乱数発生器１１０３が起動されると、乱数発生器１１０３は０〜Ａ−１の範囲内で乱数を生成する（Ｓ１２０３）。この乱数をｒｉ（ｉ番目のｒ）とする。
次に、重複確認部１１０４は、乱数発生器１１０３が出力した乱数ｒｉが、既に乱数使用リスト１１０５に登録されているか否かを確認する（Ｓ１２０４）。もし既に登録済みであれば（Ｓ１２０４のＮＯ）、重複確認部１１０４は再度乱数発生器１１０３を起動させて（Ｓ１２０３）、乱数使用リスト１１０５内の乱数との重複のない乱数ｒｉを得る（Ｓ１２０４のＹＥＳ）。
重複確認部１１０４は、乱数使用リスト１１０５内の乱数との重複のない乱数ｒｉを得たら、これを乱数使用リスト１１０５に登録する（Ｓ１２０５）。
【００５５】
乱数ｒｉはｇと共にべき乗器１１０６に与えられる。べき乗器１１０６はｇをｒｉでべき乗する。べき乗した値は更に、本実施形態の群演算とも言える剰余演算器１１１０によってｐ記憶部５１４の法ｐを用いた剰余演算が行われる。そして、この値はハッシュ関数器１１０７に与えられ、ハッシュ値ｘｉを得る。つまり、以下の式を実行する（Ｓ１２０６）：
【００５６】
【数１】
【００５７】
この時点で得られた（ｘｉ，ｒｉ）の組を、一旦一時リスト１１０８に出力し、保持する（Ｓ１２０７）。
次に、制御部１１０２は内部に保持しているカウンタ変数ｉがレコード数ｔ１１０９以上か否かを確認する（Ｓ１２０８）。もしｔ以上でなければ、カウンタ変数ｉをインクリメントし（Ｓ１２０９）、再度乱数発生器１１０３から一連の処理を繰り返す（Ｓ１２０３）。
カウンタ変数ｉがレコード数ｔ１１０９と等しくなれば、必要なレコード数ｔ１１０９だけ、コミットメント値ｘと乱数ｒの組が、一時リスト１１０８に保持されたこととなる。そこで、一時リスト１１０８の内容を定数記録部４０５に出力し（Ｓ１２１０）、一連の処理を終了する（Ｓ１２１１）。
【００５８】
［証明者装置１０２］
図１３は、証明者装置１０２のブロック図である。
入出力制御部１３０２は、センター１０４や検証者装置１０３とのデータの送受信と、証明者装置１０２全体の制御を行う。
入出力制御部１３０２には、ＥＥＰＲＯＭよりなるカウンタ変数格納部１３０３と、ＲＯＭ１３０４と、演算処理部１３０５が接続されている。
カウンタ変数格納部１３０３は、カウンタ変数ｉを格納している。ｉの初期値は「１」であり、最終値は「ｔ」である。カウンタ変数ｉは、ＲＯＭ１３０４内に格納されているコミットメント数列１３０６のレコード番号を指し示すポインタである。
また、ＲＯＭ１３０４にはセンター１０４から受け取った秘密鍵ｓと応答定数Ａが、それぞれＲＯＭ１３０４内の所定の領域に、ｓ記憶部１３０７及びＡ記憶部１３０８として格納されている。
【００５９】
演算処理部１３０５は、入出力制御部１３０２とＲＯＭ１３０４から演算処理に必要な値を受け取り、レスポンス値ｙを出力する。
【００６０】
以下、図３を参照して、入出力制御部１３０２を中心とする証明者装置１０２の全体の動作を説明する。
入出力制御部１３０２は、検証者装置１０３からコミットメント要求を受信すると（Ｓ３０１）、カウンタ変数格納部１３０３内のカウンタ変数ｉを読み込む。そして、ＲＯＭ１３０４内に格納されているコミットメント数列１３０６のｉ番目のレコードのコミットメント値ｘｉを読み込み、これを検証者装置１０３に出力する（Ｓ３０２）。
この後、入出力制御部１３０２は、検証者装置１０３からチャレンジ数ｃが送信されるのを待つ。つまり、受信待ちである。
入出力制御部１３０２は、検証者装置１０３から送信された（Ｓ３０４）チャレンジ数ｃを受信すると、コミットメント数列１３０６のｉ番目のレコードの乱数ｒｉと、受信したチャレンジ数ｃを演算処理部１３０５に渡す。
演算処理部１３０５は、ＲＯＭ１３０４内に格納されている秘密鍵ｓと応答定数Ａを読み出し、チャレンジ数ｃと乱数ｒｉと共に、後述する演算処理を行い、レスポンス値ｙを算出する。
レスポンス値ｙは、入出力制御部１３０２によって検証者装置１０３に送信される（Ｓ３０５）。
【００６１】
［証明者装置１０２：演算処理部１３０５］
図１４は証明者装置１０２内の演算処理部１３０５のブロック図であり、図１５は演算処理部１３０５の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１５０１）、先ずコミットメント数列１３０６から読み出した乱数ｒｉから減算器１４０３でＡを引いて、一時変数ｒ’を算出する（Ｓ１５０２）。なお、図１４では説明の便宜のため、コミットメント数列１３０６から読み出したｒｉをｒｉ記憶部１４０２に一旦格納している
と共に、一時変数ｒ’をｒ’記憶部１４０４に一旦格納している。
次に、ｃとｓを乗算器１４０５で乗算し、一時変数ｙ’を算出する（Ｓ１５０３）。なお、図１４では説明の便宜のため、検証者装置１０３から送信されたチャレンジ数ｃをｃ記憶部１４０６に一旦格納していると共に、一時変数ｙ’をｙ’記憶部１４０７に一旦格納している。
次に、ｒｉとｙ’を加算器１４０８で加算し、一時変数ｙ０を算出する（Ｓ１５０４）。
次に、ｒ’とｙ’を加算器１４０９で加算し、一時変数ｙ１を算出する（Ｓ１５０５）。
【００６２】
次に、比較器１４１０で一時変数ｙ１と数値「０」１４１１を比較し、一時変数ｙ１が０未満、つまり負の値であるか確認する（Ｓ１５０６）。もし負の値ならば（Ｓ１５０６のＹＥＳ）、比較器１４１０の判定出力によって、スイッチ１４１２はｙとしてｙ０を選択する（Ｓ１５０７）。もし正の値ならば（Ｓ１５０６のＮＯ）、スイッチ１４１２はｙとしてｙ１を選択する（Ｓ１５０８）。
そして、ｙを出力し（Ｓ１５０９）、一連の処理を終了する（Ｓ１５１０）。
【００６３】
［検証者装置１０３］
図１６は検証者装置１０３のブロック図であり、図１７は検証者装置１０３の検証処理の流れを示すフローチャートである。
入出力制御部１６０２は、証明者装置１０２とのデータの送受信と、検証者装置１０３全体の制御を行う。
入出力制御部１６０２には、証明者装置１０２から受信するコミットメント値ｘを一時的に格納するｘ記憶部１６０３と、乱数発生器１６０４と、乱数発生器１６０４が生成したチャレンジ数ｃを記憶するｃ記憶部１６０５と、証明者装置１０２から受信するレスポンス値ｙを一時的に格納するｙ記憶部１６０６が接続されている。
【００６４】
乱数発生器１６０４は、チャレンジ数範囲Ｂを記憶するＢ記憶部１６０７からチャレンジ数範囲Ｂを得て、０〜Ｂ−１の範囲の乱数を生成する。これはチャレンジ数ｃとして証明者装置１０２に送信される。
ｃはＩ記憶部１６０８に格納されているＩと共にべき乗器１６０９にてべき乗が算出される。べき乗器１６０９の出力は、本実施形態の群演算とも言える剰余演算器１６１５にて、ｐ記憶部１６１７から供給される法ｐで剰余演算が行われる。
一方、ｙはｇ記憶部１６１０から得られるｇと共にべき乗器１６１１にてべき乗が算出される。べき乗器１６１１の出力は、本実施形態の群演算とも言える剰余演算器１６１６にて、ｐ記憶部１６１７から供給される法ｐで剰余演算が行われる。
この、それぞれの剰余演算器１６１５及び１６１６の出力が共に乗算器１６１２に供給され、乗算される。
乗算器１６１２の出力はハッシュ関数器１６１３に入力され、ハッシュ値が出力される。
このハッシュ値が、コミットメント値ｘと比較される。
一致検出器１６１４はコミットメント値ｘとハッシュ値との一致を検証し、一致していれば「１」を、一致していなければ「０」を出力する。これが判定出力となる。
【００６５】
以下、図３を参照して、入出力制御部１６０２を中心とする検証者装置１０３の全体の動作を説明する。
最初に、入出力制御部１６０２は証明者装置１０２に対しコミットメント要求を送信する（Ｓ３０１）。
そして、入出力制御部１６０２は、証明者装置１０２からコミットメント値ｘが送信されるのを待つ。
入出力制御部１６０２は、証明者装置１０２からコミットメント値ｘを受信したら、これを一旦ｘ記憶部１６０３に保持する（Ｓ３０３）。この後、乱数発生器１６０４を稼動させ、チャレンジ数ｃを証明者装置１０２へ送信する（Ｓ３０４）。
そして、入出力制御部１６０２は、証明者装置１０２からレスポンス値ｙが送信されるのを待つ。
入出力制御部１６０２は、証明者装置１０２からレスポンス値ｙを受信すると、検証処理を行い、得られた値とコミットメント値ｘとの一致を確認し、一致／不一致を出力する（Ｓ３０６）。
【００６６】
図１６と図１７を参照して、検証処理を説明する。
証明者装置１０２からレスポンス値ｙを受信すると（Ｓ１７０１）、べき乗器１６０９、べき乗器１６１１、剰余演算器１６１５、剰余演算器１６１６、乗算器１６１２及びハッシュ関数器１６１３を稼動させ、以下の式に記す演算処理を行う（Ｓ１７０２）：
【００６７】
Ｚ＝Ｈａｓｈ（（ｇｙｍｏｄ ｐ）（Ｉｃｍｏｄ ｐ））
【００６８】
次に、先に受信して保持してあるコミットメント値ｘと、算出したＺとを比較器９０８で比較する（Ｓ１７０３）。
値が一致していれば、証明者装置１０２は正当なものであると判断し、「１」を出力する（Ｓ１７０４）。
値が一致していなければ、証明者装置１０２は不正なものであると判断し、「０」を出力する（Ｓ１７０５）。
そして、一連の処理を終了する（Ｓ１７０６）。
【００６９】
［証明処理］
検証者装置１０３と証明者装置１０２が実行する証明処理について、以下、簡単に説明する。
コミットメント値ｘは、図１１にて説明したコミットメント数列生成部４０４によって、乱数ｒから以下の数式で生成される：
【００７０】
ｘ＝Ｈａｓｈ（ｇｒｍｏｄ ｐ）
【００７１】
一方、証明者装置１０２は、検証者装置１０３が乱数発生器１６０４で作成して送信したチャレンジ数ｃを受信すると、演算処理部１３０５で以下の数式でｙを算出する：
【００７２】
ｙ＝ｒ＋ｃｓ
【００７３】
更に、センター１０４の定数演算部４０２内の公開鍵生成器５１２では、秘密鍵ｓと群Ｇの元ｇから、公開鍵Ｉを以下の数式で算出する：
【００７４】
Ｉ＝ｇ−ｓｍｏｄ ｐ
【００７５】
以上より、以下のように算出できる：
【００７６】
ｇｙｍｏｄ ｐＩｃｍｏｄ ｐ＝ｇｒ＋ｃｓｍｏｄ ｐ（ｇ−ｓ）ｃｍｏｄ ｐ
＝ｇｒ＋ｃｓｍｏｄ ｐｇ−ｃｓｍｏｄ ｐ
＝ｇｒ＋ｃｓ−ｃｓｍｏｄ ｐ＝ｇｒｍｏｄ ｐ
∴ｇｙｍｏｄ ｐＩｃｍｏｄ ｐ＝ｇｒｍｏｄ ｐ
∴Ｈａｓｈ（ｇｒｍｏｄ ｐ）＝Ｈａｓｈ（（ｇｙｍｏｄ ｐ）（Ｉｃｍｏｄ ｐ））
【００７７】
次に、本実施形態で利用している「ｙ’−Ａ」という数式の意味を説明する。
【００７８】
【数２】
【００７９】
［サイドチャネル攻撃に対する耐性］
本来なら、証明者装置１０２は単純に内部の演算処理部で「ｙ＝ｒ＋ｃｓ」という演算処理を行えば、容易にレスポンス値ｙを算出できる。
しかし、この計算ステップでは、サイドチャネル攻撃の一種である、タイミング解析攻撃ならびに単純電力解析攻撃に対して脆弱である。そこで、この演算処理をマスキングするために、応答定数Ａという要素を加え、演算処理をやや複雑にすることで、タイミング解析攻撃ならびに単純電力解析攻撃を回避する。
ところが、もし、証明者装置１０２が以下に記すプログラムの処理を行うと、サイドチャネル攻撃の一種である、タイミング解析攻撃ならびに単純電力解析攻撃に対して脆弱である：
【００８０】
ｙ’＝ｒ＋ｃｓ #変数ｙ’にｒ＋ｃｓを代入する。
ｉｆ（ｙ’＜Ａ）｛ #ｙ’がＡより小さければ、
ｙ＝ｙ’ #ｙはｙ’を出力する。
｝ｅｌｓｅ｛ #さもなくば、
ｙ＝ｙ’−Ａ #ｙはｙ’−Ａを出力する。
｝
【００８１】
なお、上述のプログラムの「#（井桁）」以降は、コメントである。
上述のプログラムでは、ｙ’がＡとの大小関係に応じて、ｙ’−Ａという演算を行う場合と行わない場合とで、演算処理ステップ数の差が生じる。
タイミング解析攻撃ならびに単純電力解析攻撃とは、暗号鍵などのセキュリティパラメータ値によって暗号の演算時間が異なるような実装が行われた場合に、この演算時間を観測することによって、セキュリティパラメータの値を逆算する攻撃法である。この攻撃法に対処するには、どのようなセキュリティパラメータの値であっても、常に同じ時間で暗号化や復号化等の演算処理が完了するように実装する必要がある。
【００８２】
そこで、本実施形態の証明者装置１０２では、以下のプログラムで示される演算手順を行う：
【００８３】
ｒ’＝ｒｉ−Ａ #図１５のステップＳ１５０２
ｙ’＝ｃｓ #Ｓ１５０３
ｙ０＝ｒｉ＋ｙ’ #Ｓ１５０４
ｙ１＝ｒ’＋ｙ’ #Ｓ１５０５
ｉｆ（ｙ１＜０）｛ #Ｓ１５０６：ｙ１が０より小さければ、
ｙ＝ｙ０ #Ｓ１５０７：ｙはｙ０を出力する。
｝ｅｌｓｅ｛ #さもなくば、
ｙ＝ｙ１ #Ｓ１５０８：ｙはｙ１を出力する。
｝
【００８４】
以上の処理手順により、ｙ１の値の如何にかかわらず、証明者装置１０２の演算処理部は常に同じ演算ステップ数を実行することとなるので、タイミング解析攻撃ならびに単純電力解析攻撃に対する脆弱性は十分に低減できる。
【００８５】
［従来技術との比較］
本実施形態の本人確認システムと、従来技術の本人確認システムとを比較する。
「Ｓｃｈｎｏｒｒ方式」（非特許文献１参照）と呼ばれる、公開鍵暗号を用いた本人確認方法は、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性は完全にない。しかしながら、サイドチャネル攻撃に対抗するために、証明者装置で剰余演算と位数算出（オーダー関数）を実行する必要がある。つまり、証明者装置に対して高い演算能力を要求する。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【００８６】
「ＧＰＳ方式」（非特許文献２及び非特許文献３参照）と呼ばれる、公開鍵暗号を用いた本人確認方法は、Ｓｃｈｎｏｒｒ方式と比べると、証明者装置では剰余演算や位数算出を実行する必要がない。つまり、証明者装置に対して高い演算能力を要求しないので、演算能力の点ではＳｃｈｎｏｒｒ方式より有利である。
しかし、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性が完全にない、とは言い切れない。また、証明者装置の内部の演算処理で、レスポンス値ｙを算出する「ｙ＝ｒ＋ｃｓ」という演算がそのまま外部から見えてしまう。そこで、乱数ｒを生成する範囲を示す応答定数Ａを、ｃｓの値の範囲であるＢＳよりも大幅に大きくしなければならない。このため、必然的にコミットメント数列の一部を構成する乱数ｒのビット数を大きくせざるを得ず、証明者装置に要求される記憶容量が大きくなってしまう。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【００８７】
本実施形態の本人確認システムでは、上述のＳｃｈｎｏｒｒ方式とＧＰＳ方式がそれぞれ抱える欠点を、両方共解決している。
本実施形態の本人確認システムは、Ｓｃｈｎｏｒｒ方式と同様に、サイドチャネル攻撃に対して堅牢である。
証明者装置に要求される記憶容量は、Ｓｃｈｎｏｒｒ方式と比べると、およそ１１％程度の増加で済む。
証明者装置が必要とする演算手段は、ＧＰＳ方式と同様、加算器と乗算器だけで済む。
したがって、証明者装置に要求されるハードウェア資源が極めて軽く、ＲＦＩＤ等の低資源装置に適する。
【００８８】
本実施形態には、以下のような応用例が考えられる。
（１）証明者装置１０２内のコミットメント数列のポインタである、カウンタ変数格納部１３０３内のカウンタ変数ｉを強制的に動かして、コミットメント数列を使用不能にすると、証明者装置１０２の再利用を防止できる。
このことを実現させるために、証明者装置１０２の入出力制御部１３０２に、検証者装置１０３から発行された特定のコマンドを受信すると、カウンタ変数格納部１３０３内のカウンタ変数ｉを、コミットメント数列１３０６のレコード数ｔを超える数、或は「０」等の、コミットメント数列１３０６のレコード番号を指し示さない値に書き換える処理を追加する。
【００８９】
（２）センター１０４内の定数演算部４０２が生成した各種定数はそのままに、検証仕様決定部４０３でハッシュ関数だけを異ならせると、コミットメント数列生成部４０４からは全く異なるコミットメント数列を出力することができるので、定数演算部４０２が生成した各種定数をハッシュ関数の種類毎に使い回すことができる。
【００９０】
（３）実施形態では低資源装置の代表的なものとして、ＲＦＩＤを例に挙げて説明したが、低資源装置はこれに限られない。電気的に直接接続可能な電極を備えるＩＣカード等も、本実施形態で用いる低資源装置として適用可能である。
【００９１】
（４）図２（ｂ）に示した生産段階では、証明者装置１０２を一個作る度に、コミットメント数列生成処理（Ｓ２０７、Ｓ２１０）を実施していた。つまり、コミットメント数列生成部４０４を、証明者装置１０２を一個作る度に動作させていた。しかし、コミットメント数列｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝は、乱数ｒと、これに対応する値ｘとの組み合わせであるので、証明者装置１０２の生産段階の前に、予め生産数とｔを乗じたレコード数だけ「作り置き」してもよい。
【００９２】
（５）本実施形態では、証明者装置の演算処理におけるサイドチャネル攻撃の脅威から秘密鍵の漏洩を防ぐために、群の性質を利用して、演算ステップを隠蔽するための応答定数Ａを採用している。
ここで、本実施形態では、群演算に素数ｐを法とする剰余演算を採用した。
群演算は、本実施形態で開示した剰余演算に限られない。
周知のように、暗号の世界では、群（有限体或は有限群とも呼ぶ）における離散対数問題の解の困難さを利用するアルゴリズムが多く利用される。したがって、本実施形態で採用した剰余演算に代えて、このようなアルゴリズムに基づく群演算を採用することができる。
一例としては、楕円曲線暗号が挙げられる。多種多様な楕円曲線暗号のアルゴリズムのうちの一例としては、楕円ＥｌＧａｍａｌ暗号で用いられる次の楕円曲線上の有理点を，群演算として採用することができる：
【００９３】
Ｅｑ（ａ，ｂ）：ｙ２＝ｘ３＋ａｘ＋ｂ
【００９４】
また、この際、群生成器５０６の仕様も併せて変更する必要が生じる。つまり、剰余演算の法ｐを決定することと同様に、楕円曲線暗号では、適切な楕円曲線を選ぶ演算処理が必要になる。これは、非特許文献６に開示されているように、ランダムに曲線を定めた後、曲線の位数（オーダー）、すなわち曲線状の点の数を計算する。この計算処理は、現状ではＳｃｈｏｏｆのアルゴリズム及びその変形を利用することとなる。
【００９５】
本実施形態においては、本人確認システムを開示した。
サイドチャネル攻撃を防ぐために、Ｓｃｈｎｏｒｒ方式では証明者装置で剰余演算と位数算出（オーダー関数）を実行することで対応していた。一方で、ＧＰＳ方式では証明者装置で演算する数値のビット数を多く取ることで対応していた。
本実施形態では、ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、群Ｇの元ｇのオーダー（位数）の倍数に設定した。
応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。
証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【００９６】
ＲＦＩＤ等の低資源装置を用いる、有限回数の本人確認処理を行うシステムで、本実施形態は、低資源装置に対して極めて少ない演算能力と、従来技術と同等の記憶容量で、実用的な本人確認処理を実現できる。
更に、本実施形態の本人確認システムは、サイドチャネル攻撃に対しても強いので、セキュリティ面で堅牢な本人確認処理を実現できる。
【００９７】
以上、本発明の実施形態例について説明したが、本発明は上記実施形態例に限定されるものではなく、特許請求の範囲に記載した本発明の要旨を逸脱しない限りにおいて、他の変形例、応用例を含む。
【図面の簡単な説明】
【００９８】
【図１】本発明の一実施形態の例である、本人確認システムの概略図である。
【図２】センターと検証者装置と証明者装置との処理の大まかな流れを示すシーケンス図である。
【図３】証明者装置と検証者装置との間で行われる、検証処理の流れを示すシーケンス図である。
【図４】センターのブロック図である。
【図５】センター内部の定数演算部のブロック図である。
【図６】定数演算部の処理の流れを説明するフローチャートである。
【図７】定数演算部内の群生成器のブロック図である。
【図８】群生成器の処理の流れを示すフローチャートである。
【図９】定数演算部内の応答定数生成器のブロック図である。
【図１０】応答定数生成器の処理の流れを示すフローチャートである。
【図１１】センター内のコミットメント数列生成部のブロック図である。
【図１２】コミットメント数列生成部の処理の流れを示すフローチャートである。
【図１３】証明者装置のブロック図である。
【図１４】証明者装置内の演算処理部のブロック図である。
【図１５】演算処理部の処理の流れを示すフローチャートである。
【図１６】検証者装置のブロック図である。
【図１７】検証者装置の検証処理の流れを示すフローチャートである。
【符号の説明】
【００９９】
１０１…本人確認システム、１０２…証明者装置、１０３…検証者装置、１０４…センター、１０５…入出力インターフェース、１０６…ベルトコンベア、１０７…入出力インターフェース、４０２…定数演算部、４０３…検証仕様決定部、４０４…コミットメント数列生成部、４０５…定数記録部、５０２…基礎定数生成器、５０３…ｑ記憶部、５０４…Ｓ記憶部、５０５…Ｂ記憶部、５０６…群生成器、５０７…応答定数生成器、５０８…秘密鍵生成器、５０９…ｇ記憶部、５１０…ｓ記憶部、５１１…Ａ記憶部、５１２…公開鍵生成器、５１３…Ｉ記憶部、５１４…ｐ記憶部、７０２…乱数発生器、７０３…素数判定器、７０４…数値「２」、７０５…乗算器、７０６…加算器、７０７…数値「１」、７０８…素数判定器、７０９…数値「２」、７１０…ω記憶部、７１１…乗算器、７１２…数値「２」、７１３…べき乗器、７１５…剰余演算器、９０２…乗算器、９０３…カウンタ変数ｍ、９０４…初期値「０」、９０５…数値「２」、９０６…べき乗器、９０７…乗算器、９０８…比較器、１１０２…制御部、１１０３…乱数発生器、１１０４…重複確認部、１１０５…乱数使用リスト、１１０６…べき乗器、１１０７…ハッシュ関数器、１１０８…一時リスト、１１０９…レコード数ｔ、１３０２…入出力制御部、１３０３…カウンタ変数格納部、１３０４…ＲＯＭ、１３０５…演算処理部、１３０６…コミットメント数列、１３０７…ｓ記憶部、１３０８…Ａ記憶部、１４０２…ｒｉ記憶部、１４０３…減算器、１４０４…ｒ’記憶部、１４０５…乗算器、１４０６…ｃ記憶部、１４０７…ｙ’記憶部、１４０８…加算器、１４０９…加算器、１４１０…比較器、１４１１…数値「０」、１４１２…スイッチ、１６０２…入出力制御部、１６０３…ｘ記憶部、１６０４…乱数発生器、１６０５…ｃ記憶部、１６０６…ｙ記憶部、１６０７…Ｂ記憶部、１６０８…Ｉ記憶部、１６０９…べき乗器、１６１０…ｇ記憶部、１６１１…べき乗器、１６１２…乗算器、１６１３…ハッシュ関数器、１６１４…一致検出器、１６１５、１６１６…剰余演算器、１６１７…ｐ記憶部
【技術分野】
【０００１】
本発明は、本人確認システムに適用して好適な技術に関する。
より詳細には、ＲＦＩＤに代表される、演算能力及び記憶容量が限られるデバイスで、有限回数の本人確認動作を実現する技術に関する。
【背景技術】
【０００２】
現在、市場ではＩＣカードやＲＦＩＤ（Radio Frequency IDentification）等の、超小型の認証機能を備える装置が広く使われている。これらの装置はその認証機能によって、本人であることを確認した上で、次の動作へ移行する。ＩＣカードであれば、それは金銭の入出金であり、ＲＦＩＤであれば、貼付されている商品の流通の許可等である。
なお、これ以降、ＩＣカードやＲＦＩＤ等の、演算能力と記憶容量が限られている装置を「低資源装置」と呼ぶ。
【０００３】
情報技術の進歩により、これら電子的な認証機能を備える装置が広く流通していると共に、逆にその認証機能を破ろうとする、悪意ある者の脅威も増大しつつある。認証機能の根幹は暗号であり、コンピュータ等の情報処理装置の演算能力の進歩が、暗号を破る技術としても利用されるからである。
【０００４】
本発明に関連する先行技術文献を、非特許文献１、非特許文献２、非特許文献３及び非特許文献４に示す。
【非特許文献１】Schnorr, C.-P. Efficient Identification and Signatures for Smart Cards. In CRYPTO ’89 (1990), vol. 435 of Lecture Notes in Computer Science, Springer, pp. 235.251.
【非特許文献２】Girault, M. Self-certified public keys. In EUROCRYPT ’91 (1992), vol. 4547 of Lecture Notes on Computer Science, Springer, pp. 490.497.
【非特許文献３】Girault, M., Poupard, G., and Stern, J. On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order. Journal of Cryptology 19, 4 (October 2006), 463.487.
【非特許文献４】K.W.Campbell, M.J.Wiener, "DES is not a group", CRYPTO'92.
【非特許文献５】科学 第７８巻 第１０号『暗号への脅威「サイドチャネル攻撃」とその対策』崎山一男、太田和夫、pp.1080-1083(2008/10/1)
【非特許文献６】現代暗号 (シリーズ・情報科学の数学) 、岡本龍明、山本博資、pp.119-122(1997/6/30)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ＩＣカードの認証機能で使われる暗号は、非特許文献４で開示される、トリプルＤＥＳと呼ばれる共通鍵暗号が広く使われている。
一般に、共通鍵暗号方式は、秘密鍵を通信者同士（証明者装置と検証者装置）が保管しなければならず、通信者同士の通信から秘密鍵の漏洩を防ぐために、通信者同士の通信路に秘匿性を確保する必要がある。また、検証者装置の秘密鍵の管理を厳重にする必要がある。
そこで、通信路の秘匿性をなくしてもよく、検証者装置側の秘密鍵の管理が不要である公開鍵暗号方式を、ＩＣカードやＲＦＩＤに採用しようとする議論が、暗号の関係者で活発に行われている。
【０００６】
非特許文献１に開示される「Ｓｃｈｎｏｒｒ方式」は、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性は完全にない。しかしながら、装置の電流変化や演算時間の相違等から秘密鍵を類推するサイドチャネル攻撃に対抗するために、証明者装置で剰余演算と位数算出（オーダー関数）を実行する必要がある。つまり、証明者装置に対して高い演算能力を要求する。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
なお、サイドチャネル攻撃については例えば非特許文献５にその詳細が記されている。
【０００７】
非特許文献２及び非特許文献３に開示される「ＧＰＳ方式」は、Ｓｃｈｎｏｒｒ方式と比べると、証明者装置では剰余演算や位数算出を実行する必要がない。つまり、証明者装置に対して高い演算能力を要求しないので、演算能力の点ではＳｃｈｎｏｒｒ方式より有利である。
しかし、証明者装置と検証者装置との間の通信路から、秘密情報が漏洩する可能性が完全にない、とは言い切れない。また、証明者装置の内部の演算処理から秘密情報の漏洩の可能性を払拭するために、証明者装置の内部に保持する情報のビット数を大きくせざるを得ず、証明者装置に要求される記憶容量が大きくなってしまう。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【０００８】
本発明はかかる点に鑑みてなされたものであり、秘密情報の漏洩の可能性が低く、低資源装置に好適な、有限回数の本人確認処理を実現する、本人確認システムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明の本人確認システムは、秘密鍵ｓと秘密鍵に対応する公開鍵Ｉと定数Ａ及び定数Ｂとを生成すると共に、ハッシュ関数を利用してコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を生成するセンターと、生成された公開鍵Ｉと定数Ｂとセンターで利用されるハッシュ関数とを利用して証明処理を実行する検証者装置と、生成された秘密鍵ｓと定数Ａとコミットメント数列とを記憶する記憶部と、検証者装置にコミットメント値ｘを送信し、検証者装置からチャレンジ数ｃを受信し、検証者装置にレスポンス値ｙを送信する入出力制御部と、秘密鍵ｓと定数Ａと乱数ｒと、受信したチャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａをレスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、よりなるものである。
【００１０】
サイドチャネル攻撃を防ぐために、Ｓｃｈｎｏｒｒ方式では証明者装置で剰余演算と位数算出（オーダー関数）を実行することで対応していた。一方で、ＧＰＳ方式では証明者装置で演算する数値のビット数を多く取ることで対応していた。
本発明では、ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、群Ｇの元ｇのオーダー（位数）の倍数に設定した。
応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。
証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【発明の効果】
【００１１】
本発明により、秘密情報の漏洩の可能性が低く、低資源装置に好適な、有限回数の本人確認処理を実現する、本人確認システムを提供できる。
【発明を実施するための最良の形態】
【００１２】
本実施形態を説明する前に、本実施形態で説明する本人確認システムと、これに用いるＲＦＩＤ（Radio Frequency IDentification）の概略を説明する。
ＲＦＩＤは、その名の通り、電波を用いて本人識別を実行する装置である。およそ数ｍｍ乃至数ｃｍ程度の極小型にて形成され、電波そのものを駆動電源として利用する。また、大量生産され、使い捨てを容認する程度の低コストで作られる。このため、内部に形成される集積回路は、低コスト且つ超低消費電力を実現する必要があるため、その演算能力及び記憶容量は低く抑えられている。これ以降、本実施形態では、このように演算能力と記憶容量が限られている装置を「低資源装置」と呼ぶ。
本実施形態に係る本人確認システムは、ＲＦＩＤに代表される低資源装置に対し、実施回数を限定した（有限回数の）本人確認動作を実現する。
【００１３】
無線タグとも呼ばれるＲＦＩＤは、主に物流の現場で、商品に貼付されて利用される。物流の要所で、正規の物品であることを証明するための「本人確認動作」を実行するために利用される。このような利用状況から、本実施形態の本人確認システムでは、低資源装置に有限回数の本人確認動作を実現することを目的として構築されている。
【００１４】
前述の「有限回数」については、物流の現場の状況に応じて変化する。
例えば、ある物流システムでは、商品が生産拠点から三箇所の問屋を経て商店に到達するので、最低五回以上は証明処理ができなければならない。
しかし、別の物流システムでは、生産拠点から産地直送で商店に到達するので、最低二回の証明処理ができれば足りる、と考えることができる。
本実施形態では、このような現場の状況に柔軟に対応できる、有限回数の本人確認動作を実現する仕組みを提供する。
【００１５】
以下、本発明の実施の形態を、図１〜図１７を参照して説明する。なお、本実施形態の説明は、図面毎に以下の構成を採る。
［システム全体構成］図１
［システム全体の処理の流れ］図２、図３
［センター］図４
［センター：定数演算部］図５、図６
［センター：群生成器］図７、図８
［センター：応答定数生成器］図９、図１０
［センター：コミットメント数列生成部］図１１、図１２
［証明者装置］図１３
［証明者装置：演算処理部］図１４、図１５
［検証者装置］図１６、図１７
［証明処理］
［サイドチャネル攻撃に対する耐性］
［従来技術との比較］
【００１６】
［システム全体構成］
図１は、本発明の一実施形態の例である、本人確認システム１０１の概略図である。この本人確認システム１０１は、ＲＦＩＤを量産する図示しない工場と、工場で生産されたＲＦＩＤ（証明者装置）１０２と、生産されたＲＦＩＤが正しく製造された装置であるか否かを検証する、検証者装置１０３とで構成される。更に、工場内には、証明者装置１０２を生産する段階の途中で、発明者が発明した本人確認方式を実践するために必要な「定数」を生成し、記録する装置として、センター１０４が設けられている。
つまり、本人確認システム１０１は、センター１０４と、証明者装置１０２と、検証者装置１０３の三者で構成されている。
【００１７】
センター１０４は、最初に幾つかの定数を算出して、検証者装置１０３に送信する。図１では、「Ｉ」、「Ｂ」、「ｇ」、「ｐ」「Ｈａｓｈ（）」という定数と関数名が、センター１０４から検証者装置１０３に送られている。これら変数及び関数名の詳細は後述する。
検証者装置１０３は、センター１０４から受信した定数等を記憶する。
以上が、証明者装置１０２を生産する前の準備段階である。この段階は、後述する図２（ａ）に相当する。
【００１８】
次に、センター１０４は証明者装置１０２の生産処理を行う。この生産処理は、最初の段階で算出した幾つかの定数と、証明者装置１０２毎にユニークな数列を、入出力インターフェース１０５を通じて証明者装置１０２に記録する。図１では、生産工程の端的な表現として、センター１０４は、ベルトコンベア１０６上に並べられて移動する証明者装置１０２（ＲＦＩＤ）に対し、「Ａ」、「ｓ」という定数と、「｛（ｘ１，ｒ１），．．．（ｘｔ，ｒｔ）｝」という数列を記録する。これら変数及び数列の詳細は後述する。
以上が、証明者装置１０２の生産段階である。この段階は、後述する図２（ｂ）に相当する。
【００１９】
工場で生産された後の証明者装置１０２は、検証者装置１０３によって「本人確認処理」が行われる。例えば、証明者装置１０２がＲＦＩＤの場合は、当該ＲＦＩＤが貼付された商品が、物流の途中で検証者装置１０３による検証が行われる。
検証者装置１０３は、入出力インターフェース１０７を介して証明者装置１０２にアクセスし、証明者装置１０２が正しく工場で生産されたものなのか、つまり、悪意の第三者による改竄なく、センター１０４が生成した所定の定数が記憶されている、正規の物品であるか否かを検証する。検証の結果、正規の物品である、つまり「本人である」ことが確認できたら、検証者装置１０３は「本人である」旨の判定結果を出力する。逆に、検証の結果、正規の物品でない、つまり「本人でない」ことが確認できたら、検証者装置１０３は「本人でない」旨の判定結果を出力する。
以上が、検証者装置１０３による証明者装置１０２の本人確認段階である。この段階は、後述する図３に相当する。
【００２０】
［システム全体の処理の流れ］
図２（ａ）及び（ｂ）は、センター１０４と検証者装置１０３と証明者装置１０２との処理の大まかな流れを示すシーケンス図である。説明の便宜のため、図４を参照しつつ説明する。
図２（ａ）は、証明者装置１０２を生産する前の準備段階の流れを示すシーケンス図である。
先ず、センター１０４は、図４にて後述する定数演算部４０２を稼動して、定数演算処理を行う（Ｓ２０１）。
定数演算処理によって生成された定数Ｉ、Ｂ、ｇ、ｐは、検証者装置１０３に送信される（Ｓ２０２）。検証者装置１０３は、定数Ｉ、Ｂ、ｇ、ｐを受信すると、これを記憶する（Ｓ２０３）。
【００２１】
次に、センター１０４は、図４にて後述する検証仕様決定部４０３を稼動して、検証仕様決定処理を行う（Ｓ２０４）。
検証仕様決定処理によって決定されたハッシュ関数Ｈａｓｈの仕様（種類）は、検証者装置１０３に送信される（Ｓ２０５）。検証者装置１０３は、受信したハッシュ関数Ｈａｓｈの種類を内部に設定する（Ｓ２０６）。
【００２２】
周知のように、ハッシュ関数は任意長のデータ入力を受けて、固定長のデータを出力する関数である。現代の暗号技術は膨大なデータ量を扱うことが多いので、主にそのデータ量を削減しつつ、セキュリティを維持するために用いられる。データ量の削減は、暗号を扱う装置の記憶容量を削減するだけでなく、演算ステップ数を削減する効果がある。
多くの場合、ハッシュ関数はプログラムで実現される。特に、本実施形態のように、センター１０４と検証者装置１０３がハッシュ関数を交換可能な装置として構成するならば、殆どの場合、パソコンやワークステーション等の計算機に、所定のプログラムを実行させることで構築することが多い。したがって、センター１０４で選択したハッシュ関数Ｈａｓｈは、そのプログラムをモジュールとして検証者装置１０３に転送してもよい。
【００２３】
センター１０４と検証者装置１０３で利用されるハッシュ関数は、以下の条件を満たす必要がある。
（１）ハッシュ値が与えられたときにその入力を求めるのが困難であること。
（２）ある入力に対する出力と同じ値を出力するような異なる入力を求めるのが困難であること。
（３）同じ値を出力するような異なる入力の組を求めるのが困難であること。
以上の条件を満たす必要があるため、例えばハッシュ関数の入力を推測可能なＭＤ５等は、本実施形態における実装にはそぐわないといえる。
上記条件を満たすハッシュ関数は、例えば周知のＳＨＡ−１や、特開２００８−２３３６６１号公報に開示されているもの等が挙げられる。
【００２４】
なお、「ハッシュ関数を決定する」という行為は、必ずしも複数のハッシュ関数から一つを選択する、という動作を必要とする訳ではない。本人確認システム１０１の全体の仕様として、使用するハッシュ関数を最初から一つだけに固定化してしまっても一向に構わない。大事なことは、センター１０４の中（図４及び図１１にて後述するコミットメント数列生成部４０４）及び検証者装置１０３の中で使用するハッシュ関数器は、同じものでなければならない、ということである。
【００２５】
次に、図２（ｂ）は、証明者装置１０２の生産段階の流れを示すシーケンス図である。
センター１０４は、図４にて後述するコミットメント数列生成部４０４を稼動して、証明者装置１０２に記録させるためのコミットメント数列を生成する（Ｓ２０７）。その際、先の定数演算処理にて生成された定数Ａ、ｇ、ｐと、準備段階で実行した検証仕様決定処理（Ｓ２０４）にて決定されたハッシュ関数Ｈａｓｈと、コミットメント数列レコード数ｔを受け取り、これら定数等を用いてコミットメント数列を生成する。
コミットメント数列とは、乱数ｒとこれに対応するコミットメント値ｘの組（ｘ，ｒ）よりなるレコードがｔ個あるテーブル｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝である。
【００２６】
次に、センター１０４は、コミットメント数列生成部４０４によって生成されたコミットメント数列と、先の定数演算処理（Ｓ２０１）にて生成された定数Ａ、ｓとを、図４にて後述する定数記録部４０５を通じて、証明者装置１０２に記録する（Ｓ２０８）。一方、証明者装置１０２は、センター１０４から定数Ａ、ｓとコミットメント数列を受信すると、これを内部の後述するＲＯＭに記憶する（Ｓ２０９）。
上述のステップＳ２０７、Ｓ２０８及びＳ２０９の処理は、証明者装置１０２を一個生産する毎に繰り返される（Ｓ２１０、Ｓ２１１、Ｓ２１２）。
【００２７】
生産段階において、センター１０４から証明者装置１０２に転送される情報のうち、秘密鍵ｓとコミットメント数列｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝は、秘密情報である。これら情報は、外部に漏れてはならない。
一方、生産段階において、センター１０４から証明者装置１０２に転送される情報のうち、応答定数Ａは、公開情報である。つまり、外部に漏れても問題ない。
また、準備段階においてセンター１０４で生成される情報のうち、Ｂ、ｇ、ｐ、Ｉも公開情報である。
したがって、証明処理の段階では、秘密情報は証明者装置１０２の内部にのみ存在し、検証者装置１０３には存在しない。
【００２８】
図３は証明者装置１０２と検証者装置１０３との間で行われる、検証処理の流れを示すシーケンス図である。
検証者装置１０３は、証明者装置１０２に対してコミットメント値ｘを要求する（Ｓ３０１）。証明者装置１０２は、検証者装置１０３から送られたコミットメント要求に呼応して、コミットメント値ｘを送信する（Ｓ３０２）。検証者装置１０３は、コミットメント値ｘを受信すると、これを一旦内部に記憶する（Ｓ３０３）。
次に、検証者装置１０３はチャレンジ数ｃを生成し、これを証明者装置１０２に送信する（Ｓ３０４）。証明者装置１０２は、チャレンジ数ｃを受信すると、これを基に応答値ｙを生成し、検証者装置１０３に送信する（Ｓ３０５）。検証者装置１０３は受信した応答値ｙと、先に記憶していたコミットメント値ｘ、先に送信したチャレンジ数ｃ等を用いて、証明者装置１０２が正規の装置であるのかを検証する。検証した結果は、所定の処理機構等に出力する（Ｓ３０６）。
【００２９】
前述の「所定の処理機構」は、様々な態様が考えられる。
例えば、商品流通の仕組みにおいては、本実施形態に係るＲＦＩＤを貼付した商品をチェックしていて、もし当該ＲＦＩＤの改竄が認められた場合、当該商品の流通を緊急的に停止させ、悪意ある改竄がどこで行われたかを調査することが考えられる。単に対象品を除外する等の物理的な処理に留まらず、追跡調査を行う等の人間社会行動的な処理も含む。
つまり、検証者装置１０３の検証結果は、最低限アラームとして表示するか、何らかの稼動状態を停止させる等の処理のいずれかを実行し得るトリガとなる。
【００３０】
［センター１０４］
図４はセンター１０４のブロック図である。
定数演算部４０２は、図２（ａ）の準備段階で稼動する機能ブロックである。所定の演算処理を実行して、Ａ、Ｂ、ｇ、ｓ、ｐ、Ｉを出力する。
検証仕様決定部４０３は、図２（ａ）の準備段階で稼動する機能ブロックである。後述のコミットメント数列生成部４０４と検証者装置１０３で共通に使用するハッシュ関数の種類を決定すると共に、コミットメント数列生成部４０４で生成するコミットメント数列のレコード数ｔを決定する。
コミットメント数列生成部４０４は、図２（ｂ）の生産段階で稼動する機能ブロックである。定数演算部４０２からＡ、ｇ、ｐを受け取り、検証仕様決定部４０３にて決定されたハッシュ関数を用いて、ｔ個のレコード数のコミットメント数列を生成する。
定数記録部４０５は、図２（ｂ）の生産段階で稼動する機能ブロックである。定数演算部４０２からＡ、ｓを受け取り、コミットメント数列生成部４０４が生成したコミットメント数列を、証明者装置１０２に送信して、記録させる。
【００３１】
［センター１０４：定数演算部４０２］
図５はセンター１０４内部の定数演算部４０２のブロック図であり、図６は定数演算部４０２の処理の流れを説明するフローチャートである。
処理を開始すると（Ｓ６０１）、先ず、基礎定数生成器５０２は、初期基本定数ｑと、秘密鍵範囲Ｓと、チャレンジ数範囲Ｂを、以下の条件で作成する。
【００３２】
Ｓ＜ｑ≦ＢＳ 但し、ｑ，Ｓ：１６０ビット以上、Ｂ：３５ビット以上
【００３３】
作成されたｑ、Ｓ、Ｂは、それぞれｑ記憶部５０３、Ｓ記憶部５０４、Ｂ記憶部５０５に一時的に記憶される。各々の記憶部はＲＡＭやレジスタで構成される。
【００３４】
秘密鍵範囲Ｓは、後述する秘密鍵ｓを乱数で生成する際の最大値を規定するので、なるべく大きな値であることが望ましい。
【００３５】
次に、初期基本定数ｑを基に、群生成器５０６にて群Ｇの元ｇ及び剰余演算の法ｐを生成する（Ｓ６０３）。なお、ステップＳ６０３のｇ，ｐ生成処理は、群Ｇの全ての元を算出することなく、効率よくｇを算出する処理である。
次に、ｑ、Ｓ及びＢを基に、応答定数生成器５０７にて応答定数Ａを生成する（Ｓ６０４）。
次に、秘密鍵範囲Ｓを基に、秘密鍵生成器５０８にて秘密鍵ｓを生成する（Ｓ６０５）。秘密鍵生成器５０８の実体は乱数発生器であり、０〜Ｓ−１の範囲の乱数を指定する。
なお、ステップＳ６０３、Ｓ６０４及びＳ６０５は、順番を問わない。
【００３６】
作成されたｐ、ｇ、ｓ、Ａは、それぞれｐ記憶部５１４、ｇ記憶部５０９、ｓ記憶部５１０、Ａ記憶部５１１に一時的に記憶される。各々の記憶部はＲＡＭやレジスタで構成される。
【００３７】
次に、ｇ、ｐとｓを基に、公開鍵生成器５１２にて公開鍵Ｉを生成する（Ｓ６０６）。公開鍵Ｉは、以下の式で算出する。
【００３８】
Ｉ＝ｇ−ｓｍｏｄ ｐ
【００３９】
なお、「ｍｏｄ」は剰余演算を意味する。この、公開鍵Ｉの演算は、ｇ−ｓの値に対し、更に群演算を実行した結果である。本実施形態における群演算は、法ｐを用いた剰余演算である。
作成されたＩは、Ｉ記憶部５１３に一時的に記憶される。Ｉ記憶部５１３もＲＡＭやレジスタで構成される。
【００４０】
以上、作成された各定数は、それぞれ以下の三箇所に出力される。
先ず、ｇ、Ｉ、Ｂ、ｐは、検証者装置１０３に出力される（Ｓ６０７）。
次に、Ａ、ｇ、ｐが、コミットメント数列生成部４０４に出力される（Ｓ６０８）。
最後に、Ａとｓが、定数記録部４０５へ出力される（Ｓ６０９）。
これら出力処理が終わると、定数演算部４０２の処理が終了する（Ｓ６１０）。
【００４１】
［センター１０４：群生成器５０６］
図７は定数演算部４０２内の群生成器５０６のブロック図であり、図８は群生成器５０６の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ８０１）、先ず、乱数発生器７０２は乱数ωを生成する。
次に、乱数ωは素数判定器７０３によって素数であるか否かが判定される（Ｓ８０３）。素数でなければ、素数判定器７０３は再度乱数発生器７０２を起動させ、新たな乱数ωを生成させる。つまり、任意の素数を素数判定器７０３というフィルタを通じて出力する。
素数である乱数ωは、数値「２」７０４と、ｑ記憶部５０３内のｑと共に、乗算器７０５で乗算される。その後、加算器７０６で数値「１」７０７が加算される。つまり、以下の式を実行する（Ｓ８０４）：
【００４２】
ｐ＝２ｑω＋１
【００４３】
算出した値ｐは、素数判定器７０８で素数か否かが判定される（Ｓ８０５）。素数でなければ（Ｓ８０５のＮＯ）、再度ステップＳ８０２に戻り、乱数発生器７０２から処理のやり直しが行われる。素数であれば、一旦ｐ記憶部５１４に記憶される。
【００４４】
次に、数値「２」７０９とω記憶部７１０に記憶されているωを乗算器７１１で乗算した値で、数値「２」７１２をべき乗器７１３にてべき乗する。この値を、ステップＳ８０５で得たｐをｐ記憶部５１４から読み出して、剰余演算器７１５にて剰余を算出する。つまり、以下の式を実行する（Ｓ８０６）：
【００４５】
ｇ＝２２ωｍｏｄ ｐ
【００４６】
上述の式で算出した値が、群Ｇの元ｇと、本実施形態の群演算として用いる剰余演算の法ｐである。このｇ及びｐを出力して（Ｓ８０７）、処理を終了する（Ｓ８０８）。
【００４７】
なお、乱数発生器７０２は、任意の整数の乱数を作成すればよい。後述する他の乱数発生器（図１１の乱数発生器１１０３及び図１６の乱数発生器１６０４）とは異なり、乱数発生範囲は限定されない。
【００４８】
なお、群生成器５０６の演算処理により、ｇｑｍｏｄ ｐ＝１が必ず成立する。ｑは「ｇの位数」と呼ばれており、「ｏｒｄ（ｇ）」と記す。
【００４９】
［センター１０４：応答定数生成器５０７］
図９は定数演算部４０２内の応答定数生成器５０７のブロック図であり、図１０は応答定数生成器５０７の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１００１）、先ず、Ｂ記憶部５０５に格納されているＢと、Ｓ記憶部５０４に格納されているＳを、乗算器９０２で乗算する（Ｓ１００２）。この値をｕとする。
次に、カウンタ変数ｍ９０３を初期値「０」９０４で初期化する（Ｓ１００３）。
これ以降はループ処理である。
先ず、数値「２」９０５をべき乗器９０６により、カウンタ変数ｍ９０３から得られる変数ｍでべき乗し、乗算器９０７にてｑ記憶部５０３から得られるｑと乗算する。つまり、以下の式を実行する（Ｓ１００４）：
【００５０】
Ａ＝２ｍｑ
【００５１】
算出した値Ａを、比較器９０８で先のステップＳ１００２にて算出した値ｕと比較する（Ｓ１００５）。比較の結果、Ａがｕ以上でない、つまりＡがｕよりも小さい場合は（Ｓ１００５のＮＯ）、カウンタ変数ｍ９０３をインクリメントし（Ｓ１００６）、再度ステップＳ１００４の式を演算する。
ステップＳ１００５でＡがｕ以上であれば（Ｓ１００５のＹＥＳ）、この値を応答定数Ａとして出力し（Ｓ１００７）、処理を終了する（Ｓ１００８）。
【００５２】
図９の比較器９０８の出力は、真のときにカウンタ変数ｍ９０３をインクリメントする。これがステップＳ１００５のＮからステップＳ１００６に相当する。
比較器９０８の出力が偽のときには、ＮＯＴゲート９０９で反転され、スイッチ９１０をオン制御する。これがステップＳ１００５のＹからステップＳ１００７に相当する。
【００５３】
以上のような手順にて、応答定数生成器５０７で算出した応答定数Ａは、ｑに２ｍを乗算した数であるので、Ａはｑで割り切れる。また、ＢとＳとの乗算値ｕと比較しているため、Ａ≧ＢＳが保障される。
前述のように、ｑはｇの位数（オーダー）であるので、Ａはｏｒｄ（ｇ）で割り切れる。
【００５４】
［センター１０４：コミットメント数列生成部４０４］
図１１はセンター１０４内のコミットメント数列生成部４０４のブロック図であり、図１２はコミットメント数列生成部４０４の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１２０１）、先ず制御部１１０２内の図示しないカウンタ変数ｉを１に初期化する（Ｓ１２０２）。
次に、制御部１１０２によって乱数発生器１１０３が起動されると、乱数発生器１１０３は０〜Ａ−１の範囲内で乱数を生成する（Ｓ１２０３）。この乱数をｒｉ（ｉ番目のｒ）とする。
次に、重複確認部１１０４は、乱数発生器１１０３が出力した乱数ｒｉが、既に乱数使用リスト１１０５に登録されているか否かを確認する（Ｓ１２０４）。もし既に登録済みであれば（Ｓ１２０４のＮＯ）、重複確認部１１０４は再度乱数発生器１１０３を起動させて（Ｓ１２０３）、乱数使用リスト１１０５内の乱数との重複のない乱数ｒｉを得る（Ｓ１２０４のＹＥＳ）。
重複確認部１１０４は、乱数使用リスト１１０５内の乱数との重複のない乱数ｒｉを得たら、これを乱数使用リスト１１０５に登録する（Ｓ１２０５）。
【００５５】
乱数ｒｉはｇと共にべき乗器１１０６に与えられる。べき乗器１１０６はｇをｒｉでべき乗する。べき乗した値は更に、本実施形態の群演算とも言える剰余演算器１１１０によってｐ記憶部５１４の法ｐを用いた剰余演算が行われる。そして、この値はハッシュ関数器１１０７に与えられ、ハッシュ値ｘｉを得る。つまり、以下の式を実行する（Ｓ１２０６）：
【００５６】
【数１】
【００５７】
この時点で得られた（ｘｉ，ｒｉ）の組を、一旦一時リスト１１０８に出力し、保持する（Ｓ１２０７）。
次に、制御部１１０２は内部に保持しているカウンタ変数ｉがレコード数ｔ１１０９以上か否かを確認する（Ｓ１２０８）。もしｔ以上でなければ、カウンタ変数ｉをインクリメントし（Ｓ１２０９）、再度乱数発生器１１０３から一連の処理を繰り返す（Ｓ１２０３）。
カウンタ変数ｉがレコード数ｔ１１０９と等しくなれば、必要なレコード数ｔ１１０９だけ、コミットメント値ｘと乱数ｒの組が、一時リスト１１０８に保持されたこととなる。そこで、一時リスト１１０８の内容を定数記録部４０５に出力し（Ｓ１２１０）、一連の処理を終了する（Ｓ１２１１）。
【００５８】
［証明者装置１０２］
図１３は、証明者装置１０２のブロック図である。
入出力制御部１３０２は、センター１０４や検証者装置１０３とのデータの送受信と、証明者装置１０２全体の制御を行う。
入出力制御部１３０２には、ＥＥＰＲＯＭよりなるカウンタ変数格納部１３０３と、ＲＯＭ１３０４と、演算処理部１３０５が接続されている。
カウンタ変数格納部１３０３は、カウンタ変数ｉを格納している。ｉの初期値は「１」であり、最終値は「ｔ」である。カウンタ変数ｉは、ＲＯＭ１３０４内に格納されているコミットメント数列１３０６のレコード番号を指し示すポインタである。
また、ＲＯＭ１３０４にはセンター１０４から受け取った秘密鍵ｓと応答定数Ａが、それぞれＲＯＭ１３０４内の所定の領域に、ｓ記憶部１３０７及びＡ記憶部１３０８として格納されている。
【００５９】
演算処理部１３０５は、入出力制御部１３０２とＲＯＭ１３０４から演算処理に必要な値を受け取り、レスポンス値ｙを出力する。
【００６０】
以下、図３を参照して、入出力制御部１３０２を中心とする証明者装置１０２の全体の動作を説明する。
入出力制御部１３０２は、検証者装置１０３からコミットメント要求を受信すると（Ｓ３０１）、カウンタ変数格納部１３０３内のカウンタ変数ｉを読み込む。そして、ＲＯＭ１３０４内に格納されているコミットメント数列１３０６のｉ番目のレコードのコミットメント値ｘｉを読み込み、これを検証者装置１０３に出力する（Ｓ３０２）。
この後、入出力制御部１３０２は、検証者装置１０３からチャレンジ数ｃが送信されるのを待つ。つまり、受信待ちである。
入出力制御部１３０２は、検証者装置１０３から送信された（Ｓ３０４）チャレンジ数ｃを受信すると、コミットメント数列１３０６のｉ番目のレコードの乱数ｒｉと、受信したチャレンジ数ｃを演算処理部１３０５に渡す。
演算処理部１３０５は、ＲＯＭ１３０４内に格納されている秘密鍵ｓと応答定数Ａを読み出し、チャレンジ数ｃと乱数ｒｉと共に、後述する演算処理を行い、レスポンス値ｙを算出する。
レスポンス値ｙは、入出力制御部１３０２によって検証者装置１０３に送信される（Ｓ３０５）。
【００６１】
［証明者装置１０２：演算処理部１３０５］
図１４は証明者装置１０２内の演算処理部１３０５のブロック図であり、図１５は演算処理部１３０５の処理の流れを示すフローチャートである。
処理を開始すると（Ｓ１５０１）、先ずコミットメント数列１３０６から読み出した乱数ｒｉから減算器１４０３でＡを引いて、一時変数ｒ’を算出する（Ｓ１５０２）。なお、図１４では説明の便宜のため、コミットメント数列１３０６から読み出したｒｉをｒｉ記憶部１４０２に一旦格納している
と共に、一時変数ｒ’をｒ’記憶部１４０４に一旦格納している。
次に、ｃとｓを乗算器１４０５で乗算し、一時変数ｙ’を算出する（Ｓ１５０３）。なお、図１４では説明の便宜のため、検証者装置１０３から送信されたチャレンジ数ｃをｃ記憶部１４０６に一旦格納していると共に、一時変数ｙ’をｙ’記憶部１４０７に一旦格納している。
次に、ｒｉとｙ’を加算器１４０８で加算し、一時変数ｙ０を算出する（Ｓ１５０４）。
次に、ｒ’とｙ’を加算器１４０９で加算し、一時変数ｙ１を算出する（Ｓ１５０５）。
【００６２】
次に、比較器１４１０で一時変数ｙ１と数値「０」１４１１を比較し、一時変数ｙ１が０未満、つまり負の値であるか確認する（Ｓ１５０６）。もし負の値ならば（Ｓ１５０６のＹＥＳ）、比較器１４１０の判定出力によって、スイッチ１４１２はｙとしてｙ０を選択する（Ｓ１５０７）。もし正の値ならば（Ｓ１５０６のＮＯ）、スイッチ１４１２はｙとしてｙ１を選択する（Ｓ１５０８）。
そして、ｙを出力し（Ｓ１５０９）、一連の処理を終了する（Ｓ１５１０）。
【００６３】
［検証者装置１０３］
図１６は検証者装置１０３のブロック図であり、図１７は検証者装置１０３の検証処理の流れを示すフローチャートである。
入出力制御部１６０２は、証明者装置１０２とのデータの送受信と、検証者装置１０３全体の制御を行う。
入出力制御部１６０２には、証明者装置１０２から受信するコミットメント値ｘを一時的に格納するｘ記憶部１６０３と、乱数発生器１６０４と、乱数発生器１６０４が生成したチャレンジ数ｃを記憶するｃ記憶部１６０５と、証明者装置１０２から受信するレスポンス値ｙを一時的に格納するｙ記憶部１６０６が接続されている。
【００６４】
乱数発生器１６０４は、チャレンジ数範囲Ｂを記憶するＢ記憶部１６０７からチャレンジ数範囲Ｂを得て、０〜Ｂ−１の範囲の乱数を生成する。これはチャレンジ数ｃとして証明者装置１０２に送信される。
ｃはＩ記憶部１６０８に格納されているＩと共にべき乗器１６０９にてべき乗が算出される。べき乗器１６０９の出力は、本実施形態の群演算とも言える剰余演算器１６１５にて、ｐ記憶部１６１７から供給される法ｐで剰余演算が行われる。
一方、ｙはｇ記憶部１６１０から得られるｇと共にべき乗器１６１１にてべき乗が算出される。べき乗器１６１１の出力は、本実施形態の群演算とも言える剰余演算器１６１６にて、ｐ記憶部１６１７から供給される法ｐで剰余演算が行われる。
この、それぞれの剰余演算器１６１５及び１６１６の出力が共に乗算器１６１２に供給され、乗算される。
乗算器１６１２の出力はハッシュ関数器１６１３に入力され、ハッシュ値が出力される。
このハッシュ値が、コミットメント値ｘと比較される。
一致検出器１６１４はコミットメント値ｘとハッシュ値との一致を検証し、一致していれば「１」を、一致していなければ「０」を出力する。これが判定出力となる。
【００６５】
以下、図３を参照して、入出力制御部１６０２を中心とする検証者装置１０３の全体の動作を説明する。
最初に、入出力制御部１６０２は証明者装置１０２に対しコミットメント要求を送信する（Ｓ３０１）。
そして、入出力制御部１６０２は、証明者装置１０２からコミットメント値ｘが送信されるのを待つ。
入出力制御部１６０２は、証明者装置１０２からコミットメント値ｘを受信したら、これを一旦ｘ記憶部１６０３に保持する（Ｓ３０３）。この後、乱数発生器１６０４を稼動させ、チャレンジ数ｃを証明者装置１０２へ送信する（Ｓ３０４）。
そして、入出力制御部１６０２は、証明者装置１０２からレスポンス値ｙが送信されるのを待つ。
入出力制御部１６０２は、証明者装置１０２からレスポンス値ｙを受信すると、検証処理を行い、得られた値とコミットメント値ｘとの一致を確認し、一致／不一致を出力する（Ｓ３０６）。
【００６６】
図１６と図１７を参照して、検証処理を説明する。
証明者装置１０２からレスポンス値ｙを受信すると（Ｓ１７０１）、べき乗器１６０９、べき乗器１６１１、剰余演算器１６１５、剰余演算器１６１６、乗算器１６１２及びハッシュ関数器１６１３を稼動させ、以下の式に記す演算処理を行う（Ｓ１７０２）：
【００６７】
Ｚ＝Ｈａｓｈ（（ｇｙｍｏｄ ｐ）（Ｉｃｍｏｄ ｐ））
【００６８】
次に、先に受信して保持してあるコミットメント値ｘと、算出したＺとを比較器９０８で比較する（Ｓ１７０３）。
値が一致していれば、証明者装置１０２は正当なものであると判断し、「１」を出力する（Ｓ１７０４）。
値が一致していなければ、証明者装置１０２は不正なものであると判断し、「０」を出力する（Ｓ１７０５）。
そして、一連の処理を終了する（Ｓ１７０６）。
【００６９】
［証明処理］
検証者装置１０３と証明者装置１０２が実行する証明処理について、以下、簡単に説明する。
コミットメント値ｘは、図１１にて説明したコミットメント数列生成部４０４によって、乱数ｒから以下の数式で生成される：
【００７０】
ｘ＝Ｈａｓｈ（ｇｒｍｏｄ ｐ）
【００７１】
一方、証明者装置１０２は、検証者装置１０３が乱数発生器１６０４で作成して送信したチャレンジ数ｃを受信すると、演算処理部１３０５で以下の数式でｙを算出する：
【００７２】
ｙ＝ｒ＋ｃｓ
【００７３】
更に、センター１０４の定数演算部４０２内の公開鍵生成器５１２では、秘密鍵ｓと群Ｇの元ｇから、公開鍵Ｉを以下の数式で算出する：
【００７４】
Ｉ＝ｇ−ｓｍｏｄ ｐ
【００７５】
以上より、以下のように算出できる：
【００７６】
ｇｙｍｏｄ ｐＩｃｍｏｄ ｐ＝ｇｒ＋ｃｓｍｏｄ ｐ（ｇ−ｓ）ｃｍｏｄ ｐ
＝ｇｒ＋ｃｓｍｏｄ ｐｇ−ｃｓｍｏｄ ｐ
＝ｇｒ＋ｃｓ−ｃｓｍｏｄ ｐ＝ｇｒｍｏｄ ｐ
∴ｇｙｍｏｄ ｐＩｃｍｏｄ ｐ＝ｇｒｍｏｄ ｐ
∴Ｈａｓｈ（ｇｒｍｏｄ ｐ）＝Ｈａｓｈ（（ｇｙｍｏｄ ｐ）（Ｉｃｍｏｄ ｐ））
【００７７】
次に、本実施形態で利用している「ｙ’−Ａ」という数式の意味を説明する。
【００７８】
【数２】
【００７９】
［サイドチャネル攻撃に対する耐性］
本来なら、証明者装置１０２は単純に内部の演算処理部で「ｙ＝ｒ＋ｃｓ」という演算処理を行えば、容易にレスポンス値ｙを算出できる。
しかし、この計算ステップでは、サイドチャネル攻撃の一種である、タイミング解析攻撃ならびに単純電力解析攻撃に対して脆弱である。そこで、この演算処理をマスキングするために、応答定数Ａという要素を加え、演算処理をやや複雑にすることで、タイミング解析攻撃ならびに単純電力解析攻撃を回避する。
ところが、もし、証明者装置１０２が以下に記すプログラムの処理を行うと、サイドチャネル攻撃の一種である、タイミング解析攻撃ならびに単純電力解析攻撃に対して脆弱である：
【００８０】
ｙ’＝ｒ＋ｃｓ #変数ｙ’にｒ＋ｃｓを代入する。
ｉｆ（ｙ’＜Ａ）｛ #ｙ’がＡより小さければ、
ｙ＝ｙ’ #ｙはｙ’を出力する。
｝ｅｌｓｅ｛ #さもなくば、
ｙ＝ｙ’−Ａ #ｙはｙ’−Ａを出力する。
｝
【００８１】
なお、上述のプログラムの「#（井桁）」以降は、コメントである。
上述のプログラムでは、ｙ’がＡとの大小関係に応じて、ｙ’−Ａという演算を行う場合と行わない場合とで、演算処理ステップ数の差が生じる。
タイミング解析攻撃ならびに単純電力解析攻撃とは、暗号鍵などのセキュリティパラメータ値によって暗号の演算時間が異なるような実装が行われた場合に、この演算時間を観測することによって、セキュリティパラメータの値を逆算する攻撃法である。この攻撃法に対処するには、どのようなセキュリティパラメータの値であっても、常に同じ時間で暗号化や復号化等の演算処理が完了するように実装する必要がある。
【００８２】
そこで、本実施形態の証明者装置１０２では、以下のプログラムで示される演算手順を行う：
【００８３】
ｒ’＝ｒｉ−Ａ #図１５のステップＳ１５０２
ｙ’＝ｃｓ #Ｓ１５０３
ｙ０＝ｒｉ＋ｙ’ #Ｓ１５０４
ｙ１＝ｒ’＋ｙ’ #Ｓ１５０５
ｉｆ（ｙ１＜０）｛ #Ｓ１５０６：ｙ１が０より小さければ、
ｙ＝ｙ０ #Ｓ１５０７：ｙはｙ０を出力する。
｝ｅｌｓｅ｛ #さもなくば、
ｙ＝ｙ１ #Ｓ１５０８：ｙはｙ１を出力する。
｝
【００８４】
以上の処理手順により、ｙ１の値の如何にかかわらず、証明者装置１０２の演算処理部は常に同じ演算ステップ数を実行することとなるので、タイミング解析攻撃ならびに単純電力解析攻撃に対する脆弱性は十分に低減できる。
【００８５】
［従来技術との比較］
本実施形態の本人確認システムと、従来技術の本人確認システムとを比較する。
「Ｓｃｈｎｏｒｒ方式」（非特許文献１参照）と呼ばれる、公開鍵暗号を用いた本人確認方法は、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性は完全にない。しかしながら、サイドチャネル攻撃に対抗するために、証明者装置で剰余演算と位数算出（オーダー関数）を実行する必要がある。つまり、証明者装置に対して高い演算能力を要求する。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【００８６】
「ＧＰＳ方式」（非特許文献２及び非特許文献３参照）と呼ばれる、公開鍵暗号を用いた本人確認方法は、Ｓｃｈｎｏｒｒ方式と比べると、証明者装置では剰余演算や位数算出を実行する必要がない。つまり、証明者装置に対して高い演算能力を要求しないので、演算能力の点ではＳｃｈｎｏｒｒ方式より有利である。
しかし、証明者装置と検証者装置との間の通信路から、秘密情報（秘密鍵ｓ及び乱数ｒ）が漏洩する可能性が完全にない、とは言い切れない。また、証明者装置の内部の演算処理で、レスポンス値ｙを算出する「ｙ＝ｒ＋ｃｓ」という演算がそのまま外部から見えてしまう。そこで、乱数ｒを生成する範囲を示す応答定数Ａを、ｃｓの値の範囲であるＢＳよりも大幅に大きくしなければならない。このため、必然的にコミットメント数列の一部を構成する乱数ｒのビット数を大きくせざるを得ず、証明者装置に要求される記憶容量が大きくなってしまう。
したがって、証明者装置に要求されるハードウェア資源が極めて厳しいので、ＲＦＩＤ等の低資源装置に適さない。
【００８７】
本実施形態の本人確認システムでは、上述のＳｃｈｎｏｒｒ方式とＧＰＳ方式がそれぞれ抱える欠点を、両方共解決している。
本実施形態の本人確認システムは、Ｓｃｈｎｏｒｒ方式と同様に、サイドチャネル攻撃に対して堅牢である。
証明者装置に要求される記憶容量は、Ｓｃｈｎｏｒｒ方式と比べると、およそ１１％程度の増加で済む。
証明者装置が必要とする演算手段は、ＧＰＳ方式と同様、加算器と乗算器だけで済む。
したがって、証明者装置に要求されるハードウェア資源が極めて軽く、ＲＦＩＤ等の低資源装置に適する。
【００８８】
本実施形態には、以下のような応用例が考えられる。
（１）証明者装置１０２内のコミットメント数列のポインタである、カウンタ変数格納部１３０３内のカウンタ変数ｉを強制的に動かして、コミットメント数列を使用不能にすると、証明者装置１０２の再利用を防止できる。
このことを実現させるために、証明者装置１０２の入出力制御部１３０２に、検証者装置１０３から発行された特定のコマンドを受信すると、カウンタ変数格納部１３０３内のカウンタ変数ｉを、コミットメント数列１３０６のレコード数ｔを超える数、或は「０」等の、コミットメント数列１３０６のレコード番号を指し示さない値に書き換える処理を追加する。
【００８９】
（２）センター１０４内の定数演算部４０２が生成した各種定数はそのままに、検証仕様決定部４０３でハッシュ関数だけを異ならせると、コミットメント数列生成部４０４からは全く異なるコミットメント数列を出力することができるので、定数演算部４０２が生成した各種定数をハッシュ関数の種類毎に使い回すことができる。
【００９０】
（３）実施形態では低資源装置の代表的なものとして、ＲＦＩＤを例に挙げて説明したが、低資源装置はこれに限られない。電気的に直接接続可能な電極を備えるＩＣカード等も、本実施形態で用いる低資源装置として適用可能である。
【００９１】
（４）図２（ｂ）に示した生産段階では、証明者装置１０２を一個作る度に、コミットメント数列生成処理（Ｓ２０７、Ｓ２１０）を実施していた。つまり、コミットメント数列生成部４０４を、証明者装置１０２を一個作る度に動作させていた。しかし、コミットメント数列｛（ｘ１，ｒ１），（ｘ２，ｒ２），．．．（ｘｔ，ｒｔ）｝は、乱数ｒと、これに対応する値ｘとの組み合わせであるので、証明者装置１０２の生産段階の前に、予め生産数とｔを乗じたレコード数だけ「作り置き」してもよい。
【００９２】
（５）本実施形態では、証明者装置の演算処理におけるサイドチャネル攻撃の脅威から秘密鍵の漏洩を防ぐために、群の性質を利用して、演算ステップを隠蔽するための応答定数Ａを採用している。
ここで、本実施形態では、群演算に素数ｐを法とする剰余演算を採用した。
群演算は、本実施形態で開示した剰余演算に限られない。
周知のように、暗号の世界では、群（有限体或は有限群とも呼ぶ）における離散対数問題の解の困難さを利用するアルゴリズムが多く利用される。したがって、本実施形態で採用した剰余演算に代えて、このようなアルゴリズムに基づく群演算を採用することができる。
一例としては、楕円曲線暗号が挙げられる。多種多様な楕円曲線暗号のアルゴリズムのうちの一例としては、楕円ＥｌＧａｍａｌ暗号で用いられる次の楕円曲線上の有理点を，群演算として採用することができる：
【００９３】
Ｅｑ（ａ，ｂ）：ｙ２＝ｘ３＋ａｘ＋ｂ
【００９４】
また、この際、群生成器５０６の仕様も併せて変更する必要が生じる。つまり、剰余演算の法ｐを決定することと同様に、楕円曲線暗号では、適切な楕円曲線を選ぶ演算処理が必要になる。これは、非特許文献６に開示されているように、ランダムに曲線を定めた後、曲線の位数（オーダー）、すなわち曲線状の点の数を計算する。この計算処理は、現状ではＳｃｈｏｏｆのアルゴリズム及びその変形を利用することとなる。
【００９５】
本実施形態においては、本人確認システムを開示した。
サイドチャネル攻撃を防ぐために、Ｓｃｈｎｏｒｒ方式では証明者装置で剰余演算と位数算出（オーダー関数）を実行することで対応していた。一方で、ＧＰＳ方式では証明者装置で演算する数値のビット数を多く取ることで対応していた。
本実施形態では、ＧＰＳ方式の演算の方式を踏襲しつつ、ＧＰＳ方式よりも演算の数値のビット数を少なくするために、証明者装置内の演算の数値の一つである応答定数Ａを、群Ｇの元ｇのオーダー（位数）の倍数に設定した。
応答定数Ａをｇの自然数倍に設定すると、群の性質により、証明者装置の演算結果であるｙ＝ｃｓ＋ｒからＡを減算しても、検証者装置側で同じ値を得ることができる。
証明者装置では、ｙの値の正負に応じてｙからＡを減算するか否かを選択する。この際に、ｙの値の如何にかかわらず、ｙからＡを減算する処理手順を二重に実行することで、サイドチャネル攻撃に対する耐性を備えることができる。
【００９６】
ＲＦＩＤ等の低資源装置を用いる、有限回数の本人確認処理を行うシステムで、本実施形態は、低資源装置に対して極めて少ない演算能力と、従来技術と同等の記憶容量で、実用的な本人確認処理を実現できる。
更に、本実施形態の本人確認システムは、サイドチャネル攻撃に対しても強いので、セキュリティ面で堅牢な本人確認処理を実現できる。
【００９７】
以上、本発明の実施形態例について説明したが、本発明は上記実施形態例に限定されるものではなく、特許請求の範囲に記載した本発明の要旨を逸脱しない限りにおいて、他の変形例、応用例を含む。
【図面の簡単な説明】
【００９８】
【図１】本発明の一実施形態の例である、本人確認システムの概略図である。
【図２】センターと検証者装置と証明者装置との処理の大まかな流れを示すシーケンス図である。
【図３】証明者装置と検証者装置との間で行われる、検証処理の流れを示すシーケンス図である。
【図４】センターのブロック図である。
【図５】センター内部の定数演算部のブロック図である。
【図６】定数演算部の処理の流れを説明するフローチャートである。
【図７】定数演算部内の群生成器のブロック図である。
【図８】群生成器の処理の流れを示すフローチャートである。
【図９】定数演算部内の応答定数生成器のブロック図である。
【図１０】応答定数生成器の処理の流れを示すフローチャートである。
【図１１】センター内のコミットメント数列生成部のブロック図である。
【図１２】コミットメント数列生成部の処理の流れを示すフローチャートである。
【図１３】証明者装置のブロック図である。
【図１４】証明者装置内の演算処理部のブロック図である。
【図１５】演算処理部の処理の流れを示すフローチャートである。
【図１６】検証者装置のブロック図である。
【図１７】検証者装置の検証処理の流れを示すフローチャートである。
【符号の説明】
【００９９】
１０１…本人確認システム、１０２…証明者装置、１０３…検証者装置、１０４…センター、１０５…入出力インターフェース、１０６…ベルトコンベア、１０７…入出力インターフェース、４０２…定数演算部、４０３…検証仕様決定部、４０４…コミットメント数列生成部、４０５…定数記録部、５０２…基礎定数生成器、５０３…ｑ記憶部、５０４…Ｓ記憶部、５０５…Ｂ記憶部、５０６…群生成器、５０７…応答定数生成器、５０８…秘密鍵生成器、５０９…ｇ記憶部、５１０…ｓ記憶部、５１１…Ａ記憶部、５１２…公開鍵生成器、５１３…Ｉ記憶部、５１４…ｐ記憶部、７０２…乱数発生器、７０３…素数判定器、７０４…数値「２」、７０５…乗算器、７０６…加算器、７０７…数値「１」、７０８…素数判定器、７０９…数値「２」、７１０…ω記憶部、７１１…乗算器、７１２…数値「２」、７１３…べき乗器、７１５…剰余演算器、９０２…乗算器、９０３…カウンタ変数ｍ、９０４…初期値「０」、９０５…数値「２」、９０６…べき乗器、９０７…乗算器、９０８…比較器、１１０２…制御部、１１０３…乱数発生器、１１０４…重複確認部、１１０５…乱数使用リスト、１１０６…べき乗器、１１０７…ハッシュ関数器、１１０８…一時リスト、１１０９…レコード数ｔ、１３０２…入出力制御部、１３０３…カウンタ変数格納部、１３０４…ＲＯＭ、１３０５…演算処理部、１３０６…コミットメント数列、１３０７…ｓ記憶部、１３０８…Ａ記憶部、１４０２…ｒｉ記憶部、１４０３…減算器、１４０４…ｒ’記憶部、１４０５…乗算器、１４０６…ｃ記憶部、１４０７…ｙ’記憶部、１４０８…加算器、１４０９…加算器、１４１０…比較器、１４１１…数値「０」、１４１２…スイッチ、１６０２…入出力制御部、１６０３…ｘ記憶部、１６０４…乱数発生器、１６０５…ｃ記憶部、１６０６…ｙ記憶部、１６０７…Ｂ記憶部、１６０８…Ｉ記憶部、１６０９…べき乗器、１６１０…ｇ記憶部、１６１１…べき乗器、１６１２…乗算器、１６１３…ハッシュ関数器、１６１４…一致検出器、１６１５、１６１６…剰余演算器、１６１７…ｐ記憶部
【特許請求の範囲】
【請求項１】
秘密鍵ｓと前記秘密鍵に対応する公開鍵Ｉと定数Ａ及び定数Ｂとを生成すると共に、ハッシュ関数を利用してコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を生成するセンターと、
生成された前記公開鍵Ｉと前記定数Ｂと前記センターで利用される前記ハッシュ関数とを利用して証明処理を実行する検証者装置と、
生成された前記秘密鍵ｓと前記定数Ａと前記コミットメント数列とを記憶する記憶部と、前記検証者装置に前記コミットメント値ｘを送信し、前記検証者装置からチャレンジ数ｃを受信し、前記検証者装置にレスポンス値ｙを送信する入出力制御部と、前記秘密鍵ｓと前記定数Ａと前記乱数ｒと、受信した前記チャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａを前記レスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、
よりなる本人確認システム。
【請求項２】
前記演算処理部は、
ｒ−Ａを演算してｒ’を得る第一の演算手順と、
ｒ＋ｃｓを演算してｙ０を得る第二の演算手順と、
ｒ’＋ｃｓを演算してｙ１を得る第三の演算手順と、
前記ｙ１の正負を判定し、負であるときは前記ｙ０を、そうでないときは前記ｙ１を前記レスポンス値ｙとして出力する第四の演算手順と、
を実行するものである、請求項１記載の本人確認システム。
【請求項３】
群Ｇの元ｇを算出し、前記元ｇの位数の自然数倍である応答定数Ａを算出し、秘密鍵ｓから群演算にて公開鍵Ｉを算出し、ハッシュ関数を決定し、前記応答定数Ａと前記群ｇから前記群演算及び前記ハッシュ関数にてコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を算出するセンターと、
前記公開鍵Ｉと前記群演算と前記ハッシュ関数とを利用して証明処理を実行する検証者装置と、
前記秘密鍵ｓと前記応答定数Ａと前記コミットメント数列とを記憶する記憶部と、前記検証者装置に前記コミットメント値ｘを送信し、前記検証者装置からチャレンジ数ｃを受信し、前記検証者装置にレスポンス値ｙを送信する入出力制御部と、前記秘密鍵ｓと前記定数Ａと前記乱数ｒと、受信した前記チャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａを前記レスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、
よりなる本人確認システム。
【請求項４】
前記演算処理部は、
ｒ−Ａを演算してｒ’を得る第一の演算手順と、
ｒ＋ｃｓを演算してｙ０を得る第二の演算手順と、
ｒ’＋ｃｓを演算してｙ１を得る第三の演算手順と、
前記ｙ１の正負を判定し、負であるときは前記ｙ０を、そうでないときは前記ｙ１を前記レスポンス値ｙとして出力する第四の演算手順と、
を実行するものである、請求項３記載の本人確認システム。
【請求項１】
秘密鍵ｓと前記秘密鍵に対応する公開鍵Ｉと定数Ａ及び定数Ｂとを生成すると共に、ハッシュ関数を利用してコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を生成するセンターと、
生成された前記公開鍵Ｉと前記定数Ｂと前記センターで利用される前記ハッシュ関数とを利用して証明処理を実行する検証者装置と、
生成された前記秘密鍵ｓと前記定数Ａと前記コミットメント数列とを記憶する記憶部と、前記検証者装置に前記コミットメント値ｘを送信し、前記検証者装置からチャレンジ数ｃを受信し、前記検証者装置にレスポンス値ｙを送信する入出力制御部と、前記秘密鍵ｓと前記定数Ａと前記乱数ｒと、受信した前記チャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａを前記レスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、
よりなる本人確認システム。
【請求項２】
前記演算処理部は、
ｒ−Ａを演算してｒ’を得る第一の演算手順と、
ｒ＋ｃｓを演算してｙ０を得る第二の演算手順と、
ｒ’＋ｃｓを演算してｙ１を得る第三の演算手順と、
前記ｙ１の正負を判定し、負であるときは前記ｙ０を、そうでないときは前記ｙ１を前記レスポンス値ｙとして出力する第四の演算手順と、
を実行するものである、請求項１記載の本人確認システム。
【請求項３】
群Ｇの元ｇを算出し、前記元ｇの位数の自然数倍である応答定数Ａを算出し、秘密鍵ｓから群演算にて公開鍵Ｉを算出し、ハッシュ関数を決定し、前記応答定数Ａと前記群ｇから前記群演算及び前記ハッシュ関数にてコミットメント値ｘと乱数ｒの組よりなるコミットメント数列を算出するセンターと、
前記公開鍵Ｉと前記群演算と前記ハッシュ関数とを利用して証明処理を実行する検証者装置と、
前記秘密鍵ｓと前記応答定数Ａと前記コミットメント数列とを記憶する記憶部と、前記検証者装置に前記コミットメント値ｘを送信し、前記検証者装置からチャレンジ数ｃを受信し、前記検証者装置にレスポンス値ｙを送信する入出力制御部と、前記秘密鍵ｓと前記定数Ａと前記乱数ｒと、受信した前記チャレンジ数ｃとを用いて、ｒ＋ｃｓ＜Ａであるときはｒ＋ｃｓを、そうでないときはｒ＋ｃｓ−Ａを前記レスポンス値ｙとして出力する演算処理部と、を有する証明者装置と、
よりなる本人確認システム。
【請求項４】
前記演算処理部は、
ｒ−Ａを演算してｒ’を得る第一の演算手順と、
ｒ＋ｃｓを演算してｙ０を得る第二の演算手順と、
ｒ’＋ｃｓを演算してｙ１を得る第三の演算手順と、
前記ｙ１の正負を判定し、負であるときは前記ｙ０を、そうでないときは前記ｙ１を前記レスポンス値ｙとして出力する第四の演算手順と、
を実行するものである、請求項３記載の本人確認システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１０−１１８７９６（Ｐ２０１０−１１８７９６Ａ）
【公開日】平成２２年５月２７日（２０１０．５．２７）
【国際特許分類】
【出願番号】特願２００８−２８９２６６（Ｐ２００８−２８９２６６）
【出願日】平成２０年１１月１１日（２００８．１１．１１）
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
【公開日】平成２２年５月２７日（２０１０．５．２７）
【国際特許分類】
【出願日】平成２０年１１月１１日（２００８．１１．１１）
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
[ Back to top ]