ブロムの計画

ブロム方式は、暗号における対称閾値鍵交換プロトコルである。この方式は、スウェーデンの暗号学者ロルフ・ブロムが1980年代初頭に一連の論文で提案した。^{[1] [2]}

信頼できる当事者は各参加者に秘密鍵と公開識別子を提供し、これにより任意の 2 人の参加者が通信用の共有鍵を独立して作成できるようになります。ただし、攻撃者が少なくとも k 人のユーザーの鍵を侵害できる場合、このスキームを破り、すべての共有鍵を再構築できます。Blom のスキームは、しきい値秘密分散の一種です。

ブロムの方式は現在、HDCP （バージョン1.xのみ）コピー保護方式で、 HD DVDプレーヤーや高精細テレビなどの高精細コンテンツソースと受信機の共有キーを生成するために使用されています。^[3]

鍵交換プロトコルには、信頼できる当事者 (Trent) とユーザー グループが関与します。Aliceと Bob をグループの 2 人のユーザーとします。 ${\displaystyle \scriptstyle n}$

トレントは、有限体上のランダムで秘密の対称行列 を選択します。ここで、p は素数です。新しいユーザーをキー共有グループに追加する場合は、が必要です。 ${\displaystyle \scriptstyle D_{k,k}}$ ${\displaystyle \scriptstyle GF(p)}$${\displaystyle \scriptstyle D}$

例えば：

${\displaystyle {\begin{aligned}k&=3\\p&=17\\D&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}\ \mathrm {mod} \ 17\end{aligned}}}$

新規ユーザーのアリスとボブは、鍵交換グループに参加したいと考えています。トレントは、それぞれの公開識別子、つまり k 要素ベクトルを選択します。

${\displaystyle I_{\mathrm {Alice} },I_{\mathrm {Bob} }\in GF^{k}(p)}$。

例えば：

${\displaystyle I_{\mathrm {Alice} }={\begin{pmatrix}1\\2\\3\end{pmatrix}},I_{\mathrm {Bob} }={\begin{pmatrix}5\\3\\1\end{pmatrix}}}$

次に、Trent は秘密鍵を計算します。

${\displaystyle {\begin{aligned}g_{\mathrm {Alice} }&=DI_{\mathrm {Alice} }\\g_{\mathrm {Bob} }&=DI_{\mathrm {Bob} }\end{aligned}}}$

上記のように 使用します:${\displaystyle D}$

${\displaystyle {\begin{aligned}g_{\mathrm {Alice} }&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}1\\2\\3\end{pmatrix}}={\begin{pmatrix}19\\36\\24\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}2\\2\\7\end{pmatrix}}\ \\g_{\mathrm {Bob} }&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}5\\3\\1\end{pmatrix}}={\begin{pmatrix}25\\47\\36\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}8\\13\\2\end{pmatrix}}\ \end{aligned}}}$

各参加者は自分の秘密鍵を使用して、グループの他の参加者と共有鍵を計算します。

今、アリスとボブは互いに通信したいと考えています。アリスはボブの識別子と自分の秘密鍵を持っています。 ${\displaystyle \scriptstyle I_{\mathrm {Bob} }}$${\displaystyle \scriptstyle g_{\mathrm {Alice} }}$

彼女は共有鍵 を計算します。ここで は行列転置 を表します。ボブも自分の秘密鍵と彼女の識別子を使用して同じことを実行し、同じ結果を返します。 ${\displaystyle \scriptstyle k_{\mathrm {Alice/Bob} }=g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} }}$${\displaystyle \scriptstyle T}$

${\displaystyle k_{\mathrm {Alice/Bob} }=k_{\mathrm {Alice/Bob} }^{T}=(g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} })^{T}=(I_{\mathrm {Alice} }^{T}D^{T}I_{\mathrm {Bob} })^{T}=I_{\mathrm {Bob} }^{T}DI_{\mathrm {Alice} }=k_{\mathrm {Bob/Alice} }}$

それぞれが次のように共有キーを生成します。

${\displaystyle {\begin{aligned}k_{\mathrm {Alice/Bob} }&={\begin{pmatrix}2\\2\\7\end{pmatrix}}^{T}{\begin{pmatrix}5\\3\\1\end{pmatrix}}=2\times 5+2\times 3+7\times 1=23\ \mathrm {mod} \ 17=6\\k_{\mathrm {Bob/Alice} }&={\begin{pmatrix}8\\13\\2\end{pmatrix}}^{T}{\begin{pmatrix}1\\2\\3\end{pmatrix}}=8\times 1+13\times 2+2\times 3=40\ \mathrm {mod} \ 17=6\end{aligned}}}$

攻撃者がすべての共有キーを計算する前に、少なくとも k 個のキーが侵害される必要があることを保証するために、識別子は k 線形独立である必要があります。つまり、ランダムに選択された k 個のユーザー識別子のすべてのセットは線形独立である必要があります。そうでない場合、悪意のあるユーザーのグループは、識別子が自分の識別子に線形従属している他のメンバーのキーを計算できます。この特性を保証するために、識別子は MDS コード マトリックス (最大距離分離可能なエラー訂正コード マトリックス) から選択することが望ましいです。MDS マトリックスの行は、ユーザーの識別子になります。MDS コード マトリックスは、実際にはリードソロモン エラー訂正コードのコード マトリックスを使用して選択できます (このエラー訂正コードは、簡単に理解できる数学のみを必要とし、非常に迅速に計算できます)。^[4]