マックエリス暗号

Summarize Timeline Top Qs Fact Check

マックエリス暗号は，鍵を生成する確率的アルゴリズム，暗号化をする確率的アルゴリズム，復号アルゴリズムの，３つのアルゴリズムから成る．マックエリス暗号を用いる全てのユーザは，共通のセキュリティパラメータ ${\displaystyle n,k,t}$ を用いる．

暗号の原理は，鍵生成者アリスが，効率的な復号アルゴリズムが分かっている符号 ${\displaystyle C}$ を（何らかの線形符号の族から）選び，符号 ${\displaystyle C}$ を公開するが復号アルゴリズムは秘密に保つ，というものである．符号${\displaystyle C}$の復号には，符号${\displaystyle C}$の生成行列の知識だけではなく，符号の族から${\displaystyle C}$を選び出したときに用いたパラメータを必要とする．例えば，二元ゴッパ符号においては，復号にはゴッパ多項式とcode locatorsが必要である．したがって，アリスは適切に難読化された ${\displaystyle C}$の生成行列を公開することができる．

より具体的には，鍵は以下のように生成される．

1. アリスは，何らかの符号の族（例えば，二元ゴッパ符号．この族には多数の符号が含まれている必要がある．）から，${\displaystyle t}$ビット誤りを効率的に訂正可能な二元${\displaystyle (n,k)}$-符号 ${\displaystyle C}$ を選ぶ．効率的な復号アルゴリズムを ${\displaystyle A}$ とする．また，符号${\displaystyle C}$ の生成行列（の一つ）を ${\displaystyle G}$ とする．線形符号は多くの生成行列を持つが，大抵の場合，自然な生成行列の選択が存在する．そのような生成行列は ${\displaystyle A}$ を明らかにしてしまう場合があるため，秘密にしておかなければならない．
2. アリスは，${\displaystyle k\times k}$ の正則行列 ${\displaystyle S}$ をランダムに選ぶ．
3. アリスは ${\displaystyle n\times n}$ の置換行列 ${\displaystyle P}$ をランダムに選ぶ．
4. アリスは ${\displaystyle k\times n}$ 行列 ${\displaystyle {\hat {G}}=SGP}$ を計算する．
5. アリスの公開鍵は ${\displaystyle ({\hat {G}},t)}$ であり，秘密鍵は ${\displaystyle (S,P,A)}$ である．なお，復号アルゴリズム ${\displaystyle A}$ は符号 ${\displaystyle C}$ の選択に使ったパラメータによって定まるため，このパラメータのみを記憶すれば良い．

ボブがメッセージ ${\displaystyle m}$ をアリスに送りたいとしよう．アリスの公開鍵＝暗号化のための鍵が ${\displaystyle ({\hat {G}},t)}$ であるならば，ボブは以下のように ${\displaystyle m}$ を暗号化する．

1. ボブはメッセージ ${\displaystyle m}$ を長さ ${\displaystyle k}$ のビット列として表現する．
2. ボブは，ベクトル ${\displaystyle c^{\prime }=m{\hat {G}}}$ を計算する．
3. ボブは，${\displaystyle n}$ビットのベクトルであり，ちょうど ${\displaystyle t}$ 個の要素が１（残りは０）であるようなベクトル ${\displaystyle z}$ をランダムに生成する．（つまり，ベクトル ${\displaystyle z}$ の長さは ${\displaystyle n}$ で重みが ${\displaystyle t}$．）^[1]
4. ボブは暗号文として ${\displaystyle c=c^{\prime }+z}$ を計算する．

暗号文 ${\displaystyle c}$ を受け取った時，アリスは次のようにして復号して元のメッセージを得る．

1. アリスは ${\displaystyle P}$ の逆行列 ${\displaystyle P^{-1}}$ を計算する．
2. アリスは ${\displaystyle {\hat {c}}=cP^{-1}}$ を計算する．
3. アリスは復号アルゴリズム ${\displaystyle A}$ を使って ${\displaystyle {\hat {c}}}$ を復号し，復号結果 ${\displaystyle {\hat {m}}}$ を得る．
4. アリスは ${\displaystyle m={\hat {m}}S^{-1}}$ を計算する．${\displaystyle m}$ が元のメッセージである．

暗号化と復号の手順より，${\displaystyle {\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}}$ が成り立ち，${\displaystyle P}$ が置換行列であるため${\displaystyle zP^{-1}}$ は重み ${\displaystyle t}$ のベクトルである．

ゴッパ符号 ${\displaystyle G}$ は最大 ${\displaystyle t}$ 個のエラーを訂正することができ，ベクトル ${\displaystyle mSG}$ と ${\displaystyle cP^{-1}}$ との距離は高々 ${\displaystyle t}$ である．したがって，復号アルゴリズムによって正しい符号語 ${\displaystyle {\hat {m}}=mS}$ が得られる．

${\displaystyle S}$ の逆行列をかけることで，${\displaystyle m={\hat {m}}S^{-1}=mSS^{-1}}$ が得られ，これはボブが送ったメッセージに等しい．

初めの論文でマックエリスはパラメータとして ${\displaystyle n=1024,k=524,t=50}$ を提案していた．^[1] その場合，公開鍵のサイズは 524*(1024-524) = 262,000 ビットである． 最近の解析により，80ビット安全を達成するためのパラメータとしては，標準的な代数的復号を使う場合は ${\displaystyle n=2048,k=1751,t=27}$，ゴッパ符号に対するリスト復号を用いる場合は${\displaystyle n=1632,k=1269,t=34}$ とすることが提案されており，公開鍵長はそれぞれ 520,047ビット，460,647ビットとなる．^[5] 量子コンピュータでの解読に耐性を持たせるためには，ゴッパ符号を用いる場合は ${\displaystyle n=6960,k=5413,t=119}$ とすることが提案されており，公開鍵長は 8,373,911ビットになる．^[8]