(57)【要約】【課題】暗号通信における不正エンティティの追跡を鍵を取得することなく確実に実行することの可能な構成を提供する。【解決手段】復号機器の検証に基づいて不正エンティティを特定する際に、正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力し、検査対象機器に格納された秘密鍵ｄｉを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と入力暗号文Ｃに対応する平文Ｍとの比較を実行して復号文Ｍ’＝平文Ｍであることを条件として識別子ｊｉに対応するエンティティを不正エンティティとして特定する。本構成により、不正復号器からの不正鍵の取得や鍵の解析処理を実行することなく不正エンティティの特定処理を実現することが可能となる。【選択図】  図８
2004221800.tif 000002
【特許請求の範囲】
【請求項１】
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡方法であり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力ステップと、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較処理ステップと、
前記比較処理ステップにおいて、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定ステップと、
を有することを特徴とする暗号処理システムにおける不正エンティティ追跡方法。
【請求項２】
前記暗号処理システムにおける不正エンティティ追跡方法において、
前記公開鍵ｅＳ、および秘密鍵ｄｉは、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義されるものであり、異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数１】
2004221800.tif 000020
に従って設定し、
前記正規エンティティ識別子ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす識別子であり、
前記暗号文Ｃは、セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）であり、
前記追跡用ヘッダｈ’は、セッション鍵ｓと、乱数ｒを含む下記式、
【数２】
2004221800.tif 000021
として定義された構成であることを特徴とする請求項１に記載の暗号処理システムにおける不正エンティティ追跡方法。
【請求項３】
前記不正エンティティ追跡方法において、
ｋ＝２、ａ１＝１として設定し、
前記追跡用ヘッダｈ’（ｓ，ｒ）を、下記式、
【数３】
2004221800.tif 000022
として設定したことを特徴とする請求項２に記載の暗号処理システムにおける不正エンティティ追跡方法。
【請求項４】
暗号文を生成し提供するデータ提供手段と、暗号文を受領し復号するデータ受領手段とを有する暗号処理システムにおいて、
公開鍵ｅＳ、および、前記データ受領手段（エンティティｉ（ｉ＝任意の整数））各々に対応する秘密鍵ｄｉを、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義し、
セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）と、下記式、
ｈ（ｓ、ｒ）＝（ｓＹｒ、Ｙ０ｒ、Ｙ１ｒ、…、Ｙｋ−１ｒ）ｍｏｄＮ
に従って生成するヘッダｈ（ｓ，ｒ）とを、前記データ提供手段から前記データ受領手段に提供する暗号処理システムであって、
前記公開鍵ｅＳ、秘密鍵ｄｉ、およびヘッダｈ（ｓ，ｒ）は、下記の設定、すなわち、
異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数４】
2004221800.tif 000023
に従って設定したものであり、前記ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす正規エンティティ識別子ｊｉであり、ｓはセッション鍵、ｒは乱数である、
構成を有することを特徴とする暗号処理システム。
【請求項５】
前記データ受領手段は、
前記ヘッダｈ（ｓ，ｒ）に基づいて、下記式、
【数５】
2004221800.tif 000024
に従って、セッション鍵ｓを取得し、取得セッション鍵ｓに基づいて、暗号文Ｃ＝ＥＳ（Ｍ）の復号処理を実行して平文Ｍを取得する構成であることを特徴とする請求項４に記載の暗号処理システム。
【請求項６】
前記暗号処理システムにおいて、
ｋ＝２、ａ１＝１として設定し、
前記ヘッダｈ（ｓ，ｒ）を、下記式、
ｈ（ｓ、ｒ）＝（ｓＹｒ、Ｙ０ｒ、Ｇｒ）ｍｏｄＮ
として設定したことを特徴とする請求項４に記載の暗号処理システム。
【請求項７】
前記データ受領手段は、
前記ヘッダｈ（ｓ，ｒ）に基づいて、下記式、
【数６】
2004221800.tif 000025
に従って、セッション鍵ｓを取得し、取得セッション鍵ｓに基づいて、暗号文Ｃ＝ＥＳ（Ｍ）の復号処理を実行して平文Ｍを取得する構成であることを特徴とする請求項６に記載の暗号処理システム。
【請求項８】
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡処理装置であり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力手段と、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により取得される復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較手段と、
前記比較手段において、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定手段と、
を有することを特徴とする不正エンティティ追跡処理装置。
【請求項９】
前記不正エンティティ追跡処理装置において、
前記公開鍵ｅＳ、および秘密鍵ｄｉは、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義されるものであり、異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数７】
2004221800.tif 000026
に従って設定し、
前記正規エンティティ識別子ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす識別子であり、
前記暗号文Ｃは、セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）であり、
前記追跡用ヘッダｈ’は、セッション鍵ｓと、乱数ｒを含む下記式、
【数８】
2004221800.tif 000027
として定義された構成であることを特徴とする請求項８に記載の不正エンティティ追跡処理装置。
【請求項１０】
前記不正エンティティ追跡処理装置において、
ｋ＝２、ａ１＝１として設定し、
前記追跡用ヘッダｈ’（ｓ，ｒ）を、下記式、
【数９】
2004221800.tif 000028
として設定する処理を実行する構成を有することを特徴とする請求項９に記載の不正エンティティ追跡処理装置。
【請求項１１】
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡処理を実行するコンピュータ・プログラムであり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力ステップと、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較処理ステップと、
前記比較処理ステップにおいて、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定ステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号処理システムにおける不正エンティティ追跡方法、暗号処理システム、および不正エンティティ追跡処理装置、並びにコンピュータ・プログラムに関する。さらに、詳細には、暗号化データを例えば同報通信などにより配信するシステムにおいて、正当なデータ利用権を持たない機器、またはユーザの利用を排除するものであり、正当なデータ利用権に対応して配布される正当な個人秘密鍵に基づいて生成した不正鍵を適用したデータの不正利用があった場合、不正鍵を格納した不正復号器から不正鍵を取得して鍵を解析することなく不正利用を特定するブラックボックス追跡を実現可能とした暗号処理システムにおける不正エンティティ追跡方法、暗号処理システム、および不正エンティティ追跡処理装置、並びにコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【０００３】
暗号化方式には、大別して共通鍵方式、公開鍵方式がある。共通鍵方式は、対称暗号方式ともよばれ、発信者、受信者の双方で共通の鍵を保有する。共通鍵方式の代表的な方法として、ＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）がある。ＤＥＳアルゴリズムの特徴は、暗号化と復号化とをほぼ同じアルゴリズムで実行可能なことである。
【０００４】
この共通鍵暗号に対して、発信者と受信者の鍵を異なるものとした構成が公開鍵方式または非対称暗号方式である。公開鍵暗号方式では、暗号化、復号化に共通の鍵を用いる共通鍵暗号方式と異なり、秘密に保つ必要のある秘密鍵は、特定の１人が持てばよいため鍵の管理において有利である。ただし、公開鍵暗号方式は共通鍵暗号方式に比較してデータ処理速度が遅く、一般には、秘密鍵の配送、ディジタル署名等のデータ量の少ない対象に多く用いられている。公開鍵暗号方式の代表的なものにはＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）暗号がある。これは非常に大きな２つの素数（例えば１５０桁）の積を用いるものであり、大きな２つの素数（例えば１５０桁）の積の素因数分解する処理の困難さを利用している。
【０００５】
公開鍵暗号方式では、不特定多数に公開鍵を使用可能とする構成であり、配布する公開鍵が正当なものであるか否かを証明する証明書、いわゆる公開鍵証明書を使用する方法が多く用いられている。例えば、利用者Ａが公開鍵、秘密鍵のペアを生成して、生成した公開鍵を認証局に対して送付して公開鍵証明書を認証局から入手する。利用者Ａは公開鍵証明書を一般に公開する。不特定のユーザは公開鍵証明書から所定の手続きを経て公開鍵を入手して文書等を暗号化して利用者Ａに送付する。利用者Ａは秘密鍵を用いて暗号化文書等を復号する等のシステムである。また、利用者Ａは、秘密鍵を用いて文書等に署名を付け、不特定のユーザが公開鍵証明書から所定の手続きを経て公開鍵を入手して、その署名の検証を行なうシステムである。
【０００６】
公開鍵証明書は、公開鍵暗号方式における認証局あるいは発行局（ＣＡ：Ｃｅｒｔｉｆｉｃａｔｅ  ＡｕｔｈｏｒｉｔｙまたはＩＡ：Ｉｓｓｕｅｒ  Ａｕｔｈｏｒｉｔｙ）が発行する証明書であり、ユーザが自己のＩＤ、公開鍵等を認証局に提出することにより、認証局側が認証局のＩＤや有効期限等の情報を付加し、さらに認証局による署名を付加して作成される証明書である。
【０００７】
公開鍵暗号方式としては、上述したＲＳＡ方式の他にｎが素数の場合の離散対数問題の困難さを利用した離散対数暗号が知られている。米国標準のディジタル署名方式として知られるＤＳＡ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｔａｎｄａｒｄ）には、この離散対数暗号が用いられている。また、Ｖ．Ｍｉｌｌｅｒ，  Ｎ．Ｋｏｂｌｉｔｚによって提案された楕円曲線暗号（ＥＣＣ：Ｅｌｌｉｐｉｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ）が、安全性および高速性の点で昨今注目されている。楕円曲線暗号は、１６０ｂｉｔの鍵でＲＳＡ１０２４ｂｉｔの鍵と同等の強度を持つと言われる。
【０００８】
有料放送や、ＤＶＤ，ＣＤ等の記録媒体、あるいはインターネットによるコンテンツ配信などにより有料コンテンツを複数の受信者に対して提供する場合、コンテンツを暗号化し、コンテンツを正規に購入した受信者のみが復号可能となるようにする必要がある。このように、複数の受信者に同一の暗号文を効率的に配信し、かつ特定の受信者のみが暗号文を復号可能となる方法として、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）がある。
【０００９】
放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）は上述の公開鍵暗号方式の一態様であり、送信者（またはシステム運営者）が、特定の受信者集合にのみ秘密情報を配っておき、平文（コンテンツ等）をセッション鍵で暗号化したものと、セッション鍵を各受信者の秘密情報で復号するためのヘッダを同報配信するものである。
【００１０】
ヘッダと暗号文は任意のユーザが、放送や、ＤＶＤ，ＣＤ等の記録媒体、あるいはインターネットによるコンテンツ受信により取得可能であるが、ヘッダを復号し、セッション鍵を得ることができるのは秘密情報を所有するユーザのみであるため、コンテンツの利用ユーザを制限することが可能となる。しかしながらこのような方式では、秘密情報を保持するユーザが自身の秘密情報を不正に複製し、それを用いて不正復号器を構成することが可能である。
【００１１】
このような不正利用を抑止する方式として、不正者追跡法が存在する。放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）における不正追跡法の代表的な形態は、特定のユーザに渡される秘密情報を、各ユーザ固有のものとすることによって、不正復号器が発見された場合に不正者を特定可能とするものである。
【００１２】
このような不正者追跡法の中で、Ｋｕｒｏｓａｗａ、Ｄｅｓｍｅｄｔはｎ人の秘密鍵を持つ受信者のうち、不正者がｋ人以内であれば、不正者を確実に特定することが可能となる方式を提案している（非特許文献１）。この方式では、公開鍵とヘッダから、秘密鍵をもたない受信者がセッション鍵および平文を得ること（秘匿性に関する安全性）は、エルガマル（ＥｌＧａｍａｌ）暗号を解読することと等価であることが証明されている。また、不正者がｋ人以内であれば、不正者を正確に特定できないような鍵を不正者の集合が生成すること（追跡可能性に関する安全性）は、離散対数問題を解くことと等しいことも証明されている。
【００１３】
しかし、Ｋｕｒｏｓａｗａ、Ｄｅｓｍｅｄｔ  の方式では、安全性は証明可能であるが、ｋ＋１人以上の不正者が結託した場合、不正者を正確に特定できないという問題点があった。また、ｋの値を大きくすると、ヘッダサイズおよび各エンティティに要求される計算量もｋに比例して大きくなるという問題点がある。
【００１４】
また、光成、境、笠原は、Ｋｕｒｏｓａｗａ、Ｄｅｓｍｅｄｔ  の方式を楕円曲線上で実現し、さらに新たな工夫を加えることによって、不正者が何人結託しても不正者を確実に特定可能である方式を提案している（非特許文献２）。この方式では、追跡可能性に関する安全性については一部証明されているが、秘匿性に関する安全性に関しては証明されていない。また方式実装をする際、高速に実現しようとすると適切な楕円曲線を選択する必要があるが、これを効率的に見つけるアルゴリズムが未知であるという問題点がある。
【００１５】
本特許出願人は、上記問題点に鑑み、前述のＫｕｒｏｓａｗａ、Ｄｅｓｍｅｄｔの方式において明らかにされた理論、すなわち、公開鍵とヘッダから、秘密鍵をもたない受信者がセッション鍵および平文を得ること（秘匿性に関する安全性）は、エルガマル（ＥｌＧａｍａｌ）暗号を解読することと等価であること、また、不正者がｋ人以内であれば、不正者を正確に特定できないような鍵を不正者の集合が生成すること（追跡可能性に関する安全性）は、離散対数問題を解くことと等しいことに基づき、前述のＫｕｒｏｓａｗａ、Ｄｅｓｍｅｄｔ  の方式を合成数を法とする乗法群上で実現し、さらに新たな工夫を加えることにより、安全性が証明可能で、不正者が何人結託しても不正者を確実に特定可能な不正者追跡を実現可能としたシステムについて、先の特許出願（未公開：特願２００２−３２２０９７）において提案した。
【００１６】
しかしながら、上記提案構成は、不正復号器からの鍵の取得、解析を必要とする構成であり、鍵の取得が困難な機器についての不正追跡処理が困難となるという問題があった。
【００１７】
【非特許文献１】
Ｋ．  Ｋｕｒｏｓａｗａ，  Ｙ．  Ｄｅｓｍｅｄｔ，  “Ｏｐｔｉｍｕｍ  Ｔｒａｉｔｏｒ  Ｔｒａｃｉｎｇ  ａｎｄ  Ａｓｙｍｍｅｔｒｉｃ  Ｓｃｈｅｍｅ，”  Ａｄｖａｎｃｅｓ  ｉｎ  ＣｒｙｐｔｏｌｏｇｙＰｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＥＵＲＯＣＲＹＰＴＯ  ９８，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．１４０３，  ｐｐ．１４５−１５７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９８．
【非特許文献２】
Ｓ．  Ｍｉｔｓｕｎａｒｉ、  Ｒ．  Ｓａｋａｉ、  Ｍ．  Ｋａｓａｈａｒａ、  “Ａ  Ｎｅｗ  Ｔｒａｉｔｏｒ  Ｔｒａｃｉｎｇ、”ＩＥＩＣＥ  ＴＲＡＮＳ．  Ｆｕｎｄａｍｅｎｔａｌｓ，  ｖｏｌ．Ｅ８５−Ａ，  Ｎｏ．  ２，  ｐｐ．  ４８１−４８４，  ２００２．
【００１８】
【発明が解決しようとする課題】
本発明は、上記、問題点に鑑みてなされたものであり、正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において、復号機器の検証に基づいて不正エンティティを特定する際に、不正復号器からの不正鍵の取得や鍵の解析処理を実行することなく不正エンティティの特定処理を実現可能とした不正エンティティ追跡方法、暗号処理システム、および不正エンティティ追跡処理装置、並びにコンピュータ・プログラムを提供することを目的とする。
【００１９】
【課題を解決するための手段】
本発明の第１の側面は、
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡方法であり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力ステップと、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較処理ステップと、
前記比較処理ステップにおいて、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定ステップと、
を有することを特徴とする暗号処理システムにおける不正エンティティ追跡方法にある。
【００２０】
さらに、本発明の暗号処理システムにおける不正エンティティ追跡方法の一実施態様において、前記公開鍵ｅＳ、および秘密鍵ｄｉは、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義されるものであり、異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数１０】
2004221800.tif 000003
に従って設定し、
前記正規エンティティ識別子ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす識別子であり、前記暗号文Ｃは、セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）であり、前記追跡用ヘッダｈ’は、セッション鍵ｓと、乱数ｒを含む下記式、
【数１１】
2004221800.tif 000004
として定義された構成であることを特徴とする。
【００２１】
さらに、本発明の暗号処理システムにおける不正エンティティ追跡方法の一実施態様において、ｋ＝２、ａ１＝１として設定し、前記追跡用ヘッダｈ’（ｓ，ｒ）を、下記式、
【数１２】
2004221800.tif 000005
として設定したことを特徴とする。
【００２２】
さらに、本発明の第２の側面は、
暗号文を生成し提供するデータ提供手段と、暗号文を受領し復号するデータ受領手段とを有する暗号処理システムにおいて、
公開鍵ｅＳ、および、前記データ受領手段（エンティティｉ（ｉ＝任意の整数））各々に対応する秘密鍵ｄｉを、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義し、
セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）と、下記式、
ｈ（ｓ、ｒ）＝（ｓＹｒ、Ｙ０ｒ、Ｙ１ｒ、…、Ｙｋ−１ｒ）ｍｏｄＮ
に従って生成するヘッダｈ（ｓ，ｒ）とを、前記データ提供手段から前記データ受領手段に提供する暗号処理システムであって、
前記公開鍵ｅＳ、秘密鍵ｄｉ、およびヘッダｈ（ｓ，ｒ）は、下記の設定、すなわち、
異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数１３】
2004221800.tif 000006
に従って設定したものであり、前記ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす正規エンティティ識別子ｊｉであり、ｓはセッション鍵、ｒは乱数である、
構成を有することを特徴とする暗号処理システムにある。
【００２３】
さらに、本発明の暗号処理システムの一実施態様において、前記データ受領手段は、前記ヘッダｈ（ｓ，ｒ）に基づいて、下記式、
【数１４】
2004221800.tif 000007
に従って、セッション鍵ｓを取得し、取得セッション鍵ｓに基づいて、暗号文Ｃ＝ＥＳ（Ｍ）の復号処理を実行して平文Ｍを取得する構成であることを特徴とする。
【００２４】
さらに、本発明の暗号処理システムの一実施態様において、ｋ＝２、ａ１＝１として設定し、前記ヘッダｈ（ｓ，ｒ）を、下記式、
ｈ（ｓ、ｒ）＝（ｓＹｒ、Ｙ０ｒ、Ｇｒ）ｍｏｄＮ
として設定したことを特徴とする。
【００２５】
さらに、本発明の暗号処理システムの一実施態様において、前記データ受領手段は、前記ヘッダｈ（ｓ，ｒ）に基づいて、下記式、
【数１５】
2004221800.tif 000008
に従って、セッション鍵ｓを取得し、取得セッション鍵ｓに基づいて、暗号文Ｃ＝ＥＳ（Ｍ）の復号処理を実行して平文Ｍを取得する構成であることを特徴とする。
【００２６】
さらに、本発明の第３の側面は、
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡処理装置であり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力手段と、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により取得される復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較手段と、
前記比較手段において、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定手段と、
を有することを特徴とする不正エンティティ追跡処理装置にある。
【００２７】
さらに、本発明の不正エンティティ追跡処理装置の一実施態様において、前記公開鍵ｅＳ、および秘密鍵ｄｉは、各々、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）、ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）として定義されるものであり、異なる素数ｐ，ｑ、に基づいて素数Ｐ＝２ｐ＋１，Ｑ＝２ｑ＋１を設定し、Ｎ＝ＰＱ、λ＝ｐｑを算出し、乗法群ＺＮ＊の元のうち、位数がλとなる元Ｇを設定し、１以上の任意整数＝ｋとし、乗法群Ｚ＊λの元ａ０，．．．，ａｋ−１に基づく、乗法群Ｚ＊λ上の多項式ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数Ｒ∈Ｚ＊λとに基づく算出値Ｙ，Ｙ０，．．，Ｙｋ−１を下記式、
【数１６】
2004221800.tif 000009
に従って設定し、
前記正規エンティティ識別子ｊｉは、ｇｃｄ（ｆ（ｊｉ）、λ）＝１を満たす識別子であり、
前記暗号文Ｃは、セッション鍵ｓに基づく平文Ｍの暗号文、すなわちＣ＝ＥＳ（Ｍ）であり、
前記追跡用ヘッダｈ’は、セッション鍵ｓと、乱数ｒを含む下記式、
【数１７】
2004221800.tif 000010
として定義された構成であることを特徴とする。
【００２８】
さらに、本発明の不正エンティティ追跡処理装置の一実施態様において、ｋ＝２、ａ１＝１として設定し、前記追跡用ヘッダｈ’（ｓ，ｒ）を、下記式、
【数１８】
2004221800.tif 000011
として設定する処理を実行する構成を有することを特徴とする。
【００２９】
さらに、本発明の第４の側面は、
正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において復号機器検証に基づいて不正エンティティを特定する不正エンティティ追跡処理を実行するコンピュータ・プログラムであり、
正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力するデータ入力ステップと、
前記検査対象機器において、入力追跡用ヘッダｈ’と、入力暗号文Ｃに基づいて、前記検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と前記入力暗号文Ｃに対応する平文Ｍとの比較処理を実行する比較処理ステップと、
前記比較処理ステップにおいて、復号文Ｍ’＝平文Ｍであることを条件として、前記識別子ｊｉに対応するエンティティを不正エンティティとして特定する不正エンティティ特定ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００３０】
【作用】
本発明の構成によれば、正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において、復号機器の検証に基づいて不正エンティティを特定する際に、正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力し、検査対象機器に格納された秘密鍵ｄｉを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と入力暗号文Ｃに対応する平文Ｍとの比較を実行して復号文Ｍ’＝平文Ｍであることを条件として識別子ｊｉに対応するエンティティを不正エンティティとして特定することが可能となり、不正復号器からの不正鍵の取得や鍵の解析処理を実行することなく不正エンティティの特定処理を実現することが可能となる。
【００３１】
さらに、本発明の構成によれば、暗号文を生成し提供するデータ提供手段と、暗号文を受領し復号するデータ受領手段とを有する暗号処理システムにおいて、公開鍵ｅＳ、および、データ受領手段各々に対応する秘密鍵ｄｉを設定し、秘密鍵ｄｉを正規エンティティ固有の秘密鍵として構成するとともに、暗号文Ｃを復号する際に処理すべきヘッダ情報を正規エンティティの識別子ｊｉを含むヘッダｈとして設定することで、不正エンティティの追跡処理の際に、不正エンティティと推測されるエンティティの識別子を設定したヘッダを追跡用ヘッダとして構成して復号器に入力し、出力結果のデータ検証を実行することにより、不正エンティティの特定が可能となる安全な暗号処理システムが実現される。
【００３２】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記憶媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００３３】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【００３４】
【発明の実施の形態】
以下、本発明の暗号処理システムにおける不正エンティティ追跡方法、暗号処理システム、および不正エンティティ追跡処理装置、並びにコンピュータ・プログラムについて詳細に説明する。
【００３５】
本発明は、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）を適用した暗号通信システム、およびその通信システムにおける不正追跡処理方法である。放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）は、前述したように、正当な利用権を有するユーザに対するコンテンツデータの限定的利用を実現しようとするものであり、データ提供者、またはシステム管理者が、正当なデータ利用権を持つ受信者等のユーザ集合にのみ秘密情報（秘密鍵）を配っておき、平文（コンテンツ等）をセッション鍵で暗号化したものと、セッション鍵を各受信者の秘密鍵で復号するためのヘッダを同報配信または提供するものである。これにより、ヘッダと暗号文は任意のユーザが取得可能であるが、ヘッダを復号し、セッション鍵を得ることができるのは秘密鍵を所有するユーザのみであるため、暗号文を復号して平文を取得することの可能なユーザを制限した構成、いわゆる限定ユーザに対するコンテンツ配信が可能となる。
【００３６】
このような、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）において、正当な秘密鍵を持たないエンティティにおいてセッション鍵生成が容易に行われると、受信者制限構成は成立しなくなる。従って、セッション鍵の生成困難性が、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）において求められる１つの重要な要素となる。
【００３７】
また、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）においては、秘密鍵を保持する受信者が、自身の秘密鍵を不正に複製し、他のユーザに提供したり、複製鍵を用いて多数の不正復号器を作成してしまう恐れがある。従って、このような不正復号器の生成、利用についても排除することが必要となる。このような事態に対処するためには、例えば不正復号器の格納情報に基づいて秘密鍵の漏洩ルートを探索可能であること、すなわち、不正追跡処理可能性があることが求められる。このように、不正追跡処理可能性も、放送型暗号（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）において求められる１つの重要な要素となる。
【００３８】
本発明の暗号通信システムの処理構成、および上述したセッション鍵の生成困難性、不正追跡処理可能性について、以下、説明する。なお、説明は、下記の項目順に行なう。
１．用語、記号の説明
２．暗号通信処理および不正追跡処理
３．ブラックボックス追跡処理の安全性の証明
４．不正追跡処理装置、エンティティを構成する装置例
【００３９】
［１．用語、記号の定義］
まず、以下の説明において使用する用語および記号の定義について説明する。本明細書においては、暗号文を同報配信するシステムを、単にシステムと呼ぶものとする。また、不正追跡処理装置、および復号機器やプログラム、ユーザ等を総称してエンティティと呼ぶものとする。システムの各要素を以下のように定義する。
【００４０】
正規エンティティ：システムに加入しているエンティティであり、システム管理者から正規な個人秘密鍵を付与されているエンティティ。
個人秘密鍵：暗号文（暗号化コンテンツ）に対応するヘッダ情報に基づいて、セッション鍵（暗号文の復号に適用する鍵）を取得するために適用する鍵として利用可能な個人秘密情報であり、システム管理者から正規エンティティに対して、安全な通信路あるいは記憶媒体を介して配布される。
配信用ヘッダ：セッション鍵を各個人秘密鍵で復号するための情報であり、同報配信される暗号文と同様、同報配信される。任意エンティティが受信可能である。
追跡用ヘッダ：不正追跡処理を実行する際に不正追跡処理実行者により生成され追跡処理対象の復号器に入力される。
【００４１】
不正者：正規に取得した自身の個人秘密鍵の複製、あるいは個人秘密鍵と同等の処理が可能な鍵を生成して他のエンティティに提供したり、新たな復号器に格納するなどして、不正な復号処理装置の生成を行なう正規エンティティ。
不正鍵：本来の不正者が特定不可能である、個人秘密鍵と同等の性質を持つ鍵であり、不正者により提供され不正復号器に格納される鍵。
不正復号器：個人秘密鍵を不正に複製した複製鍵、もしくは不正者が提供した不正鍵が格納されたデータ復号処理を実行するデータ処理装置。
【００４２】
なお、不正者が結託するとは、不正者が自身の個人秘密鍵を提供し合い、不正鍵を構成しようと試みることをいい、結託閾値とは、不正鍵を構成するために必要な最低限の不正者数を言うものとする。以下、本発明で用いる記号について説明する。
【００４３】
Ｍ：平文
ｓ：セッション鍵
Ｃ：暗号文
Ｅａ（ｂ）：共通鍵ａによるｂの暗号
Ｄａ（ｃ）：共通鍵ａによるｃの復号
ｈ（ａ，ｂ）：セッション鍵ａと乱数ｂからなる配信用ヘッダ
ｈ’（ａ，ｂ）：セッション鍵ａと乱数ｂからなる追跡用ヘッダ
ｎ：正規エンティティの総数
Ｔ：送信者
ｅＳ：システムで用いる公開鍵
ｅｎｔｉｔｙｉ：ｉ  番目のエンティティ
ｄｉ：エンティティｉ（ｅｎｔｉｔｙｉ）の個人秘密鍵
ｊｉ：エンティティｉ（ｅｎｔｉｔｙｉ）に固有の番号（エンティティ識別子）
（ａ，ｂ，ｃ．．）ｍｏｄＮ：（ａｍｏｄＮ，ｂｍｏｄＮ，ｃｍｏｄＮ．．．）を意味する
【００４４】
［２．暗号通信処理および不正追跡処理］
次に、本発明を適用した暗号通信処理、および不正追跡処理について説明する。本発明を適用した暗号通信処理、および不正追跡処理を実行する場合、その処理フェーズは、大きく分けて準備処理、暗号データ配信処理、暗号データ復号処理、不正者追跡処理の４つの処理フェーズに分割される。不正追跡処理フェーズには、通常追跡とブラックボックス追跡の二種類の追跡方法が存在する。ここで、通常追跡とは、不正復号器中に含まれる個人秘密鍵が取得可能であり、復号器から取得した鍵の解析を伴う不正追跡処理を意味し、ブラックボックス追跡とは、不正復号器中に含まれる個人秘密鍵が取得不可能である場合などにおいて、復号器から鍵を取得することなく、不正復号器へのデータ入力と、その出力データに基づいて不正者の個人秘密鍵を特定する追跡処理を意味する。以下、各フェーズにおける処理の詳細について説明する。
【００４５】
（２．１．準備処理）
同報配信システムのシステム管理者は以下の手順にしたがって、セッション鍵ｓおよび暗号文Ｍを配信する準備を行う。なお、システム管理者は、同報配信を実行する送信者が兼ねる構成としても、あるいは、送信者とは別エンティティとしてもよい。
【００４６】
準備処理は、公開鍵の生成と公開処理、および秘密鍵の生成と配布処理によって構成される。準備処理に関する一連の手続きについて、図１〜図３の処理フローを参照して説明する。
【００４７】
図１は、公開鍵の生成と公開処理、および秘密鍵の生成と配布処理を含む準備処理全体の処理フローを示し、図２は、図１におけるステップＳ１０８の公開鍵生成処理の詳細処理フローを示している。さらに、図３は、図１におけるステップＳ１１０の秘密鍵生成処理の詳細処理フローを示している。
【００４８】
図１に示す処理フローに従って、準備処理の一連の手続きについて説明する。ステップＳ１０１において、互いに異なる大きな素数：ｐ、ｑを生成し、ステップＳ１０２において、Ｐ＝２ｐ＋１、Ｑ＝２ｑ＋１を満たす素数Ｐ，Ｑを生成する。また、Ｎ＝ＰＱとしてＮを生成する。さらに、ステップＳ１０３において、素数ｐ，ｑに基づいてλ＝ｐｑを計算する。
【００４９】
次に、ステップＳ１０４〜Ｓ１０５において、乗法群：ＺＮ＊の元のうち、位数がλとなる元：Ｇを求める。なお、乗法群：ＺＮ＊とは、ＺＮかつＮと互いに素な整数の集合（＝（Ｚ／ＮＺ＊））である。
【００５０】
ステップＳ１０６において、乗法群：Ｚ＊λ上の乱数ａ０を生成する。すなわちａ０を乗法群：Ｚ＊λの元として生成し、乗法群：Ｚ＊λ上の多項式：ｆ（ｘ）＝ａ０＋ｘを構成する。次に、ステップＳ１０７において、乱数：Ｒを乗法群：Ｚ＊λの元として生成する。
【００５１】
次に、ステップＳ１０８において公開鍵ｅＳを生成する。まず、乱数：Ｒ、および元：Ｇに基づいて、公開鍵：ｅＳ（Ｎ，Ｇ，Ｙ，Ｙ０）の要素：Ｙ，Ｙ０を下記式（式１）に基づいて計算する。
【００５２】
【数１９】
2004221800.tif 000012
【００５３】
次に、式１によって算出される要素：Ｙ，Ｙ０と、ステップＳ１０２で生成したＰＱに基づくＮ（Ｎ＝ＰＱ）と、ステップＳ１０４で計算した乗法群：ＺＮ＊の元：Ｇを含む公開鍵：ｅＳを、以下のように構成し、公開する。
ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）
【００５４】
図２を参照してステップＳ１０８の公開鍵：ｅＳ（Ｎ，Ｇ，Ｙ，Ｙ０）生成処理の詳細について説明する。
【００５５】
まず、ステップＳ２０１において、図１のステップＳ１０２で生成したＮ（Ｎ＝ＰＱ）と、ステップＳ１０４で計算した乗法群：ＺＮ＊の元：Ｇ、ステップＳ１０６において設定した乗法群：Ｚ＊λ上の乱数：ａ０、さらに、ステップＳ１０７で設定した乱数：Ｒの組（Ｎ，Ｇ，Ｒ，ａ０）を入力する。
【００５６】
ステップＳ２０２、およびステップＳ２０３において、上記式（式１）に従って、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）の要素：Ｙ，Ｙ０を計算する。ステップＳ２０４において、公開鍵：ｅＳ（Ｎ，Ｇ，Ｙ，Ｙ０）を出力する。
【００５７】
図１の処理フローに戻り、準備処理の手続きについて説明を続ける。図２の処理フローに従って、生成された公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）は、ステップＳ１０９において公開処理がなされる。この公開鍵の公開処理は、例えば、ネットワーク上において制限なくアクセス可能なサーバに格納する処理、あるいは同報配信処理、あるいはＤＶＤ、ＣＤ等、各種記憶媒体に格納し提供する処理などによって実行される。この公開処理によって、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）は、正規エンティティ、および正規エンティティ以外のエンティティも取得可能となる。
【００５８】
次に、ステップＳ１１０において、個人秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）の生成処理を実行する。個人秘密鍵生成に関する詳細処理について、図３の処理フローを参照して説明する。
【００５９】
まず、ステップＳ３０１において、図１のステップＳ１０２で生成したＮ（Ｎ＝ＰＱ）と、ステップＳ１０３において、素数ｐ，ｑに基づいて生成されたλ＝ｐｑと、ステップＳ１０７で設定した乱数：Ｒ、ステップＳ１０６において設定した乗法群：Ｚ＊λ上の乱数：ａ０の組（Ｎ，λ，Ｒ，ａ０）を入力する。
【００６０】
次に、各エンティティｉ（ｅｎｔｉｔｙｉ）ごとの秘密鍵を生成するため、ｉの値の設定および更新処理を実行する。ステップＳ３０２においてｉ←０とし、ステップＳ３０３において、ｉ←ｉ＋１とする。
【００６１】
ステップＳ３０４、ステップＳ３０５では、エンティティｉ（ｅｎｔｉｔｙｉ  ）ごとにｇｃｄ（ａ０＋ｊｉ，λ）＝１を満たすエンティティｉ（ｅｎｔｉｔｙｉ）ごとの固有の番号（エンティティ識別子）：ｊｉを選択する。なお、ｇｃｄ（ａ，ｂ）は、ａとｂの最大公約数である。
【００６２】
ステップＳ３０６において、Ｒｆ（ｊｉ）−１ｍｏｄλ＝Ｒ（ａ０＋ｊｉ）−１ｍｏｄλを算出し、ステップＳ３０７において、秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）をエンティティｉ（ｅｎｔｉｔｙｉ  ）に対応する秘密情報、すなわち秘密鍵：ｄｉとして出力する。
【００６３】
図１のステップＳ１１１では、上述した処理によって生成した各エンティティｉ（ｅｎｔｉｔｙｉ  ）に対応する秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）を各正規ユーザに対して送信する。
【００６４】
エンティティに対する秘密鍵の送信は、図４に示すように、システム管理者１０１から、暗号文の復号処理を実行するユーザ側エンティティ１２１（１）〜１２１（ｎ）に対して、例えば１対１通信路等、安全な通信路を介して送信される。
【００６５】
以上の処理により、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）、および、各エンティティｉ（ｅｎｔｉｔｙｉ  ）に対する秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）を設定し、準備処理を終了する。
【００６６】
なお、上述の説明では、公開鍵を公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定する例について説明したが、例えば任意のｋ個の乱数を設定して公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）を設定する構成としてもよい。
【００６７】
すなわち、公開鍵を、Ｐ、Ｑに基づく合成数：Ｎ＝ＰＱと、
乗法群：ＺＮ＊の元のうち、位数がλとなる元：Ｇと、
１以上の任意整数＝ｋとし、乗法群：Ｚ＊λの元：ａ０，．．．，ａｋ−１に基づく、乗法群：Ｚ＊λ上の多項式：ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１と、乱数：Ｒ∈ＺＮ＊とに基づく算出値：Ｙ，Ｙ０，．．，Ｙｋ−１、とを含む下記式（式２）として設定する構成としてもよい。
【００６８】
【数２０】
2004221800.tif 000013
【００６９】
また、この公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）に対して、ユーザ側のデータ受信手段（エンティティｉ）各々に対応する秘密鍵：ｄｉは、乗法群：Ｚ＊λ上の多項式：ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１を適用し、データ受信手段（エンティティｉ）ごとの識別子であり、ｇｃｄ（ａ０＋ｊｉ、λ）＝１を満たすエンティティ識別子：ｊｉを含む構成、すなわち、
ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）
として設定する。
【００７０】
上述したような任意数のｋに対する公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）を設定する構成が、一般的な構成である。この一般構成において、ｋ＝２、ａ１＝１として設定することで、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定可能となる。公開鍵を、ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定することで、簡易な情報の処理による暗号通信、例えば後述するヘッダ構成を簡略化したり、復号処理を簡略化することが可能となる。
【００７１】
（２．２．配信処理）
次に、暗号化されたデータの同報配信処理について、図５の処理フローを参照して説明する。暗号化データの同報配信を実行するデータ送信者：Ｔは、暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）を生成し、送信データ：（ｈ（ｓ，ｒ），Ｃ）をデータ受信者としてのエンティティｉ（ｅｎｔｉｔｙｉ  ）に配信する。データ配信は、同報配信処理として実行される。従って、データを受信可能なエンティティは、正当な秘密鍵秘密鍵：ｄｉを有するエンティティとは限らず、誰でもが受信可能である。
【００７２】
暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）を含む送信データ：（ｈ（ｓ，ｒ），Ｃ）の生成、配信処理について、図５の処理フローを参照して説明する。
【００７３】
ステップＳ４０１において、セッション鍵：ｓを生成する。次に、ステップＳ４０２において、送信すべき平文：Ｍに対して、セッション鍵：ｓを適用して暗号化処理を実行して暗号文：Ｃ＝ＥＳ（Ｍ）を生成する。
【００７４】
次に、ステップＳ４０３において、システムで用いる公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）、を入力し、ステップＳ４０４において、乱数：ｒをランダムに生成する。
【００７５】
次に、ステップＳ４０５において、ステップＳ４０４で生成した乱数：ｒ、および公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）の要素に基づいて、ヘッダ：ｈ（ｓ，ｒ）＝（ｓＹｒ，Ｙ０ｒ，Ｇｒ）ｍｏｄＮを計算する。
【００７６】
最後に、ステップＳ４０６において、ステップＳ４０２で生成した暗号文：Ｃ＝ＥＳ（Ｍ）と、ステップＳ４０５で生成した、ヘッダ：ｈ（ｓ，ｒ）＝（ｓＹｒ，Ｙ０ｒ，Ｇｒ，）ｍｏｄＮとの送信データ：ｈ（ｓ，ｒ），Ｃを送信する。
【００７７】
上述の処理により、データ送信者：Ｔにおいて、暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）が生成され、データ受信者としてのエンティティｉ（ｅｎｔｉｔｙｉ  ）に同報配信される。
【００７８】
図６に、送信者２０１からユーザ側エンティティ１２１（１）〜１２１（ｎ）に対する暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）から成る送信データ：（ｈ（ｓ，ｒ），Ｃ）の送信処理構成を示す。公開鍵２０２は、例えば、ネットワーク上において制限なくアクセス可能なサーバに格納され、正規エンティティ、および正規エンティティ以外のエンティティも取得可能である。
【００７９】
暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）から成る送信データ：（ｈ（ｓ，ｒ），Ｃ）は、同報通信路を介して配信され、正規エンティティ、および正規エンティティ以外のエンティティも取得可能である。
【００８０】
なお、これらの情報送信は、衛星等を介した無線送信、インターネット等を介した有線送信、さらにＤＶＤ、ＣＤ等の媒体を介した提供等、様々な手法で実行可能である。
【００８１】
なお、上述の説明では、公開鍵を公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定した場合のデータ配信例について説明したが、例えば任意のｋ個の乱数を設定して公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）を設定する構成とした場合は、ヘッダ：ｈ（ｓ，ｒ）＝（ｓＹｒ，Ｙ０ｒ，．．．，Ｙｋ−１ｒ）ｍｏｄＮとして設定する。
【００８２】
（２．３．復号処理）
データ送信者：Ｔから暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ、ｒ）を含むデータ：（ｈ（ｓ，ｒ），Ｃ）を受信したエンティティｉ（ｅｎｔｉｔｙｉ  ）は、暗号文：Ｃとヘッダ：ｈ（ｓ，ｒ）から、平文：Ｍを得る。この復号処理について、図７の処理フローに従って説明する。
【００８３】
まず、ステップＳ５０１において、ヘッダ：ｈ（ｓ，ｒ）、暗号文：Ｃ、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）、個人秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）を入力する。ステップＳ５０２において、以下の計算式（式３）に従った演算により、セッション鍵：ｓを得る。
【００８４】
【数２１】
2004221800.tif 000014
【００８５】
次に、ステップＳ５０３において、セッション鍵：ｓと暗号文：Ｃから、以下の計算により平文：Ｍを求める。
Ｍ＝ＤＳ（Ｃ）
【００８６】
ステップＳ５０４において、平文：Ｍを出力する。これらの処理により、正当な個人秘密鍵：ｄｉを有するエンティティｉ（ｅｎｔｉｔｙｉ  ）は、データ送信者：Ｔから暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ，ｒ）を含むデータ：（ｈ（ｓ，ｒ），Ｃ）を受信し、平文：Ｍを得ることができる。
【００８７】
なお、上述の説明では、公開鍵を公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定した場合の復号処理例について説明したが、任意のｋ個の乱数を設定して公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）を設定する構成とした場合は、ヘッダ：ｈ（ｓ，ｒ）＝（ｓＹｒ，Ｙ０ｒ，．．．，Ｙｋ−１ｒ）ｍｏｄＮを受信することとなり、また、ユーザ側のデータ受信手段（エンティティｉ）各々に対応する秘密鍵：ｄｉは、乗法群：Ｚ＊λ上の多項式：ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１を適用し、データ受信手段（エンティティｉ（ｉ＝任意の整数））ごとの識別子であり、ｇｃｄ（ａ０＋ｊｉ、λ）＝１を満たすエンティティ識別子：ｊｉを含む構成、すなわち、
ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）
として設定されることになる。
【００８８】
この場合、セッション鍵：ｓの取得処理は、下記式（式４）に基づいて実行されることになる。
【００８９】
【数２２】
2004221800.tif 000015
【００９０】
（２．４．追跡処理）
追跡フェーズには、以下の２通りの追跡法が存在する。通常追跡処理と、ブラックボックス追跡処理の２通りの処理が存在する。通常追跡処理と、ブラックボックス追跡処理の概要は、以下のとおりである。
【００９１】
（１）通常追跡処理
不正な復号を実行している機器（不正復号器：Ｘ）が発見され、その中にエンティティｕ（ｅｎｔｉｔｙｕ）に対して提供されているはずの秘密鍵：ｄｕ＝（ｊｕ，Ｒｆ（ｊｕ）−１ｍｏｄλ）が含まれていた場合、送信者：Ｔまたはシステム管理者は、エンティティｕ（ｅｎｔｉｔｙｕ）を不正復号器：Ｘに秘密鍵：ｄｕ＝（ｊｕ，Ｒｆ（ｊｕ）−１ｍｏｄλ）を不正に提供した不正者として特定する不正追跡処理である。
【００９２】
不正復号器内の秘密鍵：ｄｕ＝（ｊｕ，Ｒｆ（ｊｕ）−１ｍｏｄλ）には、エンティティｕ（ｅｎｔｉｔｙｕ）に固有の番号（エンティティ識別子）：ｊｕが含まれているので、システム管理者が、正規な個人秘密鍵を提供したエンティティ情報と、エンティティｕ（ｅｎｔｉｔｙｕ）に固有の番号（エンティティ識別子）とを対応付けた正規エンティティ情報テーブルを保持することにより、テーブルに基づいて、不正復号器に秘密鍵を提供した秘密鍵保持者、すなわちエンティティｕ（ｅｎｔｉｔｙｕ）を不正者として特定することが可能となる。
【００９３】
（２）ブラックボックス追跡処理
不正復号器が発見され、その中に含まれる不正者の個人秘密鍵ｄｕが取得できない場合など、秘密鍵の解析を行うことなく不正者の個人秘密鍵ｄｕおよび不正者ｅｎｔｉｔｙｕを特定する不正追跡処理方式である。
【００９４】
ブラックボックス追跡処理は、追跡用ヘッダ：ｈ（ｓ，ｒ）を生成し、不正復号器と推定される機器に暗号文：Ｃとともに入力し、その出力、すなわち復号結果に基づいて不正者の個人秘密鍵ｄｕおよび不正者ｅｎｔｉｔｙｕを特定する処理である。ブラックボックス追跡処理の詳細について、以下説明する。
【００９５】
図８にブラックボックス追跡処理の処理手順を説明するフローチャートを示す。図８の各ステップの詳細について説明する。まず、ステップＳ６０１において、セッション鍵：ｓを生成する。次に、ステップＳ６０２において、任意の平文：Ｍに対して、セッション鍵：ｓを適用して暗号化処理を実行して暗号文：Ｃ＝ＥＳ（Ｍ）を生成する。
【００９６】
次に、ステップＳ６０３において、システムで適用されている公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）、を入力し、次に、各検査対象機器ｉ（ｅｎｔｉｔｙｉ）ごとの処理を実行するため、ｉの値の設定および更新処理を実行する。ステップＳ６０４においてｉ←０とし、ステップＳ６０５において、ｉ←ｉ＋１とする。
【００９７】
次に、ステップＳ６０６において、不正者と推測されるエンティティｕｉ（ｅｎｔｉｔｙｕｉ）に固有の番号（エンティティ識別子）：ｊｕｉを選択する。
【００９８】
次に、ステップＳ６０７において、乗法群：Ｚ＊λ上の乱数ａ０’を生成する。ａ０’を乗法群：Ｚ＊λの元として生成し、乗法群：Ｚ＊λ上の多項式：ｆ（ｊｕｉ）＝ａ０＋ｊｕｉを生成する。次に、ステップＳ６０８において、乱数：ｒを生成する。
【００９９】
次に、ステップＳ６０９において、ステップＳ６０１で生成したセッション鍵：ｓと、ステップＳ６０８で生成した乱数：ｒとに基づく追跡用ヘッダ：ｈ’（ｓ，ｒ）を下記式（式５）に従って設定して、検査対象復号器に、ステップＳ６０２で生成した暗号文：Ｃとともに入力する。
【０１００】
【数２３】
2004221800.tif 000016
【０１０１】
次に、ステップＳ６１０において、検査対象復号器において、入力された追跡用ヘッダ：ｈ’（ｓ，ｒ）と、暗号文：Ｃとに基づく処理、すなわちヘッダの処理によるセッション鍵取得と、取得したセッション鍵に基づく暗号文の復号処理を実行する。ステップＳ６１０の処理の詳細について、図９のフローチャートを参照して説明する。
【０１０２】
まず、ステップＳ７０１において、入力した追跡用ヘッダ：ｈ’（ｓ，ｒ）、暗号文：Ｃ、公開鍵および機器内に格納した個人秘密鍵に基づいて、以下の計算式（式６）に従った演算により、セッション鍵：ｓ’を得る。
【０１０３】
【数２４】
2004221800.tif 000017
【０１０４】
次に、ステップＳ７０２において、セッション鍵：ｓ’と暗号文：Ｃから、以下の計算により復号：Ｍ’を求める。
Ｍ’＝ＤＳ’（Ｃ）
【０１０５】
次にステップＳ７０３において、復号文：Ｍ’を出力する。図８の処理フローに戻りブラックボックス追跡処理の手順の説明を続ける。
【０１０６】
ステップＳ６１０において、図９のフローで説明したように、検査対象機器に入力した追跡用ヘッダ：ｈ’と、暗号文：Ｃとによって復号文：Ｍ’が取得されると、ステップＳ６１１において、復号文：Ｍ’と本来の平文：Ｍとの比較を実行する。平文：Ｍと入力暗号文：Ｃとの関係は、Ｃ＝ＥＳ（Ｍ）である。すなわち、平文：Ｍに対してセッション鍵：ｓを適用して暗号化処理を実行して暗号文：Ｃが生成される。
【０１０７】
ステップＳ６１１において、復号文：Ｍ’と本来の平文：Ｍとが一致した場合、検査対象機器に入力した追跡用ヘッダ：ｈ’（ｓ，ｒ）に基づいて正しいセッション鍵が取得され、取得した正しいセッション鍵に基づいて暗号文：Ｃの復号処理が正しく実行されたことになる。
【０１０８】
入力した追跡用ヘッダ：ｈ’（ｓ，ｒ）は、不正者と推測されるエンティティｕｉ（ｅｎｔｉｔｙｕｉ）に固有の番号（エンティティ識別子）：ｊｕｉを適用して生成されたヘッダであり、この追跡用ヘッダ：ｈ’（ｓ，ｒ）に基づいて正しいセッション鍵を取得できる機器は、不正者と推測されるエンティティｕｉ（ｅｎｔｉｔｙｕｉ）の秘密鍵：ｄｕｉ＝（ｊｕｉ，Ｒｆ（ｊｕｉ）−１ｍｏｄλ）を持つ機器であることが明らかとなる。
【０１０９】
従って、ステップＳ６１１において、復号文：Ｍ’と本来の平文：Ｍとが一致した場合、検査対象機器には、秘密鍵：ｄｕｉ＝（ｊｕｉ，Ｒｆ（ｊｕｉ）−１ｍｏｄλ）が格納されていると判断し、ステップＳ６１２において、エンティティｕｉ（ｅｎｔｉｔｙｕｉ）を不正者として特定する。すなわち、エンティティｕｉ（ｅｎｔｉｔｙｕｉ）が、自己の秘密鍵を検査対象機器に不正にコピー格納していると判定する。
【０１１０】
例えば複数の不正機器と思われる検査対象機器が存在し、その検査対象機器に対して同一の追跡用ヘッダを入力し、それぞれが正しい復号結果（Ｍ’＝Ｍ）を出力した場合に、エンティティｕｉ（ｅｎｔｉｔｙｕｉ）が、自己の秘密鍵を複数の復号機器に不正にコピー格納していると判定するものである。
【０１１１】
ステップＳ６１１において、復号文：Ｍ’と本来の平文：Ｍとが一致しなかった場合、検査対象機器には、秘密鍵：ｄｕｉ＝（ｊｕｉ，Ｒｆ（ｊｕｉ）−１ｍｏｄλ）が格納されていると判断されないことになる。この場合は、ステップＳ６０５に戻り、値：ｉの更新処理（ｉ＝ｉ＋１）を実行し、異なる不正者と推測されるエンティティｕｉ（ｅｎｔｉｔｙｕｉ）に固有の番号（エンティティ識別子）：ｊｕｉを選択して、同様の処理、すなわち、追跡用ヘッダの生成処理、生成した追跡用ヘッダと暗号文の検査対象機器に対する入力、および検査対象機器における復号処理を実行する。
【０１１２】
検査対象機器からの出力結果としての復号文：Ｍ’と元の平文：Ｍとが一致するまで同様の処理を実行し、一致した場合に、そのときの追跡用ヘッダに適用したエンティティｕｉ（ｅｎｔｉｔｙｕｉ）に固有の番号（エンティティ識別子）：ｊｕｉを持つエンティティｕｉ（ｅｎｔｉｔｙｕｉ）を、自己の秘密鍵を検査対象機器に不正にコピー格納したと判定する。
【０１１３】
上述したように、不正追跡処理は、図８に従った処理を実行する装置、具体的には、ＰＣ等のコンピュータ・プログラムを実行可能な機器によって構成される不正追跡処理装置によって実行可能である。
【０１１４】
不正追跡処理装置の具体的な構成要素を簡潔にまとめると、以下の構成要素を持つ機器であることが条件となる。すなわち、正規ユーザの識別子ｊｉを含む追跡用ヘッダｈ’（ｓ，ｒ）と、暗号文Ｃを検査対象機器に入力するデータ入力手段と、検査対象機器に格納された秘密鍵ｄｉ、および公開鍵ｅＳを適用した暗号文Ｃの復号処理により出力される復号文Ｍ’を取得し入力暗号文Ｃに対応する平文Ｍと比較する比較手段と、比較手段において、Ｍ’＝Ｍであることを条件として、前記識別子ｊｉに対応するユーザを不正者として特定する不正者特定手段とを有する装置である。ただし、これらの各手段は、具体的には図８に示す処理フローに従って処理を実行するＣＰＵ等の制御手段によって構成される。具体的なハードウェア構成例については、後段において説明する。
【０１１５】
なお、上述の説明では、公開鍵を公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）として設定した場合の復号処理例について説明したが、任意のｋ個の乱数を設定して公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０，．．，Ｙｋ−１）を設定する構成とした場合は、追跡用ヘッダ：ｈ’（ｓ，ｒ）は、下記式（式７）として設定する。
【０１１６】
【数２５】
2004221800.tif 000018
【０１１７】
ユーザ側のデータ復号機器（エンティティｉ）各々に対応する秘密鍵：ｄｉは、乗法群：Ｚ＊λ上の多項式：ｆ（ｘ）＝ａ０＋ａ１ｘ＋．．．ａｋ−１ｘｋ−１を適用し、データ復号機器（エンティティｉ（ｉ＝任意の整数））ごとの識別子であり、ｇｃｄ（ａ０＋ｊｉ、λ）＝１を満たすエンティティ識別子：ｊｉを含む構成、すなわち、
ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）
として設定されることになる。この場合、セッション鍵：ｓの取得処理は、前記式（式４）に基づいて実行されることになる。
【０１１８】
［３．ブラックボックス追跡処理の安全性の証明］
次に、上述したブラックボックス追跡処理の安全性について証明する。上述したように、ブラックボックス追跡を実現するためには、不正と思われる復号器に対して追跡用ヘッダを入力し、その出力結果が正しい平文であるかどうかを判断する処理が必要となる。
【０１１９】
このとき、検査すべき復号器が、追跡用ヘッダと、通常の配信用ヘッダとを判別し、配信用ヘッダが入力された場合のみ復号結果を出力し、それ以外の場合、すなわち追跡用ヘッダの入力時には何も出力しないように設定されてしまうと、不正者を特定することは不可能となる。従って、ブラックボックス追跡を確実に実行するためには、検査対象機器に入力された情報が、追跡用ヘッダか否かを区別できないようにする必要がある。
【０１２０】
このように、追跡用ヘッダと、通常の配信用ヘッダとの判別が不可能であることを証明することで、ブラックボックス追跡処理の安全性が証明される。以下、ブラックボックス追跡機能が確実に実行できる、すなわち、いかなる不正復号器も、入力された情報が追跡用ヘッダであるか否かを決定することができないことを示す。
【０１２１】
上述した暗号処理では方式そのものが合成数を法とする乗法群上で構成されているため、ブラックボックス追跡を実現するためには、合成数を法とする乗法群におけるＤｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  問題を解くことが困難でなければならない。まずＤｉｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（ＤＤＨＰ）の定義を簡単に示す。
【０１２２】
生成元Ｇによって生成される有限巡回群を［Ｇｒｐ］とする。また、ａ、ｂ、ｃを乱数とする。このとき、Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題とは、（Ｇａ、Ｇｂ、Ｇｃ）∈Ｇｒｐが与えられたときに、ｃ＝ａｂ  ｍｏｄ｜Ｇｒｐ｜（ただし、｜Ｇｒｐ｜はＧｒｐの位数を表す）であるか否かを１／２より高い確率で決定する問題をいう。
【０１２３】
また、Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題を解くとは、（Ｇａ、（Ｇａ、Ｇｂ、Ｇｃ）∈Ｇｒｐが与えられたときに、ｃ＝ａｂ  ｍｏｄ｜Ｇｒｐ｜（ただし、｜Ｇｒｐ｜はＧｒｐの位数を表す）であるか否かを１／２より高い確率で決定する確率的多項式時間アルゴリズムが存在することを表す。
【０１２４】
合成数を法とする乗法群におけるＤＤＨＰを解くことが可能であれば、検査対象機器は以下のようにして入力された情報が配信用ヘッダであるか追跡用ヘッダであるかを１／２よりも高い確率で判断することが可能となる。
【０１２５】
検査対象機器に入力されたヘッダを、
Ｈ（ｓ、ｒ）＝（ｈ１、ｈ２、ｈ３）
とすると、Ｈ（ｓ、ｒ）が配信用ヘッダである場合、公開鍵ｅＳおよび配信用ヘッダｈ（ｓ、ｒ）は、それぞれ、
ｅＳ＝（Ｎ、Ｇ、Ｙ、Ｙ０）、および
ｈ（ｓ、ｒ）＝（ｓＹｒ、Ｙ０ｒ、Ｇｒ）ｍｏｄＮ
となる。このとき、Ｙ０およびｈ２ｍｏｄＮ、ｈ３ｍｏｄＮを用いて合成数を法とする乗法群におけるＤＤＨＰを解くことにより、下記式（式８）の等号が成立するか否かを判断する。
【０１２６】
【数２６】
2004221800.tif 000019
【０１２７】
上記式（式８）の等号が成立するならば入力情報が配信用ヘッダであるとする。
【０１２８】
ブラックボックス追跡を実現するためには、合成数を法とする乗法群におけるＤＤＨＰを解くことが困難である必要がある。これに関して、Ｓｈｏｕｐ  は、ｇｅｎｅｒｉｃ  ａｌｇｏｒｉｔｈｍを用いて群［Ｇｒｐ］におけるＤＤＨＰを解くためには、群［Ｇｒｐ］の位数の素因数のうち最小の素数をｑ’として，最低でもΘ（ｑ’１／２）の計算量が必要であることを証明している［Ｖ．Ｓｈｏｕｐ，“Ｌｏｗｅｒ  Ｂｏｕｎｄｓ  ｆｏｒ  Ｄｉｓｃｒｅｔｅ  Ｌｏｇａｒｉｔｈｍｓ  ａｎｄ  Ｒｅｌａｔｅｄ  Ｐｒｏｂｌｅｍｓ，”ＬＮＣＳ１２３３，ＥＵＲＯＣＲＹＰＴ‘９７，ｐｐ．２５６−２６６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｂｅｒｌｉｎ，１９９７．］。
【０１２９】
また、大きな２つの素数の積を法とする乗法群において、ＤＤＨＰを解く確率的多項式時間アルゴズムは知られておらず、前述のような群においてＤＤＨＰを解くことは困難であると考えられている。このことは、例えば［Ｄ．Ｂｏｎｅｈ，“Ｔｈｅ  Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｐｒｏｂｌｅｍ，”Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｔｈｉｒｄ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ  Ｓｙｍｐｏｓｉｕｍ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｖｏｌ．１４２３，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ４８−６３，１９９８．］において示されている。
【０１３０】
上述した本発明に従ったブラックボックス追跡処理では、Ｎを法とする乗法群において、位数がλ＝ｐｑとなる元Ｇを生成元とする巡回部分群を用いているため、ｐ，ｑを十分大きく設定することによりＤＤＨＰを解くことは困難となる。
【０１３１】
従って、検査対象機器は入力された情報が配信用ヘッダであるか否かを判断することはＤＤＨＰを解く困難性と同様であり、１／２よりも高い確率で判断することは不可能となる。すなわち、ブラックボックス追跡処理の安全性が証明される。
【０１３２】
従って、検査対象機器は入力された情報が配信用ヘッダであるか追跡用ヘッダであるかを１／２よりも高い確率で判断することは不可能であり、上述したブラックボックス追跡は安全に実行することが可能である。
【０１３３】
［４．不正追跡処理装置、エンティティを構成する装置例］
次に、先に図８を参照して説明した処理を実行する不正追跡処理装置、および暗号文：Ｃを受信し、ヘッダ：ｈ（ｓ，ｒ）、公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）、秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）に基づいて暗号文の復号処理を実行するユーザ側エンティティ側の情報処理装置（ユーザ側情報処理装置）、および、暗号文：Ｃ、ヘッダ：ｈ（ｓ，ｒ）を生成し、エンティティ側の情報処理装置にデータ送信を実行するデータ送信側情報処理装置、さらに公開鍵発行、秘密鍵発行処理を実行するシステム管理者の情報処理装置として適用可能な情報処理装置の構成例について説明する。
【０１３４】
上述の実施例で述べた各エンティティにおける一連の処理は、ハードウェア、ソフトウェアの組み合わせにより実行可能な処理である。すなわち、汎用のコンピュータや、マイクロコンピュータにプログラムを実行させることにより行うことが可能である。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、例えば汎用のコンピュータや１チップのマイクロコンピュータ等にインストールされる。図１０は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施形態としての構成例を示している。
【０１３５】
図１０に示す情報処理装置構成例は１つの例であり、各エンティティにおける情報処理装置は、ここに示すべての機能を必ずしも備えることが要求されるものではない。図１０に示すＣＰＵ（Ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０１は、各種プログラムや、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）を実行するプロセッサである。ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ−Ｍｅｍｏｒｙ）５０２は、ＣＰＵ５０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３は、ＣＰＵ５０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用される。
【０１３６】
ＨＤＤ５０４はハードディスクの制御を実行し、ハードディスクに対する各種データ、プログラムの格納処理および読み出し処理を実行する。暗号処理手段５０５は、送信データの暗号処理、復号処理等を実行する暗号処理部あるいは復号処理部として機能する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭ５０２に格納し、ＣＰＵ５０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０１３７】
メモリ（セキュアモジュール）５０６は例えば耐タンパ構造を持つメモリとして構成され、暗号処理に必要な鍵データ、アクセス許可書の格納領域として使用可能である。例えば、ユーザ側エンティティの情報処理装置であれば、秘密鍵：ｄｉ＝（ｊｉ，Ｒｆ（ｊｉ）−１ｍｏｄλ）を格納する記憶部として設定される。なお、これらのデータは、他のメモリ領域、記憶媒体に格納することも可能であり、例えば公開鍵：ｅＳ＝（Ｎ，Ｇ，Ｙ，Ｙ０）等の公開されたデータは、ハードディスク等に格納しても問題ない。
【０１３８】
バス５２１はＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｎｅｔ／Ｉｎｔｅｒｆａｃｅ）バス等により構成され、各モジュール、入出力インタフェース１２２を介した各入手力装置とのデータ転送を可能にしている。
【０１３９】
入力部５１１は、例えばキーボード、ポインティングデバイス等によって構成され、ＣＰＵ５０１に各種のコマンド、データを入力するためにユーザにより操作される。出力部５１２は、例えばＣＲＴ、液晶ディスプレイ等であり、各種情報をテキストまたはイメージ等により表示する。
【０１４０】
通信部５１３はシステムの接続したエンティティ、例えば暗号データの通信エンティティとの通信処理を実行し、ＣＰＵ５０１の制御の下に、各記憶部から供給されたデータ、あるいはＣＰＵ５０１によって処理されたデータ、暗号化されたデータ等を送信したり、他エンティティからのデータを受信する処理を実行する。
【０１４１】
ドライブ５１４は、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  ＲｅａｄＯｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体５１５の記録再生を実行するドライブであり、各リムーバブル記録媒体５１５からのプログラムまたはデータ再生、リムーバブル記録媒体５１５に対するプログラムまたはデータ格納を実行する。
【０１４２】
各記憶媒体に記録されたプログラムまたはデータを読み出してＣＰＵ５０１において実行または処理を行なう場合は、読み出したプログラム、データは入出力インタフェース５２２、バス５２１を介して例えば接続されているＲＡＭ５０３に供給される。
【０１４３】
先に各フロー図を参照した説明内に含まれる処理を実行するためのプログラムは例えばＲＯＭ５０２に格納されてＣＰＵ５０１によって処理されるか、あるいはハードディスクに格納されＨＤＤ５０４を介してＣＰＵ５０１に供給されて実行される。
【０１４４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０１４５】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１４６】
例えば、プログラムは記憶媒体としてのハードディスクやＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１４７】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記憶媒体にインストールすることができる。
【０１４８】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１４９】
【発明の効果】
以上、説明したように、本発明の構成によれば、正規エンティティに提供した秘密鍵を適用した復号処理により限定エンティティのみの暗号データ利用を可能とした暗号処理構成において、復号機器の検証に基づいて不正エンティティを特定する際に、正規エンティティの識別子ｊｉを含む追跡用ヘッダｈ’と、暗号文Ｃを検査対象機器に入力し、検査対象機器に格納された秘密鍵ｄｉを適用した復号処理により復号文Ｍ’を取得し、取得した復号文Ｍ’と入力暗号文Ｃに対応する平文Ｍとの比較を実行して復号文Ｍ’＝平文Ｍであることを条件として識別子ｊｉに対応するエンティティを不正エンティティとして特定することが可能となり、不正復号器からの不正鍵の取得や鍵の解析処理を実行することなく不正エンティティの特定処理を実現することが可能となる。
【０１５０】
さらに、本発明の構成によれば、暗号文を生成し提供するデータ提供手段と、暗号文を受領し復号するデータ受領手段とを有する暗号処理システムにおいて、公開鍵ｅＳ、および、データ受領手段各々に対応する秘密鍵ｄｉを設定し、秘密鍵ｄｉを正規エンティティ固有の秘密鍵として構成するとともに、暗号文Ｃを復号する際に処理すべきヘッダ情報を正規エンティティの識別子ｊｉを含むヘッダｈとして設定することで、不正エンティティの追跡処理の際に、不正エンティティと推測されるエンティティの識別子を設定したヘッダを追跡用ヘッダとして構成して復号器に入力し、出力結果のデータ検証を実行することにより、不正エンティティの特定が可能となる安全な暗号処理システムが実現される。
【図面の簡単な説明】
【図１】公開鍵の生成と公開処理、および秘密鍵の生成と配布処理を含む準備処理全体の処理フローを示す図である。
【図２】図１におけるステップＳ１０８の公開鍵生成処理の詳細処理フローを示す図である。
【図３】図１におけるステップＳ１１０の秘密鍵生成処理の詳細処理フローを示す図である。
【図４】システム管理者から、各エンティティに対する安全な通信路を介した秘密鍵送信構成を説明する図である。
【図５】暗号化されたデータの同報配信処理について説明するフロー図である。
【図６】送信者から各エンティティに対する暗号文：Ｃと、暗号文に対する付加情報としてのヘッダ：ｈ（ｓ、ｒ）から成る送信データ：Ｃ，ｈ（ｓ、ｒ）の送信処理構成を示す図である。
【図７】暗号文：Ｃとヘッダ：ｈ（ｓ、ｒ）を含むデータを受信したエンティティにおける復号処理の手順を説明するフロー図である。
【図８】ブラックボックス追跡処理の処理手順を説明するフロー図である。
【図９】ブラックボックス追跡処理における検査対象機器の復号処理手順を説明するフロー図である。
【図１０】各エンティティの情報処理装置の構成例を示す図である。
【符号の説明】
１０１  システム管理者
１２１  ユーザ側エンティティ
２０１  送信者
２０２  公開鍵
５０１  ＣＰＵ
５０２  ＲＯＭ
５０３  ＲＡＭ
５０４  ＨＤＤ
５０５  暗号処理手段
５０６  メモリ
５１１  入力部
５１２  出力部
５１３  通信部
５１４  リムーバブル記憶媒体
５２１  バス
５２２  入出力インタフェース
【図１】
2004221800.tif 000029
【図２】
2004221800.tif 000030
【図３】
2004221800.tif 000031
【図４】
2004221800.tif 000032
【図５】
2004221800.tif 000033
【図６】
2004221800.tif 000034
【図７】
2004221800.tif 000035
【図８】
2004221800.tif 000036
【図９】
2004221800.tif 000037
【図１０】
2004221800.tif 000038