マックエリス暗号
また,符号 C {\displaystyle C} の生成行列(の一つ)を G {\displaystyle G} とする.線形符号は多くの生成行列を持つが,大抵の場合,自然な生成行列の選択が存在する.そのような生成行列は A {\displaystyle A} を明らかにしてしまう場合があるため,秘密にしておかなければならない.
アリスは, k × k {\displaystyle k\times k} の正則行列 S {\displaystyle S} をランダムに選ぶ.
アリスは n × n {\displaystyle n\times n} の置換行列 P {\displaystyle P} をランダムに選ぶ.
アリスは k × n {\displaystyle k\times n} 行列 G ^ = S G P {\displaystyle {\hat {G}}=SGP} を計算する.
アリスの公開鍵は ( G ^ , t ) {\displaystyle ({\hat {G}},t)} であり,秘密鍵は ( S , P , A ) {\displaystyle (S,P,A)} である.なお,復号アルゴリズム A {\displaystyle A} は符号 C {\displaystyle C} の選択に使ったパラメータによって定まるため,このパラメータのみを記憶すれば良い.
暗号の原理は,鍵生成者アリスが,効率的な復号アルゴリズムが分かっている符号 C {\displaystyle C} を(何らかの線形符号の族から)選び,符号 C {\displaystyle C} を公開するが復号アルゴリズムは秘密に保つ,というものである.符号 C {\displaystyle C} の復号には,符号 C {\displaystyle C} の生成行列の知識だけではなく,符号の族から C {\displaystyle C} を選び出したときに用いたパラメータを必要とする.例えば,二元ゴッパ符号においては,復号にはゴッパ多項式とcode locatorsが必要である.したがって,アリスは適切に難読化された C {\displaystyle C} の生成行列を公開することができる.
より具体的には,鍵は以下のように生成される.
アリスは,何らかの符号の族(例えば,二元ゴッパ符号.この族には多数の符号が含まれている必要がある.)から, t {\displaystyle t} ビット誤りを効率的に訂正可能な二元 ( n , k ) {\displaystyle (n,k)} -符号 C {\displaystyle C} を選ぶ.効率的な復号アルゴリズムを A {\displaystyle A} とする.