(57)【特許請求の範囲】
【請求項１】
「ｎ／３」人より少ない「ｒ」人の無効にされたユーザの集まりは、デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができるように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを暗号化する方法であって、
サーバが、各ユーザに対して、少なくとも１つの一次鍵を割り当てる工程と、
前記サーバが、少なくとも１つの二次鍵を生成する工程と、
前記サーバが、前記少なくとも１つの二次鍵を使用して前記デジタルメッセージを暗号化することによって、暗号文を生成する工程と、
前記サーバが、前記生成された暗号文を前記特権ユーザの端末に通信する工程とを含み、
前記生成された暗号文の数が、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるとき、各ユーザに対する鍵導出コストと一次鍵の数との積が、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする方法。
【請求項２】
各ユーザに対する前記生成された暗号文の数と前記一次鍵の数の積は、「ｒ（ｌｏｇ３（ｎ／ｒ）＋１）」以下であることを特徴とする請求項１に記載の方法。
【請求項３】
少なくとも１人のユーザは、１つの一次鍵だけを前記サーバから受信することを特徴とする請求項１に記載の方法。
【請求項４】
前記サーバが、ユーザが一次鍵から二次鍵を導出するコストを考慮することなく、前記生成された暗号文の最大数とユーザが知る必要のある二次鍵の最大数との間の組み合わせのトレードオフのために、ユーザに二次鍵を割り当てる工程をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記サーバが、バイナリーのツリーのルートに関連付けられているブロードキャスト発信元と、前記バイナリーのツリーの葉ノード「ｎｕ」に関連付けられている複数「ｎ」人のユーザとを用いて、前記バイナリーのツリーを形成する工程をさらに含み、
「ｎｉ」は、「ｎｊ」の祖先であり、
前記「ｎｉ」は、前記「ｎｊ」から前記ルートまでの経路上にあり、
前記「ｎｉ」が、前記「ｎｕ」の祖先であるが、前記「ｎｊ」が、前記「ｎｕ」の祖先ではないように、前記一次鍵「Ｋｎｉ，ｎｊ∈Ｋｕ」は、前記葉ノード「ｎｕ」の各々に対して生成され、
前記「Ｋｕ」は、一次鍵の集合であることを特徴とする請求項１に記載の方法。
【請求項６】
【数１】
0004625011.tif 000015
となるように、前記サーバが、ノードペア（ｎｉ，ｎｊ）に対して鍵「Ｋｎｉ，ｎｊ∈Ｋ」を生成する工程をさらに含み、
前記「ｌ（ｎｉ）」及び前記「ｌ（ｎｊ）」は、前記ルートからの前記ノード「ｎｉ」及び「ｎｊ」の深さであり、
「１≦ｂ≦ｌｏｇ２ｎ」であり、
前記「Ｋ」は、全ての二次鍵の集合であることを特徴とする請求項５に記載の方法。
【請求項７】
「Ｐ」内の各ユーザが、「Ｋｐ」内の少なくとも１つの鍵を知るが、無効にされたユーザが、当該「Ｋｐ」内の鍵を知らないように、鍵の集合「Ｋｐ∈Ｋ」を選択する工程をさらに含み、
前記「Ｐ」は、特権ユーザの集合であることを特徴とする請求項６に記載の方法。
【請求項８】
各特権ユーザ「ｕ」が、前記特権ユーザの集合内にノードペアを有するが、無効にされたユーザが、前記特権ユーザの集合内にノードペアを有しないように、ノードペアの集合｛（ｎｉ，ｎｊ）：「ｎｉ」は、「ｎｊ」の祖先である｝を生成する工程をさらに含み、
前記「ｎｉ」は、前記「ｎｕ」の祖先であるが、前記「ｎｊ」は、前記「ｎｕ」の祖先ではないことを特徴とする請求項７に記載の方法。
【請求項９】
【数２】
0004625011.tif 000016
となるように、前記サーバが、各ノードペアを、ノードペアの鍵集合「ｋｎｉ，Ｎ１，ｋＮ１，Ｎ２，…，ｋＮ２，ｎｊ∈Ｋ」に分割する工程をさらに含み、
前記「ｎｉ」は、前記「Ｎ１」の祖先であり、前記「Ｎ１」は、前記「Ｎ２」の祖先であり、前記「Ｎ２」は、前記「ｎｊ」の祖先であることを特徴とする請求項８に記載の方法。
【請求項１０】
前記サーバが、
前記ルート及び前記無効にされたユーザ「ｒ∈Ｒ」によってＳｔｅｉｎｅｒツリー「Ｔ＝ＳＴ（Ｒ）」を形成する工程と、
２つの葉「ｎｋ」及び「ｎｌ∈Ｔ」の最小の共通の祖先「ｎｋｌ」が、当該祖先「ｎｋｌ」のサブツリー内に前記「Ｔ」の別の葉を含まないように、前記２つの葉「ｎｋ」及び「ｎｌ」を見出す工程と、
「ｎｉ」を「ｎｋ」の祖先である「ｎｋｌ」の子とし、「ｎｊ」を「ｎｌ」の祖先である「ｎｋｌ」の子とし、「ｎｉ≠ｎｋ」である場合、（ｎｉ，ｎｋ）を前記ノードペアの集合に加え、「ｎｊ≠ｎｌ」である場合、（ｎｊ，ｎｌ）を前記ノードペア対の集合に加える工程と、
前記「Ｔ」から前記「ｎｋｌ」の全ての子孫を除去し、前記「ｎｋｌ」が葉になるようにする工程と
をさらに含むことを特徴とする請求項８に記載の方法。
【請求項１１】
前記サーバが、
「ＫＰ」内の各鍵で、ブロードキャストセッション鍵「ｂｋ」を暗号化して、暗号文の集合「ＣＰ」を生成する工程と、
前記「Ｐ」の構成員がどの暗号文を復号すべきかについて決定するのに充分な復号許可情報と共に、前記「ＣＰ」を送信する工程と
をさらに含むことを特徴とする請求項７に記載の方法。
【請求項１２】
前記復号許可情報は、「Ｒ」であることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記復号許可情報は、「Ｐ」であることを特徴とする請求項１１に記載の方法。
【請求項１４】
事前ブロードキャスト伝送の回数は、前記「Ｋｐ」内の鍵の数であることを特徴とする請求項７に記載の方法。
【請求項１５】
前記二次鍵は、ＲＳＡタイプの法を使用して生成されることを特徴とする請求項１に記載の方法。
【請求項１６】
前記「ａ」の値を調整することによって、前記鍵格納コストと送信される暗号文の数との間のトレードオフを微調整することができることを特徴とする請求項１に記載の方法。
【請求項１７】
「ｒ」人の無効にされたユーザの集まりは、デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができるように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを暗号化する方法であって、
サーバが、各ユーザに対して、少なくとも１つの一次鍵を割り当てる工程と、
前記サーバが、ＲＳＡタイプの法を使用することによって、少なくとも１つの二次鍵を生成する工程と、
前記サーバが、前記少なくとも１つの二次鍵を使用して前記デジタルメッセージを暗号化することによって暗号文を生成する工程と、
前記サーバが、前記生成された暗号文を前記特権ユーザの端末に通信する工程とを含み、
前記生成された暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるとき、各ユーザに対する鍵導出コストと一次鍵の数との積が、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする方法。
【請求項１８】
各ユーザに対する前記生成された暗号文の数と前記一次鍵の数の積は、「ｒ（ｌｏｇ３（ｎ／ｒ）＋１）」以下であることを特徴とする請求項１７に記載の方法。
【請求項１９】
少なくとも１人のユーザは、１つの一次鍵だけを受信することを特徴とする請求項１７に記載の方法。
【請求項２０】
前記サーバが、ユーザが一次鍵から二次鍵を導出するコストを考慮することなく、前記生成された暗号文の最大数とユーザが知る必要のある二次鍵の最大数との間の組み合わせのトレードオフのために、ユーザに二次鍵を割り当てる工程をさらに含むことを特徴とする請求項１７に記載の方法。
【請求項２１】
前記サーバが、バイナリーのツリーのルートに関連付けられているブロードキャスト発信元と、前記バイナリーのツリーの葉ノード「ｎｕ」に関連付けられている複数「ｎ」人のユーザとを用いて、前記バイナリーのツリーを形成する工程をさらに含み、
「ｎｉ」は、「ｎｊ」の祖先であり、
前記「ｎｉ」は、前記「ｎｊ」から前記ルートまでの経路上にあり、
前記「ｎｉ」が、前記「ｎｕ」の祖先であるが、前記「ｎｊ」が、前記「ｎｕ」の祖先ではないように、前記一次鍵「Ｋｎｉ，ｎｊ∈Ｋｕ」は、前記葉ノード「ｎｕ」の各々に対して生成され、
前記「Ｋｕ」は、一次鍵の集合であることを特徴とする請求項１７に記載の方法。
【請求項２２】
【数３】
0004625011.tif 000017
となるように、前記サーバが、ノードペア（ｎｉ，ｎｊ）に対して鍵「Ｋｎｉ，ｎｊ∈Ｋ」を生成する工程をさらに含み、
前記「ｌ（ｎｉ）」及び前記「ｌ（ｎｊ）」は、前記ルートからの前記ノード「ｎｉ」及び「ｎｊ」の深さであり、
「１≦ｂ≦ｌｏｇ２ｎ」であり、
前記「Ｋ」は、全ての二次鍵の集合であることを特徴とする請求項２１に記載の方法。
【請求項２３】
「Ｐ」内の各ユーザが、「Ｋｐ」内の少なくとも１つの鍵を知るが、無効にされたユーザが、当該「Ｋｐ」内の鍵を知らないように、鍵の集合「Ｋｐ∈Ｋ」を選択する工程をさらに含み、
前記「Ｐ」は、特権ユーザの集合であることを特徴とする請求項２２に記載の方法。
【請求項２４】
各特権ユーザ「ｕ」が、前記特権ユーザの集合内にノードペアを有するが、無効にされたユーザが、前記特権ユーザの集合内にノードペアを有しないように、ノードペアの集合｛（ｎｉ，ｎｊ）：「ｎｉ」は、「ｎｊ」の祖先である｝を生成する工程をさらに含み、
前記「ｎｉ」は、前記「ｎｕ」の祖先であるが、前記「ｎｊ」は、前記「ｎｕ」の祖先ではないことを特徴とする請求項２３に記載の方法。
【請求項２５】
【数４】
0004625011.tif 000018
となるように、前記サーバが、各ノードペアを、ノードペアの鍵集合「ｋｎｉ，Ｎ１，ｋＮ１，Ｎ２，…，ｋＮ２，ｎｊ∈Ｋ」に分割する工程をさらに含み、
前記「ｎｉ」は、前記「Ｎ１」の祖先であり、前記「Ｎ１」は、前記「Ｎ２」の祖先であり、前記「Ｎ２」は、前記「ｎｊ」の祖先であることを特徴とする請求項２４に記載の方法。
【請求項２６】
前記サーバが、
前記ルート及び前記無効にされたユーザ「ｒ∈Ｒ」によってＳｔｅｉｎｅｒツリー「Ｔ＝ＳＴ（Ｒ）」を形成する工程と、
２つの葉「ｎｋ」及び「ｎｌ∈Ｔ」の最小の共通の祖先「ｎｋｌ」が、当該祖先「ｎｋｌ」のサブツリー内に前記「Ｔ」の別の葉を含まないように、前記２つの葉「ｎｋ」及び「ｎｌ」を見出す工程と、
「ｎｉ」を「ｎｋ」の祖先である「ｎｋｌ」の子とし、「ｎｊ」を「ｎｌ」の祖先である「ｎｋｌ」の子とし、「ｎｉ≠ｎｋ」である場合、（ｎｉ，ｎｋ）を前記ノードペアの集合に加え、「ｎｊ≠ｎｌ」である場合、（ｎｊ，ｎｌ）を前記ノードペア対の集合に加える工程と、
前記「Ｔ」から前記「ｎｋｌ」の全ての子孫を除去し、前記「ｎｋｌ」が葉になるようにする工程と
をさらに含むことを特徴とする請求項２５に記載の方法。
【請求項２７】
前記サーバが、
「ＫＰ」内の各鍵で、ブロードキャストセッション鍵「ｂｋ」を暗号化して、暗号文の集合「ＣＰ」を生成する工程と、
前記「Ｐ」の構成員がどの暗号文を復号すべきかについて決定するのに充分な復号許可情報と共に、前記「ＣＰ」を送信する工程と
をさらに含むことを特徴とする請求項２３に記載の方法。
【請求項２８】
前記復号許可情報は、「Ｒ」であることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記復号許可情報は、「Ｐ」であることを特徴とする請求項２７に記載の方法。
【請求項３０】
事前ブロードキャスト伝送の回数は、前記「Ｋｐ」内の鍵の数であることを特徴とする請求項２３に記載の方法。
【請求項３１】
前記「ａ」の値を調整することによって、前記鍵格納コストと送信される暗号文の数との間のトレードオフを微調整することができることを特徴とする請求項１７に記載の方法。
【請求項３２】
「ｒ」人の無効にされたユーザの集まりは、デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができるように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを復号する方法であって、
端末が、前記ブロードキャスト発信元から暗号文を受信する工程と、
前記端末が、ＲＳＡタイプの法を使用して、ユーザ側に格納されている一次鍵から二次鍵を導出する工程と、
前記端末が、前記導出された二次鍵を使用して暗号文を復号する工程とを含み、
前記生成された暗号文の数が、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるとき、各ユーザに対する鍵導出コストと一次鍵の数との積が、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする方法。
【請求項３３】
各ユーザに対する前記生成された暗号文の数と前記一次鍵の数の積は、「ｒ（ｌｏｇ３（ｎ／ｒ）＋１）」以下であることを特徴とする請求項３２に記載の方法。
【請求項３４】
少なくとも１人のユーザは、１つの一次鍵だけを格納することを特徴とする請求項３２に記載の方法。
【請求項３５】
「ｒ＜ｎ／３」であることを特徴とする請求項３２に記載の方法。
【請求項３６】
ユーザ「ｕ」が有する二次鍵の数を調整することによって、各ユーザに対する前記鍵導出コストと一次鍵の数との間のトレードオフを微調整することができることを特徴とする請求項３２に記載の方法。
【請求項３７】
ブロードキャスト発信元と「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間の暗号化方式用の鍵生成方法であって、
前記ブロードキャスト発信元から前記ユーザに送信される暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるときに、各ユーザに対する鍵導出コストと一次鍵の数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であり、
サーバが、各二次鍵「ｋｉ」に対して、当該「ｋｉ」を導出できるユーザの部分集合「Ｕｉ＝{ｕ：ｋｉ∈Ｋ’ｕ}⊆Ｕ」を関連付ける工程と、
前記サーバが、有向非巡回グラフ（ＤＡＧ）の頂点に対して、前記二次鍵の各々を関連付ける工程と、
前記サーバが、第１の頂点「ｖ」に関連付けられているユーザ部分集合が、第２の頂点「ｗ」に関連付けられているユーザの部分集合に含まれる場合に、２つの頂点の間に有向エッジを配置する工程を含むことを特徴とする方法。
【請求項３８】
前記サーバが、各頂点に対して、ユニークな素数を割り当てる工程をさらに含むことを特徴とする請求項３７に記載の方法。
【請求項３９】
前記サーバが、頂点「ｖ」から頂点「ｗ」への有向エッジが存在する各頂点「ｗ」における素数の積となるように設定される公開パラメータ「ｅ」を、前記グラフ内の各頂点「ｖ」に対して割り当てる工程をさらに含むことを特徴とする請求項３８に記載の方法。
【請求項４０】
前記サーバが、
（ｐ−１）（ｑ−１）が前記頂点に割り当てられた前記素数の倍数ではないように、ＲＳＡの法「Ｎ＝ｐｑ」を選択する工程と、
「ｎ」及び「ｍ」が「１」以外の公約数を持たないように、前記「ｍ」の値を定める工程と、
各頂点「ｖ」に対して、「ｅｄ＝１  ｍｏｄ  （ｐ−１）（ｑ−１）」となるように、「ｄ」を計算する工程と、
各頂点に対して、秘密鍵「ｋ＝ｍｄ  ｍｏｄ  ｎ」を割り当てる工程と
をさらに含むことを特徴とする請求項３９に記載の方法。
【請求項４１】
前記サーバが、
「ｅ１」が、「ｅ２」の倍数であるとき、前記「ｗ」に関連付けられている公開パラメータを「ｅ１」と表わし、前記「ｖ」に関連付けられている公開パラメータを「ｅ２」と表わす工程と、
「ｇ＝ｅ１／ｅ２」を計算する工程と、
前記「ｗ」に関連付けられている既知の秘密鍵を「ｋ」と表わす工程と、
「ｋｇ  ｍｏｄ  ｎ」に従って、前記「ｖ」に関連付けられる秘密鍵を計算する工程と
をさらに含むことを特徴とする請求項４０に記載の方法。
【請求項４２】
「ｎ／３」人より少ない「ｒ」人の無効にされたユーザの集まりは、デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができるように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを復号する方法であって、
端末が、前記ブロードキャスト発信元から暗号文を受信する工程と、
前記端末が、ユーザ側に格納されている一次鍵から二次鍵を導出する工程と、
前記端末が、前記導出された二次鍵を使用して暗号文を復元する工程とを含み、
前記暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるときに、各ユーザに対する鍵導出コストと一次鍵の数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする方法。
【請求項４３】
閾値「ｆ≧１」に対して、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員を含む「ｆ（ｎ−ｒ）」人のユーザは、デジタルメッセージを復号することができるが、残りの「ｎ−ｆ（ｎ−ｒ）」人の無効にされたユーザの集まりは、前記デジタルメッセージを復号することができないように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを暗号化する方法であって、
サーバが、各ユーザに対して、少なくとも１つの一次鍵を割り当てる工程と、
少なくとも１つの二次鍵を生成する工程と、
前記サーバが、前記少なくとも１つの二次鍵を使用して前記デジタルメッセージを暗号化することによって暗号文を生成する工程と、
前記サーバが、前記生成された暗号文を前記特権ユーザの端末に通信する工程とを含み、
【数５】
0004625011.tif 000019
であり、
「｜Ｋｕ｜」は、ユーザ「ｕ」の鍵格納要件であり、かつ、前記二次鍵の部分集合「｜Ｋ’ｕ｜」であり、
「ｃｕ」は、「ｕ」の最悪の場合の鍵導出コストであり、
「ｔ」は、前記暗号文の数であり、
「ｆ」は、復号する資格のあるユーザの総数に対する前記暗号文を復号できるユーザの総数の比率であり、
「ｆ」は、前記ブロードキャスト発信元によって決定されることを特徴とする方法。
【請求項４４】
閾値「ｆ≧１」に対して、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員を含む「ｆ（ｎ−ｒ）」人のユーザは、デジタルメッセージを復号することができるが、残りの「ｎ−ｆ（ｎ−ｒ）」人の無効にされたユーザの集まりは、前記デジタルメッセージを復号することができないように、ブロードキャスト発信元と前記「ｒ」人の無効にされたユーザを含む複数「ｎ」人のユーザとの間で前記デジタルメッセージを復号する方法であって、
端末が、前記ブロードキャスト発信元から暗号文を受信する工程と、
前記端末が、ＲＳＡタイプの法を使用して、ユーザ側に格納されている一次鍵から二次鍵を導出する工程と、
前記端末が、前記導出された二次鍵を使用して暗号文を復元する工程とを含み、
【数６】
0004625011.tif 000020
であり、
「｜Ｋｕ｜」は、ユーザ「ｕ」の鍵格納要件であり、かつ、前記二次鍵の部分集合「｜Ｋ’ｕ｜」であり、
「ｃｕ」は、「ｕ」の最悪の場合の鍵導出コストであり、
「ｔ」は、前記暗号文の数であり、
「ｆ」は、復号する資格のあるユーザの総数に対する前記暗号文を復号できるユーザの総数の比率であり、
「ｆ」は、前記ブロードキャスト発信元によって決定されることを特徴とする方法。
【請求項４５】
コンピュータに、請求項１に記載の方法を実行させるコンピュータプログラム。
【請求項４６】
コンピュータに、請求項１７に記載の方法を実行させるコンピュータプログラム。
【請求項４７】
コンピュータに、請求項３２に記載の方法を実行させるコンピュータプログラム。
【請求項４８】
コンピュータに、請求項４２に記載の方法を実行させるコンピュータプログラム。
【請求項４９】
コンピュータに、請求項３７に記載の方法を実行させるコンピュータプログラム。
【請求項５０】
コンピュータに、請求項４３に記載の方法を実行させるコンピュータプログラム。
【請求項５１】
コンピュータに、請求項４４に記載の方法を実行させるコンピュータプログラム。
【請求項５２】
ブロードキャスト発信元からのデジタルメッセージを復号するブロードキャストシステムにおける端末であって、
前記ブロードキャストシステムは、「ｎ」個の端末を含み、
「ｒ」個の無効にされた端末の集まりは、前記デジタルメッセージを復号することができないが、「ｎ−ｒ」個の特権端末の選択された部分集合の各構成員は、前記デジタルメッセージを復号することができ、
１つ又は複数の一次鍵を受信する命令と、前記ブロードキャスト発信元から暗号文を受信する命令と、ＲＳＡタイプの法を使用して一次鍵から二次鍵を導出する命令と、前記導出された二次鍵を使用して前記暗号文を復号する命令とを格納するメモリと、
前記メモリからの前記命令を実行するプロセッサとを備え、
前記暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるときに、各端末に対する鍵導出コストと一次鍵の数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする端末。
【請求項５３】
「ｒ＜ｎ／３」であることを特徴とする請求項５２に記載の端末。
【請求項５４】
ブロードキャスト発信元からのデジタルメッセージを復号するブロードキャストシステムにおける端末であって、
ブロードキャストシステムは、「ｎ」個の端末を含み、
「ｎ／３」個より小さい「ｒ」個の無効にされた端末の集まりは、前記デジタルメッセージを復号することができないが、「ｎ−ｒ」個の特権端末の選択された部分集合の各構成員は、前記デジタルメッセージを復号することができ、
１つ又は複数の一次鍵を受信する命令と、前記ブロードキャスト発信元から暗号文を受信する命令と、ＲＳＡタイプの法を使用して一次鍵から二次鍵を導出する命令と、前記導出された二次鍵を使用して前記暗号文を復号する命令とを格納するメモリと、
前記メモリからの前記命令を実行するプロセッサとを備え、
前記暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるときに、各端末に対する鍵導出コストと一次鍵の個数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とする端末。
【請求項５５】
デジタルメッセージを暗号化してブロードキャストするためのブロードキャストシステムにおけるブロードキャスト発信元であって、
前記ブロードキャストシステムは、「ｎ」人のユーザを含み、
「ｒ」人の無効にされたユーザの集まりは、前記デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができ、
１つ又は複数の一次鍵を前記ユーザに割り当てる命令と、ＲＳＡタイプの法を使用して二次鍵を生成する命令と、前記二次鍵によってデータを暗号化して暗号文を生成する命令と、前記暗号文を前記ユーザに通信する命令とを格納するメモリと、
前記メモリからの前記命令を実行するプロセッサとを備え、
前記暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、かつ、「ａ≧３」であるときに、各端末に対する鍵導出コストと一次鍵の数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とするブロードキャスト発信元。
【請求項５６】
「ｒ＜ｎ／３」であることを特徴とする請求項５５に記載のブロードキャスト発信元。
【請求項５７】
デジタルメッセージを暗号化してブロードキャストするブロードキャストシステムにおけるブロードキャスト発信元であって、
ブロードキャストシステムは、「ｎ」人のユーザを含み、
「ｎ／３」人よりも少ない「ｒ」人の無効にされたユーザの集まりは、前記デジタルメッセージを復号することができないが、「ｎ−ｒ」人の特権ユーザの選択された部分集合の各構成員は、前記デジタルメッセージを復号することができ、
１つ又は複数の一次鍵を前記ユーザに割り当てる命令と、二次鍵を生成する命令と、前記二次鍵によってデータを暗号化して暗号文を生成する命令と、前記暗号文を前記ユーザに通信する命令とを格納するメモリと、
前記メモリからの前記命令を実行するプロセッサとを備え、
前記暗号文の数は、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下であり、
「ａ＝２ｂ」で、「１≦ｂ≦ｌｏｇｎ」で、「ａ≧３」であるときに、各端末に対する鍵導出コストと一次鍵の数の積は、「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」以下であることを特徴とするブロードキャスト発信元。
【請求項５８】
事前ブロードキャスト伝送用帯域「ｔ」と鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間のトレードオフを実施するブロードキャストシステムであって、
請求項５５又は５７に記載のブロードキャスト発信元と、
請求項５２又は５４に記載の複数の端末とを備えることを特徴とするブロードキャストシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００３年５月２１日に出願された仮出願第６０/４７２,５９１号及び２００３年６月２５日に出願された仮出願第６０/４８２,５０１号の利益を主張する。本出願は、参照によりこれらの仮出願を組み入れる。
【０００２】
本出願は、ブロードキャスト暗号に関し、更に詳しくは、事前ブロードキャスト伝送（pre-broadcast transmission）用帯域と鍵の格納コストと鍵の導出コストとの間で構成可能なトレードオフを有する効率的なブロードキャスト暗号方式の実施に関する。
【背景技術】
【０００３】
ブロードキャスト暗号方式によって、特権ユーザ（privileged user）、即ち、ユーザの選択部分集合「Ｐ」だけが解読することができるように、センターは、ブロードキャストチャネルで、多数のユーザに暗号化データを送信することができる。従来の用途としては、有料テレビや、ＣＤ/ＤＶＤ/フラッシュメモリ上のコンテンツの保護や、映像や音楽や株価情報やニュース記事等のような特権コンテンツの安全なインターネットマルチキャストが挙げられる。しかしながら、ブロードキャスト暗号方式は、潜在的に利益をもたらすコンテンツの選択的な開示を必要とするどのような環境においても使用され得る。
【０００４】
一般的に、ブロードキャスト暗号方式は、一連の事前ブロードキャスト伝送を必要とし、当該事前ブロードキャスト伝送の終わりに、「Ｐ」内のユーザは、ブロードキャストセッション鍵「ｂｋ」を解読することができる。次いで、ブロードキャストの残り部分が、「ｂｋ」を使用して暗号化される。
【０００５】
効率化の観点では、ブロードキャスト暗号方式における最も重要なパラメータは、１）センターによって行なわれる事前ブロードキャスト伝送の回数「ｔ」、２）ユーザが持続的に格納しなければならない鍵材料の最大量「ｋ」、３）ユーザが事前ブロードキャスト伝送からのブロードキャストセッション鍵「ｂｋ」を解読するために実行しなければならない最大計算量「ｃ」である。「ｎ」ユーザのシステムにおいて、「ｎ」ユーザのうちの「ｒ」ユーザが、無効にされる場合、ブロードキャスト暗号方式は、パラメータ「ｔ」とパラメータ「ｋ」とパラメータ「ｃ」との間の良いバランスを見出さなければならない。
【０００６】
効率的な解決策を見出すことが難しいブロードキャスト暗号の問題の一変形は、いわゆる「ステートレス受信機（stateless receiver）」の事例である。この変形は、次の要求事項を含む。
１．特権集合「Ｐ」内の各ユーザは、ブロードキャストを自身で解読することができる。
２．特権集合「Ｐ」外には、ブロードキャストを解読することができるユーザの集団はいない。
３．連続的なブロードキャストは、無関係の特権集合をアドレス指定することができる。
４．他のユーザが、特権集合から脱退するか又は参加する場合であっても、ユーザは、自身の鍵を更新する必要がない。
５．ユーザの鍵は、当該ユーザの視聴履歴によって影響されない。
【０００７】
かかる場合、ユーザには、初期鍵又は初期鍵の集合が提供され、その後のブロードキャストを解読するときに、当該ユーザは、この鍵材料を使用することのみ可能である。ステートレス受信機は、製造時のような初期段階で与えられた鍵しか格納することができない。その結果、無効にされていない受信機が、当該初期受信機鍵を使用して現在のセッション鍵を得ることを可能にするために、全てのブロードキャストメッセージは、充分な情報を含まなければならない。上述の定義は、フリーライド、すなわち、ブロードキャストを解読することのできる特権集合外のユーザにも、ある程度、門戸を開くことができるように拡張することもできる。
【０００８】
ステートレスモデルは、コストが高いだけでなく余計な障害ポイントをもたらすようなどのようなタイプの鍵更新手順をも含まないので、好ましい。ステートレスモデルでは、鍵が更新されないので、不揮発性の耐タンパ型記憶装置に、かかる鍵を埋め込むことができる。この強化されたセキュリティは、ブロードキャスト環境における著作権侵害の可能性を低減する。
【０００９】
ステートレス受信機のブロードキャスト暗号の問題、すなわち、事前ブロードキャスト「ｔ」とユーザ鍵格納「ｋ」とユーザ解読計算「ｃ」との間の現実的なトレードオフは、文献上周知である。しかしながら、従来から提案されている解決策は、全て、少なくとも１つのパラメータに関して不十分である。基本的に、これらの提案は、３つのカテゴリ、１）誤り訂正コードを使用する方式、２）鍵ツリーを使用する方式、及び３）ＲＳＡを使用する方式のうちの１つに属する。
【００１０】
誤り訂正コードを使用する方式では、無効にされたユーザ「ｒ」の数を事前に指定する必要があり、かつ、パラメータ「ｔ」、「ｋ」及び「ｃ」の少なくとも１つが「ｒ」に対して少なくとも線形性を持たなければならない。しかしながら、無効にされたユーザ「ｒ」の数は、実際には時々変化する。鍵ツリーに基づくステートレス受信機のブロードキャスト暗号方式では、耐タンパ型スマートカードのような限られた装置に「ｌｏｇｎ個（又は、それ以上）」の鍵を格納する必要がある。ユーザ鍵格納「ｋ」は、非常に高くなる。
【００１１】
ＲＳＡ公開鍵暗号方式は、『Ｒ．Ｌ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＬ．Ａｄｌｅｍａｎ（ＲＳＡ）著、「Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ-Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｏｍｍ．  Ｏｆ  ｔｈｅ  ＡＣＭ（１９７８）、第２１巻、１２０-１２６頁』に提案された。ＲＳＡ方式によれば、鍵保持者は、「ｅｄ≡１（ｍｏｄ  Φ（ｎ））」となるように、２つの大きい素数「ｐ」及び「ｑ」並びに２つの指数「ｅ」及び「ｄ」を選択する。ここで、「Φ（ｎ）＝ＬＣＭ（ｐ−１）（ｑ−１）」である。かかるＲＳＡ公開鍵暗号方式は、「ｅ」及び積「ｎ＝ｐｑ」を公開するが、「ｄ」、「ｐ」及び「ｑ」を秘密にしておく。メッセージ「ｍ∈Ｚ／ｎＺ」を暗号化するために、送信者は、「ｍｅ（ｍｏｄ  ｎ）」を計算し、当該計算結果を鍵保持者に送信する。解読するために、鍵保持者は、「ｍ≡（ｍｅ）ｄ（ｍｏｄ  ｎ）」を計算する。過去２７年にわたって、多数の暗号についての発明が、ＲＳＡの発明者が想像しなかったＲＳＡに関連する着想を使用してきた。ＲＳＡ暗号方式は、それ自身、ブロードキャスト暗号に係る問題に対処するものではない。
【００１２】
『Ｓ．Ｇ．Ａｋｌ及びＰ．Ｄ．Ｔａｙｌｏｒ著、「Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｓｏｌｕｔｉｏｎ  ｔｏ  ａ  Ｍｕｌｔｉｌｅｖｅｌ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｂｌｅｍ」、Ｃｒｙｐｔｏ’８２、Ｐｌｅｎｕｍ  Ｐｒｅｓｓ（１９８２）、４３３-４５０頁』において、Ａｋｌ及びＴａｙｌｏｒは、ＲＳＡに関連する技術を使用してアクセス制御を処理した。Ａｋｌ-Ｔａｙｌｏｒで、各ユーザは、１つ又は複数のセキュリティクラスの構成員である。任意の固定されたセキュリティクラスの集合に対して、かかる方式における各ユーザは、構成員になっている任意のセキュリティクラスにアクセスすることを可能にする単一の「マスター鍵」を得る。これらのセキュリティクラスは、包含関係の下で、「部分順序集合（ｐｏｓｅｔ：partially-ordered set）」を形成する。このｐｏｓｅｔは、「有向非巡回グラフ（ＤＡＧ：directed acyclic graph）」としてモデル化されることができる。Ａｋｌ-Ｔａｙｌｏｒは、ＲＳＡを使用して、所定のＤＡＧ用に調整された「非混合形式鍵（immiscible keys）」の集合を生成する。セキュリティクラスの非構成員は、結託してもセキュリティクラスにアクセスすることはできない。センターは、ＲＳＡ係数「ｎ＝ｐｑ」を生成し、幾つかの「ｍ∈（Ｚ／ｎＺ）＊」を定める。鍵は、公知の「ｅｉ」に対して、「ｋｉ＝ｍ１／ｅｉ（ｍｏｄ  ｎ）」の形を有する。ＲＳＡの重要な特性は、「ｅ」が与えられると、任意の「ｍ」に対して、「ｍｅ（ｍｏｄ  ｎ）」をコンピュータで計算することは容易であるが、「ｍ１／ｅ（ｍｏｄ  ｎ）」をコンピュータで計算することは難しいことである、すなわち、ｅ乗を計算することは容易であるが、ｅ乗根を計算することは難しいことである。したがって、「ｅｊ」が「ｅｉ」を割る場合、「ｋｉ→ｋｊ」となる。換言すると、「ｅｊ」が「ｅｉ」を割る場合、鍵「ｋｉ」から鍵「ｋｊ」を計算することができる。より一般的には、
｛ｋｉ１，…ｋｉｚ｝→ｋｊ  （「ｅｊ」が「ＬＣＭ（ｅｉ１，…ｅｉｚ）」を割る場合のみ）    …    （１）
となる。
【００１３】
したがって、鍵の可導性（derivability）は、「ｅｉ」の因数分解によって完全に影響される。Ａｋｌ-Ｔａｙｌｏｒにおいて、ＤＡＧの各頂点「νｉ」は、別個の素数「ｐｉ」及び
【数１】
0004625011.tif 000002
に関連付けられる。鍵は、非混合形式であり、セキュリティクラスの非構成員は、結託してもアクセスを行うことはできない。しかし、Ａｋｌ-Ｔａｙｌｏｒにおいて、「ｋｉ」から「ｋｊ」を計算するコストは、非常に高い。加えて、Ａｋｌ-Ｔａｙｌｏｒ方式は、特権部分集合が１つのブロードキャストから別のブロードキャストに変わることができるというブロードキャスト暗号に係る問題に対処していない。
【００１４】
Ｔ．Ａｓａｎｏ著、「Ａ  Ｒｅｖｏｃａｔｉｏｎ  Ｓｃｈｅｍｅ  ｗｉｔｈ  Ｍｉｎｉｍａｌ  Ｓｔｏｒａｇｅ  ａｔ  Ｒｅｃｅｉｖｅｒｓ」、Ａｓｉａｃｒｙｐｔ  ’０２、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２５０１（２００２）、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、４３３頁-４５０頁において、Ａｓａｎｏは、各ユーザが単一の鍵を格納するだけで済むステートレス受信機のブロードキャスト暗号方式を提案している。Ａｓａｎｏ方式によれば、「ａ」が、分岐因子を表し、ツリーの各ノード（ルート以外）が、「ａ−１」個の兄弟を持つように、ユーザは、階層ツリーの葉として位置付けられる。各ユーザは、「（２ａ−１−１）ｌｏｇａｎ＋１」個の部分集合鍵を導き出すことができる。ここで、各部分集合は、ユーザの葉の祖先を、当該祖先の兄弟のうちの幾つか（全部ではない）と共に含む。これらの部分集合は、包含関係にあるｐｏｓｅｔを形成し、鍵の可導性は、ＤＡＧによってモデル化されることができる。特権ユーザは、自身の鍵を使用して二次鍵を導出することができ、そのうちの１つの二次鍵が、ブロードキャストセッション鍵「ｂｋ」を復元し、次いで、ブロードキャストを復元するために使用される。Ａｓａｎｏ方式は、ＲＳＡ暗号方式に関連する技術を使用して、どの鍵を他の鍵から導出することができるかについて決定する。しかし、Ａｓａｎｏ方式が使用する可導性のグラフは、極めて最適化されていない。伝送回数を「ｔ＝Ｏ（ｒｌｏｇａ（ｎ／ｒ））」と定めると、ユーザの計算量要件は、「ａ」が増加するにつれて急速に巨大になる「ｃ＝Ｏ（２ａｌｏｇａｎ）」となることである。したがって、Ａｓａｎｏ方式は、ユーザが１つの鍵を格納するだけでよく、かつ、ユーザの解読計算量に対して事前ブロードキャスト伝送の回数をトレードオフすることができるという利点を持つが、事前ブロードキャスト伝送が減少するにつれて計算量は受け入れられない速度で増大する。
【００１５】
Ｍ．Ｌｕｂｙ及びＪ．Ｓｔａｄｄｏｎ著、「Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｂｏｕｎｄｓ  ｆｏｒ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ」、Ｅｕｒｏｃｒｙｐｔ  ’９８、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １４０３（１９９８）、Ｓｐｒｉｎｇｅｒ-Ｖｅｒｌａｇ、５１２頁-５２６頁において、Ｌｕｂｙ及びＳｔａｄｄｏｎは、無条件に安全なワンタイムブロードキャスト暗号方式（ＯＴＢＥＳ）の変形を検討した。このモデルでは、各ユーザ「ｕ」に、幾つかの鍵の集合「Ｋ’ｕ」が与えられる。Ｌｕｂｙ-Ｓｔａｄｄｏｎ方式は、「ｍａｘｕ｜Ｋ’ｕ｜」と事前ブロードキャスト伝送の回数「ｔ」とに関連する組み合わせの境界、すなわち
【数２】
0004625011.tif 000003
を示す。ここで、「ｎ」は、ユーザの総数であり、「ｒ」は、ブロードキャストを見る権利が与えられていないユーザの数である。しかしながら、鍵間に、可導性が無く、鍵は、（ワンタイムパッドとして）１回しか使用されない。
【００１６】
したがって、パラメータ「ｔ」とパラメータ「ｋ」とパラメータ「ｃ」との間の受入れ可能かつ構成可能なトレードオフを持つブロードキャスト暗号方式が必要である。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上述の観点から、本発明の１つの目的は、事前ブロードキャスト伝送用帯域「ｔ」と鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の構成可能かつ実用的なトレードオフを有する安全かつ効率的なブロードキャスト暗号方式を実施するための方法、コンポーネント及びシステムを提供することである。当該方式は、ＲＳＡ暗号方式に大まかに関連する方法を使用して、鍵のペア同士の関係、すなわち、一方の鍵を他方の鍵から導出することができるか否かについて強化する。ブロードキャストを解読するために、特権ユーザは、自身の一次鍵の１つを使用して、ブロードキャストを解読するために使用される二次鍵を導出する。潜在的に、単一の一次鍵から多数の二次鍵を導出することができる。一次鍵のみ、ユーザの装置に格納する必要がある。
【課題を解決するための手段】
【００１８】
本発明の一態様によれば、ブロードキャストの発信元が、ランダムな特権部分集合を効率的に含む一方、対応する無効にされた部分集合を除外することを可能にするように、ユーザに対して一次鍵及び二次鍵を割り当てる具体的な組み合わせ構成が提供される。例えば、これらの構成の１つは、各ユーザが単一の一次鍵だけを格納することを必要とし、事前ブロードキャスト伝送用帯域「ｔ＝Ｏ（ｒｌｏｇａ（ｎ／ｒ））」を持ち、かつ、鍵導出のために「（２ａ−ｌｏｇ（ａ）−２）ｌｏｇａ（ｎ）」個の計算ユニットを必要とする。ここで、「ａ」は、調整可能なパラメータである。同一の「ｋ」及び「ｔ」に対して、Ａｓａｎｏの構成では、「ｃ＝（２ａ−ｌ）ｌｏｇａ（ｎ）」である。したがって、本発明は、Ａｓａｎｏ方式に比べて飛躍的な改善を示す。
【００１９】
本発明の別の態様によれば、好ましくは、鍵とユーザの部分集合との間で、ブロードキャスト暗号に対して組み合わせ的に最適な任意のマッピングを取り、二次鍵とユーザの部分集合との間で、同一の最適なマッピングを用いて、ブロードキャスト暗号を、一次鍵の鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の構成可能なトレードオフを有するＲＳＡに基づく方式に変換するための一般的方法が提供される。本発明は、無条件に安全なブロードキャスト暗号に関する組み合わせ結果を、鍵導出にＲＳＡ型技術を使用するブロードキャスト暗号の問題に直接適用することを可能にする。該方法は、基本的に次のように動作する。
１．鍵管理者は、適切な係数「ｎ」を選択し、「ｎ」を法とする乱数「ｍ」、すなわち、「ｍ∈Ｚ／ｎＺ」を選択する。
２．例えば、好ましくは、無条件に安全なブロードキャスト暗号に対して、組み合わせ的に最適であるユーザへの鍵の割り当てを見出す。
３．各ユーザ「ｕ」に対して、当該ユーザに既知の二次鍵の集合「Ｋ’ｕ」を結びつける。
４．各鍵「ｋｉ」に、個別の素数「ｐｉ」を関連付け、「ｋｉ」を「ｍ１／ｐｉ（ｍｏｄ  ｎ）」となるように再定義する。
５．各ユーザに１つの鍵だけを格納させるために、ユーザ「ｕ」に数字「ｍ１／ｅｕ（ｍｏｄ  ｎ）」が与えられる。ここで、
【数３】
0004625011.tif 000004
である。
６．「ｋｉ∈Ｋ’ｕ」の場合、ユーザ「ｕ」は、「ｍ１／ｐｉ＝（ｍ１／ｅｕ）ｅｕ／ｐｉ（ｍｏｄ  ｎ）」を導出することができる。
【００２０】
したがって、ユーザが１つの鍵だけを格納する本発明は、鍵格納コストと鍵導出コストとの間の構成可能なトレードオフが可能となるように、容易に適合され得る。また、ある状況下では、効率を改善する他の変形も可能である。
【００２１】
本発明の更なる目的は、好ましくは、「ｔ」及び「ｋ」に関連して組み合わせ的に最適化されたブロードキャスト暗号方式を、「ｔ」、「ｋ」及び「ｃ」に関して組み合わせ的に最適化され、かつ、「ｋ」と「ｃ」との間の構成可能なトレードオフを有するＲＳＡ関連技術を使用した新しいブロードキャスト暗号方式に変換するための一般的方法を提供することである。
【００２２】
ここで、本発明を、添付の図面を参照しながら説明する。機能的に同様の要素は、同一の参照番号を使用して示されている。
【発明を実施するための最良の形態】
【００２３】
本発明は、事前ブロードキャスト伝送用帯域「ｔ」と鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の構成可能かつ実用的なトレードオフを有する安全かつ効率的なブロードキャスト暗号方式を実施するための方法、コンポーネント及びシステムを提供する。ユーザの集合「Ｕ」内の各ユーザ「ｕ」は、一次鍵の集合「Ｋｕ」を格納する。ユーザの鍵格納コストは、 ユーザが格納する鍵の数、すなわち、「｜Ｋｕ｜」と定義される。「Ｋｕ」内の一次鍵から、ユーザ「ｕ」は、二次鍵の集合「Ｋ’ｕ」を導出することができる。二次鍵の集合「Ｋ’ｕ」は、一次鍵の集合「Ｋｕ」より大きいことが好ましい。「Ｋ’ｕ」は、「Ｋ」、すなわち、全ての二次鍵の集合の部分集合である。ユーザの特権集合「Ｐ」だけがブロードキャストを復号できるようにブロードキャストを暗号化するために、ブロードキャストの発信元は、「Ｐ」の各構成員が「Ｋｐ」内の少なくとも１つの鍵を導出することができるが、「Ｕ−Ｐ」内における無効にされた構成員が「Ｋｐ」内の少なくとも１つの鍵を導出することができないように、二次鍵の集合「Ｋｐ∈Ｋ」を見出す。かかる発信元は、ブロードキャストセッション鍵「ｂｋ」を選択し、「Ｋｐ」内の鍵の各々で「ｂｋ」を暗号化し、次いで、「ｂｋ」を使用してブロードキャストを暗号化する。かかる発信元は、「｜Ｋｐ｜」個の暗号化「ｂｋ」、暗号化されたブロードキャスト及びどの暗号化「ｂｋ」を復号することができるかについて「Ｐ」の構成員に決定させる情報を送信する。伝送回数「ｔ」は、「｜Ｋｐ｜」と定義される。ユーザが「Ｐ」内にいる場合、当該ユーザは、格納された一次鍵「Ｋｕ」の集合を使用して、「Ｋ’ｕ∩ＫＰ」内の適切な二次鍵を導出し、「ｂｋ」を復号し、次いでブロードキャストを復号することによって、復号化を行うことができる。一次鍵から二次鍵を導出するには、幾つかの計算ユニット「ｃ」が必要である。これらのユニットの性質及び数は、鍵の可導性が数学的にどのように処理されるかに依存する。本発明では、鍵の可導性は、ＲＳＡ暗号方式に関連する技術を使用して処理される。
【００２４】
一実施形態では、本発明の方法は、次のように実施される。第１に、ブロードキャスト発信元から要求される事前ブロードキャスト伝送の最大回数と、ユーザが知る必要のある二次鍵の最大数との間のほぼ最適な組み合わせのトレードオフが達成されるように、ユーザに二次鍵が割り当てられる。この第１の部分は、鍵間の可導性を考慮しない。第２に、ユーザへの二次鍵の割り当てを前提として、鍵格納コストと鍵導出コストとの間の望ましいトレードオフに従って、一次鍵が構築される。
【００２５】
上述の第１の部分は、純粋に組み合わせの問題である。ブロードキャストを復号するために、ユーザが二次鍵の１つを導出することができなければならないという合理的な想定の下で、本発明の一実施形態におけるユーザ毎の二次鍵の最大数と必要な事前ブロードキャスト伝送の回数との間の関係は、次の通りである。
【数４】
0004625011.tif 000005
ここで、「ａ」は、調整可能なパラメータであり、特に指定されない限り、２を底とする対数が採用される。この構成は、２つの理由で好ましい。第１に、鍵の数が、無効にされたユーザの数である「ｒ」に依存しない。無効にされたユーザの数は、ブロードキャスト毎にかなり変化するので、この依存性の欠如は、望ましい。第２に、この構成は、任意の固定された「ａ」に対する「Ｌｕｂｙ-Ｓｔａｄｄｏｎ不等式（２）」に対して、かなり緊密であり、全ての「ｒ」に対して、当該不等式の右辺の最大値を取る。
【００２６】
図１は、本発明の一実施形態に係る「ｎ＝３２」のツリー構造のグラフ表現を示す。「Ｕ」によって定義される葉に対応するユーザの集合に、鍵「Ｋｎｉ，ｎｊ」が与えられる。
【００２７】
図示する通り、深さ
【数５】
0004625011.tif 000006
のバイナリーのツリーが構築され、各ユーザ「ｕ」は、このツリーの葉に関連付けられる。「ｎｉ」及び「ｎｊ」をこのツリー（内部又は葉）のノードとする。ここで、「ｎｉ≠ｎｊ」であり、かつ、「ｎｉ」が「ｎｊ」からツリーのルートまでの経路上にある場合、「ｎｉ」は、ノード「ｎｊ」の祖先と定義される。レベルの観点から、「ｌ（ｎｉ）」及び「ｌ（ｎｊ）」を、ルートからのこれらのノードへのツリーにおける深さと定義する。整数「ｂ」は、「１≦ｂ≦ｌｏｇ２ｎ」となるように選択され、整数「ａ」は、「２ｂ」に設定される。図１に示す実施形態では、「ｂ＝２」及び「ａ＝４」である。変数「ａ」は、必ずしも「２」の正確な累乗である必要はない。変数「ａ」が、２の正確な累乗でない場合、「ａ」個の葉を持つ「ｂ」レベルのサブツリーは完全ではない。「ｎｉ」が「ｎｊ」の祖先であり、かつ、
【数６】
0004625011.tif 000007
であるように、全てのノードのペア（ｎｉ，ｎｊ）に対して鍵「Ｋｎｉ，ｎｊ」は生成され、「Ｋ」は全てのそのような鍵の集合である。
【００２８】
図１において、そのようなノードペアには、以下ようなものが含まれる。
「ｌ（ｎｉ）＝０」及び「ｌ（ｎｊ）＝１」の場合、（ｎ０，ｎ１）及び（ｎ０，ｎ２）、
「ｌ（ｎｉ）＝１」及び「ｌ（ｎｊ）＝２」の場合、（ｎ１，ｎ３）、（ｎ１，ｎ４）、（ｎ２，ｎ５）及び（ｎ２，ｎ６）、
「ｌ（ｎｉ）＝２」及び「ｌ（ｎｊ）＝３」の場合、（ｎ３，ｎ７）、（ｎ３，ｎ８）、（ｎ４，ｎ９）、（ｎ４，ｎ１０）、（ｎ５，ｎ１１）、（ｎ５，ｎ１２）、（ｎ６，ｎ１３）及び（ｎ６，ｎ１４）、
「ｌ（ｎｉ）＝２」及び「ｌ（ｎｊ）＝４」の場合、（ｎ３，ｎ１５）、（ｎ３，ｎ１６）、（ｎ３，ｎ１７）、（ｎ３，ｎ１８）、（ｎ４，ｎ１９）、（ｎ４，ｎ２０）、（ｎ４，ｎ２１）、（ｎ４，ｎ２２）、（ｎ５，ｎ２３）、（ｎ５，ｎ２４）、（ｎ５，ｎ２５）、（ｎ５，ｎ２６）、（ｎ６，ｎ２７）、（ｎ６，ｎ２８）、（ｎ６，ｎ２９）及び（ｎ６，ｎ３０）、
「ｌ（ｎｉ）＝３」及び「ｌ（ｎｊ）＝４」の場合、（ｎ７，ｎ１５）、（ｎ７，ｎ１６）、（ｎ８，ｎ１７）、（ｎ８，ｎ１８）、（ｎ９，ｎ１９）、（ｎ９，ｎ２０）、（ｎ１０，ｎ２１）、（ｎ１０，ｎ２２）、（ｎ１１，ｎ２３）、（ｎ１１，ｎ２４）、（ｎ１２，ｎ２５）、（ｎ１２，ｎ２６）、（ｎ１３，ｎ２７）、（ｎ１３，ｎ２８）、（ｎ１４，ｎ２９）及び（ｎ１４，ｎ３０）、
「ｌ（ｎｉ）＝４」及び「ｌ（ｎｊ）＝５」の場合、（ｎ１５，ｎ３１）、（ｎ１５，ｎ３２）、（ｎ１６，ｎ３３）、（ｎ１６，ｎ３４）、（ｎ１７，ｎ３５）、（ｎ１７，ｎ３６）、（ｎ１８，ｎ３７）、（ｎ１８，ｎ３８）、（ｎ１９，ｎ３９）、（ｎ１９，ｎ４０）、（ｎ２０，ｎ４１）、（ｎ２０，ｎ４２）、（ｎ２１，ｎ４３）、（ｎ２１，ｎ４４）、（ｎ２２，ｎ４５）、（ｎ２２，ｎ４６）、（ｎ２３，ｎ４７）、（ｎ２３，ｎ４８）、（ｎ２４，ｎ４９）、（ｎ２４，ｎ５０）、（ｎ２５，ｎ５１）、（ｎ２５，ｎ５２）、（ｎ２６，ｎ５３）、（ｎ２６，ｎ５４）、（ｎ２７，ｎ５５）、（ｎ２７，ｎ５６）、（ｎ２８，ｎ５７）、（ｎ２８，ｎ５８）、（ｎ２９，ｎ５９）、（ｎ２９，ｎ６０）、（ｎ３０，ｎ６１）及び（ｎ３０，ｎ６２）
【００２９】
葉ノード「ｎｕ」に関連付けられるユーザ「ｕ」には、「Ｋ」における鍵「Ｋｎｉ，ｎｊ」が付与される。ここで、「ｎｉ」は、「ｎｕ」の祖先であるが、「ｎｊ」は、「ｎｕ」の祖先ではない。換言すると、ユーザ「ｕ」には、鍵「Ｋｎｉ，ｎｊ」が付与され、当該ユーザの葉「ｎｕ」は、「ｎｉ」をルートとするサブツリーから「ｎｊ」をルートとするサブツリーを引いた中にある。全体で、各ユーザは、「（２ａ−ｂ−２）＝（２ａ−ｌｏｇａ−２）ｌｏｇａｎ」個以下の鍵を受け取る。例えば、図１に示すノード「ｎ３１」に対応するユーザ「ｕｌ」には、次の鍵を付与することができる。
「ｋｎ０，ｎ２」、「ｋｎ０，ｎ４」、「ｋｎ０，ｎ５」、「ｋｎ０，ｎ６」、「ｋｎ１，ｎ４」、「ｋｎ３，ｎ８」、「ｋｎ３，ｎ１６」、「ｋｎ３，ｎ１７」、「ｋｎ３，ｎ１８」、「ｋｎ７，ｎ１６」、「ｋｎ１５，ｎ３２」
【００３０】
特権ユーザの集合「Ｐ」に対する暗号化されたブロードキャストを制限するために、「Ｐ」内の各ユーザが「Ｋｐ」内の少なくとも１つの鍵を知るが、無効にされたユーザが「Ｋｐ」内の少なくとも１つの鍵を知らないように、ブロードキャスト発信元は、好ましくは、最小サイズの鍵の集合「Ｋｐ∈Ｋ」を見出さなければならない。一実施形態では、「Ｋｐ」の計算は、２段階で構成される。第１段階で、ブロードキャスト発信元は、各特権ユーザ「ｕ」（無効にされたユーザを除く）が当該集合内にノードペアを有するように、（好ましくは、最小サイズの）ノードペアの集合｛（ｎｉ，ｎｊ）：「ｎｉ」は、「ｎｊ」の祖先である｝を生成する。ここで、「ｎｉ」は、「ｎｕ」の祖先であるが、「ｎｊ」は、「ｎｕ」の祖先ではない。第２段階において、各ノードペアは、ノードペアの鍵の集合「ｋｎｉ，Ｎ１，ＫＮ１，Ｎ２，…，ｋＮ２，ｎｊ」等に分解される。ここで、「ｎｉ」は、
【数７】
0004625011.tif 000008
のように「Ｎｌ」の祖先である。「ｎｉ」が「ｎｕ」の祖先であり、「ｎｊ」が「ｎｕ」の祖先でない場合、ユーザ「ｕ」は、これらの鍵の１つを正確に知る。ブロードキャスト発信元は、ノードペアの集合内の全ノードに対するノードペアの鍵の集合の結合となるように「Ｋｐ」を設定する。
【００３１】
特に、「Ｔ＝ＳＴ（Ｒ）」を、ツリーのルート及び無効にされたユーザＲの葉｛ｎＲ１，…，ｎＲｒ｝によって形成される「Ｓｔｅｉｎｅｒツリー」とする。Ｓｔｅｉｎｅｒツリーは、全ての指定ノードを相互に接続する最小限のエッジを持つグラフである。バイナリーツリーのルートのノード及び全ての葉ノードに対するＳｔｅｉｎｅｒツリーは、バイナリーツリー全体そのものである。図１において、無効にされたノードは、「ｎ３５」、「ｎ３６」及び「ｎ３９」乃至「ｎ６２」である。Ｓｔｅｉｎｅｒツリーは、エッジ「ｎ３」−「ｎ７」、ノード「ｎ７」をルートとするサブツリー内の全てのエッジ、エッジ「ｎ８」−「ｎ１８」及び「ｎ１８」をルートとするサブツリー内の全てのエッジを除くバイナリーツリー内の全てのエッジを含む。ノードペアの集合は、次の一連の段階を繰り返すことによって繰り返し生成される。
１．２つの葉「ｎｋ」、「ｎｌ∈Ｔ」の最小の共通な祖先「ｎｋｌ」が、「ｎｋｌ」のサブツリー内に「Ｔ」の別の葉を含まないように、「ｎｋ」、「ｎｌ」を見出す。
２．「ｎｉ」を、「ｎｋ」の祖先である「ｎｋｌ」の子とし、「ｎｊ」を「ｎｌ」の祖先である「ｎｋｌ」の子とする。「ｎｉ≠ｎｋ」である場合、（ｎｉ，ｎｋ）をノードペアの集合に加え、「ｎｊ≠ｎｌ」である場合、（ｎｊ，ｎｌ）をノードペアの集合に加える。
３．「Ｔ」から「ｎｋｌ」の全ての子孫を除去し、「ｎｋｌ」が葉になるようにする。
【００３２】
１つの葉「ｎｋ」のみが残り、かつ、「ｎｋ≠ｎ０（ルートノード）」である特殊な場合、ノードペア（ｎｏ，ｎｋ）及び「ｎｏ」の子孫は、「Ｔ」から除去される。各反復後に、「Ｔ」内の葉の子孫である全ての特権葉は、幾つかのノードペアによってカバーされる。また、各反復（特殊な場合を除く）により、「Ｔ」内の葉の数が、１つずつ減少するので、プロセスは、「ｒ」回以下の反復後に終了する。このプロセスにより、「２ｒ−１」個以下のノードペアから構成されるノードペアの集合が生成される。
【００３３】
ノードペアの集合が生成されると、ブロードキャスト発信元は、各ノードペアを、好ましくは、最小サイズのノードペアの鍵の集合に分解する。例えば、ノードペア（ｎｉ，ｎｊ）は、「Ｎｌ」をレベル
【数８】
0004625011.tif 000009
における「ｎｊ」の祖先とし、かつ、「ｌ（ｎｊ）−ｌ（Ｎｚ）≦ｂ」となるまで、全ての「ｙ」に対して「Ｎｙ＋１」をレベル「ｌ（Ｎｙ）＋ｂ」における「ｎｊ」の祖先とすることによって、「｜（ｌ（ｎｊ）―ｌ（ｎｉ））／ｂ｜」個の鍵に分解されることができる。
【００３４】
本発明の一実施形態では、ブロードキャスト発信元は、「ＫＰ」を生成すると、「Ｋｐ」内の各鍵でブロードキャストセッション鍵「ｂｋ」を暗号化して、暗号文「ＣＰ」の集合を生成する。ブロードキャスト発信元は、「Ｐ」の構成員がどの暗号文を復号するのかについて決定するのに充分な情報と共に、「ＣＰ」を送信する。「Ｒ」が、無効にされたユーザの集合であり、「｜Ｒ｜」が、「｜Ｐ｜」よりもずっと小さい場合、送信される情報は、「Ｒ」である。代替的に、ブロードキャストは、「Ｐ」又はノードペアの集合を送信することができる。
【００３５】
復号するために、特権ユーザは、どの暗号文を復号すべきかについて決定しなければならない。一実施形態では、ユーザは、ブロードキャスト発信元と同一の技術を使用してノードペアの集合を決定することにより、上述の決定を行う。次いで、特権ユーザは、「ｎｉ」が、「ｎｕ」、すなわち、ユーザの葉の祖先であるが、「ｎｊ」が、「ｎｕ」の祖先ではないように、ノードペア（ｎｉ，ｎｊ）を見出す。次いで、特権ユーザは、「ｎｌ」が「ｎｕ」の祖先ではないときに、上述のように計算された通り、（ｎｉ，ｎｊ）の分解結果内で「ｎｕ」の祖先として「ｎｋ」を有する鍵「ｋｎｋ，ｎｌ」を決定することによって、上述の分解結果内の鍵を決定する。特権ユーザは、「ｋｎｋ，ｎｌ」を使用して、「ＣＰ」の適切な暗号文を復号し、ブロードキャストセッション鍵「ｂｋ」を復元し、その後、ブロードキャストを復元する。
【００３６】
上述の実施形態では、ユーザ毎の二次鍵の数は、
【数９】
0004625011.tif 000010
以下である。伝送の回数は、「ｔ＝ ＫＰ」である。「ＮＰ」を、上述の手順で計算されたノードペアの数とする。次いで、各ノードペアは、平均して「ｌｏｇ（ｎ／ＮＰ）／ｂ」個以下のノードペアの鍵に分解されるので、「ｔ」は、「ＮＰｌｏｇａ（ｎ／ＮＰ）」以下であり、「ＮＰｌｏｇａ（ｎ／ＮＰ）」は、「ＮＰ＝２ｒ−１」、すなわち、ノードペアの最大数で、最大値になると推定される。したがって、「ｔ」は、「（２ｒ−１）ｌｏｇａ（ｎ／（２ｒ−１））」以下である。また、「ｘ」が、変数であり、「２ｒａ２−ｘ≦ｎ」のときに、より洗練された技術を使用して、「ｔ」が、「ｒ（ｌｏｇａ（ｎ／ｒ）＋ｘ）」以下であることを証明することもできる。例えば、「ｔ」は、「２ｒａ≦ｎ」のときに、「ｒ（ｌｏｇａ（ｎ／ｒ）＋１）」以下である。
【００３７】
本発明の第２の部分では、ユーザに対する二次鍵の割り当てを前提として、鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の所望のトレードオフに従って、一次鍵が構築される。このトレードオフの正確な性質は、（一次鍵から二次鍵の）鍵の可導性を数学的にどのように処理するかに依存する。本発明の一実施形態では、鍵の可導性は、ＲＳＡ暗号化方式に関連する技術を使用して処理される。
【００３８】
鍵の可導性は、グラフによってモデル化することができる。一般的に、各二次鍵「ｋｉ」は、「ｋｉ」を導出することができるユーザの部分集合「Ｕｉ＝｛ｕ：ｋｉ∈Ｋ’ｕ｝⊆Ｕ」に関連付けられることができる。これらの部分集合は、例えば、「Ｕｉ⊂Ｕｊ」のときに、「Ｕｉ＜Ｕｊ」の包含関係の下で、ｐｏｓｅｔを形成することができる。このｐｏｓｅｔは、各ユーザの部分集合「Ｕｉ」をＤＡＧの頂点と関連付け、「Ｕｉ＜Ｕｊ」のときに、ＤＡＧにおける「ｖｉ」から「ｖｊ」への有向エッジを含めることによって、ＤＡＧとしてモデル化されることができる。「Ｕｉ＜Ｕｊ」である場合、「Ｕｉ」内の各ユーザが「Ｕｊ」内にも入るので、鍵「ｋｉ」から鍵「ｋｊ」を導出することができる。したがって、「ｖｉ→ｖｊ」である（つまり、頂点「ｖｉ」から頂点「ｖｊ」への有向エッジがある）場合にのみ、ＤＡＧの有向エッジは、鍵の可導性、すなわち、「ｋｉ→ｋｊ」をモデル化する（つまり、鍵「ｋｉ」から鍵「ｋｊ」を導出することができる）。特定の状況で、一部の（ｉ，ｊ）に対して、頂点「ｖｉ」から頂点「ｖｊ」への有向エッジが無い場合でも、「ｋｉ→ｋｊ」を持つことは有利であるかもしれないが、推移性（つまり、「ｋｉ→ｋｊ」かつ「ｋｊ→ｋｌ」であれば、「ｋｉ→ｋｌ」であること）が必要である。
【００３９】
図２は、鍵可導性を有向非巡回グラフとしてモデル化する方法を示すフローチャートを示す。ステップ２０１において、プロセスは、ユーザに対して二次鍵を割り当てることにより開始する。ステップ２０２において、プロセスは、二次鍵の各々に対してユーザの部分集合を識別し、二次鍵が、対応するユーザの部分集合内のユーザによって導出され得る。次いで、プロセスは、ＤＡＧの頂点に、二次鍵の各々又は当該二時鍵の対応するユーザの部分集合を関連付ける。ステップ２０３において、第１の頂点「ｖ」に関連付けられたユーザの部分集合が、第２の頂点「ｗ」に関連付けられたユーザの部分集合に含まれる場合、２つの頂点の間に有向エッジが配置される。ステップ２０４において、グラフの各頂点にユニークな素数が割り当てられる。ステップ２０５において、プロセスは、頂点「ｖ」から頂点「ｗ」への有向エッジが存在する各頂点「ｗ」における素数の積となるように設定される公開パラメータ「ｅ」を、当該グラフの各頂点「ｖ」に割り当てる。一般的方法に対しては、フローチャートの最初の３つのステップだけが必要である。しかしながら、当該グラフに鍵を割り当てる方法を示すために、本発明のＲＳＡに基づく実施形態に対して、最後の２つのステップが追加されている。
【００４０】
推移的ＤＡＧ「Ｇ＝（Ｖ，Ｅ）」を前提として、ＲＳＡに関連する技術を使用して、「Ｇ」が鍵間の可導性をモデル化するように、鍵の集合「Ｋ」を構築することが可能である。ブロードキャスト発信元は、当該ブロードキャスト発信元以外の誰にとっても、ＲＳＡタイプの法（RSA-type modulus）「Ｎ」を自明ではない因数に分解することが難しいように、「Ｎ」を生成する。好ましくは、「Ｎ」は、２つの安全な素数の積、すなわち、「Ｎ＝ｐｑ」として計算される。ここで、「ｐ」及び「ｑ」は、素数「ｐ’」及び「ｑ’」に対して「ｐ＝２ｐ’＋ｌ」及び「ｑ＝２ｑ’＋ｌ」となるような大きい（例えば、５１２ビットの）素数である。しかし、「Ｎ」を因数分解することが難しい限り、当該「Ｎ」を異なる方法で生成することができる。センターは、幾つかの「ｍ∈（Ｚ／ｎＺ）＊」を固定する。鍵は、公知の「ｅｉ」に対して「ｋｉ＝ ｍ１／ｅｉ（ｍｏｄ  ｎ）」 の形を有する。
【００４１】
図３は、ＲＳＡに基づく技術を使用して、ＤＡＧの頂点に対して鍵を割り当てる方法を示すフローチャートを示す。ステップ３０１において、プロセスは、情報理論的ブロードキャスト暗号方式をＤＡＧに関連付けることにより開始する。ステップ３０２において、ＲＳＡの法「Ｎ」が選択される。一実施形態では、ＲＳＡの法「Ｎ」は、２つの素数「ｐ」及び「ｑ」の積である。ここで、（ｐ−１）（ｑ−１）は、グラフの頂点に割り当てられた素数の倍数ではない。ステップ３０３において、「ｎ」及び「ｍ」が「１」以外の公約数を持たないように、「ｍ」の値が固定される。ステップ３０４において、 各頂点「ｖ」に対して、「ｅｄ＝１  ｍｏｄ  （ｐ−１）（ｑ−１）」となるように「ｄ」が計算される。ステップ３０５において、秘密鍵「ｋ＝ｍｄ  ｍｏｄ  ｎ」が、各頂点に割り当てられる。「ｅｊ」が「ｅｉ」を割ると、ユーザは、「ｋｉ」から「ｋｊ」を導出することができる。更に詳しくは、
｛ｋｉ１，…ｋｉｚ｝→ｋｊ  （「ｅｊ」が「ＬＣＭ（ｅｉ１，…ｅｉｚ）」を割る場合のみ）    …    （５）
となる。
【００４２】
したがって、鍵の可導性は、「ｅｉ」の因数分解によって完全に影響される。本発明の一実施形態では、「ｅｉ」を構造化する方法は、所望の鍵格納コスト、つまり、どれだけ多くの一次鍵をユーザが格納するかに依存する。極端な場合、ユーザが、１個の一次鍵しか格納しないことを希望する場合、「ｅｉ」を選択する方法は、ＤＡＧにおける各頂点「ｖｉ」に別個の素数「ｐｉ」を関連付けて、
【数１０】
0004625011.tif 000011
を設定することである。そうすると、まさしく「ｖｉ→ｖｊ」のときに、「ｋｉ→ｋｊ」となる。
【００４３】
図４は、所定の頂点の鍵を、当該所定の頂点に隣接する頂点から導出する方法を示すフローチャートを示す。一実施形態によれば、これらの鍵は、非混合形式の特性を有する。つまり、「１≦ｙ≦ｚ」に対して「ｋｉ→ｋｊ」である場合のみ「｛ｋｉ１，…，ｋｉ２｝→ｋｊ」である。したがって、鍵を組み合わせて新しい情報を得ることはできない。ユーザ「ｕ」の一次鍵は、「ｍ１／Ｅｎ（ｍｏｄ  ｎ）」となるように設定される。ここで、「Ｅｕ＝ＬＣＭ（｛ｅｉ：ｕ∈Ｕｉ｝）」である。.図４に示された方法は、頂点「ｗ」から頂点「ｖ」への有向エッジが存在し、かつ、頂点「ｗ」の秘密鍵が既知であると仮定して、頂点「ｖ」の秘密鍵を導出するために使用される。ステップ４０１において、プロセスが開始する。ステップ４０２において、「ｅ１」は、「ｗ」に関連付けられた公開パラメータを表わすために使用され、「ｅ２」は、「ｖ」に関連付けられた公開パラメータを表わすために使用される。ここで、「ｅ１」は、「ｅ２」の倍数である。ステップ４０３において、値「ｇ＝ｅ１／ｅ２」が算出される。ステップ４０４において、「ｋ」は、「ｗ」に関連付けられた秘密鍵を表わすために使用される。「ｖ」に関連付けられた秘密鍵は、「ｋｇ  ｍｏｄ  ｎ」である。
【００４４】
一次鍵から二次鍵を計算するには、計算コストがかかる。「｜ｋｉ｜」は、「ｋｊ∈Ｋｕ：ｋｉ→ｋｊ（「ｋｉ」から導出可能な「Ｋｕ」内の鍵の数）」を表わすものとする。「｜ｋｉ｜」が大きい場合には、「ｅｉ」も大きい。特に、「ｅｉ」は、「｜ｋｉ｜＋１」個の素因数を有する。最悪の場合、一定数の二次鍵の導出コスト「ｃｕ」及び鍵格納コスト「｜Ｋｕ｜」は、反対の関係を有する。一般的に、安全な格納は、計算よりも高価であるので、特に有利なトレードオフは、ユーザが単一の一次鍵を格納する場合、つまり、「｜Ｋｕ｜＝１」の場合であろう。この場合、「ｅｉ」が、どのように構造化されているかに関係なく、「ｃｕ＝｜Ｋｕ｜」である（実際には、一次鍵が二次鍵ではない場合には、「ｃｕ＝｜Ｋｕ｜−１」とすることが可能である）。「｜Ｋｕ｜」のときに「ｅｉ」を構造化する上述の方法は、幾つかのＤＡＧに対する平均的な事例の鍵導出コストを実質的に低減することができる。
【００４５】
しかし、より高い鍵格納コストを受け入れることができるかもしれない。実際、鍵格納コストと鍵導出コストとの間のトレードオフは、一定の二次鍵の集合に対して構成可能であり、格納される一次鍵の数を低減すると、結果的に、一次鍵から二次鍵を導出するコストが増加する。
【００４６】
「｜Ｋｕ｜＞１」の場合、「ｅｉ」を構造化する方法の一実施形態では、ＤＡＧにおける各頂点「ｖｉ」に別個の素数「ｐｉ」を関連付け、「ｅｉ＝ｐｉ」となるように設定する。「Ｋ’＝｛ｍ１／ｅ１，…，ｍ１／ｅｌ｝」をユーザ「ｕ」が導出できる二次鍵の集合とし、所望の一次鍵の数は、「ｄ≦ｌ」であるものと想定する。ここで、「ｌ」は、ユーザ「ｕ」が有する二次鍵の数、すなわち、「｜Ｋ’ｕ｜」である。適切な一次鍵は、二次鍵を「ｄ」グループに区分化することによって構築され得る。なお、「ｄ」グループでは、各々が、
【数１１】
0004625011.tif 000012
個の鍵を有する。例えば、そのような１つのグループは、鍵「｛ｍ１／ｅｉ，…，ｍ１／ｅｉ＋ｊ｝」から構成されるものと想定する。このグループにおける全ての二次鍵は、一次鍵「ｍ１／Ｅ１，ｊ」から導出され得る。ここで、「Ｅｉ，ｊ＝ＬＣＭ（ｅｉ，…，Ｅｉ＋ｊ）＝ｐｉｐｉ＋１…ｐｉ＋ｊ」である。全部で「ｄ」個のグループがあるので、全部で「ｄ」個のそのような一次鍵がある。「ｄ」の値を、任意の正の整数に「微調整」することができる。各グループは、「ｄ’」個以下の鍵によって構成されるので、最悪の場合の鍵導出「ｃ」は、「ｄ’−１」回以下の指数計算である。
【００４７】
一般的に、ＤＡＧに適合する「ｅｉ」のどんな構造化も許容される。上述の方程式（６）及び鍵が非混合形式でなければならないという要求事項に照らして、対応する「ｋｉ」が、ＤＡＧに適合するならば、「ｅｉ」の集合は、ＤＡＧに適合する。
【００４８】
本発明の第１の部分及び第２の部分を結合することにより、ここで検討されているＲＳＡ関連ブロードキャスト暗号方式のクラスに対してほぼ最適であり、送信回数「ｔ」と鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の構成可能なトレードオフを持つブロードキャスト暗号方式が得られる。特に、第１の部分は、Ｌｕｂｙ−Ｓｔａｄｄｏｎ境界に照らしてほぼ最適であり、「ｔ」と二次鍵の最大数「ｍａｘｕ｜Ｋ’ｕ｜」との間のトレードオフをもたらす構成を見出すことを含む。第２の部分は、結果的に、所定の希望する鍵導出コスト「ｍａｘｕｃｕ」に対して、二次鍵を導出することができる一次鍵の最小数「ｍａｘｕ｜Ｋｕ｜」がもたらされる。「ｍａｘｕ｜Ｋ’ｕ｜≦ｍａｘｕ｜Ｋｕ｜｜ｃｕ｜であるため、２つの部分は、３つの変数「ｔ」、「ｋ」及び「ｃ」の全てに関係し、当該３つの変数の間のほぼ最適なトレードオフを見出す。
【００４９】
２つの部分は、各々独立して役立つ。例えば、第１の部分についての構造化は、無条件に安全なブロードキャスト暗号にも使用することができる。また、第２の部分の方法は、一般的に、ブロードキャスト暗号に適するユーザへの二次鍵の任意の割り当てにも適用される。
【００５０】
従来のステートレス受信機のブロードキャスト暗号方式に勝る本発明の１つの利点は、実用的な構成可能性である。特に、本発明は、各ユーザが希望する場合には、単一の一次鍵だけを格納することを可能にする。Ａｓａｎｏ以外の従来の方式では、各ユーザが、特定の方式に応じて、少なくとも「ｒ」個又は「ｌｏｇｎ」個の鍵を格納する必要があった。Ａｓａｎｏは、各ユーザが、当該ユーザの鍵格納コストを最小化することを可能にしたが、鍵格納コスト「ｋ」と鍵導出コスト「ｃ」との間の構成可能なトレードオフを提供しておらず、「ｔ」と「ｋ」と「ｃ」との間の総合的トレードオフにとっては不都合である。特に、Ａｓａｎｏ方式では、鍵可導性グラフの分岐因子を「ａ」で表わし、各ユーザが単一の鍵を格納すると想定し、かつ、伝送の最大回数を「ｔ＝ｒ（ｌｏｇａ（ｎ／ｒ）＋ｌ）」としており、Ａｓａｎｏによるユーザの計算要件は、「ｃ＝（２ａ−１−１）ｌｏｇａｎ」となり、「ａ≧３」のときに急速に巨大になる。同等の伝送帯域幅及び鍵格納コストに対して、本発明は、鍵導出のために、「（２ａ−ｌｏｇａ−２）ｌｏｇａｎ」個以下の計算ユニットを必要とするだけである。加えて、本発明の各ユーザに対する伝送回数と一次鍵の数の積は、多くても「ｒ（ｌｏｇ３（ｎ／ｒ）＋１）」にすぎない。
【００５１】
参照によって本明細書に組み込まれる『Ｍ．Ａｂｄａｌｌａ、Ｙ．Ｓｈａｖｉｔｔ及びＡ．Ｗｏｏｌ著、「Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ  ｆｏｒ  Ｒｅｓｔｒｉｃｔｅｄ  Ｍｕｌｔｉｃａｓｔ  Ｕｓｉｎｇ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ」、ＡＣＭ  Ｔｒａｎｓ  ｏｎ Ｎｅｔｗｏｒｋｉｎｇ、第８巻第４号、４４３−４５４頁、２０００年』は、情報理論の文脈で、ブロードキャスト発信元が、（「Ｐ」の全構成員に加えて）無効にされたユーザ「Ｒ」の一部の構成員を許容する用意があるならば、事前ブロードキャスト伝送用帯域及び／又は鍵格納コストをどのようにして低減することができるかについて記載している。特に、全ての特権集合「Ｐ」に対して、「｜ｒ（Ｐ）｜／｜Ｐ｜≦ｆ」であるならば、鍵の割り当ては、ｆ重化（f-redundant）として定義される。ここで、「ｒ（Ｐ）」は、「Ｐ」向けに意図されたブロードキャストを復号できるユーザの集合であり、より緩やかな下限
【数１２】
0004625011.tif 000013
を得る。ここで、「ｋ」は、ユーザが持続的に格納しなければならない鍵材料の最大量であり、「ｆ」は、復号する資格のあるユーザの総数に対する暗号文を復号できるユーザの総数の比率であり、「ｆ」は、常に少なくとも「１」である。
【００５２】
比率「ｆ」は、ブロードキャスト発信元によって決定される。「ｆ」が大きく設定された場合、多くの非特権ユーザが、ブロードキャストを復号することができる。
【００５３】
Ａｂｄａｌｌａ等も、また、優れた鍵のカバーを見出すための構造及びアルゴリズムを提供している。この方法を、上述したＡｋｉ-Ｔａｙｌｏｒに基づく構造に拡張することによって、同様のトレードオフが、次の通り得られる。
【数１３】
0004625011.tif 000014
ここで、「｜Ｋｕ｜」は、ユーザ「ｕ」の鍵格納要件であり、「ｃｕ」は、最悪の場合の鍵導出コストである。
【００５４】
本発明の鍵の可導性の概念は、Ａｂｄａｌｌａ-Ｓｈａｖｉｔｔ-Ｗｏｏｌ方式に加えられる。換言すると、比較的多数の二次鍵を使用する代わりに、本発明の一実施形態に係るシステムは、少数の一次鍵「｜Ｋｕ｜」を使用することができ、当該システムが、鍵導出性コストを受け入れる用意があるならば、「｜Ｋｕ｜」は、「｜Ｋ’ｕ｜」の適切な部分集合である。
【００５５】
図５は、本発明の一実施形態に係るブロードキャスト暗号のためのシステムの信号フローを簡潔に示す。センター５０１は、ブロードキャストセッション鍵「ｂｋ」を選択し、暗号化鍵の各々により「ｂｋ」を暗号化して、暗号文の集合を生成する。特権ユーザだけが、ブロードキャストセッション鍵を正しく復号することができる。無効にされたユーザは、「ｂｋ」に関する情報を得ることができない。次いで、センター５０１は、暗号文と、特権ユーザがどの暗号文を復号できるかについて決定することを可能にする情報とを送信する。
【００５６】
特権ユーザ５１１及び５１２は、格納された復号鍵によって、適切な暗号文を復号して、ブロードキャストセッション鍵「ｂｋ」を復元し、その後、ブロードキャストを復元する。無効にされたユーザ５２１及び５２２は、暗号文及びブロードキャストを復号できない。
【００５７】
図６は、本発明の一実施形態に従って、通信ネットワークで、サーバ又はセンターから暗号化データを受信する端末又はクライアントのブロック図を示す。本発明のブロードキャストシステムは、上述したブロードキャスト暗号方式に従って暗号化されたブロードキャストを生成又は受信するエンティティに各々関連付けられ得る多数の端末を含む。
【００５８】
各端末６００は、メモリ６０２との間で双方向通信を行うプロセッサ６０１を含む。プロセッサ６０１は、上述した手順を実行して、ブロードキャストを生成し、送信し、受信し又は復号するためのプログラムコードを実行する。また、プロセッサ６０１は、他の端末に送信される情報を生成するためのプログラムコードをも実行する。プログラムコードは、既知の方法に従って作成され得る。メモリ６０２は、プログラムコードのみならず、中間結果及びブロードキャスト暗号手順の実行中に使用される他の情報をも格納する。
【００５９】
エンティティが通信を行うことができる通信ネットワーク６０３が提供される。通信ネットワークは、例えば、ＬＡＮコンピュータネットワーク、ＷＡＮコンピュータネットワーク及び／又は移動電話ネットワークを含む様々な汎用的形態であってもよい。
【００６０】
図７は、本発明の一実施形態に従って通信ネットワークで端末又はクライアントにデータを配布するセンター又はサーバのブロック図を示す。各センター７００は、メモリ７０２との間で双方向通信を行うプロセッサ７０１を含む。プロセッサ７０１は、上述した手順を実行して、ブロードキャストを生成し、暗号化し、送信し、又は受信するためのプログラムコードを実行する。メモリ６０２は、プログラムコードのみならず、中間結果及びブロードキャスト暗号手順の実行中に使用される他の情報をも格納する。エンティティが通信を行うことができる通信ネットワーク７０３が提供される。
【００６１】
図８は、センター８０１と多数の端末８１１、８１２、８１３、８１４と通信ネットワーク８０３とを含む本発明の一実施形態に係るブロードキャスト暗号用のシステムのブロック図を示す。 センター及び端末については、図６及び図７を参照して上述した。
【００６２】
本発明について、特定の説明に役に立つ実施形態を参照にして記述して説明したが、本発明は、これらの実施形態に限定されることを意図したものではない。当業者は、発明の精神から逸脱することなく、変形及び変化を施すことができることを理解するであろう。したがって、添付の請求の範囲内に該当するそのような全ての変形及び変化、並びに、それらの均等物を本発明内に含めるつもりである。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施形態における「ｎ＝３２」及び「ｂ＝２」の場合のツリー構成のグラフ表現を示す。
【図２】本発明の一実施形態において、鍵の可導性をＤＡＧとしてモデル化する方法を示すフローチャートを示す。
【図３】本発明の一実施形態において、ＲＡＳに基づく技術を使用してＤＡＧの頂点に鍵を割り当てる方法を示すフローチャートを示す。
【図４】本発明の一実施形態において、所定の頂点用の鍵を隣接する頂点から導出する方法を示すフローチャートを示す。
【図５】本発明の一実施形態におけるブロードキャスト暗号用のシステムの信号フローを簡潔に示す。
【図６】本発明の一実施形態における通信ネットワーク上でサーバ又はセンターからの暗号化データを受信する端末又はクライアントのブロック図を示す。
【図７】本発明の一実施形態における通信ネットワーク上で端末又はクライアントにデータを配布するセンター又はサーバのブロック図を示す。
【図８】本発明の一実施形態におけるブロードキャスト暗号用のシステムのブロック図を示す。
【図１】
0004625011.tif 000021
【図２】
0004625011.tif 000022
【図３】
0004625011.tif 000023
【図４】
0004625011.tif 000024
【図５】
0004625011.tif 000025
【図６】
0004625011.tif 000026
【図７】
0004625011.tif 000027
【図８】
0004625011.tif 000028