(57)【要約】【課題】通信に関するメタデータを秘匿することができる、N（≧2）者間の鍵交換技術を提供する。【解決手段】通信装置Uiが第一鍵を生成する第一鍵生成ステップと、i∈{1, …, n}について、通信装置Uiが、集合R-{Ui}を指定して、i∈{n+1, …, N}について、通信装置Uiが、φを指定して第一鍵を匿名ブロードキャストする第一匿名ブロードキャストステップと、通信装置Uiが第二鍵を生成する第二鍵生成ステップと、i∈{1, …, n}について、通信装置Uiが、集合R-{Ui}を指定して、i∈{n+1, …, N}について、通信装置Uiが、φを指定して第二鍵を匿名ブロードキャストする第二匿名ブロードキャストステップと、i∈{1, …, n}について、通信装置Uiが、所定の条件を満たす場合に、セッション鍵SKを生成するセッション鍵生成ステップとを含む。【選択図】図２
2019047390.tif 000002
【特許請求の範囲】
【請求項１】
Nを2以上の整数、Lを1以上の整数とし、
N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でメッセージM1, …, Mnを共有する匿名ブロードキャスト方法であって、
IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j) (1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j)(1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵とし、
i∈{1, …, n}について、通信装置Uiが、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)と前記識別子IDiと前記メッセージMiの組であるメッセージ(IDi, Mi)から、署名ωi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (IDi, Mi))を生成し、マスタ公開鍵Σj=1,..,LMPKjと前記識別子IDiと前記署名ωiと前記メッセージMiの組である平文(IDi, ωi, Mi)と集合R-{Ui}から、暗号文Ci←(Σj=1,..,LMPKj, (IDi, ωi, Mi), (R-{Ui}))を生成し、
i∈{n+1, …, N}について、通信装置Uiが、ダミーメッセージである暗号文Ciを生成する暗号文生成ステップと、
i∈{1, …, N}について、通信装置Uiが、ミックスネットがシャッフルした暗号文{C1, …, CN}を取得する暗号文取得ステップと、
i∈{1, …, N}について、通信装置Uiが、復号鍵Σj=1,..,Ldki(j)と前記暗号文Ck(1≦k≦N)からメッセージ(IDk, ωk, Mk)←(Σj=1,..,Ldki(j), Ck)を生成し、Ui∈R-{Uk}である場合、前記マスタ公開鍵Σj=1,..,LSMPKjと前記メッセージ(IDk, ωk, Mk)から検証結果Verk←(Σj=1,..,LSMPKj, IDk, Mk, ωk)を生成し、署名ωkの検証が成功した場合、前記メッセージMkを前記識別子IDkの通信装置Ukから送信されたメッセージとみなし、通信装置Ui∈Rが、前記メッセージM1, …, Mnを取得するメッセージ復元ステップと、
を含む匿名ブロードキャスト方法。
【請求項２】
Nを2以上の整数、Lを1以上の整数とし、
N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でセッション鍵SKを共有する鍵交換方法であって、
IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j) (1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j)(1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵、Gをg,hを生成元とする素数位数pの有限巡回群、||を連結演算子とし、
通信装置Ui(1≦i≦N)の記録部に、秘密ストリングsti, st'iが記録されており、
i∈{1, …, n}について、通信装置Uiが、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを計算し、Ri=gr_i、ci=gk_ihs_iを計算することにより、第一鍵(Ri, ci)を生成し、
i∈{n+1, …, N}について、通信装置Uiが、Ri, ci∈RGをランダムに選択し、第一鍵(Ri, ci)を生成する第一鍵生成ステップと、
i∈{1, …, n}について、通信装置Uiが、集合R-{Ui}を指定して前記第一鍵(Ri, ci)を匿名ブロードキャストし、
i∈{n+1, …, N}について、通信装置Uiが、受信者なしを意味するφを指定して前記第一鍵(Ri, ci)を匿名ブロードキャストする第一匿名ブロードキャストステップと、
i∈{2, …, n}について、通信装置Uiが、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)を用いてセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Ri-1r_i)を用いてKi(l)を計算し、擬似ランダム関数により(sid, Ri+1r_i)を用いてKi(r)を計算し、Ki(l)とKi(r)との排他的論理和によりTiを計算し、T'i∈RZp2をランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)とメッセージ(R, Ri, ci, ki, si, Ti, T'i)から署名σi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (R, Ri, ci, ki, si, Ti, T'i))を生成し、第二鍵(ki, si, Ti, T'i, σi)を生成し、
i=1について、通信装置U1が、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)からセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Rnr_1)を用いてK1(l)を計算し、擬似ランダム関数により(sid, R2r_1)を用いてK1(r)を計算し、K1(l)とK1(r)との排他的論理和によりT1を計算し、K1(l)とk1||s1との排他的論理和によりT'を計算し、k"1, s"1∈RZpをランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lsk1(j)とメッセージ(R, R1, c1, k"1, s"1, T1, T')から署名σ1←(Σj=1,..,LSMPKj, Σj=1,..,Lsk1(j), (R, R1, c1, k"1, s"1, T1, T'))を生成し、第二鍵(k"1, s"1, T1, T', σ1)を生成し、
i∈{n+1, …, N}について、通信装置Uiが、ki, si∈RZp、Ti, T'i∈RZp2、σi∈RΣ（ただし、Σは署名空間）をランダムに選択し、第二鍵(ki, si, Ti, T'i, σi)を生成する第二鍵生成ステップと、
i∈{2, …, n}について、通信装置Uiが、集合R-{Ui}を指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストし、
i=1について、通信装置U1が、集合R-{U1}を指定して前記第二鍵(k"1, s"1, T1, T', σ1)を匿名ブロードキャストし、
i∈{n+1, …, N}について、通信装置Uiが、前記φを指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストする第二匿名ブロードキャストステップと、
i∈{2, …, n}について、通信装置Uiが、前記第二鍵(k"1, s"1, T1, T', σ1)と前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n, k≠i)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkの検証が成功であった場合は、Ki(l)と、Tj(1≦j≦i-1)の排他的論理和との排他的論理和によりK1(l)を計算し、T'とK1(l)との排他的論理和によりk1||s1を計算し、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成し、
i=1について、通信装置U1が、前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkの検証が成功であり、かつ、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成するセッション鍵生成ステップと、
を含む鍵交換方法。
【請求項３】
Nを2以上の整数、Lを1以上の整数とし、
N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でメッセージM1, …, Mnを共有する匿名ブロードキャストシステムであって、
IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j) (1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j)(1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵とし、
通信装置Ui(1≦i≦N)は、匿名ブロードキャスト部を含み、
前記匿名ブロードキャスト部は、
i∈{1, …, n}について、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)と前記識別子IDiと前記メッセージMiの組であるメッセージ(IDi, Mi)から、署名ωi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (IDi, Mi))を生成し、マスタ公開鍵Σj=1,..,LMPKjと前記識別子IDiと前記署名ωiと前記メッセージMiの組である平文(IDi, ωi, Mi)と集合R-{Ui}から、暗号文Ci←(Σj=1,..,LMPKj, (IDi, ωi, Mi), (R-{Ui}))を生成し、
i∈{n+1, …, N}について、ダミーメッセージである暗号文Ciを生成する暗号文生成部と、
ミックスネットがシャッフルした暗号文{C1, …, CN}を取得する暗号文取得部と、
復号鍵Σj=1,..,Ldki(j)と前記暗号文Ck(1≦k≦N)からメッセージ(IDk, ωk, Mk)←(Σj=1,..,Ldki(j), Ck)を生成し、
i∈{1, …, n}（ただし、i≠k）について、前記マスタ公開鍵Σj=1,..,LSMPKjと前記メッセージ(IDk, ωk, Mk)から検証結果Verk←(Σj=1,..,LSMPKj, IDk, Mk, ωk)を生成し、署名ωkの検証が成功した場合、前記メッセージMkを前記識別子IDkの通信装置Ukから送信されたメッセージとみなし、
i∈{1, …, n}について、前記メッセージM1, …, Mnを取得するメッセージ復元部と、
を含む匿名ブロードキャストシステム。
【請求項４】
Nを2以上の整数、Lを1以上の整数とし、
N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でセッション鍵SKを共有する鍵交換システムであって、
IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j) (1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j)(1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵、Gをg,hを生成元とする素数位数pの有限巡回群、||を連結演算子とし、
通信装置Ui(1≦i≦N)は、
秘密ストリングsti, st'iを記録する記録部と、
i∈{1, …, n}について、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを計算し、Ri=gr_i、ci=gk_ihs_iを計算することにより、第一鍵(Ri, ci)を生成し、
i∈{n+1, …, N}について、Ri, ci∈RGをランダムに選択し、第一鍵(Ri, ci)を生成する第一鍵生成部と、
i∈{1, …, n}について、集合R-{Ui}を指定して前記第一鍵(Ri, ci)を匿名ブロードキャストし、
i∈{n+1, …, N}について、受信者なしを意味するφを指定して前記第一鍵(Ri, ci)を匿名ブロードキャストする第一匿名ブロードキャスト部と、
i∈{2, …, n}について、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)を用いてセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Ri-1r_i)を用いてKi(l)を計算し、擬似ランダム関数により(sid, Ri+1r_i)を用いてKi(r)を計算し、Ki(l)とKi(r)との排他的論理和によりTiを計算し、T'i∈RZp2をランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)とメッセージ(R, Ri, ci, ki, si, Ti, T'i)から署名σi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (R, Ri, ci, ki, si, Ti, T'i))を生成し、第二鍵(ki, si, Ti, T'i, σi)を生成し、
i=1について、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)からセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Rnr_1)を用いてK1(l)を計算し、擬似ランダム関数により(sid, R2r_1)を用いてK1(r)を計算し、K1(l)とK1(r)との排他的論理和によりT1を計算し、K1(l)とk1||s1との排他的論理和によりT'を計算し、k"1, s"1∈RZpをランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lsk1(j)とメッセージ(R, R1, c1, k"1, s"1, T1, T')から署名σ1←(Σj=1,..,LSMPKj, Σj=1,..,Lsk1(j), (R, R1, c1, k"1, s"1, T1, T'))を生成し、第二鍵(k"1, s"1, T1, T', σ1)を生成し、
i∈{n+1, …, N}について、ki, si∈RZp、Ti, T'i∈RZp2、σi∈RΣ（ただし、Σは署名空間）をランダムに選択し、第二鍵(ki, si, Ti, T'i, σi)を生成する第二鍵生成部と、
i∈{2, …, n}について、集合R-{Ui}を指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストし、
i=1について、集合R-{U1}を指定して前記第二鍵(k"1, s"1, T1, T', σ1)を匿名ブロードキャストし、
i∈{n+1, …, N}について、前記φを指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストする第二匿名ブロードキャスト部と、
i∈{2, …, n}について、前記第二鍵(k"1, s"1, T1, T', σ1)と前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n, k≠i)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkの検証が成功であった場合は、Ki(l)と、Tj(1≦j≦i-1)の排他的論理和との排他的論理和によりK1(l)を計算し、T'とK1(l)との排他的論理和によりk1||s1を計算し、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成し、
i=1について、前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkの検証が成功であり、かつ、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成するセッション鍵生成部と、
を含む鍵交換システム。
【請求項５】
請求項３に記載の匿名ブロードキャストシステムまたは請求項４に記載の鍵交換システムを構成する通信装置。
【請求項６】
請求項３に記載の匿名ブロードキャストシステムまたは請求項４に記載の鍵交換システムを構成する通信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は情報セキュリティ技術の応用に関し、特に、グループを形成する複数のユーザが共通鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
従来からグループを形成する複数のユーザが共通鍵を共有する鍵交換技術が提案されている。そのような鍵交換技術を実現するシステムの一例を図１に示す。鍵交換システム９０は、鍵交換サーバ７００およびN（≧2）台の通信装置８００1, …, ８００Nを含む。この実施形態では、鍵交換サーバ７００および通信装置８００1, …, ８００Nはそれぞれ通信網９００へ接続され、各通信装置８００iは鍵交換サーバ７００を介してその他の通信装置８００j（1≦i, j≦N, ただし、iとjは異なる）と相互に鍵を交換する。しかし、通信の機密性を確保するために必要となる鍵交換により、どの通信装置がどの通信装置と、いつ、どの程度の頻度にて通信しているのかといった通信に関するメタデータが外部の攻撃者に漏れてしまい、メタデータを完全に秘匿することが困難であるという問題があった。例えば、公開鍵基盤(PKI: Public Key Infrastracture)を用いた鍵交換では、公開鍵を入手したユーザが公開鍵の所有者であるユーザと通信をしたいことが攻撃者にわかってしまう。
【０００３】
そこで、メタデータを秘匿できる鍵交換技術として、非特許文献１にあるプロトコルが提案されている。非特許文献１の技術では、その通信路で確率的公開鍵暗号を用いて２者間の鍵交換を実現する。これにより、２者間の鍵交換に際しての通信に関するメタデータ（例えば、電話番号、送信先、送信元、通信時刻、通信経路、添付ファイル名、送信回数など）を秘匿することが可能となる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】David Lazar and Nickolai Zeldovich, “Alpenhorn: Bootstrapping Secure Communication without Leaking Metadata”、［online］、［平成29年7月14日検索］、インターネット<URL:https://vuvuzela.io/alpenhorn-extended.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の技術では、共通鍵を交換することができるユーザは２者に限られる。このため、N（≧3）者間の通信において、メタデータを秘匿したうえで鍵交換を実現することができなかった。
【０００６】
そこで本発明は、通信に関するメタデータを秘匿することができる、N（≧2）者間の鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様は、Nを2以上の整数、Lを1以上の整数とし、N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でメッセージM1, …, Mnを共有する匿名ブロードキャスト方法であって、IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j)(1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j) (1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵とし、i∈{1, …, n}について、通信装置Uiが、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)と前記識別子IDiと前記メッセージMiの組であるメッセージ(IDi, Mi)から、署名ωi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (IDi, Mi))を生成し、マスタ公開鍵Σj=1,..,LMPKjと前記識別子IDiと前記署名ωiと前記メッセージMiの組である平文(IDi, ωi, Mi)と集合R-{Ui}から、暗号文Ci←(Σj=1,..,LMPKj, (IDi, ωi, Mi), (R-{Ui}))を生成し、i∈{n+1, …, N}について、通信装置Uiが、ダミーメッセージである暗号文Ciを生成する暗号文生成ステップと、i∈{1, …, N}について、通信装置Uiが、ミックスネットがシャッフルした暗号文{C1, …, CN}を取得する暗号文取得ステップと、i∈{1, …, N}について、通信装置Uiが、復号鍵Σj=1,..,Ldki(j)と前記暗号文Ck(1≦k≦N)からメッセージ(IDk, ωk, Mk)←(Σj=1,..,Ldki(j), Ck)を生成し、Ui∈R-{Uk}である場合、前記マスタ公開鍵Σj=1,..,LSMPKjと前記メッセージ(IDk, ωk, Mk)から検証結果Verk←(Σj=1,..,LSMPKj, IDk, Mk, ωk)を生成し、署名ωkの検証が成功した場合、前記メッセージMkを前記識別子IDkの通信装置Ukから送信されたメッセージとみなし、通信装置Ui∈Rが、前記メッセージM1, …, Mnを取得するメッセージ復元ステップと、を含む。
【０００８】
本発明の一態様は、Nを2以上の整数、Lを1以上の整数とし、N台の通信装置U1, …, UNのうち、通信装置の集合R={U1, …, Un}(2≦n≦N）に含まれる通信装置の間でセッション鍵SKを共有する鍵交換方法であって、IDi(1≦i≦N)を通信装置Uiの識別子、MPKj(1≦j≦L)を匿名IDベースブロードキャスト暗号のマスタ公開鍵、SMPKj(1≦j≦L)をIDベース署名のマスタ公開鍵、dki(j) (1≦i≦N, 1≦j≦L)を匿名IDベースブロードキャスト暗号の復号鍵、ski(j)(1≦i≦N, 1≦j≦L)をIDベース署名の署名鍵、Gをg,hを生成元とする素数位数pの有限巡回群、||を連結演算子とし、通信装置Ui(1≦i≦N)の記録部に、秘密ストリングsti, st'iが記録されており、i∈{1, …, n}について、通信装置Uiが、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを計算し、Ri=gr_i、ci=gk_ihs_iを計算することにより、第一鍵(Ri, ci)を生成し、i∈{n+1, …, N}について、通信装置Uiが、Ri, ci∈RGをランダムに選択し、第一鍵(Ri, ci)を生成する第一鍵生成ステップと、i∈{1, …, n}について、通信装置Uiが、集合R-{Ui}を指定して前記第一鍵(Ri, ci)を匿名ブロードキャストし、i∈{n+1, …, N}について、通信装置Uiが、受信者なしを意味するφを指定して前記第一鍵(Ri, ci)を匿名ブロードキャストする第一匿名ブロードキャストステップと、i∈{2, …, n}について、通信装置Uiが、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)を用いてセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Ri-1r_i)を用いてKi(l)を計算し、擬似ランダム関数により(sid, Ri+1r_i)を用いてKi(r)を計算し、Ki(l)とKi(r)との排他的論理和によりTiを計算し、T'i∈RZp2をランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)とメッセージ(R, Ri, ci, ki, si, Ti, T'i)から署名σi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (R, Ri, ci, ki, si, Ti, T'i))を生成し、第二鍵(ki, si, Ti, T'i, σi)を生成し、i=1について、通信装置U1が、ターゲット衝突困難ハッシュ関数により、前記ck(1≦k≦n)からセッションＩＤ sidを計算し、擬似ランダム関数により(sid, Rnr_1)を用いてK1(l)を計算し、擬似ランダム関数により(sid, R2r_1)を用いてK1(r)を計算し、K1(l)とK1(r)との排他的論理和によりT1を計算し、K1(l)とk1||s1との排他的論理和によりT'を計算し、k"1, s"1∈RZpをランダムに選択し、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lsk1(j)とメッセージ(R, R1, c1, k"1, s"1, T1, T')から署名σ1←(Σj=1,..,LSMPKj, Σj=1,..,Lsk1(j), (R, R1, c1, k"1, s"1, T1, T'))を生成し、第二鍵(k"1, s"1, T1, T', σ1)を生成し、i∈{n+1, …, N}について、通信装置Uiが、ki, si∈RZp、Ti, T'i∈RZp2、σi∈RΣ（ただし、Σは署名空間）をランダムに選択し、第二鍵(ki, si, Ti, T'i, σi)を生成する第二鍵生成ステップと、i∈{2, …, n}について、通信装置Uiが、集合R-{Ui}を指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストし、i=1について、通信装置U1が、集合R-{U1}を指定して前記第二鍵(k"1, s"1, T1, T', σ1)を匿名ブロードキャストし、i∈{n+1, …, N}について、通信装置Uiが、前記φを指定して前記第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストする第二匿名ブロードキャストステップと、i∈{2, …, n}について、通信装置Uiが、前記第二鍵(k"1, s"1, T1, T', σ1)と前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n, k≠i)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), ��k)を生成し、署名σkの検証が成功であった場合は、Ki(l)と、Tj(1≦j≦i-1)の排他的論理和との排他的論理和によりK1(l)を計算し、T'とK1(l)との排他的論理和によりk1||s1を計算し、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成し、i=1について、通信装置U1が、前記第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n)を取得すると、前記マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)と前記署名σkから、検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkの検証が成功であり、かつ、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つ場合は、擬似ランダム関数により、前記sid、前記ki(1≦i≦n)の排他的論理和を用いて前記セッション鍵SKを生成するセッション鍵生成ステップと、を含む。
【発明の効果】
【０００９】
本発明によれば、メタデータを秘匿したうえで、複数のユーザが共通鍵を共有することが可能となる。さらに、より一般に、メタデータを秘匿したうえで、複数のユーザがメッセージを共有することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】鍵交換システム９０の構成の一例を示す図。
【図２】鍵交換システム１０の構成の一例を示す図。
【図３】鍵生成サーバ１００の構成の一例を示す図。
【図４】公開用サーバ２００の構成の一例を示す図。
【図５】ミックスネットサーバ３００の構成の一例を示す図。
【図６】通信装置４００の構成の一例を示す図。
【図７】匿名ブロードキャスト部４１０の構成の一例を示す図。
【図８】システムセットアップにおける鍵生成サーバ１００の動作の一例を示す図。
【図９】システムセットアップにおける公開用サーバ２００の動作の一例を示す図。
【図１０】システムセットアップにおける通信装置４００の動作の一例を示す図。
【図１１】ブロードキャストにおける通信装置４００の動作の一例を示す図。
【図１２】セッション鍵生成における通信装置４００の動作の一例を示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１２】
＜表記方法＞
実施形態の説明に先立って、この明細書における表記方法について説明する。
【００１３】
_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００１４】
ある集合Setについて、Setから要素mをランダムに選ぶことを、m∈RSetと表記する。
【００１５】
あるアルゴリズムALGについて、入力xと乱数rに対してALGがyを出力することを、y←ALG(x;r)と表記する。なお、ALGが確定的アルゴリズムの場合は、乱数rは空である。
【００１６】
кをセキュリティパラメータとする。
【００１７】
［擬似ランダム関数(PRF)］
F={Fк:Domк×FSк→Rngк}кを定義域{Domк}к、鍵空間{FSк}к、値域{Rngк}кを持つ関数族とする。このとき、もし任意の多項式時間の識別者Dに対して、関数Fкと真正ランダム関数RFк:Domк→Rngкが見分けられなければ、F={Fк}кを擬似ランダム関数族と呼ぶ。擬似ランダム関数の具体例は、例えば、下記参考非特許文献１に記載されている。
（参考非特許文献１：O.ゴールドライヒ著、「現代暗号・確率的証明・擬似乱数」、シュプリンガー・フェアラーク東京、2001年）
【００１８】
［ターゲット衝突困難ハッシュ関数］
H={Hк:Domк→Rngк}кを定義域{Domк}к、値域{Rngк}кを持つハッシュ関数族とする。このとき、もし任意の多項式時間の攻撃者Aに対して、x∈RDomкを与えた上でHк(x)=Hк(x')となるようなx'(≠x)を見つけられなければ、H={Hк}кをターゲット衝突困難ハッシュ関数族と呼ぶ。ターゲット衝突困難ハッシュ関数の具体例は、例えば、下記参考非特許文献２に記載されている。
（参考非特許文献２：J.A.ブーフマン著、「暗号理論入門  原書第3版」、丸善出版、2007年）
【００１９】
［ねじれ擬似ランダム関数(twisted PRF)］
関数tPRF:{0, 1}к×FSк×FSк×{0, 1}к→Rngкをねじれ擬似ランダム関数と呼び、擬似ランダム関数Fкを用いて、
【００２０】
【数１】
2019047390.tif 000003
【００２１】
と定義する。ただし、a,b'∈{0, 1}кであり、a',b∈FSкである。ねじれ擬似ランダム関数の具体例は、例えば、下記参考非特許文献３に記載されている。
（参考非特許文献３：Kazuki Yoneyama, “One-Round Authenticated Key Exchange with Strong Forward Secrecy in the Standard Model against Constrained Adversary”, IEICE Transactions, vol. E96-A, no. 6, pp. 1124-1138, 2013.）
【００２２】
［ミックスネット(Mix-Net)］
ミックスネットシステムは、M台（Mは2以上の整数）のミックスネットサーバS1, …, SMを含む。最初のサーバであるミックスネットサーバS1は、１つのラウンド（すなわち、S1, …, SMによる一連の処理）で処理対象となるn個（nは2以上の整数）の入力メッセージを受信する。その後、各ミックスネットサーバが、m=1, …, Mと順にメッセージをシャッフルしていく。最後のサーバであるミックスネットサーバSMは、N個（Nは2以上の整数）の出力メッセージを出力する。任意の外部の攻撃者がM-1台のミックスネットサーバと結託した場合であっても、その攻撃者は入力メッセージと出力メッセージとの間の関係について知ることはできない。安全なミックスネットプロトコルの具体例は、例えば、下記参考非特許文献４に記載されている。
（参考非特許文献４：Miyako Ohkubo, Masayuki Abe, “A Length-Invariant Hybrid Mix”, ASIACRYPT'00, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, pp.178-191, 2000.）
【００２３】
［匿名IDベースブロードキャスト暗号(Anonymous ID-based Broadcast Encryption: AIBBE)］
匿名IDベースブロードキャスト暗号は、以下の４つのアルゴリズムで構成される。
【００２４】
マスタ鍵生成アルゴリスム(1κ)は、セキュリティパラメータκを入力とし、マスタ秘密鍵MSKとマスタ公開鍵MPKを出力する。鍵生成センタKGCは、マスタ秘密鍵MSKを与えられる。また、マスタ公開鍵MPKは、公開される。
【００２５】
復号鍵生成アルゴリズム(MSK, IDi)は、マスタ秘密鍵MSKとユーザi(1≦i≦N)の識別子IDiを入力とし、復号鍵dkiを出力する。復号鍵dkiは、ユーザiに安全に送信される。
【００２６】
暗号化アルゴリズム(MPK, M, R)は、マスタ公開鍵MPKと平文Mと受信者の集合Rを入力とし、暗号文CTを出力する。なお、受信者の集合Rは、平文Mの受信者となるユーザの識別子の集合である。
【００２７】
復号アルゴリズム(dki, CT)は、復号鍵dkiと暗号文CTを入力とし、受信者の集合Rにユーザiの識別子IDiが含まれる場合は平文Mを出力する。
【００２８】
安全なAIBBEの具体例は、例えば、下記参考非特許文献５に記載されている。
（参考非特許文献５：Kai He, Jian Weng, Jia-Nan Liu, Joseph K. Liu, Wei Liu, Robert H. Deng, “Anonymous Identity-Based Broadcast Encryption with Chosen-Ciphertext Security”, ASIA CCS'16, Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, pp.247-255, 2016.）
【００２９】
匿名IDベースブロードキャスト暗号を用いてエニートラスト匿名IDベースブロードキャスト暗号(anytrust-AIBBE: AT-AIBBE)を定義する。信用を分散するため、AT-AIBBEには、複数の鍵生成センタ(KGC1, …, KGCL)が含まれる（Lは1以上の整数）。鍵生成センタKGCj(1≦j≦L)はマスタ公開鍵MPKjを公開する。また、鍵生成センタKGCj(1≦j≦L)は、ユーザi(1≦i≦N)のための復号鍵dki(j)を生成する。ユーザi(1≦i≦N)は、平文Mを暗号化し、暗号文CT←(Σj=1,..,LMPKj, M, R)を得る。また、ユーザi(1≦i≦N)は、暗号文CTを復号し、平文M←(Σj=1,..,Ldki(j), CT)を得る（ただし、受信者の集合Rにユーザiの識別子IDiが含まれる場合に限る）。鍵生成センタKGCj(1≦j≦L)のうち、L-1個の鍵生成センタに悪意があった場合であっても、そのL-1個の鍵生成センタは暗号文CTを復号することができない。
【００３０】
［IDベース署名(ID-based Signature)］
IDベース署名は、以下の４つのアルゴリズムで構成される。
【００３１】
マスタ鍵生成アルゴリスム(1κ)は、セキュリティパラメータκを入力とし、マスタ秘密鍵SMSKとマスタ公開鍵SMPKを出力する。鍵生成センタKGCは、マスタ秘密鍵SMSKを与えられる。また、マスタ公開鍵SMPKは、公開される。
【００３２】
署名鍵生成アルゴリズム(SMSK, IDi)は、マスタ秘密鍵SMSKとユーザi(1≦i≦N)の識別子IDiを入力とし、署名鍵skiを出力する。署名鍵skiは、ユーザiに安全に送信される。
【００３３】
署名生成アルゴリズム(SMPK, ski, M)は、マスタ公開鍵SMPKと署名鍵skiとメッセージMを入力とし、署名σを出力する。
【００３４】
署名検証アルゴリズム(SMPK, IDi, M, σ)は、マスタ公開鍵SMPKとユーザiの識別子IDiとメッセージMと署名σを入力とし、検証結果Ver（例えば、検証結果を示す２値として0または1）を出力する。
【００３５】
IDベース署名を用いてエニートラストIDベース署名(anytrust-IBS: AT-IBS)を定義する。信用を分散するため、AT-IBSには、複数の鍵生成センタ(KGC1, …, KGCL)が含まれる（Lは1以上の整数）。鍵生成センタKGCj(1≦j≦L)はマスタ公開鍵SMPKjを公開する。また、鍵生成センタKGCj(1≦j≦L)は、ユーザi(1≦i≦N)のための署名鍵ski(j)を生成する。ユーザi(1≦i≦N)は、メッセージMに対する署名として、署名σ←(Σj=1,..,LSMPKj, Σj=1,..,L ski(j), M)を得る。また、ユーザi(1≦i≦N)は署名σを検証し、検証結果Ver←(Σj=1,..,LSMPKj, IDi, M, σ)を得る。鍵生成センタKGCj(1≦j≦L)のうち、L-1個の鍵生成センタに悪意があった場合であっても、そのL-1個の鍵生成センタは署名σを偽造することができない。
【００３６】
＜システム構成＞
実施形態の鍵交換システム１０は、図２に例示するように、L（≧1）台の鍵生成サーバ１００1, …, １００L、公開用サーバ２００、M（≧2）台のミックスネットサーバ３００1, …, ３００M、N（≧2）台の通信装置４００1, …, ４００Nを含む。この実施形態では、鍵生成サーバ１００1, …, １００L、公開用サーバ２００、ミックスネットサーバ３００1, …, ３００M、通信装置４００1, …, ４００Nはそれぞれ通信網９００へ接続される。通信網９００は、鍵生成サーバ１００1, …, １００L、公開用サーバ２００、ミックスネットサーバ３００1, …, ３００M、通信装置４００1, …, ４００Nのうち、通信が必要となる各サーバまたは各装置が、相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網である。通信網９００は安全が確保された通信路である必要はなく、例えばインターネットなどを用いることができる。
【００３７】
鍵生成サーバ１００は、図３に例示するように、マスタ鍵生成部１０１、復号鍵・署名鍵生成部１０２、送受信部１９８、記録部１９９を含む。公開用サーバ２００は、図４に例示するように、公開部２０１、送受信部２９８、記録部２９９を含む。ミックスネットサーバ３００は、図５に例示するように、シャッフル部３０１、送受信部３９８、記録部３９９を含む。通信装置４００は、図６に例示するように、秘密ストリング生成部４０１、第一匿名ブロードキャスト部４１０−１、第二匿名ブロードキャスト部４１０−２、第一鍵生成部４２１、第二鍵生成部４２３、セッション鍵生成部４２７、送受信部４９８、記録部４９９を含む。
【００３８】
ここで、第一匿名ブロードキャスト部４１０−１、第二匿名ブロードキャスト部４１０−２は、それぞれ、指定した通信装置の集合に属する通信装置間でメッセージを共有するための機能を提供する。つまり、第一匿名ブロードキャスト部４１０−１、第二匿名ブロードキャスト部４１０−２は、同一の機能を提供する。そこで、以下、第一匿名ブロードキャスト部４１０−１、第二匿名ブロードキャスト部４１０−２を匿名ブロードキャスト部４１０として説明する。匿名ブロードキャスト部４１０は、図７に例示するように、暗号文生成部４１１、暗号文取得部４１４、メッセージ復元部４１５を含む。
【００３９】
この鍵生成サーバ１００1, …, １００L、公開用サーバ２００、ミックスネットサーバ３００1, …, ３００M、通信装置４００1, …, ４００Nが、図８から図１２までに例示する各ステップの処理を行うことにより実施形態の鍵交換方法が実現される。
【００４０】
鍵生成サーバ１００1, …, １００L、公開用サーバ２００、ミックスネットサーバ３００1, …, ３００M、通信装置４００1, …, ４００Nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。各装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。各装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。各装置が備える各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００４１】
鍵生成サーバ１００1, …, １００L、公開用サーバ２００、ミックスネットサーバ３００1, …, ３００M、通信装置４００1, …, ４００Nが備える記録部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。記録部は、秘密情報を記憶する場合、耐タンパ性を有する記憶装置（例えば、SIMカードなど）であることが望ましい。
【００４２】
以降の説明では、以下のように記号を定義する。Ui（i∈{1, …, N}）はN台の通信装置４００1, …, ４００Nを表すものとする。同様に、Sm（m∈{1, …, M}）はM台のミックスネットサーバ３００1, …, ３００Mを表すものとする。
【００４３】
また、pをκビットの素数、Gを、g,hを生成元とする位数pの有限巡回群とする。TCR:{0, 1}*→{0,1}κをターゲット衝突困難ハッシュ関数とする。tPRF:{0, 1}к×FSк×FSк×{0, 1}к→Zp、tPRF':{0, 1}к×FSк×FSк×{0, 1}к→FSкをねじれ擬似ランダム関数とする。F:{0, 1}к×G→Zp2、F':{0, 1}к×Zp→FSк、F":{0, 1}к×FSк→{0, 1}к、F''':{0, 1}к×FSк→Zpを擬似ランダム関数とする。
【００４４】
＜システムセットアップ＞
図８から図１０を参照して、実施形態の鍵交換方法におけるシステムセットアップの処理手続きを説明する。
【００４５】
図８を参照して、鍵生成サーバ１００j(1≦j≦L)の動作について説明する。ステップＳ１０１において、鍵生成サーバ１００j(1≦j≦L)のマスタ鍵生成部１０１は、匿名IDベースブロードキャスト暗号のマスタ鍵生成アルゴリズムとIDベース署名のマスタ鍵生成アルゴリズムにより、セキュリティパラメータкから、マスタ秘密鍵(MSKj, SMSKj)とマスタ公開鍵(MPKj, SMPKj)を生成する。
【００４６】
次に、ステップＳ１０２において、鍵生成サーバ１００j(1≦j≦L)の復号鍵・署名鍵生成部１０２は、匿名IDベースブロードキャスト暗号の復号鍵生成アルゴリズムにより、マスタ秘密鍵MSKjと通信装置Ui(1≦i≦N)の識別子IDiから復号鍵dki(j)←(MSKj, IDi)を生成し、IDベース署名の署名鍵生成アルゴリズムにより、マスタ秘密鍵SMSKjと通信装置Ui(1≦i≦N)の識別子IDiから署名鍵ski(j)←(SMSKj, IDi)を生成する。鍵生成サーバ１００j(1≦j≦L)は、送受信部１９８を用いて、復号鍵dki(j)と署名鍵ski(j)を通信装置Ui(1≦i≦N)に送信する。通信装置Uiは、受信した復号鍵dki(j)と署名鍵ski(j)(1≦j≦L)を記録部４９９に記録する。また、通信装置Uiは、マスタ公開鍵(MPKj, SMPKj) (1≦j≦L)を取得し、記録部４９９に記録する。
【００４７】
なお、鍵生成サーバ１００jが生成するマスタ秘密鍵(MSKj, SMSKj)は、メタデータの前方機密性を守るために、周期的に更新される。その周期は、例えば、１日１回などとするとよい。
【００４８】
図９を参照して、公開用サーバ２００の動作について説明する。ステップＳ２０１において、公開用サーバ２００の公開部２０１は、通信装置Ui(1≦i≦N)が取得できるように(p, G, g, h, TCR, tPRF, tPRF', F, F', F", F''')を公開する。通信装置Ui(1≦i≦N)は、公開用サーバ２００から(p, G, g, h, TCR, tPRF, tPRF', F, F', F", F''')を適宜取得し、記録部４９９に記録する。
【００４９】
図１０を参照して、通信装置Ui(1≦i≦N)の動作について説明する。ステップＳ４０１において、通信装置Uiの秘密ストリング生成部４０１は、ねじれ擬似ランダム関数の入力となる秘密ストリング(sti, st'i)を生成する（ただし、sti∈RFSк、st'i∈R{0,1}κ）。通信装置Uiは、生成した(sti, st'i)を記録部４９９に記録する。
【００５０】
＜匿名ブロードキャスト＞
図１１を参照して、実施形態の鍵交換方法における匿名ブロードキャストの処理手続きを説明する。この匿名ブロードキャストの処理手続きは、後述するセッション鍵生成の処理手続きで用いるものである。
【００５１】
通信装置の集合R={Ui_1, …, Ui_n}（ただし、{i1, …, in}⊆{1, …, N}）とし、通信装置Ui_k(1≦k≦n)が集合Rに属する各通信装置とメッセージMi_kを秘匿化したまま共有するため、匿名ブロードキャストする。つまり、集合Rに属する各通信装置は、メッセージMi_1, …, Mi_nを受信することができるが、集合Rに属さない各通信装置は、メッセージMi_1, …, Mi_nを受信することができない。
【００５２】
以下、簡単のため、集合R={Ui_1, …, Ui_n}={U1, …, Un}として説明する。このようにしても一般性を欠くことはない。
【００５３】
１ラウンド（１つの処理単位）の匿名ブロードキャストにおいて、以下の３つの手続きが実行される。
【００５４】
（１）署名と暗号化
この手続きは、通信装置Uiが集合Rに含まれる場合、通信装置Uiが集合Rに含まれない場合の２つの場合に分けて実行される。
【００５５】
ステップＳ４１１において、Ui∈Rの場合、通信装置Uiの暗号文生成部４１１は、IDベース署名の署名生成アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)とメッセージ(IDi, Mi)（つまり、送信元である通信装置Uiの識別子IDiと共有したい元のメッセージMiの組）から、メッセージ(IDi, Mi)に対する署名ωi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (IDi, Mi))を生成する。通信装置Uiの暗号文生成部４１１は、匿名IDベースブロードキャスト暗号の暗号化アルゴリズムにより、マスタ公開鍵Σj=1,..,LMPKjと平文(IDi, ωi, Mi)（つまり、通信装置Uiの識別子IDiと署名ωiと元のメッセージMiの組）と受信者の集合R-{Ui}から暗号文Ci←(Σj=1,..,LMPKj, (IDi, ωi, Mi), (R-{Ui}))を生成する。
【００５６】
Ui∈{U1, …, UN}-Rの場合、通信装置Uiの暗号文生成部４１１は、ダミーメッセージである暗号文Ciを生成する。例えば、ダミーメッセージCiは、受信者なしを意味するφを指定して適当なメッセージMiをマスタ公開鍵Σj=1,..,LMPKjにより暗号化した暗号文Ciとする。このようにすることで、後述するステップＳ４１５における暗号文の復号が必ず失敗することになる。
【００５７】
（２）ミックスネット
通信装置Ui∈{U1, …, UN}は、送信部４９８を用いて、ミックスネットサーバS1にＳ４１１で生成した暗号文Ciを送信する。ミックスネットサーバS1, …, SMは、ミックスネットサーバS1が受信した暗号文(C1, …, CN)を順にシャッフルしていく。ミックスネットサーバSMは、公開用の掲示板に出力メッセージである暗号文(C1, …, CN)をシャッフルしたシャッフル済み暗号文(~C1, …, ~CN)を掲示する。ここで、(C1, …, CN)と(~C1, …, ~CN)は集合として等しい。つまり、{~C1, …, ~CN}={C1, …, CN}となる。例えば、ミックスネットサーバSMによる掲示は、公開用サーバ２００にシャッフル済み暗号文(~C1, …, ~CN)をアップロードすることでよい。これにより、通信装置Ui(1≦i≦N)はシャッフル済み暗号文(~C1, …, ~CN)を取得できるようになる。
【００５８】
（３）ダウンロードとチェック
ステップＳ４１４において、通信装置Ui∈{U1, …, UN}の暗号文取得部４１４は、掲示板からシャッフル済み暗号文(~C1, …, ~CN)をダウンロードすることにより、暗号文{C1, …, CN}を取得する。
【００５９】
ステップＳ４１５において、通信装置Ui∈{U1, …, UN}のメッセージ復元部４１５は、匿名IDベースブロードキャスト暗号の復号アルゴリズムにより、復号鍵Σj=1,..,Ldki(j)と暗号文Ck(1≦k≦N)から平文(IDk, ωk, Mk)←(Σj=1,..,Ldki(j), Ck)を生成する（ただし、Ui∈R-{Uk}の場合に限る）。暗号文Ckの復号が成功した場合、通信装置Uiのメッセージ復元部４１５は、IDベース署名の署名検証アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjとメッセージ(IDk, ωk, Mk)から検証結果Verk←(Σj=1,..,LSMPKj, IDk, Mk, ωk)を生成し、署名ωkを検証する。署名ωkの検証が成功した場合、通信装置Uiのメッセージ復元部４１５は、メッセージMkを識別子IDkの通信装置Ukから送信されたメッセージとみなす。その結果、通信装置Ui∈Rは、（自身が送信したメッセージMiを含む）メッセージM1, …, Mnを取得する。一方、通信装置Ui∈{U1, …, UN}-Rは、メッセージM1, …, Mnを取得することはできない。
【００６０】
以上説明したように、通信装置Uiは、匿名IDベースブロードキャスト暗号の暗号化アルゴリズムにより、送信先の情報（受信者の集合R-{Ui}）を元のメッセージとともに暗号化しているため、公開鍵基盤を用いる必要はない。したがって、メタデータの一つである送信先の情報を秘匿することができる。また、各通信装置がミックスネットを介して暗号文を受信し、元のメッセージを復元するため、メタデータの一つである送信元の情報（送信者Ui）を秘匿することができる。つまり、メタデータを秘匿したうえで、複数のユーザがメッセージを共有することが可能となる。
【００６１】
＜セッション鍵生成＞
図１２を参照して、実施形態の鍵交換方法におけるセッション鍵生成の処理手続きを説明する。
【００６２】
通信装置の集合R={Ui_1, …, Ui_n}（ただし、{i1, …, in}⊆{1, …, N}）の各通信装置の間で新しいセッションを開始し、セッション鍵を共有する。
【００６３】
先ほど同様、以下、簡単のため、集合R={Ui_1, …, Ui_n}={U1, …, Un}、通信装置Ui_1=U1として説明する。このようにしても一般性を欠くことはない。
【００６４】
集合Rに属する各通信装置とセッション鍵を秘匿化したまま共有したいと考えた通信装置U1を代表通信装置という。また、集合R-{U1}の通信装置を一般通信装置という。
【００６５】
（１）ラウンド１：１回目のブロードキャスト
この手続きは、通信装置Uiが集合Rに含まれる場合、通信装置Uiが集合Rに含まれない場合の２つの場合に分けて実行される。
【００６６】
ステップＳ４２１において、Ui∈Rの場合、通信装置Uiの第一鍵生成部４２１は、~ri∈R{0, 1}κ、~r'i∈RFSк、~ki∈R{0, 1}κ、~k'i∈RFSк、~si∈R{0, 1}κ、~s'i∈RFSкを生成し、ri=tPRF(~ri, ~r'i, sti, st'i)、ki=tPRF(~ki, ~k'i, sti, st'i)、si=tPRF(~si, ~s'i, sti, st'i)を計算する。さらに、通信装置Uiの第一鍵生成部４２１は、Ri=gr_i、ci=gk_ihs_iを計算し、第一鍵(Ri, ci)を生成する。
【００６７】
Ui∈{U1, …, UN}-Rの場合、通信装置Uiの第一鍵生成部４２１は、Ri, ci∈RGをランダムに選択し、第一鍵(Ri, ci)を生成する。
【００６８】
ステップＳ４１０−１において、Ui∈Rの場合、通信装置Uiの第一匿名ブロードキャスト部４１０−１は、集合R-{Ui}を指定して第一鍵(Ri, ci)を匿名ブロードキャストする。
【００６９】
Ui∈{U1, …, UN}-Rの場合、通信装置Uiの第一匿名ブロードキャスト部４１０−１は、受信者なしを意味するφを指定して第一鍵(Ri, ci)を匿名ブロードキャストする。
【００７０】
（２）ラウンド２：２回目のブロードキャスト
この手続きは、通信装置Uiが集合R-{U1}に含まれる場合、通信装置UiがU1である場合、通信装置Uiが集合Rに含まれない場合の３つの場合に分けて実行される。
【００７１】
ステップＳ４２３において、Ui∈R-{U1}の場合、通信装置Uiは、集合R-{Ui}に属するすべての通信装置Uk(1≦k≦n, k≠i)から第一鍵(Rk, ck)を受信すると、通信装置Uiの第二鍵生成部４２３は、sid=TCR(c1, …, cn)を計算する。なお、sidのことをセッションＩＤという。次に、通信装置Uiの第二鍵生成部４２３は、Ki(l)、Ki(r)、Tiを次式で計算し、T'i∈RZp2をランダムに選択する。
【００７２】
【数２】
2019047390.tif 000004
【００７３】
つまり、TiはKi(l)とKi(r)との排他的論理和である。
【００７４】
通信装置Uiの第二鍵生成部４２３は、IDベース署名の署名生成アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lski(j)とメッセージ(R, Ri, ci, ki, si, Ti, T'i)（つまり、受信者の集合RとＳ４２１で生成したRi, ci, ki, siと先ほど生成したTi, T'iとの組）からメッセージ(R, Ri, ci, ki, si, Ti, T'i)に対する署名σi←(Σj=1,..,LSMPKj, Σj=1,..,Lski(j), (R, Ri, ci, ki, si, Ti, T'i))を生成する。通信装置Uiの第二鍵生成部４２３は(ki, si, Ti, T'i, σi)を第二鍵として生成する。
【００７５】
Ui=U1の場合、通信装置U1は、集合R-{U1}に属するすべての通信装置Uk(2≦k≦n)から第一鍵(Rk,ck)を受信すると、通信装置Uiの第二鍵生成部４２３は、sid=TCR(c1, …, cn)を計算する。次に、通信装置Uiの第二鍵生成部４２３は、K1(l)、K1(r)、T1、T'を次式で計算し、k"1, s"1∈RZpをランダムに選択する。
【００７６】
【数３】
2019047390.tif 000005
【００７７】
ただし、||は連結演算子である。
【００７８】
通信装置Uiの第二鍵生成部４２３は、IDベース署名の署名生成アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjと署名鍵Σj=1,..,Lsk1(j)とメッセージ(R, R1, c1, k"1, s"1, T1, T')（つまり、受信者の集合RとＳ４２１で生成したR1, c1と先ほど生成したk"1, s"1, T1, T'との組）からメッセージ(R, R1, c1, k"1, s"1, T1, T')に対する署名σ1←(Σj=1,..,LSMPKj, Σj=1,..,Lsk1(j), (R, R1, c1, k"1, s"1, T1, T'))を生成する。通信装置Uiの第二鍵生成部４２３は(k"1, s"1, T1, T', σ1)を第二鍵として生成する。
【００７９】
Ui∈{U1, …, UN}-Rの場合、通信装置Uiの第二鍵生成部４２３は、ki, si∈RZp、Ti, T'i∈RZp2、署名空間Σの要素である署名σiをランダムに選択する。通信装置Uiの第二鍵生成部４２３は(ki, si, Ti, T'i, σi)を第二鍵として生成する。
【００８０】
ステップＳ４１０−２において、Ui∈R-{U1}の場合、通信装置Uiの第二匿名ブロードキャスト部４１０−２は、集合R-{Ui}を指定して第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストする。
【００８１】
Ui=U1の場合、通信装置Uiの第二匿名ブロードキャスト部４１０−２は、集合R-{U1}を指定して第二鍵(k"1, s"1, T1, T', σ1)を匿名ブロードキャストする。
【００８２】
Ui∈{U1, …, UN}-Rの場合、通信装置Uiの第二匿名ブロードキャスト部４１０−２は、受信者なしを意味するφを指定して第二鍵(ki, si, Ti, T'i, σi)を匿名ブロードキャストする。
【００８３】
（３）セッション鍵生成
この手続きは、通信装置Uiが集合R-{U1}に含まれる場合、通信装置UiがU1である場合、通信装置Uiが集合Rに含まれない場合の３つの場合に分けて実行される。
【００８４】
なお、通信装置Uiが集合Rに含まれない場合、空の処理を実行する。つまり、集合Rに含まれない通信装置Uiは、何も処理を行わない。
【００８５】
ステップＳ４２７において、Ui∈R-{U1}の場合、通信装置Uiは、集合R-{Ui}に属するすべての通信装置Uk(1≦k≦n, k≠i)から第二鍵(k"1, s"1, T1, T', σ1)、第二鍵(kk, sk, Tk, T'k, σk)(2≦k≦n, k≠i)を受信すると、通信装置Uiのセッション鍵生成部４２７は、IDベース署名の署名検証アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjと識別子IDkとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)（つまり、受信者の集合RとＳ４２３で受信したRk, ckとＳ４２７開始時に受信したkk, sk, Tk, T'kとの組）とＳ４２７開始時に受信した署名σkから検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkを検証する。署名σkの検証が失敗であった場合には、通信装置Uiのセッション鍵生成部４２７は、処理を中止する。通信装置Uiのセッション鍵生成部４２７は、K1(l)、k1||s1を次式で計算し、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つか確認する。
【００８６】
【数４】
2019047390.tif 000006
【００８７】
1≦k≦nを満たすkの少なくとも１つに対して、ck=gk_khs_kが成り立たない場合、通信装置Uiのセッション鍵生成部４２７は、処理を中止する。通信装置Uiのセッション鍵生成部４２７は、セッション鍵SKを次式で計算する。
【００８８】
【数５】
2019047390.tif 000007
【００８９】
Ui=U1の場合、通信装置U1は、集合R-{U1}に属するすべての通信装置Uk(2≦k≦n)から第二鍵(kk, sk, Tk, T'k, σk)を受信すると、通信装置U1のセッション鍵生成部４２７は、IDベース署名の署名検証アルゴリズムにより、マスタ公開鍵Σj=1,..,LSMPKjと識別子IDkとメッセージ(R, Rk, ck, kk, sk, Tk, T'k)（つまり、受信者の集合RとＳ４２３で受信したRk, ckとＳ４２７開始時に受信したkk, sk, Tk, T'kとの組）とＳ４２７開始時に受信した署名σkから検証結果Verk←(Σj=1,..,LSMPKj, IDk, (R, Rk, ck, kk, sk, Tk, T'k), σk)を生成し、署名σkを検証する。署名σkの検証が失敗であった場合には、通信装置U1のセッション鍵生成部４２７は、処理を中止する。また、通信装置U1のセッション鍵生成部４２７は、1≦k≦nを満たすkに対してck=gk_khs_kが成り立つか確認する。1≦k≦nを満たすkの少なくとも１つに対して、ck=gk_khs_kが成り立たない場合、通信装置U1のセッション鍵生成部４２７は、処理を中止する。通信装置U1のセッション鍵生成部４２７は、セッション鍵SKを次式で生成する。
【００９０】
【数６】
2019047390.tif 000008
【００９１】
Ui∈{U1, …, UN}-Rの場合、上述の通り、通信装置Uiのセッション鍵生成部４２７は、セッション鍵SKを生成しない。
【００９２】
上記のように構成することにより、この発明の鍵交換技術によれば、メタデータを秘匿したうえで、複数の通信装置でセッション鍵を共有することができる。
【００９３】
匿名ブロードキャストは、ミックスネットを用いることにより一定間隔でメッセージを交換可能な秘匿通信路を確立する。これを利用してセッション鍵生成手続きによる鍵交換を実現することにより、メタデータの秘匿化を実現する。さらに、共有したセッション鍵を用いて通信を行うことにより、秘匿通信を実現する。このようにして、鍵交換プロトコルからのメタデータの漏洩を防止することができ、メタデータを完全に秘匿することが可能となる。
【００９４】
当該鍵交換プロトコルを用いると、グローバル企業や衛星通信を利用するような企業に対して、例えば、TCP/IPにおける接続経路の匿名化を実現するTor(The Onion Router)のようなネットワークを提供し、通信におけるメタデータを含めた機密性を確保することが可能となる。
【００９５】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９６】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００９７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１００】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019047390.tif 000009
【図２】
2019047390.tif 000010
【図３】
2019047390.tif 000011
【図４】
2019047390.tif 000012
【図５】
2019047390.tif 000013
【図６】
2019047390.tif 000014
【図７】
2019047390.tif 000015
【図８】
2019047390.tif 000016
【図９】
2019047390.tif 000017
【図１０】
2019047390.tif 000018
【図１１】
2019047390.tif 000019
【図１２】
2019047390.tif 000020