JPH11340962A

JPH11340962A - 鍵配送方法及び装置

Info

Publication number: JPH11340962A
Application number: JP10142887A
Authority: JP
Inventors: Genji Nishioka; 玄次西岡; Masanori Yamazaki; 正憲山▲崎▼; Hisashi Umeki; 久志梅木
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1998-05-25
Filing date: 1998-05-25
Publication date: 1999-12-10

Abstract

(57)【要約】【課題】受信者（鍵利用者）が多い場合でも鍵共有のた
めのデータ長を短くすることができ、かつ、結託攻撃に
対して有効な鍵配送方法を提供する。【解決手段】放送局100は、自身の秘密情報でなる有限
集合A(={s(ij)|1≦i≦m,1≦j≦n｝)と集合Vj(={(X1〜X
m)|fj(X1〜Xm,s(1j)〜s(mj))=0}、fjは集合{(z1〜z2m)|
ziは整数}から集合Wj(∋0)への写像）を作成する。(r
(x,ij)) (1≦i≦m)∈Vjをランダムに選び、s(x,i)=r(x,
γ(i))(1≦i≦mn）(γは集合{1〜mn}から集合{ij}への
写像で、放送局の秘密とする）を受信者xの秘密鍵とす
る。s(ij)に対応する情報としてu(ij)を作成し、y(i)=u
(γ(i))(1≦i≦mn）とする。s(x,i)を用いて受信者xの
識別情報dxを計算し、y(1)〜y(mn)、識別情報dxを受信
者xに送信する。受信者x200は、適当な関数hを用いて、
K=h(s(x,1)〜s(x,mn),y(1)〜y(mn),dx)により共通鍵Kを
計算する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、同報暗号通信を行
なうことを目的として、送信者（鍵作成者）と受信者
（鍵利用者）とが、送信データを暗号化／復号化するた
めの共通の鍵を共有するための、鍵配送方法および装置
に関する。

【０００２】

【従来の技術】従来より、同報暗号通信（鍵管理）方法
について、幾つかの方法が提案されている。

【０００３】たとえば、文献「S.J.Kent:Security requ
irement and protocols for a broadcast scenario,IEE
E Trans. Commun.,COM-29,6,pp.778-786(1981)」に記載
のコピー鍵方式は基本的である。

【０００４】コピー鍵方式とは、従来の１対１の暗号個
別通信を、単純に同報通信に拡張したものである。１種
類の鍵のコピーを、送信者と複数の正規の受信者に配送
する。送信者は、そのコピー鍵を用いて送信データを暗
号化し、送信する。正規の受信者は、同一のコピー鍵を
用いて、暗号化された送信データを復号化する。

【０００５】その他には、文献「小山：マスタ鍵による
同報通信の暗号方式，信学論（Ｄ），J65-D，９，pp.11
51-1158(1982)」に記載のＲＳＡの個別鍵代替用マスタ
鍵を用いた同報暗号通信方法や、文献「李，常盤他：多
重化・多重分離法を用いた同報通信，1986年暗号と情報
セキュリティシンポジウム」に記載の中国人の剰余定理
を用いた情報系列の多重化・多重分離法による鍵配送方
式、あるいは、文献「満保他：効率的な同報暗号通信方
式，信学技法ISEC93-34（1993-10）」に記載の方式など
がある。

【０００６】まず、中国人の剰余定理を用いて情報系列
の多重化・多重分離法を行う方式について説明する。

【０００７】（１）鍵生成処理：受信者i (1≦i≦s）に
対して、互いに素なs個の整数g₁,g₂,...,g_S (ｒ≦ｓ）
を作成し、g_iを受信者iの秘密情報として予め受信者ｉ
に配布する。

【０００８】（２）暗号化処理：多重化すべきs個の情
報系列をM₁,M₂,...,M_Sとする。送信者は、多重化送信文
Fを，

【０００９】

【数５１】

【００１０】により計算し、Fを同報送信する。ただ
し、G,G_i,A_iは、

【００１１】

【数５２】

【００１２】であり、A_iは、上式を満たす最小の整数で
ある。

【００１３】（３）復号化処理：受信者iは、Fからg_iを
用いて、

【００１４】

【数５３】

【００１５】によりＭ_iを分離化する。

【００１６】次に、文献「満保他：効率的な同報暗号通
信方式，信学技法ISEC93-34（1993-10）」に記載の方式
について、説明する。

【００１７】（１）鍵生成処理：信頼できるセンタは、
秘密情報として、

【００１８】

【数５４】

【００１９】を作成し、公開情報として、

【００２０】

【数５５】

【００２１】を作成する。

【００２２】次に、センタは、σ∈Sに対して，

【００２３】

【数５６】

【００２４】を満たすＳσを計算し、受信者Ｕσの秘密
情報として配布する。ただし、集合S=｛f｜1対1写像f:A
={1,2,...,k}→B={1,2,...,m}, k＜m}とする。

【００２５】（２）鍵配送処理：送信者は、整数rをラ
ンダムに選び、

【００２６】

【数５７】

【００２７】なる共通鍵Kを受信者との間で共有するこ
とを目的として、

【００２８】

【数５８】

【００２９】を満たすz_iを計算し、z_i (1≦i≦m)を同報
送信する。

【００３０】受信者Ｕσは、

【００３１】

【数５９】

【００３２】を用いて、共通鍵Kを計算する。

【００３３】

【発明が解決しようとする課題】上記の中国人の剰余定
理を用いた多重化方法を利用した鍵配送などでは、受信
者数に比例して鍵配送データの長さが長くなる。このこ
とは、衛星放送サービスのように数百万人以上の多くの
受信者を対象とする場合には、効率上問題となる。

【００３４】これに対し、上記文献「満保他：効率的な
同報暗号通信方式，信学技法ISEC93-34（1993-10）」に
記載の方法によれば、受信者数が大きい場合であっても
鍵配送データの長さを短くできる。しかしながら、この
方法では、適当な数の受信者が結託し互いの秘密情報を
出し合うことで、他受信者の秘密情報を計算できるとい
う問題（このことについては、文献「西岡：同報暗号通
信における鍵配送方式に関する考察，信学技法ISEC96-4
8（1996-11）」にて報告されている）がある。また、任
意の受信者集合に属する受信者のみと鍵共有を行なうこ
とができないという問題もある。

【００３５】本発明は、上記事情に鑑みてなされたもの
であり、以下に挙げる特徴を有する鍵配送方法および装
置を提供することを主目的とする。

【００３６】（１）各受信者がそれぞれ個別の鍵情報を
所持して、鍵の共有を行う。

【００３７】（２）受信者数が大きい場合であっても、
鍵配送データの長さを短くすることができる。

【００３８】（３）適当な数の受信者が結託して互いの
秘密情報を出し合った場合でも、他受信者の鍵情報およ
び鍵作成者の秘密情報を計算することを困難にする。

【００３９】（４）任意の受信者集合に属する受信者の
みと鍵共有を行なうことができる。

【００４０】

【課題を解決するための手段】上記課題を解決するため
に、本発明は以下の構成を採用する。

【００４１】１．準備処理鍵作成者の装置において、当
該鍵作成者の秘密情報からなる有限集合A A={s(ij)|1≦i≦m,1≦j≦n｝および、集合Vj Vj={(X1，...，Xm)|fj(X1,...,Xm, s(1j),...,s(mj))=
0} (1≦j≦n) （ただし、fjは集合{(z1,...,z2m)|ziは整数}から集合W
j （∋0）への適当な写像）を作成する。

【００４２】次に、(r(x,ij)) (1≦i≦m) ∈Vj (1≦j≦
n)をランダムに選び、鍵利用者xの秘密鍵として、 s(x,i)=r(x,γ(i)) (1≦i≦mn）（ただし、γは集合{1,2,…,mn}から集合{ij|1≦i≦m,1
≦j≦n}への１対1写像で、鍵作成者の秘密とする）を求
め、これを配布する。

【００４３】２．鍵配送処理鍵作成者の装置において、
当該鍵作成者の秘密情報s(ij)に対応する情報として、 u(ij) (1≦i≦m,1≦j≦n）を作成し、 y(i)=u(γ(i)) (1≦i≦mn）とする。

【００４４】次に、鍵利用者xの秘密鍵s(x,i)を用い
て、当該鍵利用者xの識別情報dxを計算し、y(1),...,y
(mn)と識別情報dxとを、鍵利用者xに送信する。

【００４５】これを受けて、鍵利用者xの装置におい
て、適当な関数hを用いて、 K=h(s(x,1),...,s(x,mn), y(1),…,y(mn), dx) により、鍵作成者と共有する共通鍵Kを計算する。

【００４６】ここで、２．鍵配送処理として、鍵作成者
の装置において、乱数ｒを選び、適当な関数ｇにより、 z(i)=g(y(i),r) (1≦i≦mn) を計算し、z(1),...,z(mn)を、鍵利用者xに送信し、鍵
利用者xの装置において、適当な関数hを用いて、 K=h(s(x,1),...,s(x,mn), ｚ(1),…,ｚ(mn), dx) により、鍵作成者と共有する共通鍵Kを計算するように
してもよい。

【００４７】このようにすることで、乱数rを変えるこ
とで、共有鍵Kを変更することが可能となる。

【００４８】以下に、本発明の実現方法の一例について
説明する。

【００４９】１．準備処理鍵作成者の装置において、

【００５０】

【数６０】

【００５１】であるとして、鍵作成者の秘密情報の集合
KSと公開情報の集合KP（集合KPは有限アーベル（乗法）
群Ｇを決定する要素を含む）とを作成する（ただし、γ
∈{γ｜１対１写像γ：Ｃ={1,2,...,mn}→Ｄ={ij｜１≦
ｉ≦m,１≦j≦n}}であり、ord_G(g)は、

【００５２】

【数６１】

【００５３】なる最小の正整数ｘを表わす）。

【００５４】次に、整数r(x,ij)（１≦ｉ≦m,１≦j≦
n）をランダムに選び、s(x,i)=r(x,γ(i)) (１≦ｉ≦m
n）に対して、(s(x,i)) (1≦i≦mn)を、鍵利用者xの秘
密鍵として配布する。

【００５５】２．鍵配送処理鍵作成者の装置において、整数ξ_Fをランダムに選び、

【００５６】

【数６２】

【００５７】を満たす鍵Kを、鍵利用者全体の集合のう
ちの任意の部分集合Fに属する鍵利用者とのみ共有する
ことを目的に、

【００５８】

【数６３】

【００５９】から、同報通信データとして、

【００６０】

【数６４】

【００６１】を満たすy(i)、および、

【００６２】

【数６５】

【００６３】を満たす整数d(x,ξ_F)を計算し、前記同報
通信データy(i)、d(x,ξ_F)を同報送信する。

【００６４】これを受けて、鍵利用者x（ｘ∈F）の装置
において、前記同報通信データy(i)、d(x,ξ_F)と鍵作成
者によって配布された自身（鍵利用者x）の鍵情報(s(x,
i)) (1≦i≦mn)とから、

【００６５】

【数６６】

【００６６】（ただし、f_i (1≦i≦mn)は鍵作成者によ
り公開された関数で、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)
とする）により、共通鍵Kを計算する。

【００６７】ここで、鍵作成者および鍵利用者x間で共
有する鍵Kを変更する場合、以下の処理を行う。

【００６８】２．鍵配送処理として、鍵作成者の装置に
おいて、整数ζをランダムに選び、

【００６９】

【数６７】

【００７０】を満たす鍵Kを、鍵利用者全体の集合に含
まれる任意の部分集合Fに属する鍵利用者とのみ共有す
ることを目的に、同報通信データとして、

【００７１】

【数６８】

【００７２】を満たすz(i)を計算して、前記同報通信デ
ータz(i)を同報送信し、鍵利用者x（ｘ∈F）の装置にお
いて、前記同報通信データz(i)と予め同報送信されたd
(x,ξ_F)と鍵作成者によって配布された自身（鍵利用者
x）の鍵情報(s(x,i)) (1≦i≦mn)とから、

【００７３】

【数６９】

【００７４】により、共通鍵Kを計算する。

【００７５】上記説明した実現方法の一例をさらに具体
的に説明すると、以下のとおりである。

【００７６】１．準備処理鍵作成者の装置において、鍵作成者の秘密情報として、

【００７７】

【数７０】

【００７８】を作成し、公開情報として、

【００７９】

【数７１】

【００８０】を作成する（ただし、0＜g₁, g₂＜Nであ
り、ord_G(g)は、

【００８１】

【数７２】

【００８２】なる最小の正整数xを表わす）。

【００８３】次に、整数r(x,ij) (１≦ｉ≦m,１≦j≦
2）をランダムに選び、s(x,i)=r(x,γ(i))（１≦ｉ≦2
m）に対して、(s(x,i)) (1≦i≦2m)を、鍵利用者xの鍵
情報として配布する。

【００８４】２．鍵配送処理鍵作成者の装置において、整数ξ_Fをランダムに選び、

【００８５】

【数７３】

【００８６】を満たす共通鍵Kを、鍵利用者全体の集合
のうちの任意の部分集合Fに属する鍵利用者とのみ共有
することを目的に、

【００８７】

【数７４】

【００８８】から、同報通信データとして、

【００８９】

【数７５】

【００９０】を満たすy(i)、および、

【００９１】

【数７６】

【００９２】を満たす整数d(x,ξ_F)を計算し、前記同報
通信データy(i)、d(x,ξ_F)を同報送信する。

【００９３】これを受けて、鍵利用者x (x∈F) の装置
において、前記同報通信データy(i)、d(x,ξ_F)と鍵作成
者によって配布された自身（鍵利用者x）の鍵情報(s(x,
i)) (1≦i≦2m)とから、

【００９４】

【数７７】

【００９５】（ただし、f_i (1≦i≦2m）は鍵作成者によ
り公開された関数、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)と
する）により、共通鍵Kを計算する。

【００９６】ここで、鍵作成者および鍵利用者x間で共
有する鍵Kを変更する場合、以下の処理を行う。

【００９７】２．鍵配送処理として、鍵作成者の装置に
おいて、整数ζをランダムに選び、

【００９８】

【数７８】

【００９９】を満たす共通鍵Kを、鍵利用者全体の集合
に含まれる任意の部分集合Fに属する鍵利用者とのみ共
有することを目的に、同報通信データとして、

【０１００】

【数７９】

【０１０１】を満たすz(i)を計算して前記同報通信デー
タz(i)を同報送信し、鍵利用者x（ｘ∈F）の装置におい
て、前記同報通信データz(i)と予め同報送信されたd(x,
ξ_F)と鍵作成者によって配布された自身（鍵利用者x）
の鍵情報(s(x,i)) (1≦i≦2m)とから、

【０１０２】

【数８０】

【０１０３】により、共通鍵Kを計算する。

【０１０４】

【発明の実施の形態】以下に、本発明の実施の形態につ
いて説明する。

【０１０５】なお、以下に説明する各実施の形態におい
て、正整数Nおよび正整数gに対して、ord_N(g)=mとは、

【０１０６】

【数８１】

【０１０７】となる最小の正整数xがmであることを表わ
す。

【０１０８】まず、本発明の第一実施形態として、同報
暗号通信のための鍵配送方法を、衛星放送を用いた情報
配信サービスシステムに適用した場合について説明す
る。すなわち、放送局が衛星を用いて同報暗号通信した
マルチメディア情報などの情報（有償データを含む）
を、視聴資格のある受信者（あるいは、対価を支払うこ
とを了承した受信者）のみが復号化できるようにするた
めに、放送局および受信者間で鍵共有を行なうための鍵
配送方法について説明する。

【０１０９】図１は、本発明の第一実施形態が適用され
た鍵配送システムの概略構成を示している。図１に示す
ように、本実施形態のシステムは、鍵作成者の装置であ
る放送局側装置１００と、鍵利用者の装置である複数の
受信者側装置２００とで構成されている。放送局側装置
１００および複数の受信者側装置２００は、通信回線３
００により互いに接続されている。放送局側装置１００
は、通信衛星５００を用いて、マルチメディア情報など
の情報（有償データを含む）を同報暗号通信する。受信
者側装置２００は、放送局側装置１００により同報暗号
通信されたデータを、受信者および放送局間で共有して
いる鍵を用いて復号化する。

【０１１０】図２は、図１に示す放送局側装置１００の
概略構成を示している。図２に示すように、放送局側装
置１００は、乱数生成器１０１、素数生成器１０２、演
算装置１０３、べき乗算器１０４、剰余演算器１０５、
鍵生成器１０６、暗復号化装置１０７、通信装置１０
８、認証装置１０９、課金装置１１０、そして、メモリ
１１１を備えている。ここで、乱数生成器１０１、素数
生成器１０２、演算装置１０３、べき乗算器１０４、剰
余演算器１０５、鍵生成器１０６、暗復号化装置１０
７、認証装置１０９、および、課金装置１１０は、論理
回路を組み合わせるなどして、ハードウエアとして設け
てもよいし、あるいは、情報処理装置において、所定の
プログラムを実行することで実現されるようにしてもよ
い。この所定のプログラムはＣＤ−ＲＯＭなどの記憶媒
体に記憶しておくことも可能である。

【０１１１】図３は、図１に示す受信側装置２００の概
略構成を示している。図３に示すように、受信側装置２
００は、メモリ２０１、べき乗算器２０２、剰余演算器
２０３、演算装置２０４、認証装置２０５、通信装置２
０６、鍵生成器２０７、暗復号化装置２０８、そして、
ＩＣカード連結装置２０９を備えている。ここで、べき
乗算器２０２、剰余演算器２０３、演算装置２０４、認
証装置２０５、鍵生成器２０７、および、暗復号化装置
２０８は、論理回路を組み合わせるなどして、ハードウ
エアとして設けてもよいし、あるいは、情報処理装置に
おいて、所定のプログラムを実行することで実現される
ようにしてもよい。この所定のプログラムは、ＣＤ−Ｒ
ＯＭなどの記憶媒体に記憶しておくことも可能である。

【０１１２】上記構成の本実施形態が適用された鍵配送
システムの動作について、図４を参照して説明する。図
４は、図１に示す鍵配送システムにおける情報の流れを
説明するための図である。

【０１１３】１．準備処理放送局側装置１００において、以下の処理を行う。

【０１１４】演算装置１０３は、放送局の信頼できる鍵
作成者の指示にしたがい、乱数生成装置１０１、素数生
成装置１０２、べき乗算器１０４、および剰余演算器１
０５の協力を得て、次の情報を作成する。

【０１１５】秘密情報：

【０１１６】

【数８２】

【０１１７】公開情報：

【０１１８】

【数８３】

【０１１９】作成された秘密情報はメモリ１１１に格納
される。一方、公開情報は、受信者の秘密情報と共に配
布するか、あるいは、同報送信データに含めて受信者に
配布するなどの方法により公開される。

【０１２０】次に、演算装置１０３は、乱数生成器１０
１を用いて、整数r(x,ij)（１≦ｉ≦m,１≦j≦2）をラ
ンダムに選び、s(x,i)=r(x,γ(i)) (１≦ｉ≦2m）に対
して、(s(x,i)) (1≦i≦2m)を、鍵利用者xの秘密鍵とす
る。この受信者xの秘密鍵は、たとえば、フローピーデ
ィスク、ＩＣカードなどの記憶媒体に記憶して、受信者
xに配布される。

【０１２１】２．鍵配送処理まず、放送局側装置１００において、以下の処理を行
う。

【０１２２】鍵生成器１０６は、乱数生成器１０１を用
いて、整数ξ_Fをランダムに選ぶ。次に、べき乗算器１
０４、剰余演算器１０５、および、演算装置１０３の協
力を得て、

【０１２３】

【数８４】

【０１２４】を満たす共通鍵Kを生成する。そして、生
成した共通鍵Kを、鍵利用者全体の集合のうちの任意の
部分集合Fに属する鍵利用者とのみ共有することを目的
に、

【０１２５】

【数８５】

【０１２６】から、同報通信データとして、

【０１２７】

【数８６】

【０１２８】を満たすy(i)、および、

【０１２９】

【数８７】

【０１３０】を満たす整数d(x,ξ_F)を計算する。

【０１３１】暗復号化装置１０７は、マルチメディア情
報などの送信データPを、上記の鍵Kを用いて暗号化し、
暗号文Cを作成する。

【０１３２】通信装置１０８は、作成した同報通信デー
タy(i) (1≦i≦2m)、d(x,ξ_F)を、上記従来の技術で説
明した中国人の剰余定理を用いた多重化方法などにより
多重化して、多重化データWを作成する。そして、作成
した多重化データWを、通信衛星５００を介して、受信
者側装置２００に同報送信する。

【０１３３】また、暗復号化装置１０７で作成した暗号
文Cを、通信衛星５００を介して、受信者側装置２００
に同報送信する。

【０１３４】一方、受信者x（ｘ∈F）の受信者側装置２
００では、以下の処理を行う。

【０１３５】通信装置２０６は、通信衛星５００を介し
て同報送信された多重化データWおよび暗号文Cを受信す
る。このうち、多重化データWについては、分離化してy
(i)(1≦i≦2m）、d(x,ξ_F)を得る。

【０１３６】鍵生成器２０７は、べき乗算器２０２、剰
余演算器２０３、および演算装置２０４の協力を得て、
通信装置２０６で分離化されたy(i) (1≦i≦2m）、d(x,
ξ_F)と、放送局により配布され、予めメモリ２０１に格
納された受信者xの秘密鍵(s(x,i)) (1≦i≦2m)とから、

【０１３７】

【数８８】

【０１３８】（ただし、f_i (1≦i≦２m)は鍵作成者によ
り公開された関数で、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)
とする）により、共通鍵Kを計算する。

【０１３９】暗復号化装置２０８は、通信装置２０６に
より受信した暗号文Cを、鍵生成器２０７で生成された
共通鍵Kを用いて復号化し、元の送信データPを得る。

【０１４０】上記従来の技術で説明したように、文献
「満保他：効率的な同報暗号通信方式，信学技法ISEC93
-34（1993-10）」に記載の方式では、文献「西岡：同報
暗号通信における鍵配送方式に関する考察，信学技法IS
EC96-48（1996-11）」で報告されているように、適当な
数の受信者が結託して、互いに自己の秘密情報を出し合
って、所定の連立方程式を解くことにより、他の受信者
の秘密情報を計算することができる。つまり、受信者の
結託攻撃が有効になる。

【０１４１】これに対し、本実施形態によれば、受信者
の秘密情報を計算するのに用いたγを、放送局の秘密情
報として、受信者に対して秘密にしながら、共通鍵Kの
共有を行うことができるので、受信者の結託攻撃を有効
とする情報を知らせることなく、放送局および受信者間
で鍵共有を行うことができる。このため、受信者の秘密
情報が第三者に漏れる可能性をさらに低くすることがで
きる。

【０１４２】なお、本実施形態では、送信データPに対
応して乱数生成器１０１で生成するξ_Fの値を変えるこ
とにより、送信データPの識別、すなわち、送信データP
の内容に応じてその暗号文Cを復号するための共通鍵Kを
設定することが可能である。

【０１４３】また、本実施形態において、送信データP
に対する共通鍵Kを変更する場合、上記の２．鍵配送処
理において、以下の処理をさらに行うことで実現可能で
ある。

【０１４４】まず、放送局側装置１００において、以下
の処理をさらに行う。

【０１４５】鍵生成器１０６は、乱数生成器１０１を用
いて、整数ζをランダムに選ぶ。次に、べき乗算器１０
４、剰余演算器１０５、および、演算装置１０３の協力
を得て、

【０１４６】

【数８９】

【０１４７】を満たす共通鍵Kを生成する。そして、生
成した共通鍵Kを、鍵利用者全体の集合のうちの任意の
部分集合Fに属する鍵利用者とのみ共有することを目的
に、同報通信データとして、

【０１４８】

【数９０】

【０１４９】を満たすz(i)を計算する。

【０１５０】通信装置１０８は、作成した同報通信デー
タz(i) (1≦i≦2m)を、上記従来の技術で説明した中国
人の剰余定理を用いた多重化方法などにより多重化し
て、通信衛星５００を介し同報送信する。

【０１５１】一方、受信者x（ｘ∈F）の受信者側装置２
００では、以下の処理を行う。

【０１５２】通信装置２０６は、通信衛星５００を介し
て同報送信された多重化データを受信し、これを分離化
して、z(i) (1≦i≦2m）を得る。

【０１５３】鍵生成器２０７は、べき乗算器２０２、剰
余演算器２０３、および演算装置２０４の協力を得て、
通信装置２０６で分離化されたz(i) (1≦i≦2m）と、先
に取得したd(x,ξ_F)と、放送局により配布されメモリ２
０１に格納された受信者xの秘密鍵(s(x,i)) (1≦i≦2m)
とから、

【０１５４】

【数９１】

【０１５５】（ただし、f_i (1≦i≦２m)は鍵作成者によ
り公開された関数で、f_i(s(x,i),ｚ(i))=c(x,γ(i),
ξ_F)とする）により、共通鍵Kを計算する。

【０１５６】このようにすることで、整数ζを変えるこ
とにより、共有鍵Kを変更することができる。

【０１５７】以上、本発明の第一実施形態について説明
した。

【０１５８】以下に、本発明の第二実施形態について説
明する。

【０１５９】本実施形態では、上記の第一実施形態にお
いて、送信データPが有償である場合における受信者に
対する課金方法について説明する。ここでは、第一実施
形態の２．鍵配送処理において、放送局側装置１００
は、同報通信データy(i) (1≦i≦2m)、d(x,ξ_F)を多重
化して同報送信する代わりに、y(i) (1≦i≦2m)のみを
多重化して同報送信するようにしている。そして、d(x,
ξ_F)については、放送局および受信者間で認証処理を行
い、認証された受信者の受信者側装置２００に対しての
み、通信回線３００を介して送信するようにしている。

【０１６０】以下、放送局および受信者間で行われる認
証処理について説明する。

【０１６１】まず、放送局側装置１００は、鍵生成器１
０６を用いて、受信者xの秘密鍵(s(x,i)) (1≦i≦2m)に
対応する公開鍵p(x)を、第一実施形態の２．鍵配送処理
に先立って予め作成し、メモリ１０９に格納する。

【０１６２】受信者x（ｘ∈F）の受信者側装置２００
は、放送局側装置１００が同報送信した送信データPの
暗号文Cを復号する権限を得ることを目的として、通信
装置２０６により、通信回線３００を介して、放送局側
装置１００（あるいは、それに付随する装置）にアクセ
スする。

【０１６３】放送局側装置１００は、受信者xの受信者
側装置２００からアクセスを受けると、乱数生成器１０
１により乱数rを生成する。そして、通信装置１０８に
より、通信回線３００を介して、受信者xの受信者側装
置２００に送信する。

【０１６４】受信者xの受信者側装置２００は、放送局
側装置１００から乱数rを受け取ると、認証装置２０５
により、放送局により予め配布されメモリ２０１に格納
された受信者xの秘密鍵(s(x,i)) (1≦i≦2m)を用いて、
乱数rに対する署名sgn_X(r)を作成する。そして、作成し
た署名sgn_X(r)を、通信装置２０６により、通信回線３
００を介して、放送局側装置１００に送信する。

【０１６５】ここで、署名を行なう具体的な方法につい
ては、多くの方法が知られている。たとえば、文献「R.
L.Rivest,A.Shamir,L.Adleman.:A method for obtainin
g digital signatures and publickey cryptosystems,C
ommun. of the ACM, Vol.21,No.2, pp.120-126, 198
7.」に掲載のＲＳＡ暗号を用いる方法や、文献「Propos
ed Federal Information Processing Standard (DSS),
Federal Register, v.56,n.169,30,pp.42980-42982 (1
991)」に記載のＤＳＡによる方法などがある。

【０１６６】放送局側装置１００は、受信者xの受信者
側装置２００から署名sgn_X(r)を受けると、認証装置１
０９により、メモリ１０９に格納しておいた受信者xの
公開鍵p(x)を用いて、署名sgn_X(r)の正当性を確認す
る。そして、正当性が確認された場合にのみ、d(x,ξ_F)
を、通信回線３００を介して、受信者xの受信者側装置
２００に送信する。また、課金装置１１０により、受信
者xに対する課金を行う。

【０１６７】本実施形態では、上述したように、受信者
の結託攻撃を有効とする情報を知らせることなく、放送
局および受信者間で鍵共有を行うことができる。したが
って、第三者が送信データPの暗号文Cを復号化するため
には、すなわち、共通鍵Kを得るためには、受信者xから
受信者xの秘密鍵(s(x,i)) (1≦i≦2m)を取得する（すな
わち、横流ししてもらう）しかないと推測される。

【０１６８】本実施形態では、受信者xに対して、秘密
鍵(s(x,i)) (1≦i≦2m)を用いて認証した場合にのみ、
送信データPの暗号文Cを復号化する権限を与えるように
している。したがって、受信者xから秘密鍵(s(x,i)) (1
≦i≦2m)を横流ししてもらった第三者が、秘密鍵(s(x,
i)) (1≦i≦2m)を用いて認証処理を行い、受信者xにな
りすまして送信データPの暗号文Cを復号化する権限を受
けた場合、送信データPについての課金は、横流しをし
た受信者xに対して行われることになる。このように、
横流しを行なった受信者xに不利益が及ぶようにシステ
ムを構築することにより、不正な受信者が、送信データ
を見る権限を持たない第三者に自身の秘密情報を横流し
して、不正に視聴権限を譲渡することを防止することが
できる。

【０１６９】以上、本発明の第二実施形態について説明
した。

【０１７０】次に、本発明の第三実施形態について説明
する。

【０１７１】本実施形態では、上記の第一実施形態にお
いて、受信者xが、放送局から配布された、自身の秘密
鍵(s(x,i)) (1≦i≦2m)を格納したＩＣカードを利用す
ることで、自身の秘密鍵(s(x,i)) (1≦i≦2m)が第三者
に漏れるのをより効率的に防ぎながら、放送局との間で
共有する共通鍵Kを計算する方法について説明する。

【０１７２】図５は、本発明の第三実施形態で用いるＩ
Ｃカード４００の概略構成を示す。

【０１７３】図５に示すように、ＩＣカード４００は、
べき乗算器４０１、メモリ４０２、演算装置４０３、剰
余演算器４０４、認証情報作成装置４０５、そして、入
出力装置４０６を備えている。ここで、べき乗算器４０
１、演算装置４０３、剰余演算器４０４、および認証情
報作成装置４０５は、論理回路を組み合わせるなどし
て、ハードウエアとして設けてもよいし、あるいは、Ｉ
Ｃカードが備えるＣＰＵにおいて、所定のプログラムを
実行することで実現されるようにしてもよい。

【０１７４】本実施形態の動作は、受信者側装置２００
で行われる共通鍵Kの算出処理が異なる点を除いて、第
一実施形態のものと基本的に同じである。

【０１７５】本実施形態では、第一実施形態の２．鍵配
送処理において、ＩＣカード４００が受信者xの受信者
側装置２００のＩＣカード連結装置２０９に差し込まれ
ると、ＩＣカード４００内の演算装置４０３は、べき乗
算器４０１および剰余演算器４０４の協力を得て、予め
メモリ４０２に格納された受信者xの秘密鍵(s(x,i))(1
≦i≦2m)と、受信者側装置２００の通信装置２０６によ
り多重化データWから分離化されたｙ(i)あるいはz(i)と
を基に、

【０１７６】

【数９２】

【０１７７】あるいは、

【０１７８】

【数９３】

【０１７９】を満たすK(x,i)を計算する。求めた結果K
(x,i)は、入出力装置４０６により、受信者側装置２０
０のＩＣカード連結装置２０９を介して、当該装置２０
０のメモリ２０１に格納される。

【０１８０】受信者xの受信者側装置２００において、
鍵生成器１０６は、剰余演算器２０３および演算装置２
０４の協力を得て、通信装置２０６により多重化データ
Wから分離化されたd(x,ξ_F)と、ＩＣカード連結装置２
０９を介してＩＣカード４００から送られてきたK(x,i)
とを基に、

【０１８１】

【数９４】

【０１８２】あるいは、

【０１８３】

【数９５】

【０１８４】により、共通鍵Kを計算する。

【０１８５】なお、本実施形態において、上記の第二実
施形態と同様の認証処理を行う場合、ＩＣカード４００
内の認証情報作成装置４０５により、メモリ４０２に格
納された受信者xの秘密鍵(s(x,i)) (1≦i≦2m)を用い
て、受信者側装置２００が放送局側装置１００から受け
取った乱数rに対する署名sgn_X(r)を作成する。そして、
作成した署名sgn_X(r)を、受信者側装置２００の通信装
置２０６により、通信回線３００を介して、放送局側装
置１００に送信する。その後の認証処理は、放送局側装
置１００の認証装置１０９および受信者側装置２００の
認証装置２０５間において、上記の第二実施形態と同じ
要領で行えばよい。

【０１８６】以上、本発明の各実施形態について説明し
た。なお、本発明は、上記説明した各実施形態に限定さ
れるものではなく、その要旨の範囲内で数々の変形が可
能である。

【０１８７】たとえば、上記の各実施形態において、共
通鍵Kを計算するのに用いるf_i(s(x,i),y(i))およびf_i(s
(x,i),z(i))の代わりとして、放送局および受信者xの双
方が知ることができ、ξ_Fの値に応じて変化し、かつ、
受信者xに固有の値を用いてもよい。たとえば、放送局
側装置１００の乱数生成器１０１で生成され、通信装置
１０８により送信された乱数r_i (1≦i≦2m)を用いて作
成したf_i(r_i,ID(x))を用いてもよい（ただし、ID(x)は
受信者xのID情報）。あるいは、受信者xがランダムに選
んで公開した値を用いてもよい。

【０１８８】また、共通鍵Kの配送方法も、上記の各実
施形態に挙げられた数式に限定されるものではない。本
発明は、以下の処理を実行するものであればよい。

【０１８９】１．準備処理放送局側装置１００において、以下の処理を行う。

【０１９０】放送局の秘密情報からなる有限集合A A={s(ij)|1≦i≦m,1≦j≦n｝および、集合Vj Vj={(X1，...，Xm)|fj(X1,...,Xm, s(1j),...,s(mj))=
0} (1≦j≦n) （ただし、fjは集合{(z1,...,z2m)|ziは整数}から集合W
j （∋0）への適当な写像）を作成する。

【０１９１】次に、(r(x,ij)) (1≦i≦m) ∈Vj (1≦j≦
n)をランダムに選び、受信者xの秘密鍵として、 s(x,i)=r(x,γ(i)) (1≦i≦mn）（ただし、γは集合{1,2,…,mn}から集合{ij|1≦i≦m,1
≦j≦n}への１対1写像で、鍵作成者の秘密とする）を求
め、これを配布する。

【０１９２】２．鍵配送処理放送局側装置１００において、以下の処理を行う。

【０１９３】放送局の秘密情報s(ij)に対応する情報と
して、 u(ij) (1≦i≦m,1≦j≦n）を作成し、 y(i)=u(γ(i)) (1≦i≦mn）とする。

【０１９４】次に、受信者xの秘密鍵s(x,i)を用いて、
当該受信者xの識別情報dxを計算し、y(1),...,y(mn)と
識別情報dxとを、受信者xに送信する。

【０１９５】これを受けて、鍵利用者xの装置におい
て、適当な関数hを用いて、 K=h(s(x,1),...,s(x,mn), y(1),…,y(mn), dx) により、鍵作成者と共有する共通鍵Kを計算する。

【０１９６】

【発明の効果】以上説明したように、本発明によれば、
同報暗号通信において受信者（鍵利用者）数が大きい場
合であっても鍵配送データ（同報送信データ）の長さを
短く（一定）することができる。

【０１９７】また、不正な受信者が互いの秘密情報を出
し合って他の受信者の秘密情報を計算するといった結託
攻撃を困難にすることができる。これにより、効率よく
かつ安全に鍵配送を行うことができる。

【図面の簡単な説明】

【図１】本発明の第一実施形態が適用された鍵配送シス
テムの概略構成図である。

【図２】図１に示す放送局側装置１００の概略構成図で
ある。

【図３】図１に示す受信者側装置２００の概略構成図で
ある。

【図４】図１に示す鍵配送システムにおける情報の流れ
を説明するための図である。

【図５】本発明の第三実施形態で用いるＩＣカード４０
０の概略構成図である。

【符号の説明】

１００放送局側装置１０１乱数生成器１０２素数生成器１０３、２０４、４０３演算装置１０４、２０２、４０１べき乗算器１０５、２０３、４０４剰余演算器１０６、２０７鍵生成器１０７、２０８暗復号化装置１０８、２０６通信装置１０９、２０５認証装置１１０課金装置１１１、２０１、４０２メモリ２００受信者側装置２０９ＩＣカード連結装置４００ＩＣカード４０５認証情報作成装置４０６入出力装置

Claims

【特許請求の範囲】

【請求項１】複数の鍵利用者が鍵作成者によって予め作
成された個々の鍵情報を利用して、暗号通信を行うため
の共通の鍵情報を鍵作成者と共有するための鍵配送方法
であって、１．準備処理として、鍵作成者の装置において、当該鍵作成者の秘密情報からなる有限集合A A={s(ij)|1≦i≦m,1≦j≦n｝および、集合Vj Vj={(X1，...，Xm)|fj(X1,...,Xm, s(1j),...,s(mj))=
0} (1≦j≦n) （ただし、fjは集合{(z1,...,z2m)|ziは整数}から集合W
j （∋0）への適当な写像）を作成するステップと、 (r(x,ij)) (1≦i≦m) ∈Vj (1≦j≦n)をランダムに選
び、鍵利用者xの秘密鍵として、 s(x,i)=r(x,γ(i)) (1≦i≦mn）（ただし、γは集合{1,2,…,mn}から集合{ij|1≦i≦m,1
≦j≦n}への１対1写像で、鍵作成者の秘密とする）を求
め、これを配布するステップと、を備え、２．鍵配送処理として、鍵作成者の装置において、当該鍵作成者の秘密情報s(ij)に対応する情報として、 u(ij) (1≦i≦m,1≦j≦n）を作成し、 y(i)=u(γ(i)) (1≦i≦mn）とするステップと、鍵利用者xの秘密鍵s(x,i)を用いて、当該鍵利用者xの識
別情報dxを計算するステップと、 y(1),...,y(mn)と識別情報dxとを、鍵利用者xに送信す
るステップと、を備え、鍵利用者xの装置において、適当な関数hを用いて、 K=h(s(x,1),...,s(x,mn), y(1),…,y(mn), dx) により、鍵作成者と共有する共通鍵Kを計算するステッ
プと、を備えることを特徴とする鍵配送方法。
【請求項２】請求項１記載の鍵配送方法であって、２．鍵配送処理として、鍵作成者の装置において、乱数ｒを選び、適当な関数ｇにより、 z(i)=g(y(i),r) (1≦i≦mn) を計算するステップと、 z(1),...,z(mn)を、鍵利用者xに送信するステップと、
をさらに備え、鍵利用者xの装置において、適当な関数hを用いて、 K=h(s(x,1),...,s(x,mn), ｚ(1),…,ｚ(mn), dx) により、鍵作成者と共有する共通鍵Kを計算するステッ
プをさらに備えることを特徴とする鍵配送方法。
【請求項３】複数の鍵利用者が鍵作成者によって予め作
成された個々の鍵情報を利用して、暗号通信を行うため
の共通の鍵情報を鍵作成者と共有するための鍵配送方法
であって、１．準備処理として、鍵作成者の装置において、【数１】であるとして、鍵作成者の秘密情報の集合KSと公開情報
の集合KP（集合KPは有限アーベル（乗法）群Ｇを決定す
る要素を含む）とを作成するステップ（ただし、γ∈
{γ｜１対１写像γ：Ｃ={1,2,...,mn}→Ｄ={ij｜１≦ｉ
≦m,１≦j≦n}}であり、ord_G(g)は、【数２】なる最小の正整数ｘを表わす）と、整数r(x,ij)（１≦ｉ≦m,１≦j≦n）をランダムに選ぶ
ステップと、 s(x,i)=r(x,γ(i)) (１≦ｉ≦mn）に対して、(s(x,i))
(1≦i≦mn)を、鍵利用者xの秘密鍵として配布するステ
ップと、を備え、２．鍵配送処理として、鍵作成者の装置において、整数ξ_Fをランダムに選び、【数３】を満たす鍵Kを、鍵利用者全体の集合のうちの任意の部
分集合Fに属する鍵利用者とのみ共有することを目的
に、【数４】から、同報通信データとして、【数５】を満たすy(i)、および、【数６】を満たす整数d(x,ξ_F)を計算するステップと、前記同報通信データy(i)、d(x,ξ_F)を同報送信するステ
ップと、を備え、鍵利用者x（ｘ∈F）の装置において、前記同報通信データy(i)、d(x,ξ_F)と鍵作成者によって
配布された自身（鍵利用者x）の鍵情報(s(x,i)) (1≦i
≦mn)とから、【数７】（ただし、f_i (1≦i≦mn)は鍵作成者により公開された
関数で、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)とする）によ
り、共通鍵Kを計算するステップを備えることを特徴と
する鍵配送方法。
【請求項４】請求項３記載の鍵配送方法であって、２．鍵配送処理として、鍵作成者の装置において、整数ζをランダムに選び、【数８】を満たす鍵Kを、鍵利用者全体の集合に含まれる任意の
部分集合Fに属する鍵利用者とのみ共有することを目的
に、同報通信データとして、【数９】を満たすz(i)を計算するステップと、前記同報通信データz(i)を同報送信するステップと、を
さらに備え、鍵利用者x（ｘ∈F）の装置において、前記同報通信データz(i)と予め同報送信されたd(x,ξ_F)
と鍵作成者によって配布された自身（鍵利用者x）の鍵
情報(s(x,i)) (1≦i≦mn)とから、【数１０】により、共通鍵Kを計算するステップをさらに備えるこ
とを特徴とする鍵配送方法。
【請求項５】請求項４記載の鍵配送方法であって、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i)) (1≦i≦mn）の
代わりとして、鍵作成者および鍵利用者xの双方が知る
ことができ、ξ_Fの値に応じて変化し、かつ、鍵利用者x
に固有の値を用いることを特徴とする鍵配送方法。
【請求項６】請求項５記載の鍵配送方法であって、鍵作成者の装置において、乱数r_i (1≦i≦mn)を送信するステップをさらに備え、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i))の代わりとし
て、f_i(r_i,ID(x))とする（ただし、ID(x)は鍵利用者xの
ID情報）ことを特徴とする鍵配送方法。
【請求項７】請求項５記載の鍵配送方法であって、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i))の代わりとし
て、鍵利用者xがランダムに選んで公開した値とするこ
とを特徴とする鍵配送方法。
【請求項８】請求項３、４、５、６または７記載の鍵配
送方法であって、鍵利用者xの装置において、鍵作成者の装置に対して、鍵利用者xが自身の鍵情報(s
(x,i)) (1≦i≦mn)を所持することの認証処理を行うス
テップと、前記認証が成立した場合にのみd(x,ξ_F)を受け取るステ
ップと、をさらに備えることを特徴とする暗号通信にお
ける鍵配送方法。
【請求項９】請求項８記載の鍵配送方法であって、鍵作成者の装置において、鍵利用者xの認証処理が終了したとき、あるいは、d(x,
ξ_F)を送信したときに、鍵利用者xに対して課金を行な
うステップをさらに備えることを特徴とする鍵配送方
法。
【請求項１０】複数の鍵利用者が鍵作成者によって予め
作成された個々の鍵情報を利用して、暗号通信を行うた
めの共通の鍵情報を鍵作成者と共有するための鍵配送方
法であって、１．準備処理として、鍵作成者の装置において、鍵作成者の秘密情報として、【数１１】を作成し、公開情報として、【数１２】を作成するステップ（ただし、0＜g₁, g₂＜Nであり、or
d_G(g)は、【数１３】なる最小の正整数xを表わす）と、整数r(x,ij) (１≦ｉ≦m,１≦j≦2）をランダムに選ぶ
ステップと、 s(x,i)=r(x,γ(i))（１≦ｉ≦2m）に対して、(s(x,i))
(1≦i≦2m)を、鍵利用者xの鍵情報として配布するステ
ップと、を備え、２．鍵配送処理として、鍵作成者の装置において、整数ξ_Fをランダムに選び、【数１４】を満たす共通鍵Kを、鍵利用者全体の集合のうちの任意
の部分集合Fに属する鍵利用者とのみ共有することを目
的に、【数１５】から、同報通信データとして、【数１６】を満たすy(i)、および、【数１７】を満たす整数d(x,ξ_F)を計算するステップと、前記同報通信データy(i)、d(x,ξ_F)を同報送信するステ
ップと、を備え、鍵利用者x (x∈F) の装置において、前記同報通信データy(i)、d(x,ξ_F)と鍵作成者によって
配布された自身（鍵利用者x）の鍵情報(s(x,i)) (1≦i
≦2m)とから、【数１８】（ただし、f_i (1≦i≦2m）は鍵作成者により公開された
関数、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)とする）によ
り、共通鍵Kを計算するステップを備えることを特徴と
する鍵配送方法。
【請求項１１】請求項１０記載の鍵配送方法であって、２．鍵配送処理として、鍵作成者の装置において、整数ζをランダムに選び、【数１９】を満たす共通鍵Kを、鍵利用者全体の集合に含まれる任
意の部分集合Fに属する鍵利用者とのみ共有することを
目的に、同報通信データとして、【数２０】を満たすz(i)を計算するステップと、前記同報通信データz(i)を同報送信するステップと、を
さらに備え、鍵利用者x（ｘ∈F）の装置において、前記同報通信データz(i)と予め同報送信されたd(x,ξ_F)
と鍵作成者によって配布された自身（鍵利用者x）の鍵
情報(s(x,i)) (1≦i≦2m)とから、【数２１】により、共通鍵Kを計算するステップをさらに備えるこ
とを特徴とする鍵配送方法。
【請求項１２】請求項１１記載の鍵配送方法であって、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i)) (1≦i≦2m）の
代わりとして、鍵作成者および鍵利用者xの双方が知る
ことができ、ξ_Fの値に応じて変化し、かつ、鍵利用者x
に固有の値を用いることを特徴とする鍵配送方法。
【請求項１３】請求項１２記載の鍵配送方法であって、鍵作成者の装置において、乱数r_i (1≦i≦2m)を送信するステップをさらに備え、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i))の代わりとし
て、f_i(r_i,ID(x))とする（ただし、ID(x)は鍵利用者xの
ID情報）ことを特徴とする鍵配送方法。
【請求項１４】請求項１２記載の鍵配送方法であって、 f_i(s(x,i),y(i))およびf_i(s(x,i),z(i))の代わりとし
て、鍵利用者xがランダムに選んで公開した値とするこ
とを特徴とする鍵配送方法。
【請求項１５】請求項１０、１１、１２、１３または１
４記載の鍵配送方法であって、鍵利用者xの装置において、鍵作成者の装置に対して、鍵利用者xが自身の鍵情報(s
(x,i)) (1≦i≦2m)を所持することの認証処理を行うス
テップと、前記認証が成立した場合にのみd(x,ξ_F)を受け取るステ
ップと、をさらに備えることを特徴とする鍵配送方法。
【請求項１６】請求項１５記載の鍵配送方法であって、鍵作成者の装置において、鍵利用者xの認証処理が終了したとき、あるいは、d(x,
ξ_F)を送信したときに、鍵利用者xに対して課金を行な
うステップをさらに備えることを特徴とする鍵配送方
法。
【請求項１７】請求項４、５、６、７、８、９、１１、
１２、１３、１４、１５または１６記載の鍵配送方法で
あって、 ζの値を変えることにより共有鍵Kの変更を行なうこと
を特徴とする鍵配送方法。
【請求項１８】複数の鍵利用者が鍵作成者によって予め
作成された個々の鍵情報を利用して、暗号通信を行うた
めの共通の鍵情報を鍵作成者と共有するための鍵配送プ
ログラムが記憶された記憶媒体であって、当該鍵配送プログラムは、情報処理装置に、請求項１、２、３、４、５、６、７、８、９、１０、１
１、１２、１３、１４、１５、１６または１７記載の鍵
配送方法の、鍵作成者の装置におけるステップを実行す
るものであることを特徴とする鍵配送プログラムが記憶
された記憶媒体。
【請求項１９】複数の鍵利用者が鍵作成者によって予め
作成された個々の鍵情報を利用して、暗号通信を行うた
めの共通の鍵情報を鍵作成者と共有するための鍵共有プ
ログラムが記憶された記憶媒体であって、当該鍵共有プログラムは、情報処理装置に、請求項１、２、３、４、５、６、７、８、９、１０、１
１、１２、１３、１４、１５、１６または１７記載の鍵
配送方法の、鍵利用者xの装置におけるステップを実行
するものであることを特徴とする鍵共有プログラムが記
憶された記憶媒体。
【請求項２０】鍵作成者が複数の鍵利用者との間で暗号
通信を行うための共通の鍵情報を共有するための鍵配送
装置であって、鍵作成者の秘密情報からなる有限集合A A={s(ij)|1≦i≦m,1≦j≦n｝および、集合Vj Vj={(X1，...，Xm)|fj(X1,...,Xm, s(1j),...,s(mj))=
0} (1≦j≦n) （ただし、fjは集合{(z1,...,z2m)|ziは整数}から集合W
j （∋0）への適当な写像）を作成する手段と、 (r(x,ij)) (1≦i≦m) ∈Vj (1≦j≦n）をランダムに選
び、鍵利用者xの秘密鍵として、 s(x,i)=r(x,γ(i)) (1≦i≦mn）（ただし、γは集合{1,2,…,mn}から集合{ij|1≦i≦m,1
≦j≦n}への１対1写像で、鍵作成者の秘密とする）を求
める手段と、鍵作成者の秘密情報s(ij)に対応する情報として、 u(ij) (1≦i≦m,1≦j≦n）を作成し、 y(i)=u(γ(i)) (1≦i≦mn）を求める手段と、鍵利用者xの秘密鍵s(x,i)を用いて、当該鍵利用者xの識
別情報dxを求める手段と、 y(1),...,y(mn)と識別情報dxとを、鍵利用者xに送信す
る手段と、を備えることを特徴とする鍵配送装置。
【請求項２１】請求項２０記載の鍵配送装置であって、乱数ｒを選び、適当な関数ｇにより、 z(i)=g(y(i),r) (1≦i≦mn) を計算する手段と、 z(1),...,z(mn)を、鍵利用者xに送信する手段と、をさ
らに備えることを特徴とする鍵配送装置。
【請求項２２】請求項２１記載の鍵配送装置から送信さ
れたデータを基に、鍵利用者xが鍵作成者と共有する共
通の鍵情報を求める鍵共有装置であって、前記鍵配送装置から送信されたデータy(1),...,y(mn)
（あるいはz(1),...,z(mn)）およびdxと、鍵作成者より
配布された鍵利用者xの秘密鍵s(x,i)とを基に、適当な
関数hを用いて、 K=h(s(x,1),...,s(x,mn), y(1),…,y(mn), dx) あるいは、 K=h(s(x,1),...,s(x,mn), z(1),...,z(mn), dx) により、鍵作成者と共有する共通鍵Kを計算する手段を
備えることを特徴とする鍵共有装置。
【請求項２３】鍵作成者が複数の鍵利用者との間で暗号
通信を行うための共通の鍵情報を共有するための鍵配送
装置であって、【数２２】であるとして、鍵作成者の秘密情報の集合KSと公開情報
の集合KP（集合KPは有限アーベル（乗法）群Ｇを決定す
る要素を含む）とを作成する手段（ただし、γ∈{γ｜
１対１写像γ：Ｃ={1,2,...,mn}→Ｄ={ij｜１≦ｉ≦m,
１≦j≦n}}であり、ord_G(g)は、【数２３】なる最小の正整数ｘを表わす）と、整数r(x,ij)（１≦ｉ≦m,１≦j≦n）をランダムに選
び、s(x,i)=r(x,γ(i)) (1≦i≦mn）に対して、(s(x,
i)) (1≦i≦mn)を、鍵利用者xの秘密鍵とする手段と、
整数ξ_Fをランダムに選び、【数２４】を満たす共通鍵Kを、鍵利用者全体の集合のうちの任意
の部分集合Fに属する鍵利用者とのみ共有することを目
的に、【数２５】から、同報通信データとして、【数２６】を満たすy(i)、および、【数２７】を満たす整数d(x,ξ_F)を計算する手段と、前記同報通信データy(i)、d(x,ξ_F)を同報送信する手段
と、を備えることを特徴とする鍵配送装置。
【請求項２４】請求項２３記載の鍵配送装置であって、整数ζをランダムに選び、【数２８】を満たす共通鍵Kを、鍵利用者全体の集合に含まれる任
意の部分集合Fに属する鍵利用者とのみ共有することを
目的に、同報通信データとして、【数２９】を満たすz(i)を計算する手段と、前記同報通信データz(i)を同報送信する手段と、をさら
に備えることを特徴とする鍵配送装置。
【請求項２５】請求項２４記載の鍵配送装置から送信さ
れたデータを基に、鍵利用者xが鍵作成者と共有する共
通の鍵情報を求める鍵共有装置であって、前記鍵配送装置から送信されたデータy(i)（あるいはz
(i)）およびd(x,ξ_F)と、鍵作成者より配布された鍵利
用者xの秘密鍵(s(x,i)) (1≦i≦mn)とを基に、【数３０】あるいは、【数３１】（ただし、f_i (1≦i≦mn）は鍵作成者により公開された
関数であり、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)あるいは
f_i(s(x,i),z(i))=c(x,γ(i),ξ_F)とする）により、鍵作
成者と共有する共通鍵Kを計算する手段を備えることを
特徴とする鍵共有装置。
【請求項２６】鍵作成者が複数の鍵利用者との間で暗号
通信を行うための共通の鍵情報を共有するための鍵配送
装置であって、鍵作成者の秘密情報として、【数３２】を作成し、公開情報として、【数３３】を作成する手段（ただし、0＜g₁, g₂＜Nであり、ord
_G(g)は、【数３４】なる最小の正整数xを表わす）と、整数r(x,ij) (１≦ｉ≦m,１≦j≦2）をランダムに選
び、s(x,i)=r(x,γ(i))（１≦ｉ≦2m）に対して、(s(x,
i)) (1≦i≦2m)を、鍵利用者xの鍵情報とする手段と、
整数ξ_Fをランダムに選び、【数３５】を満たす共通鍵Kを、鍵利用者全体の集合のうちの任意
の部分集合Fに属する鍵利用者とのみ共有することを目
的に、【数３６】から、同報通信データとして、【数３７】を満たすy(i)、および、【数３８】を満たす整数d(x,ξ_F)を計算する手段と、前記同報通信データy(i)、d(x,ξ_F)を同報送信する手段
と、を備えることを特徴とする鍵配送装置。
【請求項２７】請求項２６記載の鍵配送装置であって、整数ζをランダムに選び、【数３９】を満たす共通鍵Kを、鍵利用者全体の集合に含まれる任
意の部分集合Fに属する鍵利用者とのみ共有することを
目的に、同報通信データとして、【数４０】を満たすz(i)を計算する手段と、前記同報通信データz(i)を同報送信する手段と、をさら
に備えることを特徴とする鍵配送装置。
【請求項２８】請求項２７記載の鍵配送装置から送信さ
れたデータを基に、鍵利用者xが鍵作成者と共有する共
通の鍵情報を求める鍵共有装置であって、前記鍵配送装置から送信されたデータy(i)（あるいはz
(i)）およびd(x,ξ_F)と、鍵作成者より配布された鍵利
用者xの秘密鍵(s(x,i)) (1≦i≦2m)とを基に、【数４１】あるいは、【数４２】（ただし、f_i (1≦i≦2m）は鍵作成者により公開された
関数であり、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)あるいは
f_i(s(x,i),z(i))=c(x,γ(i),ξ_F)とする）により、鍵作
成者と共有する共通鍵Kを計算する手段、を備えること
を特徴とする鍵共有装置。
【請求項２９】請求項２４記載の鍵配送装置から送信さ
れたデータを受信する受信装置であって、前記鍵配送装置から送信されたデータd(x,ξ_F)と、当該
受信装置に接続された計算機能付き記憶媒体から送信さ
れたデータK(x,i)（ただし、K(x,i)=y(i)^S(x,i)あるい
は、K(x,i)=z(i)^S(x,i) (∈G)）とを基に、【数４３】あるいは、【数４４】（ただし、f_i (1≦i≦mn）は鍵作成者により公開された
関数であり、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)あるいは
f_i(s(x,i),z(i))=c(x,γ(i),ξ_F)とする）により、鍵利
用者xが鍵作成者と共有する共通鍵Kを求める手段を備え
ることを特徴とする受信装置。
【請求項３０】請求項２９記載の受信装置に接続可能に
構成された計算機能付き記憶媒体であって、鍵作成者より配布された鍵利用者xの秘密鍵(s(x,i)) (1
≦i≦mn)を記憶する記憶手段と、前記記憶手段に記憶された鍵利用者xの秘密鍵(s(x,i))
(1≦i≦mn)と、前記受信装置が受信した、前記鍵配送装
置から送信されたデータy(i)あるいはz(i)と、を基に、【数４５】あるいは、【数４６】を満たすK(x,i)を求め、前記受信装置に送信する演算手
段と、を備えることを特徴とする計算機能付き記憶媒
体。
【請求項３１】請求項２７記載の鍵配送装置から送信さ
れたデータを受信する受信装置であって、前記鍵配送装置から送信されたデータd(x,ξ_F)と、当該
受信装置に接続された計算機能付き記憶媒体から送信さ
れたデータK(x,i)（ただし、K(x,i)=y(i)^S(x,i)modNあ
るいは、K(x,i)=z(i)^S(x,i)modN (∈G)）とを基に、【数４７】あるいは、【数４８】（ただし、f_i (1≦i≦2m）は鍵作成者により公開された
関数であり、f_i(s(x,i),y(i))=c(x,γ(i),ξ_F)あるいは
f_i(s(x,i),z(i))=c(x,γ(i),ξ_F)とする）により、鍵利
用者xが鍵作成者と共有する共通鍵Kを求める手段を備え
ることを特徴とする受信装置。
【請求項３２】請求項３１記載の受信装置に接続可能に
構成された計算機能付き記憶媒体であって、鍵作成者より配布された鍵利用者xの秘密鍵(s(x,i)) (1
≦i≦2m)を記憶する記憶手段と、前記記憶手段に記憶された鍵利用者xの秘密鍵(s(x,i))
(1≦i≦2m)と、前記受信装置が受信した、前記鍵配送装
置から送信されたデータy(i)あるいはz(i)と、を基に、【数４９】あるいは、【数５０】を満たすK(x,i)を求め、前記受信装置に送信する演算手
段と、を備えることを特徴とする計算機能付き記憶媒
体。