(57)【要約】【課題】  処理が高速である否認不可署名方式を提供すること。【解決手段】  公開鍵（Ｄ，Ｐ，ｋ，ｔ）と秘密鍵（Ｄ１，ｑ）が与えられる時、検証者側において、署名ＳのノルムＮ（Ｓ）がｋビット以下のときはメッセージｍのメッセージイデアルＭを計算し、ｔビットより小さい乱数ｒを生成してＨ＝（Ｍ／Ｓ）ｒを計算し、ノルムがｋ−１ビットより小さい乱数イデアルＢを生成してＣ＝ＢＨを計算することにより、チャレンジＣを生成し、署名者側において、秘密鍵（Ｄ１，ｑ）を用いて、上記チャレンジＣを類群Ｃｌ（Ｄ１）にマップし、マップされたチャレンジＣを類群Ｃｌ（Ｄ）に引き戻し、マップして引き戻した結果を二乗することにより応答Ｗを生成し、検証者側において、Ｗ＝Ｂ２が成り立つか否かをチェックして、成り立つときは署名Ｓが正当であると判断する。【選択図】    図３
2004222332.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）認証機関から電子商取引／情報サービス提供者に公開鍵と、秘密鍵と、否認不可署名方式による公開鍵に対する署名とを発行するステップと、
（ｂ）電子商取引／情報サービス提供者から提供された公開鍵の正当性を証明するために、電子商取引／情報サービス提供者からユーザに提供された署名の検証処理を認証機関がユーザとインタラクティブに実行するステップと、
を有することを特徴とする、ユーザが電子商取引／情報サービス提供者の正当性をチェックできるようにする方法。
【請求項２】
前記ステップ（ａ）は、二次体に基づく否認不可署名方式に従って署名を生成することを特徴とする請求項１記載の方法。
【請求項３】
前記ステップ（ａ）は、更に、
（ａ１）２つの素数ｐ，ｑ（ｐ，ｑ＞４、ｐ＝３ mod ４、√（ｐ／３）＜ｑ）を生成し、Ｄ１＝−ｐ及びＤ＝Ｄ１ｑ２を計算し、√｜Ｄ１｜／４のビット長ｋ及びｑ−（Ｄ１／ｑ）のビット長ｔ、但し（Ｄ１／ｑ）はクロネッカー記号を表す、を求めて、類群Ｃｌ（Ｄ）から類群Ｃｌ（Ｄ１）のマップのカーネル元Ｐを生成することによって、認証機関において公開鍵（Ｄ，Ｐ，ｋ，ｔ）及び秘密鍵（Ｄ１，ｑ）を生成するステップと、
（ａ２）メッセージｍを類群Ｃｌ（Ｄ）においてノルムがｋ＋１ビットより長いメッセージイデアルＭに埋め込み、メッセージイデアルＭを類群Ｃｌ（Ｄ１）にマップし、マップされたメッセージイデアルＭを類群Ｃｌ（Ｄ）に引き戻すことによって、認証機関においてメッセージｍに対する署名Ｓを生成するステップと、
を有することを特徴とする請求項２記載の方法。
【請求項４】
前記ステップ（ｂ）は、更に、
（ｂ１）ユーザ側において、署名ＳのノルムＮ（Ｓ）がｋビットより小さいか否かをチェックして、ノルムＮ（Ｓ）がｋビットより大きいときは署名Ｓが不正であると判断し、ノルムＮ（Ｓ）がｋビット以下のときは、メッセージｍのメッセージイデアルＭを計算し、ｔビットより小さい乱数整数ｒを生成し、Ｈ＝（Ｍ／Ｓ）ｒを計算し、ノルムがｋ−１ビットより小さい乱数イデアルＢを生成してＣ＝ＢＨを計算することにより、チャレンジＣを生成するステップと、
（ｂ２）認証機関側において、秘密鍵（Ｄ１，ｑ）を用いて、上記チャレンジＣを類群Ｃｌ（Ｄ１）にマップし、マップされたチャレンジＣを類群Ｃｌ（Ｄ）に引き戻し、マップして引き戻した結果を二乗することにより応答Ｗを生成するステップと、
（ｂ３）ユーザ側において、Ｗ＝Ｂ２が成り立つか否かをチェックして、成り立つときは署名Ｓが正当であり、そうでなければ署名Ｓは不正であると判断するステップと、
を有することを特徴とする請求項３記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名者のプライバシーを保護できるデジタル署名の一種である否認不可署名方式に関するものである。
【背景技術】
【０００２】
電気通信において、電子署名技術はデータの正当性を保証する技術として有効である。最も広く利用されている電子署名技術は、ＲＳＡ署名とよばれる冪乗剰余演算を用いるタイプの電子署名である（参照：R.Rivest, A.Shamir and L.M.Adelman, "A method for obtaining digital signatures and public key cryptosystems", Communications of ACM, 21(2), pp.120-126, 1978)。
【０００３】
署名技術の性能を評価するポイントは、安全性と署名の生成・検証の速度であり、安全性が高く、処理速度が速い署名がより優秀な署名方式である。ＲＳＡ署名は、公開情報である公開鍵から秘密鍵を得ることが計算量的に困難であることに安全性の根拠を置いている。公開鍵のサイズを大きく取ればそれだけ安全性が増す。また、このＲＳＡ署名は、高次の冪乗計算を行うため計算量が多く、署名の生成・検証に時間がかかることが大きな欠点である。
【０００４】
電子署名を拡張した方式として、ChaumとAntwerpenは否認不可署名を提案している［参照：D.Chaum, H.van Antwerpen, "Undeniable signature", Advances in Cryptology - CRYPTO'89, LNCS 435, pp.212-216, Springer-Verlag, 1990］。否認不可署名は、署名者と通信を行うことなしでは署名の正当性が確認できないという性質を有するので、署名が一人歩きすることがなく、署名者のプライバシーが守られる方式である。標準的な応用例として、ソフトウェアの安全な配布システムが挙げられる。ソフトウェア購入者は、署名者である配布元とコンタクトすることにより、第三者によってウイルスなどが混入されていないことが確認できる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
今日最も効果的な否認不可署名方式として、ＲＳＡ型否認不可署名方式［R.Gennaro, H.Krawczyk, T.Rabin, "RSA-based Undeniable Signatures", Advances in Cryptology - CRYPTO'89, LNCS 435, pp.212-216, Springer-Verlag, 1990］がある。この方式は、上記のＲＳＡ署名をベースに構成された否認不可署名であり、同じく処理の複雑さが問題である。
【０００６】
これに関して、現在秘密鍵が安全に保管でき容易に携帯できる媒体として、スマートカードが注目されている。しかし、スマートカードは計算資源が乏しく、ＲＳＡ型の否認不可署名を実行するには処理が遅いという問題点がある。また、大規模な流通システムを想定した場合、サーバへの負荷集中が問題となる。これらの理由から、効率よく高速で計算処理可能な否認不可署名が求められている。
【０００７】
従って、本発明が解決しようとする課題は、ＲＳＡ型否認不可署名と比較して処理が高速である否認不可署名方式を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明は、（ａ）認証機関から電子商取引／情報サービス提供者に公開鍵と、秘密鍵と、否認不可署名方式による公開鍵に対する署名とを発行するステップと、（ｂ）電子商取引／情報サービス提供者から提供された公開鍵の正当性を証明するために、電子商取引／情報サービス提供者からユーザに提供された署名の検証処理を認証機関がユーザとインタラクティブに実行するステップと、を有することを特徴とする、ユーザが電子商取引／情報サービス提供者の正当性をチェックできるようにする方法を提供する。
【発明の効果】
【０００９】
以上説明したように、本発明によれば、ＲＳＡ型否認不可署名と比較して処理が高速である否認不可署名方式を提供することが可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、図１〜図９を参照して、本発明に係る否認不可署名方式の実施形態を詳細に説明する。
【００１１】
本発明に係る否認不可署名方式は、二次体の類群の構造、特に最大整数環と非最大整数環の類群間の移行のための高速アルゴリズムを利用する。
【００１２】
はじめに、この否認不可署名方式に利用される二次体の性質について簡単にまとめる。
【００１３】
４以上の素数ｐ，ｑ（ｐ＝３ mod ４，√（ｐ／３）＜ｑ）に対して、Ｄ１＝−ｐおよびＤ＝Ｄ１ｑ２とおく。Ｄ１を基本判別式、Ｄを非基本判別式、ｑをコンダクタと呼ぶ。Ｚを有理整数環とすると、ＯＤ＝Ｚ＋（Ｄ＋√Ｄ）／２Ｚを判別式Ｄの二次整環と呼ぶ。判別式Ｄの類群をＣｌ（Ｄ）と記述する。類群Ｃｌ（Ｄ）の元Ａ（イデアルと呼ぶ）は、Ａ＝（ａ，ｂ）と二種類の整数で表される。ここで、ａは正の整数、ｂは、ｂ２＝Ｄ mod ４ａを満たす整数である。もし、−ａ＜ｂ≦ａ，｜ｂ｜≦ａ≦ｃ＝（ｂ２−Ｄ）／４ａで、更に、ａ＝ｃまたはａ＝｜ｂ｜の時にｂ≧０とすると、イデアルＡに対して一意的に（ａ，ｂ）が決まる。イデアルＡのノルムはＮ（Ａ）＝ａと表し、ここでＡ＝（ａ，ｂ）である。各シンボルの定義は図１に示す表にまとめられた通りである。
【００１４】
本発明の否認不可署名方式では、イデアルＡの類群Ｃｌ（Ｄ）での冪剰余Ａｒを計算する必要がある。冪剰余Ａｒの計算は、文献［J.Buchmann, S.Duellman and H.C.Williams, "On the complexity and efficiency of a new key exchange system", Advances in Cryptology - CRYPTO'89, LNCS 434, pp.597-616, Springer-Verlag, 1990］に述べられたアルゴリズム"Multply"、"Square"、"Reduce"、またはこのバリエーションである"Square&Multiply"を利用するか、文献［D.Shanks, "On Gauss and composition I, II", NATO ASI on Number Theory and Applications (R.A.Mollin, editor), pp.163-179, Kluwer Academic Press, 1989]に述べられたアルゴリズム"NUCOMP","NUDUPL"を使用する。
【００１５】
また、本発明の否認不可署名方式では、最大整数環の類群Ｃｌ（Ｄ１）と非最大整数環の類群Ｃｌ（Ｄ）との間をスイッチするアルゴリズムが重要な役割を果たす。この計算は、最大公約の計算等の簡単な演算を行うだけでよく、非常に高速である。具体的な計算例としては、文献［D.Huehnlen, M.J.Jacobson,Jr., S.Paulus and T.Takagi, "A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption", Advances in Cryptology - EUROCRYPT'98, LNCS 1403, pp.294-307, Springer-Verlag, 1998］に述べられたアルゴリズム"GoToMaxOrder"および"GoToNonMAxOrder"を使用する。
【００１６】
以下、図２〜図５を参照して、本発明に係る否認不可署名方式の処理の詳細を説明する。
【００１７】
図２は、この否認不可署名方式に用いられるパラメータをまとめたもので、図３は、この否認不可署名方式の全般的な処理手順を示し、図４は、図３の処理手順を実行するための署名者装置及び検証者装置の構成例を示す。
【００１８】
図３に示すように、この否認不可署名方式は、一般に、鍵生成（ステップＳ１０）、署名生成（ステップＳ２０）及び署名検証（ステップＳ３０）の３つの主要な段階からなる。
【００１９】
鍵生成段階において、署名者装置１０の鍵生成部１１は、次の動作を実行する。即ち、２つの素数ｐ，ｑ（ｐ，ｑ＞４、ｐ＝３ mod ４、√（ｐ／３）＜ｑ）を生成し、Ｄ１＝−ｐ、及び、Ｄ＝Ｄ１ｑ２を計算して、√｜Ｄ１｜／４のビット長ｋとｑ−（Ｄ１／ｑ）のビット長ｔ、但し（Ｄ１／ｑ）はクロネッカー記号を表す、を求める。また、判別式Ｄの類群Ｃｌ（Ｄ）から判別式Ｄ１の類群Ｃｌ（Ｄ１）へのマップのカーネル元Ｐを生成する。カーネル元Ｐは以下で説明するアルゴリズム"KERNEL"によって生成される。ここでアルゴリズム"KERNEL"は、カーネル元Ｐ（Ｃｌ（Ｄ）→Ｃｌ（Ｄ１））を生成するアルゴリズムの一例である。そして、公開鍵を（Ｄ，Ｐ，ｋ，ｔ）、秘密鍵を（Ｄ１，ｑ）と定義し、このようにして得られた公開鍵（Ｄ，Ｐ，ｋ，ｔ）及び秘密鍵（Ｄ１，ｑ）を署名者装置１０の鍵記憶部１２に格納する。
【００２０】
この否認不可署名方式の基礎となる二次体に基づく暗号系の安全性は、公知の因数分解問題と等価であるＤからＤ１とｑを計算することの困難さに依存する。この詳細については、D.Huehnlen, M.J.Jacobson,Jr., S.Paulus and T.Takagi, "A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption", Advances in Cryptology - EUROCRYPT'98, LNCS 1403, pp.294-307, Springer-Verlag, 1998を参照。
【００２１】
署名生成段階においては、署名者装置１０の署名生成部１４は次の動作を実行する。即ち、メッセージ生成部１３によって生成されたメッセージｍを類群Ｃｌ（Ｄ）のメッセージイデアルＭ＝（ｕ，ｂ）に埋め込む。メッセージイデアルＭのノルムはｋ＋１ビットより大きく、埋め込みは、以下で説明するアルゴリズム"Embedding"を用いて行う。ここで、アルゴリズム"Embedding"は、メッセージｍをメッセージイデアルＭに埋め込むアルゴリズムの一例である。そして、メッセージイデアルＭに対する署名Ｓを、下記のアルゴリズム"GoToMaxOrder"及び"GoToNonMaxOrder"を用いて、
Ｓ＝GoToNonMaxOrder（GoToMaxOrder（Ｍ））
により生成し、メッセージと署名のペア（ｍ，Ｓ）が得られる。ここで、アルゴリズム"GoToNonMaxOrder"と"GoToMaxOrder"は、基礎判別式Ｄ１の類群Ｃｌ（Ｄ１）にイデアルＭをマップするアルゴリズムと、マップされたイデアルＭを非基本判別式Ｄの類群Ｃｌ（Ｄ）に引き戻すアルゴリズムの一例である。このペア（ｍ，Ｓ）は検証者に送られる。
【００２２】
署名検証ステップは以下の３つのステップを含んでいる。
【００２３】
検証ステップＩ（ステップＳ３１）は、検証者装置２０のノルムチェック部２１及びチャレンジ生成部２２によって以下のように実行される。まず、ノルムチェック部２１によって、署名のノルムＮ（Ｓ）がｋビットより小さいかチェックする。ｋビットより大きい場合は、署名は正しくない。ｋビットより小さい時は、チャレンジ生成部２２によって次のような動作が実行される。即ち、下記のアルゴリズム"Embedding"を用いて、メッセージｍに対するメッセージイデアルＭを計算し、ｔビットより小さい乱数ｒを生成し、Ｈ＝（Ｍ／Ｓ）ｒを計算する。次に、下記のアルゴリズム"Embedding"を用いて、ノルムがｋ−１ビットより小さい乱数イデアルＢを生成し、Ｃ＝ＢＨを計算する。このＣはチャレンジ問題であり、署名者に送られる。ここで、アルゴリズム"Embedding"は乱数イデアルＢを生成するアルゴリズムの一例である。
【００２４】
検証ステップII（ステップＳ３２）は署名者装置１０の応答生成部１５によって次のように実行される。即ち、鍵記憶部１２に格納された秘密鍵（Ｄ１，ｑ）に従って、応答生成部１５は、下記のアルゴリズム"GoToMaxOrder"及び"GoToNonMaxOrder"を用いて、
Ｗ＝（GoToNonMaxOrder（GoToMaxOrder（Ｃ）））２
を計算して、このＷを検証者に応答として送り返す。ここで、アルゴリズム    "GoToNonMaxOrder"と"GoToMaxOrder"は、基礎判別式Ｄ１の類群Ｃｌ（Ｄ１）にイデアルＣをマップするアルゴリズムと、マップされたイデアルＣを非基本判別式Ｄの類群Ｃｌ（Ｄ）に引き戻すアルゴリズムの一例である。
【００２５】
検証ステップIII（ステップＳ３３）は、検証者装置２０の応答チェック部２３によって次のように実行される。即ち、応答チェック部２３は、Ｗ＝Ｂ２が成り立つかどうかをチェックする。成立すれば、署名の正当性が証明され、そうでなければ署名は不正なものである。
【００２６】
なお、否認不可署名方式は、I.Biehl, S.Paulus and T.Takagi, "Efficient Undeniable Signature Schemes based on Ideal Arithmetic in Quadratic Orders", Conference on the Mathematics of Public Key Cryptography, June 1999にも開示されているが、この文献の署名検証段階は本発明の否認不可署名方式で用いるアルゴリズムよりはるかに複雑で時間がかかるZero-Knowledge Protocol for Ｌｋｅｒ を用いており、本発明の否認不可署名方式とは異なるものである。
【００２７】
カーネル元Ｐ（Ｃｌ（Ｄ）→Ｃｌ（Ｄ１））を生成するアルゴリズム"KERNEL"は以下の通りである。
【００２８】
Algorithm KERNEL                        
Input:   基本判別式Ｄ１、コンダクタｑ
Output:  イデアルＰ （Ｃｌ（Ｄ）→Ｃｌ（Ｄ１）
1．/* Generate α ＝（ｘ＋ｙ√Ｄ１）／２*/
1.1. 整数ｘ，ｙ（＜√Ｄ１）を生成する。
【００２９】
2. /* Standard representation of α０ ＝（Ａ，Ｂ） */  
2.1. ｍ＝ｋｙ＋ｎ（ｘ＋ｙＤ１）／２を満たす整数（ｍ，ｋｎ）を求める。
【００３０】
2.2. Ａ←｜（ｘ２−ｙ２Ｄ１）｜／４ｍ２
2.3. Ｂ←（ｋｘ＋ｎ（ｘ＋ｙ）Ｄ１／２）／ｍmod ２Ａ，（−Ａ≦Ｂ＜Ａ）
3．/* Compute GoToNonMaxOrder（Ａ）＝（ａ，ｂ） */
3.1. ａ←Ａ
3.2. ｂ←Ｂｑ mod ２Ａ，（−ａ≦ｂ＜ａ）
4．/* Reduce（ａ，ｂ）*/
4.1. ｃ←（Ｄ−ｂ２）／４ａ
4.2. WHILE｛−ａ＜ｂ≦ａ＜ｃ｝or｛０≦ｂ≦ａ＝ｃ｝ＤＯ
4.2.1. −ａ≦μ＝ｂ＋２λａ＜ａを満たすμ，λを求める。
【００３１】
4.2.2.（ａ，ｂ，ｃ）←（ｃ−（ｂ＋μ）λ／２，μ，ａ）
4.3. IF ａ＝ｃAND ｂ＜０ THEN ｂ←−ｂ
4.4. RETURN（ａ，ｂ）
メッセージｍをイデアルＭへ埋め込むアルゴリズム"Embedding" は以下の通りである。
【００３２】
Algorithm Embedding                     
Input:   非基本判別式Ｄ、ｋビットより小さいメッセージｍ
Output:  メッセージイデアルＭ ∈Ｃｌ（Ｄ）
１．  ｍより大きい素数で平方剰余である最小のものをｕとする。
【００３３】
２．  ｂ２＝Ｄ mod ４ｕ，（−ｕ＜ｂ≦ｕ）を満たすｂを求める。
【００３４】
３．  RETURN Ｍ＝（ｕ，ｂ）
基礎判別式Ｄ１の類群Ｃｌ（Ｄ１）にイデアルをマップするアルゴリズム及びマップされたイデアルを非基本判別式Ｄの類群Ｃｌ（Ｄ）に引き戻すアルゴリズムである"GoToNonMaxOrder"及び"GoToMaxOrder"は以下の通りである。
【００３５】
Algoritym GoToNonMaxOrder                         
Input:   縮約イデアル（Ａ，Ｂ）∈ Ｃｌ（Ｄ１）、コンダクタｑ
Output: （ａ，ｂ）＝Ψ（υ）、但しΨ：（Ｃｌ（Ｄ１）→Ｃｌ（Ｄ）、υはＣｌ（Ｄ）の要素、を満たす縮約イデアル（ａ，ｂ）∈ Ｃｌ（Ｄ）
１．  ａ←Ａ
２．  ｂ←Ｂｑ mod ２ａ、（−ａ≦ｂ＜ａ）
３．  RETURN (ａ，ｂ）
Algorithm GoToMaxOrder                      
Input:  縮約イデアル（ａ，ｂ）∈ Ｃｌ（Ｄ）、基本判別式Ｄ１、コンダクタｑ
Output: （Ａ，Ｂ）＝Φ（α）、但しΦ：（Ｃｌ（Ｄ）→Ｃｌ（Ｄ１）、αはＣｌ（Ｄ１）の要素、を満たす縮約イデアル（Ａ，Ｂ）∈ Ｃｌ（Ｄ１）
1．/* Compute （Ａ，Ｂ）＝（ａ，ｂ）ＯＤ１ */
1.1.  Ａ←ａ
1.2.  ｂ０←Ｄ mod ２
1.3.  μ，λ∈Ｚについて、Solve １＝μｑ＋λ 
1.4   Ｂ←ｂμ＋ａｂ０λ mod ２ａ、（−Ａ≦Ｂ＜Ａ）
2. /* Reduce（Ａ，Ｂ） */  
2.1.  Ｃ←（Ｄ１−Ｂ２）／４Ａ
2.2.  WHILE｛−Ａ＜Ｂ≦Ａ＜Ｃ｝or ｛０≦Ｂ≦Ａ＝Ｃ｝ＤＯ
2.2.1.  剰余を用いた除算により−Ａ≦μ＝Ｂ＋２λＡ＜Ａを満たすμ，λ∈Ｚを求める。
【００３６】
2.2.2. （Ａ，Ｂ，Ｃ）←（Ｃ−（Ｂ＋μ）λ／２，μ，Ａ）
2.3.  IF Ａ＝Ｃ AND Ｂ＜０ THEN Ｂ←−Ｂ
2.4.  RETURN（Ａ，Ｂ）
この否認不可署名方式においては、必要な計算量は少なく、公開鍵が非常に長くても、署名検証は非常に速く行うことが可能である。
【００３７】
この否認不可署名方式の有効性を示すために、この否認不可署名方式及び従来のＲＳＡ型否認不可署名方式をソフトウェアに実装し、公開鍵のビット長が１０２４ビットの場合を例として、２つの方式における各ステップの処理時間を比較した。図５はこのシミュレーションの結果をまとめたものである。図５に示されるように、本発明の否認不可署名方式の鍵生成及び署名検証は従来のＲＳＡ型否認不可署名方式より大幅に速い。
【００３８】
更に、公開鍵のビット長が２倍に、例えば１０２４ビットから２０４８ビットになったとき、本発明の否認不可署名方式の処理時間は２倍に長くなるのみであるが、従来のＲＳＡ型否認不可署名方式の処理時間は約８倍になる。
【００３９】
次に、図６〜図９を参照して、本発明に係る否認不可署名方式の実用的な応用例について詳細に説明する。
【００４０】
図６は、ソフトウェアベンディングサーバ用否認不可署名システムの概略構成を示し、このシステムは、インターネット等の通信網１０８に接続されるクライアント１０１及び１０２、及び、ファイヤーウォール１０９を通して通信網１０８に接続される認証サーバ１０５及びソフトウェアベンディングサーバ１０６からなる。
【００４１】
このシステムにおいて、認証サーバ１０５は、ソフトウェアベンディングサーバ１０６に対し否認不可署名の秘密鍵を発行する。また、認証サーバ１０５は、ソフトウェアベンダの否認不可署名をソフトウェアベンディングサーバ１０６でダウンロード用に提示されている各ソフトウェアに添付する。クライアント１０１又は１０２が否認不可署名の添付されたソフトウェアをダウンロードする時、認証サーバ１０５で否認不可署名を検証するための処理を実行することによって、クライアント１０１又は１０２はソフトウェアがオリジナルから変更されていない（ソフトウェアがコンピュータウィルスに感染していない）ことを証明することができる。従って、このシステムにおいて、クライアント１０１又は１０２が検証者であり、認証サーバ１０５が署名者である。このようにして、ダウンロードしたソフトウェアでコンピュータウィルスに感染したものを検出することが可能となる。
【００４２】
このシステムにおいて本発明に係る否認不可署名方式を用いると、認証サーバには検証ステップ  の実行が要求されるだけで、これは既に記載したように非常に速く行うことができるので、大規模システムの場合においても認証サーバの処理負荷をかなり低減することができる。
【００４３】
更に、本発明の否認不可署名方式において、鍵生成に必要な時間は約１秒であり、従来のＲＳＡ型デジタル署名方式において必要とされる約３０分よりもはるかに短い。従来のＲＳＡ型デジタル署名方式を多数の異なるソフトウェアの署名に用いるとき、鍵生成はかなり時間を要するので、同じ鍵を何度も用いることは実際上避けられない。しかし、この同じ鍵を何度も用いることは安全性の観点からすると問題となり得る。何故なら、１つのソフトウェアに用いた鍵が何等かの方法で一旦攻撃されると、同じ鍵が用いられている全てのソフトウェアの安全性も失われることになるからである。これに関して、本発明の否認不可署名方式では、鍵生成にはほんのわずかな時間しかかからないので、同じ鍵を何度も使う必要がなく、各鍵を１度だけ用いることにより安全性を更に改善することが可能である。
【００４４】
図６のシステムにおいて、各認証サーバは、図７に例示するように構成することができる。図７の構成では、ネットワークインターフェース２０１、ＣＰＵ（中央演算処理部）２０２、主記憶装置２０３、否認不可署名鍵格納エリア２０４、コンソール及びディスプレイインターフェース２０５、磁気ディスク装置等の二次記憶装置２０６、及び、光磁気ディスク装置等の補助記憶装置２０７がバスを介して相互接続されている。ここで、否認不可署名鍵格納エリア２０４はアクセス制御回路２０８を介してバスに接続され、否認不可署名処理プログラム２０９は二次記憶装置２０６に格納される。
【００４５】
図８は、電子商取引サービス用の否認不可署名システムの概略構成を示す。
【００４６】
近年、インターネット上の電子商取引の急速な普及に伴って、顧客と電子商取引業者の間のトラブルも増加している。例えば、顧客が適切な支払いを行ったにもかかわらず商品が配送されないといったトラブルがある。このようなトラブルをなくすために、電子商取引業者としては、信頼できる認証機関によって発行される証明書を取得してこの証明書を購入契約時に顧客に交付することが有効である。ここで、証明書が不正に再利用されないように、証明書に対して否認不可署名を用いることが適切である。
【００４７】
この図８のシステムにおいて、電子商取引業者３０２は、証明書を得るために、認証機関３０３に対して証明要求を行う。この証明要求に対し、認証機関３０３は電子商取引業者３０２の正当性をテストし、電子商取引業者３０２がテストにパスした場合には、認証機関３０３は電子商取引業者３０２に対するデジタル署名の秘密鍵と公開鍵のペアを生成する。認証機関３０３はさらに、本発明の否認不可署名方式を用いて公開鍵に対する署名を生成し、秘密鍵と公開鍵と署名の組を証明書として電子商取引業者３０２に送る。
【００４８】
そして、電子商取引業者３０２から商品を購入する前に、顧客３０１は、以下のようにして電子商取引業者３０２の正当性をチェックする。即ち、顧客３０１はまず電子商取引業者３０２から公開鍵と署名を入手する。それから顧客３０１は認証機関３０３に対して業者認証要求を行う。この業者認証要求に対し、否認不可署名の署名検証が認証機関３０３と署名者とし顧客３０１を検証者として行われる。もし署名検証に失敗すれば、公開鍵は認証機関３０３から発行された真正なものではないことを意味するので顧客３０１は電子商取引業者３０２を信頼すべきではない。
【００４９】
一方、署名検証に成功した場合には、公開鍵は認証機関３０３から発行された真正なものであることを意味する。この場合、顧客３０１は次にランダムデータを生成し、これを電子商取引業者３０２の公開鍵を用いて暗号化し、暗号化したランダムデータを電子商取引業者３０２に送る。これに対し、電子商取引業者３０２は暗号化したランダムデータを電子商取引業者３０２の秘密鍵を用いて復号し、復号したランダムデータを顧客３０１に返送する。そして、顧客３０１は復号されたランダムデータが元のランダムデータを一致するかどうかチェックする。もし一致するなら電子商取引業者３０２が公開鍵に対応する認証機関３０３により発行された真正な秘密鍵も所持していることを意味するので顧客３０１は電子商取引業者３０２を信頼できるものと見做してこの電子商取引業者３０２から商品の購入を行ってもよい。このようにして、電子商取引サービス提供者の正当性をチェックすることが可能となる。
【００５０】
上述した手順を以下のように変形してもよい。
【００５１】
即ち、図８のシステムにおいて、電子商取引業者３０２はホームページを持っており、このホームページの証明書を得るために、認証機関３０３に対して証明要求を行う。この証明要求に対し、認証機関３０３は電子商取引業者３０２の正当性をテストし、電子商取引業者３０２がテストにパスした場合には、認証機関３０３は本発明の否認不可署名方式を用いてホームページのハッシュ値に対する署名を生成し、顧客のブラウザ上に表示された電子商取引業者３０２のホームページ上にこの署名を証明書として掲示する。ここで、証明書は直接電子商取引業者３０２に発行せずに顧客のブラウザ上での電子商取引業者３０２のホームページの表示の上に現れるようにすることにより、電子商取引業者３０２による証明書の不正なコピーを防止することができる。
【００５２】
そして、電子商取引業者３０２から商品を購入する前に、顧客３０１は、以下のようにして電子商取引業者３０２の正当性をチェックする。即ち、顧客３０１はまず電子商取引業者３０２のホームページ上に掲示された証明書をクリックする。すると、署名が顧客３０１に送られると共に、顧客３０１が認証機関３０３にリンクされる。そして、否認不可署名の署名検証が認証機関３０３と署名者とし顧客３０１を検証者として行われる。もし署名検証に失敗すれば、ホームページはそのハッシュ値が認証機関３０３により署名された真正なものではないことを意味するので顧客３０１は電子商取引業者３０２を信頼すべきではない。一方、署名検証に成功した場合には、顧客３０１は電子商取引業者３０２を信頼できるものと見做してこの電子商取引業者３０２から商品の購入を行ってもよい。このようにしても、電子商取引サービス提供者の正当性をチェックすることが可能となる。
【００５３】
図９は、ニュース／メール提供サービス用の否認不可署名システムの概略構成を示す。
【００５４】
近年、ＳＰＡＭメールや、メール又は添付ファイルによるコンピュータウィルス感染や、信頼性のないニュースによる社会混乱の脅威が増加している。このような脅威を取り除くために、ニュース／メール提供者は、提供するニュース／メールに否認不可署名を添付し、受領者が信頼できる認証機関により提供者の正当性を確認した後にのみに受け取ったニュース／メールを開く／読むようにすることができる。
【００５５】
この図９のシステムにおいて、ニュース／メール提供者４０２は、証明書を得るために、認証機関４０３に対して証明要求を行う。この証明要求に対し、認証機関４０３はニュース／メール提供者４０２の正当性をテストし、ニュース／メール提供者４０２がテストにパスした場合には、認証機関４０３はニュース／メール提供者４０２に対するデジタル署名の秘密鍵と公開鍵のペアを生成する。認証機関４０３はさらに、本発明の否認不可署名方式を用いて公開鍵に対する署名を生成し、秘密鍵と公開鍵と署名の組を証明書としてニュース／メール提供者４０２に送る。
【００５６】
そして、ニュース／メール提供者４０２から受け取ったニュース／メールを開封する前に、閲読者４０１は、以下のようにしてニュース／メール提供者４０２の正当性をチェックする。即ち、閲読者４０１はまずニュース／メール提供者４０２から公開鍵と署名を入手する。それから閲読者４０１は認証機関４０３に対して提供者認証要求を行う。この提供者認証要求に対し、否認不可署名の署名検証が認証機関４０３と署名者とし閲読者４０１を検証者として行われる。もし署名検証に失敗すれば、公開鍵は認証機関４０３から発行された真正なものではないことを意味するので閲読者４０１はニュース／メール提供者４０２を信頼すべきではない。
【００５７】
一方、署名検証に成功した場合には、公開鍵は認証機関４０３から発行された真正なものであることを意味する。この場合、閲読者４０１は次にランダムデータを生成し、これをニュース／メール提供者４０２の公開鍵を用いて暗号化し、暗号化したランダムデータをニュース／メール提供者４０２に送る。これに対し、ニュース／メール提供者４０２は暗号化したランダムデータをニュース／メール提供者４０２の秘密鍵を用いて復号し、復号したランダムデータを閲読者４０１に返送する。そして、閲読者４０１は復号されたランダムデータが元のランダムデータを一致するかどうかチェックする。もし一致するならニュース／メール提供者４０２が公開鍵に対応する認証機関４０３により発行された真正な秘密鍵も所持していることを意味するので閲読者４０１はニュース／メール提供者４０２を信頼できるものと見做してこのニュース／メール提供者４０２から受け取ったニュース／メールを開封してもよい。このようにして、情報サービス提供者の正当性をチェックすることが可能となる。
【００５８】
上述した手順を以下のように変形してもよい。
【００５９】
即ち、図９のシステムにおいて、ニュース／メール提供者４０２はホームページを持っており、このホームページの証明書を得るために、認証機関４０３に対して証明要求を行う。この証明要求に対し、認証機関４０３はニュース／メール提供者４０２の正当性をテストし、ニュース／メール提供者４０２がテストにパスした場合には、認証機関４０３は本発明の否認不可署名方式を用いてホームページのハッシュ値に対する署名を生成し、閲読者のブラウザ上に表示されたニュース／メール提供者４０２のホームページ上にこの署名を証明書として掲示する。ここで、証明書は直接ニュース／メール提供者４０２に発行せずに閲読者のブラウザ上でのニュース／メール提供者４０２のホームページの表示の上に現れるようにすることにより、ニュース／メール提供者４０２による証明書の不正なコピーを防止することができる。
【００６０】
そして、ニュース／メール提供者４０２から受け取ったニュース／メールを開封する前に、閲読者４０１は、以下のようにしてニュース／メール提供者４０２の正当性をチェックする。即ち、閲読者４０１はまずニュース／メール提供者４０２のホームページ上に掲示された証明書をクリックする。すると、署名が閲読者４０１に送られると共に、閲読者４０１が認証機関４０３にリンクされる。そして、否認不可署名の署名検証が認証機関４０３と署名者とし閲読者４０１を検証者として行われる。もし署名検証に失敗すれば、ホームページはそのハッシュ値が認証機関４０３により署名された真正なものではないことを意味するので閲読者４０１はニュース／メール提供者４０２を信頼すべきではない。一方、署名検証に成功した場合には、閲読者４０１はニュース／メール提供者４０２を信頼できるものと見做してこのニュース／メール提供者４０２から受け取ったニュース／メールを開封してもよい。このようにしても、情報サービス提供者の正当性をチェックすることが可能となる。
【００６１】
上述した本発明に係る実施形態は、コンピュータ技術に熟練した者にとって明らかなように、本願明細書の開示内容に従ってプログラムされた従来の汎用デジタルコンピュータを用いて好適に実装することができる。ソフトウェア技術に熟練した者にとって明らかなように、適切なソフトウェアコードは本願明細書の開示内容に基づいて熟練したプログラマによって容易に作成できる。
【００６２】
特に、上述の実施形態の各署名者装置及び検証者装置は、ソフトウェアパッケージの形態で好適に実装することができる。
【００６３】
そのようなソフトウェアパッケージは、本発明の開示する機能及びプロセスを実行するようにコンピュータをプログラムするためのコンピュータコードを格納した記録媒体を用いるコンピュータプログラム製品であってよい。記録媒体は、従来のフロッピディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気又は光学カード等のいかなるタイプのものであってもよく、また、電子的命令を格納するための他のいかなる適当な媒体であってもよいが、これらに限定されるものでもない。
【図面の簡単な説明】
【００６４】
【図１】本発明に係る否認不可署名方式に用いられる二次体の説明に使用される記号の一覧表である。
【図２】本発明に係る否認不可署名方式に用いられるパラメータの一覧表である。
【図３】本発明に係る否認不可署名方式の処理手順を示すフローチャートである。
【図４】図３の処理手順を実行するための署名者装置及び検証者装置の構成例を示すブロック図である。
【図５】本発明に係る否認不可署名方式及び従来のＲＳＡ型デジタル署名方式における効率を比較するためのシミュレーション結果の一覧表である。
【図６】本発明に係る否認不可署名方式を用いたソフトウェアベンディングサーバ用否認不可署名システムの構成例を示す概略図である。
【図７】図６の否認不可署名システムの構成例を示すブロック図である。
【図８】本発明に係る否認不可署名方式を用いた電子商取引サービス用否認不可署名システムの構成例を示す概略図である。
【図９】本発明に係る否認不可署名方式を用いたニュース／メール提供サービス用否認不可署名システムの構成例を示す概略図である。
【符号の説明】
【００６５】
１０  署名者装置
１１  鍵生成部
１２  鍵記憶部
１３  メッセージ生成部
１４  署名生成部
１５  応答生成部
２０  検証者装置
２１  ノルムチェック部
２２  チャレンジ生成部
２３  応答チェック部
１０１，１０２  クライアント
１０５  認証サーバ
１０６  ソフトウェアベンディングサーバ
１０８  通信網（インターネット）
１０９  ファイヤーウォール
２０１  ネットワークインタフェース
２０２  ＣＰＵ
２０３  主記憶装置
２０４  否認不可署名鍵格納エリア
２０５  コンソール及びディスプレイインタフェース
２０６  二次記憶装置
２０７  補助記憶装置
２０８  アクセス制御回路
２０９  否認不可署名処理プログラム
３０１  顧客
３０２  電子商取引業者
３０３，４０３  認証機関
４０１  閲読者
４０２  ニュース／メール提供者
【図１】
2004222332.tif 000003
【図２】
2004222332.tif 000004
【図３】
2004222332.tif 000005
【図４】
2004222332.tif 000006
【図５】
2004222332.tif 000007
【図６】
2004222332.tif 000008
【図７】
2004222332.tif 000009
【図８】
2004222332.tif 000010
【図９】
2004222332.tif 000011