コックスIBEスキーム

コックスIBE方式は、 2001年にクリフォード・コックスによって提案されたアイデンティティベースの暗号化システムです。^{[1]この方式の安全性は、}二次残差問題の困難性に基づいています。

PKG は以下を選択します:

1. 公開RSA係数、 は素数であり秘密に保持される、${\displaystyle \textstyle n=pq}$${\displaystyle \textstyle p,q,\,p\equiv q\equiv 3{\bmod {4}}}$
2. メッセージと暗号空間と${\displaystyle \textstyle {\mathcal {M}}=\left\{-1,1\right\},{\mathcal {C}}=\mathbb {Z} _{n}}$
3. 安全な公開ハッシュ関数。${\displaystyle \textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}}$

ユーザーが秘密鍵を取得したい場合、安全なチャネルを通じてPKGに連絡します。PKG ${\displaystyle \textstyle ID}$

1. は、 （例えば、 の複数回適用）から決定論的プロセスによって導出されます。${\displaystyle \textstyle a}$${\displaystyle \textstyle \left({\frac {a}{n}}\right)=1}$${\displaystyle \textstyle ID}$${\displaystyle \textstyle f}$
2. を計算します（またはのいずれかを満たします。下記参照）。${\displaystyle \textstyle r=a^{(n+5-pq)/8}{\pmod {n}}}$${\displaystyle \textstyle r^{2}=a{\pmod {n}}}$${\displaystyle \textstyle r^{2}=-a{\pmod {n}}}$
3. ユーザーに送信します。${\displaystyle \textstyle r}$

のビット（/としてコード化）を暗号化するには、ユーザーは ${\displaystyle \textstyle 1}$${\displaystyle \textstyle -1}$${\displaystyle \textstyle m\in {\mathcal {M}}}$${\displaystyle \textstyle ID}$

1. ランダムに選択し、${\displaystyle \textstyle t_{1}}$${\displaystyle \textstyle m=\left({\frac {t_{1}}{n}}\right)}$
2. は とは異なる を含む ランダムな値を選択します。${\displaystyle \textstyle t_{2}}$${\displaystyle \textstyle m=\left({\frac {t_{2}}{n}}\right)}$${\displaystyle \textstyle t_{1}}$
3. 計算し、 そして${\displaystyle \textstyle c_{1}=t_{1}+at_{1}^{-1}{\pmod {n}}}$${\displaystyle c_{2}=t_{2}-at_{2}^{-1}{\pmod {n}}}$
4. ユーザーに送信します。${\displaystyle \textstyle s=(c_{1},c_{2})}$

ユーザの暗号文を復号するには、 ${\displaystyle s=(c_{1},c_{2})}$${\displaystyle ID}$

1. かどうかを計算し、${\displaystyle \alpha =c_{1}+2r}$${\displaystyle r^{2}=a}$${\displaystyle \alpha =c_{2}+2r}$
2. を計算します。${\displaystyle m=\left({\frac {\alpha }{n}}\right)}$

ここで、暗号化エンティティはが の平方根を持つか の平方根を持つかを知らないことを前提としていることに注意してください。 この場合、両方のケースの暗号文を送信する必要があります。 暗号化エンティティがこの情報を知ると、送信する必要がある要素は 1 つだけです。 ${\displaystyle ID}$ ${\displaystyle r}$${\displaystyle a}$${\displaystyle -a}$

まず、 (すなわち)かつ であるため、または はを法とする平方剰余であることに注意してください。 ${\displaystyle \textstyle p\equiv q\equiv 3{\pmod {4}}}$${\displaystyle \left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1}$${\displaystyle \textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)}$${\displaystyle \textstyle a}$${\displaystyle \textstyle -a}$${\displaystyle \textstyle n}$

したがって、はの平方根です。 ${\displaystyle \textstyle r}$${\displaystyle \textstyle a}$${\displaystyle \textstyle -a}$

${\displaystyle {\begin{aligned}r^{2}&=\left(a^{(n+5-pq)/8}\right)^{2}\\&=\left(a^{(n+5-pq-\Phi (n))/8}\right)^{2}\\&=\left(a^{(n+5-pq-(p-1)(q-1))/8}\right)^{2}\\&=\left(a^{(n+5-pq-n+p+q-1)/8}\right)^{2}\\&=\left(a^{4/8}\right)^{2}\\&=\pm a\end{aligned}}}$

さらに、（ が平方剰余の場合、 についても同じ考え方が成り立ちます） ${\displaystyle \textstyle a}$${\displaystyle \textstyle -a}$

${\displaystyle {\begin{aligned}\left({\frac {s+2r}{n}}\right)&=\left({\frac {t+at^{-1}+2r}{n}}\right)=\left({\frac {t\left(1+at^{-2}+2rt^{-1}\right)}{n}}\right)\\&=\left({\frac {t\left(1+r^{2}t^{-2}+2rt^{-1}\right)}{n}}\right)=\left({\frac {t\left(1+rt^{-1}\right)^{2}}{n}}\right)\\&=\left({\frac {t}{n}}\right)\left({\frac {1+rt^{-1}}{n}}\right)^{2}=\left({\frac {t}{n}}\right)(\pm 1)^{2}=\left({\frac {t}{n}}\right)\end{aligned}}}$

この方式を破ることは、非常に困難であると考えられている二次剰余問題 を解くことと同等であることが示されています。 RSA モジュラスを選択するための一般的なルールは、安全な を使用し、均一でランダムなを選択し、さらに の信頼性チェックを含めることです(そうしないと、単一ビットを送信するパケットを変更し、オラクルを使用して復号化されたビットへの影響を観察することで 、適応型選択暗号文攻撃を仕掛けることができます)。${\displaystyle \textstyle n}$${\displaystyle \textstyle t}$${\displaystyle \textstyle t}$

この方式の主な欠点は、メッセージをビット単位でしか暗号化できないことです。したがって、セッション キーのような小さなデータ パケットにしか適していません。説明のために、1024 ビット モジュラスを使用して送信される 128 ビット キーを考えてみましょう。この場合、2 × 128 × 1024 ビット = 32 KByte (がaの 2 乗か - a かが不明な場合) を送信する必要があり、これはセッション キーが頻繁に変更されない環境でのみ許容されます。 ${\displaystyle r}$

この方式では鍵のプライバシーは保持されません。つまり、受動的な敵対者は暗号文を観察することで受信者の身元に関する意味のある情報を復元できます。