耐量子計算機暗号または耐量子暗号 (PQC：post-quantum cryptography) の候補として注目を集めている符号ベース暗号 (CBC：code-based cryptography)。 その中でも原始的かつ実用的なMcEliece暗号 (McEliece cryptosystem) についてまとめました。
準備 - Preparetion
Rを可換環とするとき、R上のm\times n行列全体の集合をR^{m\times n}と表す。 また、正方行列の各行および各列について、成分の一つが1でありそれ以外の成分が0であるとき、その行列を置換行列 (permutation matrix) とよぶ。 なお、n次の置換行列Pについて、j列目の成分1がある場所を\sigma(j)行目とすると、\sigmaは集合\{1, 2, \ldots, n\}からそれ自身への全単射 (n文字の置換) を定める。 このように置換\sigmaに対応する置換行列Pを考えると、逆写像\sigma^{-1}に対応する置換行列がPの逆行列となる。
構成方法 - Protocol
Definition 1.1 McEliece暗号 (McEliece cryptosystem)
McEliece暗号\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})は以下のように構成される：
-
\mathrm{Gen}(1^{\kappa})は、セキュリティパラメータ\kappaに応じて、復号が効率的な何らかの誤り訂正符号Cを選び、その生成行列G_{0}\in K^{k\times n}をつくる。 この誤り訂正符号Cの復号アルゴリズムを\mathrm{Dcd}、誤り訂正能力をtとする。 次に、正則なk次正方行列Sと、n次の置換行列Pをランダムに選び、G\coloneqq SG_{0}P\in K^{k\times n}を計算する。そして、公開鍵\mathrm{pk}と秘密鍵\mathrm{sk}を以下のように定める： \mathrm{pk}\leftarrow(G, t); \mathrm{sk}\leftarrow(S, G_{0}, P, \mathrm{Dcd}) 対応する平文空間は\mathcal{M} = K^{k}、暗号空間は\mathcal{C} = K^{n}とする。
-
\mathrm{Enc}_{\mathrm{pk}}(m) (m\in\mathcal{M})は、Hamming重みtのベクトルe\in K^{n}をランダムに選び、暗号文c\in K^{n}を以下のように定める： c\leftarrow mG + e.
-
\mathrm{Dec}_{\mathrm{sk}}(c) (c\in\mathcal{C})は、まず、ベクトルc'\leftarrow CP^{-1}\in K^{n}を計算し、それを誤り訂正符号Cの受信メッセージだと思って復号した結果w\leftarrow \mathrm{Dcd}(c')を計算する。 次に、連立方程式w = m'G_{0}を解いてベクトルm'\in K^{k}を得る。 そして\tilde{m}\leftarrow m'S^{-1}を復号結果とする。
復号方法 - Decoding Protocol
安全性 - Security
参考文献 - References
-
Robert J。McEliece：A Public-Key Cryptosystem Based on Algebraic Coding Theory。The Deep Space Network Progress Report、DSN PR 42-44、pp.114-116、1978。
-
縫田光司。耐量子計算機暗号。森北出版、東京、2020。
-
Marek Repka and Pierre-Louis Cayrel。Chpter 5 Cryptography Based on Error Correcting Codes: A Surevey、Multidisciplinary Perspectives in Cryptology and Information Security、pp.139-141、2014。