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