(57)【要約】【課題】格子上の問題に基づくタグ付き使い捨て署名方式を実現する。【解決手段】署名生成時には、選択されたｎ０次元のベクトルｚ０、選択されたｍ１次元のベクトルσ１、およびメッセージに対応するｋ１次元のベクトルＭ１を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすｍ０次元のベクトルσ０を得、ベクトルσ０およびσ１を含む署名を出力する。署名検証時には、ベクトルＭ１，σ０，σ１，ｚ０を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を満たすかを判定する。【選択図】図１
2016001248.tif 000002
【特許請求の範囲】
【請求項１】
ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１が１以上の整数、Ａ０がｎ０行ｋ０列の行例、Ｂ０がｎ０行ｍ０列の行例、Ａ１がｎ１行ｋ１列の行例、Ｂ１がｎ１行ｍ１列の行例、選択されたｎ０次元のベクトルがｚ０、選択されたｍ１次元のベクトルがσ１、Ｍ１がメッセージに対応するｋ１次元のベクトルであり、
Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得る第１演算部と、
ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすｍ０次元のベクトルσ０を得る第２演算部と、
前記ベクトルσ０およびσ１を含む署名を出力する出力部と、
を有する署名生成装置。
【請求項２】
請求項１の署名生成装置であって、
前記第２演算部は、前記行例Ｂ０に対応する秘密情報であるトラップドアＳ０を用いて前記ベクトルσ０を得る、署名生成装置。
【請求項３】
請求項２の署名生成装置であって、
前記トラップドアＳ０は、Ｂ０ｒ０＝０を満たすｍ０次元のベクトルｒ０が属する部分ベクトル空間を張るｍ０次元の基底ベクトルの何れかである、署名生成装置。
【請求項４】
請求項１から３の何れかの署名生成装置であって、
前記Ａ１Ｍ１＋Ｂ１σ１を含む情報がｋ０次元のベクトルである、署名生成装置。
【請求項５】
ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１が１以上の整数、Ａ０がｎ０行ｋ０列の行例、Ｂ０がｎ０行ｍ０列の行例、Ａ１がｎ１行ｋ１列の行例、Ｂ１がｎ１行ｍ１列の行列であり、
メッセージに対応するｋ１次元のベクトルＭ１、および、署名であるｍ１次元のベクトルσ１を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得る演算部と、
少なくとも、前記ベクトルｚ１、入力されたｎ０次元のベクトルｚ０、および署名であるｍ０次元のベクトルσ０を用い、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を満たすかを判定する判定部と、
を有する署名検証装置。
【請求項６】
請求項５の署名検証装置であって、
前記判定部は、前記ベクトルσ０およびσ１がガウス分布に従ったものであるかを判定し、
前記検証条件は、さらに前記ベクトルσ０およびσ１がガウス分布に従ったものであると判定されたことを含む、署名検証装置。
【請求項７】
ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１が１以上の整数、Ａ０がｎ０行ｋ０列の行例、Ｂ０がｎ０行ｍ０列の行例、Ａ１がｎ１行ｋ１列の行例、およびＢ１がｎ１行ｍ１列の行例であり、
選択されたｎ０次元のベクトルｚ０、選択されたｍ１次元のベクトルσ１、およびメッセージに対応するｋ１次元のベクトルＭ１を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすｍ０次元のベクトルσ０を得、前記ベクトルσ０およびσ１を含む署名を出力する署名生成装置と、
前記ベクトルＭ１，σ０，σ１，ｚ０を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を満たすかを判定する署名検証装置と、
を有する署名システム。
【請求項８】
請求項１から４の何れかの署名生成装置、または、請求項５もしくは６の署名検証装置、としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名技術に関し、特に、タグ付き使い捨て署名技術に関する。
【背景技術】
【０００２】
タグ付き使い捨て署名（TOS: Tagged One-Time Signature）方式は、使い捨て署名（OTS: One-Time Signature）方式の一種であり、秘密鍵と「タグ」と呼ばれる使い捨て公開鍵とに基づいてメッセージに対する署名を生成し、この秘密鍵に対応する公開鍵とタグとメッセージを用いて署名検証を行う（例えば、非特許文献１等参照）。ＴＯＳ方式では、通常のＯＴＳ方式（例えば、非特許文献２等参照）とは異なり、署名生成のための使い捨て秘密鍵を保存しておく必要がない点で利便性が高い。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions,” ASI-ACRYPT 2012, 4-24.
【非特許文献２】Payman Mohassel, “One-Time Signatures and Chameleon Hash Functions,” Selected Areas in Cryptography 2010, 302-319.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１に記載されたＴＯＳ方式は、ペアリング群上の計算量的仮定に基づく安全性（計算量的安全性）を持つ方式であり、量子計算機が実現した場合その安全性は失われる。
【０００５】
本発明の目的は、量子計算機が実現したとしてもその安全性を保持できると考えられる格子上の問題に基づくタグ付き使い捨て署名方式を提供することである。
【課題を解決するための手段】
【０００６】
署名生成時には、選択されたｎ０次元のベクトルｚ０、選択されたｍ１次元のベクトルσ１、およびメッセージに対応するｋ１次元のベクトルＭ１を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすｍ０次元のベクトルσ０を得、ベクトルσ０およびσ１を含む署名を出力する。ただし、ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１は１以上の整数、Ａ０はｎ０行ｋ０列の行例、Ｂ０はｎ０行ｍ０列の行例、Ａ１はｎ１行ｋ１列の行例、およびＢ１はｎ１行ｍ１列の行例である。
【０００７】
署名検証時には、ベクトルＭ１，σ０，σ１，ｚ０を用い、Ａ１Ｍ１＋Ｂ１σ１を含む情報に対応するｋ０次元のベクトルｚ１を得、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を満たすかを判定する。
【発明の効果】
【０００８】
本発明では、格子上の問題に基づくタグ付き使い捨て署名方式を実現できる。
【図面の簡単な説明】
【０００９】
【図１】図１は実施形態の署名システムの機能構成を例示するためのブロック図である。
【図２】図２は、実施形態の鍵生成装置の機能構成を例示するためのブロック図である。
【図３】図３Ａは、実施形態の署名生成装置の機能構成を例示するためのブロック図である。図３Ｂは、実施形態の署名検証装置の機能構成を例示するためのブロック図である。
【図４】図４Ａは、実施形態の鍵生成方法を例示するためのフロー図である。図４Ｂは、実施形態の署名生成方法を例示するためのフロー図である。図４Ｃは、実施形態の署名検証方法を例示するためのフロー図である。
【図５】図５Ａから図５Ｃは、実施形態のデータ構成を例示するための図である。
【図６】図６Ａから図６Ｃは、実施形態のデータ構成を例示するための図である。
【図７】図７Ａから図７Ｃは、実施形態のデータ構成を例示するための図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態を説明する。
［定義］
実施形態で使用する用語を定義する。
＜ＳＩＳ（Small Integer Solution）問題＞
ＳＩＳ問題とは、解法が困難とされている格子上の問題の一種であり、暗号プリミティブの安全性の根拠として用いられる（例えば、参考文献１参照）。ＳＩＳ問題とは、要約すれば、素体Ｚｑ上（ただし、ｑは素数）のｎ行ｍ列（ただし、ｎおよびｍは１以上の整数、例えば２以上の整数）の行列Ｂに対して、Ｂｒ＝０となる小さなｍ次元のベクトルｒを求める問題である。小さなベクトルとは、ノルムがある達成可能な小さな正値ｓ以下であることを意味する。例えば、その要素がほとんど０または１で構成されているベクトルは小さいベクトルといえる。例えば、ＳＩＳ問題とは、一様ランダムなＺｑの元からなるｎ行ｍ列の行列Ｂ∈Ｚｑｎ×ｍ（ただし、ｍはｎの多項式で得られる）に対し、以下の式（１）および（２）を満たす整数集合Ｚの元からなるｍ次元のベクトルｒ∈Λ⊥（Ｂ）を求める問題である。
Λ⊥（Ｂ）＝｛ｒ∈Ｚｍ：Ｂｒ＝０∈Ｚｑｎ｝⊆Ｚｍ    （１）
｜r｜２≦ｓ    （２）
ただし、｜r｜２はｒのユークリッドノルムを表す。
［参考文献１］David Cash, Dennis Hofheinz, Eike Kiltz, Chris Perkest ,“Bonsai, Trees, or How to Delegate a Lattice Basis,” Advances in Cryptology - EUROCRYPT 2010, Lecture Notes in Computer Science Volume 6110, 2010, 523-552.
【００１１】
＜アルゴリズムＧｅｎＢａｓｉｓおよびＳａｍｐｌｅＤ＞
参考文献１，２によれば、以下のようなアルゴリズムＧｅｎＢａｓｉｓおよびＳａｍｐｌｅＤが存在する。
［参考文献２］C. Gentry, C. Peikert, and V. Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” In STOC, pages 197-206. 2008.
【００１２】
アルゴリズムＧｅｎＢａｓｉｓは、ｎ，ｍ，ｑを入力とし、基底ベクトルＳ∈Ｚｍと行列Ｂ∈Ｚｑｎ×ｍとの組（Ｓ，Ｂ）を生成して出力する（（Ｓ，Ｂ）←ＧｅｎＢａｓｉｓ（ｎ，ｍ，ｑ））。ただし、基底ベクトルＳは、行列Ｂについての部分集合（部分ベクトル空間）Λ⊥（Ｂ）を張る何れかの基底であり、トラップドア（落とし戸）として機能する。
【００１３】
アルゴリズムＳａｍｐｌｅＤは、Ｓ，Ｂ，ｙ，ｓを入力とし、以下の式（３）および（４）を満たす整数集合Ｚの元からなるｍ次元のベクトルｘ∈Λｙ⊥（Ｂ）を離散ガウス分布（Discrete Gaussian Distribution）Ｄ（Λｙ⊥（Ｂ），ｓ）に従って選択して出力する（ｘ←ＳａｍｐｌｅＤ（Ｓ，Ｂ，ｙ，ｓ））。
Λｙ⊥（Ｂ）＝｛ｘ∈Ｚｍ：Ｂｘ＝ｙ｝    （３）
｜ｘ｜２≦ｓ    （４）
ただし、ｙ∈ＺｑｎはＺｑの元を要素とするランダムなｎ次元のベクトルである。離散ガウス分布Ｄ（Λｙ⊥（Ｂ），ｓ）とは、各ベクトルｘ∈Λｙ⊥（Ｂ）に対する確率がガウス分布ρｓ（ｘ）＝ｅｘｐ（−π｜ｘ｜２／ｓ２）に比例し、その他のベクトルに対する確率が０となる確率分布を意味する。なお｜ｘ｜２はｘのノルムを表す。トラップドアとして機能する基底ベクトルＳがない場合、このようなベクトルｘを求めることは困難である。
【００１４】
＜ＳＩＳ問題の困難性に基づくカメレオンハッシュ関数＞
参考文献１では、上記のＳＩＳ問題の困難性に基づいてカメレオンハッシュを構成した。以下、これについて説明する。
安全性のパラメータをｋ，ｎ，ｍ，ｓとする。ただし、ｋは１以上の整数（例えば、２以上の整数）である。まず、（Ｓ，Ｂ）←ＧｅｎＢａｓｉｓ（ｎ，ｍ，ｑ）を計算し、ｎ行ｋ列のＺｑ上の行列Ａ∈Ｚｑｎ×ｋをランダムに選ぶ。（Ａ，Ｂ）をハッシュ鍵として公開し、Ｓをトラップドアとして秘密に保持する。メッセージはｋビットのビット列であり、その各ビットをＺｑ上の値０，１に割り当てて、ｋ個のＺｑ要素からなる行ベクトルで表現する（Ｍ∈Ｚｑｋ）。Ｄ（Ｚｍ，ｓ）をｓで制限されるＺｍ上のガウス分布とする。Ｄ（Ｚｍ，ｓ）は、各ベクトルｒ∈Ｚｍに対する確率が分布ρｓ（ｒ）＝ｅｘｐ（−π｜ｒ｜２／ｓ２）に比例するガウス分布を意味する。メッセージＭをハッシュするには、Ｚｐ上のｍ行ベクトルｒ∈Ｚｍを分布Ｄ（Ｚｍ，ｓ）に従って選び、Ｈａｓｈ（ｍ，ｒ）＝ＡＭ＋Ｂｒ∈Ｚｎを計算し、その出力であるｎ次元のベクトルＨａｓｈ（ｍ，ｒ）∈Ｚｎをハッシュ値ｈとする。任意のハッシュ値ｈと任意のメッセージＭ’∈Ｚｑｋに対して、ｈ＝ＡＭ’＋Ｂｒ’となるベクトルｒ’∈Ｚｎは、トラップドアである基底ベクトルＳを用いてｒ’＝ＳａｍｐｌｅＤ（Ｓ，Ｂ，ｈ−ＡＭ’，ｓ）のように計算できる。一方、Ｓを知らない場合、そのようなｒ’を求めることはＳＩＳ問題を解くことに帰着されるため、困難である。
【００１５】
［第１実施形態］
次に第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の署名システム１は、鍵生成装置１１、署名生成装置１２、および署名検証装置１３を有しており、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の鍵生成装置１１は、基底生成部１１１、行列生成部１１２、鍵構成部１１３、出力部１１４、および制御部１１９を有する。図３Ａに例示するように、本形態の署名生成装置１２は、入力部１２１、記憶部１２２、選択部１２３、演算部１２４，１２６、タグ選択部１２５、出力部１２７、および制御部１２９を有する。図３Ｂに例示するように、本形態の署名検証装置１３は、入力部１３１、記憶部１３２、演算部１３４、判定部１３６、および制御部１３９を有する。鍵生成装置１１、署名生成装置１２、および署名検証装置１３は、それぞれ制御部１１９，１２９、および１３９の制御のもとで各処理を実行する。鍵生成装置１１、署名生成装置１２、および署名検証装置１３は、それぞれ、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。
【００１６】
＜鍵生成処理＞
鍵生成処理を説明する。なお、事前に安全性のパラメータｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１，ｓ，ｑが設定されているとする。ただし、ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１は１以上の整数であり、例えば、これらは２以上の整数である。ｓは正値であり、ｑは素数である。また、Ｚｑｎ１の元をｋ０個の｛０，１｝∈Ｚｑからなるｋ０次元のベクトルにマッピングするＺｑｎ１→｛０，１｝ｋ０なる関数Ｔが設定されているとする。ただし、上付き添え字の「ｎ１」および「ｋ０」は、それぞれ「ｎ１」および「ｋ０」を表す。関数Ｔはターゲット衝突困難性を持つ関数である。関数Ｔの構成に限定はないが、例えば、ターゲット衝突困難なハッシュ関数をＴとして用いることができる。
【００１７】
鍵生成装置１１（図２）は、鍵生成関数ＴＯＳ．ｋｅｙ（ｎ０，ｋ０，ｍ０，ｎ１，ｋ１，ｍ１，ｓ）を実行して、公開鍵ｐｋと秘密鍵ｓｋとの鍵ペア（ｓｋ，ｐｋ）を生成する。まず、図４Ａに例示するように、鍵生成装置１１の基底生成部１１１が、ｎ０，ｍ０，ｑを入力として（Ｓ０，Ｂ０）←ＧｅｎＢａｓｉｓ（ｎ０，ｍ０，ｑ）を計算する。Ｂ０∈Ｚｑｎ０×ｍ０はｎ０行ｍ０列の行例である。ただし、上付き添え字の「ｎ０」および「ｍ０」は「ｎ０」および「ｍ０」をそれぞれ表す。Ｓ０∈Ｚｍ０は行例Ｂ０に対応する秘密情報であるトラップドアである。前述のように、トラップドアＳ０はＢ０ｒ０＝０を満たすｍ０次元のベクトルｒ０が属する部分集合（部分ベクトル空間）を張るｍ０次元の基底ベクトルの何れかである。（Ｓ０，Ｂ０）は鍵構成部１１３に送られる（ステップＳ１１１）。
【００１８】
行列生成部１１２は、ｎ０行ｋ０列の行例Ａ０∈Ｚｑｎ０×ｋ０、ｎ１行ｋ１列の行例Ａ１∈Ｚｑｎ１×ｋ１、およびｎ１行ｍ１列の行例Ｂ１∈Ｚｑｎ１×ｍ１を、それぞれランダムに選択する。Ａ０，Ａ１，Ｂ１は鍵構成部１１３に送られる（ステップＳ１１２）。
【００１９】
鍵構成部１１３は、Ｓ０，Ｂ０，Ａ０，Ａ１，Ｂ１を入力とし、公開鍵ｐｋ＝（Ａ０，Ｂ０，Ａ１，Ｂ１，Ｔ，ｓ）および秘密鍵ｓｋ＝（Ｓ０）を構成して出力する。公開鍵ｐｋと秘密鍵ｓｋとの鍵ペア（ｓｋ，ｐｋ）は、出力部１１４に送られる（ステップＳ１１３）。
【００２０】
出力部１１４は、公開鍵ｐｋを署名生成装置１２（図３Ａ）および署名検証装置１３（図３Ｂ）に送信する。公開鍵ｐｋは、署名生成装置１２の入力部１２１および署名検証装置１３の入力部１３１に入力され、記憶部１２２および記憶部１３２に格納される。秘密鍵ｓｋは署名生成装置１２に安全に送られ、署名生成装置１２の入力部１２１に入力され、記憶部１２２に安全に格納される。秘密鍵ｓｋは秘密情報である（ステップＳ１１４）。
【００２１】
＜署名生成処理＞
署名生成処理を説明する。図４Ｂに例示するように、まず、メッセージｍｓｇに対応するｋ１次元のベクトルＭ１∈Ｚｑｋ１が、署名生成装置１２（図３Ａ）の入力部１２１に入力される。ベクトルＭ１はｋ１個の要素｛０，１｝∈Ｚｑｋ１からなる行ベクトルである。ベクトルＭ１は記憶部１２２に格納される（ステップＳ１２１）。
【００２２】
タグ選択部１２５は公開鍵ｐｋを入力とし、タグ生成関数ＴＯＳ.Ｔａｇ（ｐｋ）を実行してｎ０次元のベクトルｚ０∈Ｚｑｎ０をランダムに選択し、これをタグｚ０として出力する。タグｚ０は署名生成処理のたびに新たに選択される。ただし、タグ選択部１２５は、署名生成処理のたびにランダムに生成したベクトルをタグｚ０としてもよいし、事前にランダムに複数個生成しておいたｎ０次元のベクトルから署名生成処理のたびにタグｚ０を選択してもよい。選択されたタグｚ０は演算部１２６および出力部１２７に送られる（ステップＳ１２５）。
【００２３】
選択部１２３および演算部１２４，１２６は、署名生成関数ＴＯＳ．Ｓｉｇn（ｓｋ，Ｍ１，ｚ０）を実行して署名σを生成する。選択部１２３は、ガウス分布Ｄ（Ｚｍ１，ｓ）（前述のＤ（Ｚｍ，ｓ）においてｍ＝ｍ１とした分布）に従ってｍ１次元のベクトルσ１∈Ｚｑｍ１を選択して出力する。すなわち、ベクトルσ１の要素はガウス分布に従って選択される。ベクトルσ１は署名生成処理のたびに新たに選択される。ただし、選択部１２３は、署名生成処理のたびにガウス分布Ｄ（Ｚｍ１，ｓ）に従ってベクトルσ１を生成してもよいし、事前にガウス分布Ｄ（Ｚｍ１，ｓ）に従って複数個生成しておいたがｍ１次元のベクトルから署名生成処理のたびにベクトルσ１を選択してもよい。選択されたベクトルσ１は演算部１２４および出力部１２７に送られる（ステップＳ１２３）。
【００２４】
演算部１２４は、記憶部１２２から読み出した公開鍵ｐｋ、および選択部１２３から送られたベクトルσ１を入力とし、ｎ１次元のベクトルｈ１＝Ａ１Ｍ１＋Ｂ１σ１∈Ｚｑｎ１（図５Ａ）を含む情報に対応するｋ０次元のベクトルｚ１を得る。本形態では、演算部１２４は、ｎ１次元のベクトルｈ１を関数Ｔに入力してｋ０次元のベクトルｚ１＝Ｔ（ｈ１）を得て出力する（図５Ｂ）。ベクトルｚ１は演算部１２６に送られる（ステップＳ１２４）。
【００２５】
演算部１２６は、記憶部１２２から読み出した公開鍵ｓｋおよび秘密鍵ｓｋ、タグ選択部１２５から送られたタグｚ０、ならびに演算部１２４から送られたベクトルｚ１を入力とし、ｚ０＝Ａ０ｚ１＋Ｂ０σ０（図６Ａ）を満たすｍ０次元のベクトルσ０∈Ｚｑｍ０を得る。本形態の演算部１２６は、秘密鍵ｓｋからトラップドアである基底ベクトルＳ０を抽出し、公開鍵ｐｋからＡ０，Ｂ０を抽出し、ｚ０−Ａ０ｚ１（図６Ｂ）を得て、ｍ０次元のベクトルσ０＝ＳａｍｐｌｅＤ（Ｓ０，Ｂ０，ｚ０−Ａ０ｚ１，ｓ）∈Ｚｑｍ０（図６Ｃ）得て出力する。なお、タグｚ０を使い捨て公開鍵とみた場合、ベクトルσ０はタグｚ０に対応する使い捨て秘密鍵である。本形態では、アルゴリズムＳａｍｐｌｅＤによって使い捨て秘密鍵に相当するベクトルσ０を生成できるため、ベクトルσ０を保持しておく必要がない。すなわち、タグ付き使い捨て署名を実現できる。また、基底ベクトル（トラップドア）Ｓ０を知らない者がベクトルσ０を求めることはＳＩＳ問題を解くことに帰着し、困難である。ベクトルσ０は出力部１２７に送られる（ステップＳ１２６）。
【００２６】
出力部１２７は、タグｚ０、ベクトルσ０およびσ１を含む署名σ＝（σ０，σ１）、および記憶部１２２から読み出したベクトルＭ１を出力する（ステップＳ１２７）。
【００２７】
＜署名検証処理＞
署名検証処理を説明する。署名検証装置１３は、署名検証関数ＴＯＳ．Ｖｒｆ（ｐｋ,ｚ０,Ｍ１,σ）を実行する。図４Ｃに例示するように、タグｚ０、署名σ＝（σ０，σ１）、およびベクトルＭ１が、署名検証装置１３の入力部１３１に入力され、記憶部１３２に格納される。なお、入力部１３１に入力されるタグｚ０、署名σ＝（σ０，σ１）、およびベクトルＭ１は、上述のように正しく生成されたものとは限らない（ステップＳ１３１）。
【００２８】
判定部１３６は、記憶部１３２から署名σ＝（σ０，σ１）および公開鍵ｐｋを読み出し、σ０およびσ１がガウス分布Ｄ（Ｚｍ１，ｓ）に従ったものであるかを判定する。この判定は、例えば、｜ｒ｜≦ｓを満たすかを判定し、｜ｒ｜≦ｓを満たせば、σ０およびσ１がガウス分布Ｄ（Ｚｍ１，ｓ）に従ったものと判定することにする。σ０およびσ１がガウス分布Ｄ（Ｚｍ１，ｓ）に従ったものではないと判定された場合には、判定部１３６は検証失敗を表す「０」を出力し（ステップＳ１３６０）、処理を終了する。一方、σ０およびσ１がガウス分布Ｄ（Ｚｍ１，ｓ）に従ったものであると判定された場合、ステップＳ１３４に進む。
【００２９】
ステップＳ１３４では、演算部１３４が、記憶部１３２から、公開鍵ｐｋ、タグｚ０、署名σ＝（σ０，σ１）、およびベクトルＭ１を読み出し、これらを用い、ｈ１＝Ａ１Ｍ１＋Ｂ１σ１（図５Ａ）を含む情報に対応するｋ０次元のベクトルｚ１∈Ｚｑｋ０を得る。本形態では、演算部１３４は、ｎ１次元のベクトルｈ１を関数Ｔに入力してｋ０次元のベクトルｚ１＝Ｔ（ｈ１）を得て出力する（図５Ｂ）。ベクトルｚ１は判定部１３６に送られる（ステップＳ１３４）。
【００３０】
判定部１３６は、ベクトルｚ１、および記憶部１３２から読み出した公開鍵ｐｋおよびベクトルσ０を入力とし、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を判定する。この判定は、（１）ｚ０とＡ０ｚ１＋Ｂ０σ０とが一致するか否かによって行われてもよいし、（２）ｚ０の関数値とＡ０ｚ１＋Ｂ０σ０の関数値とが一致するか否かによって行われてもよいし、（３）ｚ０の関数値とＡ０ｚ１＋Ｂ０σ０の関数値とが所定の関係を満たすか否かによっても行われてもよい。あるいは、（１）〜（３）の何れかの条件を満たし、さらに別の条件を満たすか否かを判定してもよい。すなわち、ｚ０＝Ａ０ｚ１＋Ｂ０σ０を満たすことを必要条件とする検証条件を判定するのであれば、どのような判定が行われてもよい。ここで検証条件を満たさないと判断した場合、判定部１３６は検証失敗を表す「０」を出力し（ステップＳ１３６０）、処理を終了する。一方、検証条件を満たすと判断した場合、判定部１３６は検証成功を表す「１」を出力し（ステップＳ１３６１）、処理を終了する。
【００３１】
＜本形態の特徴＞
一般的なカメレオンハッシュ関数では、メッセージがあるハッシュ値になるような乱数を求めるためには、そのハッシュ値を生成したときに用いた乱数（および元のメッセージ）が必要となる。そのため、ハッシュ値をタグ（使い捨て公開鍵）として署名システムを構成する場合、その生成に利用した乱数（使い捨て秘密鍵）を保存する必要が生じてしまう。これに対し、本形態ではＳＩＳ問題の困難性に基づくカメレオンハッシュ関数を用いて署名システムを構成したため、そのような乱数（ベクトルσ０）を保存する必要はなく、秘密のトラップドアとハッシュ値のみから乱数（ベクトルσ０）を求めることができる。この特性を利用して、ハッシュ値に対応するベクトルをタグｚ０とし、トラップドアＳ０を長期の秘密鍵ｓｋとすることで、タグ付き使い捨て署名を構成できた。また、格子上の問題の一種であるＳＩＳ問題に基づいて安全性が担保されるため、量子計算機が実現したとしてもその安全性を保持できる。
【００３２】
［第１実施形態の変形例］
第１実施形態のステップＳ１２４およびＳ１３４では、ｎ１次元のベクトルｈ１を関数Ｔに入力してｋ０次元のベクトルｚ１＝Ｔ（ｈ１）を得た（図５Ｂ）。しかしながら、衝突が生じないようにｎ１次元のベクトルｈ１をｋ０次元のベクトルｚ１にマッピングできるのであれば、他の関数を用いてもよい。例えば、Ｚｑｎ１→｛０，１｝ｋ０なる関数Ｔに代えてＺｑｎ１＋ｎ２→｛０，１｝ｋ０なる関数Ｔ’（例えば、ターゲット衝突困難なハッシュ関数）を用いることにし、ｎ１次元のベクトルｈ１とｎ２次元のベクトルｗ１との連結ｈ１｜ｗ１に対してｋ０次元のベクトルｚ１＝Ｔ’（ｈ１｜ｗ１）を得てもよい（図５Ｃ）。ｗ１の例は公開鍵ｐｋ等の公開情報である。演算部１２４と演算部１３４とで同じｗ１が用いられる。
【００３３】
［第２実施形態］
次に第２実施形態を説明する。本形態は第１実施形態の変形例であり、関数Ｔを用いない構成である。以下では第１実施形態との相違点を中心に説明し、第１実施形態と同じ部分については第１実施形態と同じ参照番号を用い、説明を省略する。
【００３４】
＜構成＞
図１に例示するように、本形態の署名システム２は、鍵生成装置２１、署名生成装置２２、および署名検証装置２３を有している。図２に例示するように、本形態の鍵生成装置２１は、基底生成部１１１、行列生成部２１２、鍵構成部２１３、出力部１１４、および制御部１１９を有する。図３Ａに例示するように、本形態の署名生成装置２２は、入力部１２１、記憶部１２２、選択部１２３、演算部２２４，１２６、タグ選択部１２５、出力部１２７、および制御部１２９を有する。図３Ｂに例示するように、本形態の署名検証装置２３は、入力部１３１、記憶部１３２、演算部２３４、判定部１３６、および制御部１３９を有する。
【００３５】
＜鍵生成処理＞
本形態の鍵生成処理が第１実施形態の鍵生成処理と相違するのは、ｎ１＝ｋ０であり、関数Ｔが設定されない点である。図４Ａに例示するように、まず、基底生成部１１１がステップＳ１１１を実行し、行列生成部２１２がｎ１＝ｋ０としたステップＳ１１２の処理を実行し（ステップＳ２１２）、鍵構成部２１３がＳ０，Ｂ０，Ａ０，Ａ１，Ｂ１を入力とし、公開鍵ｐｋ＝（Ａ０，Ｂ０，Ａ１，Ｂ１，ｓ）および秘密鍵ｓｋ＝（Ｓ０）を構成して出力する（ステップＳ２１３）。その後、出力部１１４がステップＳ１１４の処理を行い、公開鍵ｐｋは、署名生成装置２２の入力部１２１および署名検証装置２３の入力部１３１に入力され、記憶部１２２および記憶部１３２に格納される。秘密鍵ｓｋは署名生成装置２２に安全に送られ、署名生成装置２２の入力部１２１に入力され、記憶部１２２に安全に格納される。
【００３６】
＜署名生成処理＞
本形態の署名生成処理は、第１実施形態の署名生成処理のステップＳ１２４をステップＳ２２４に置換したものである。ステップＳ２２４のみを説明する。ステップＳ２２４では、演算部２２４は、記憶部１２２から読み出した公開鍵ｐｋ、および選択部１２３から送られたベクトルσ１を入力とし、ｎ１＝ｋ０次元のベクトルｈ１＝Ａ１Ｍ１＋Ｂ１σ１∈Ｚｑｋ０（図７Ａ）を含む情報に対応するｋ０次元のベクトルｚ１を得る。本形態の演算部２２４は、ｋ０次元のベクトルｈ１をそのままｚ１として出力する（図７Ｂ）。ベクトルｚ１は演算部１２６に送られる（ステップＳ２２４）。その他は、第１実施形態と同じである。
【００３７】
＜署名検証処理＞
本形態の署名検証処理は、第１実施形態の署名検証処理のステップＳ１３４をステップＳ２３４に置換したものである。ステップＳ２３４のみを説明する。ステップＳ２３４では、演算部２３４が、記憶部１３２から、公開鍵ｐｋ、タグｚ０、署名σ＝（σ０，σ１）、およびベクトルＭ１を読み出し、これらを用い、ｈ１＝Ａ１Ｍ１＋Ｂ１σ１（図７Ａ）を含む情報に対応するｋ０次元のベクトルｚ１∈Ｚｑｋ０を得る。本形態では、演算部２３４は、ｋ０次元のベクトルｈ１をそのままベクトルｚ１として出力する（図７Ｂ）。ベクトルｚ１は判定部１３６に送られる（ステップＳ２３４）。その他は、第１実施形態と同じである。
【００３８】
［第２実施形態の変形例］
第２実施形態のステップＳ２２４およびＳ２３４では、ｎ１＝ｋ０次元のベクトルｈ１をそのままベクトルｚ１とした（図７Ｂ）。しかしながら、ｎ１＜ｋ０とし、ｎ１次元のベクトルｈ１とｋ０−ｎ１次元のベクトルｗ１との連結ｈ１｜ｗ１をそのままｋ０次元のベクトルｚ１としてもよい（図７Ｃ）。ｗ１の例は公開鍵ｐｋ等の公開情報である。演算部２２４と演算部２３４とで同じｗ１が用いられる。
【００３９】
［その他の変形例］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、素体Ｚｑに代えて素体Ｚｑを基礎体とした拡大体を用いてもよいし、ｑに素数以外の正整数を用いることで素体Ｚｑに代えて環Ｚｑを用いてもよい。また、上記の実施形態では、署名生成装置から署名検証装置に対し、署名とタグとメッセージに対応する情報とが同時に送られたが、これらが別々に送られてもよい。例えば、署名が送られる前にタグやメッセージが公開されてもよい。また、署名σ＝（σ０，σ１）を構成するσ０およびσ１がガウス分布Ｄ（Ｚｍ１，ｓ）に従ったものであることが明らかな場合等には、ステップＳ１３６２の処理が省略されてもよい。また、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。
【００４０】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４１】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４２】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４４】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００４５】
１，２  署名システム
１１，２１  鍵生成装置
１２，２２  署名生成装置
１３，２３  署名検証装置
【図１】
2016001248.tif 000003
【図２】
2016001248.tif 000004
【図３】
2016001248.tif 000005
【図４】
2016001248.tif 000006
【図５】
2016001248.tif 000007
【図６】
2016001248.tif 000008
【図７】
2016001248.tif 000009