Hill Cipher とネットワークコーディングによる安全、高速かつパケットロスに耐性のある通信
西田博史
ASUSA Corporation, Salem Oregon, USA
概要—本稿は改良型 Hill Cipher（HC）とランダムネットワー
クコーディング（RNC）を組み合わせることにより、安全かつパケットロスに耐性のある通信が同時に実現できることについて解説する。HC と RNC の両者は、ともに一次連立方程式を作ること
によってデータを暗号化／エンコードし、それを解くことによって復号化／デコードする。本方法はそれら二つのアルゴリズムを融合させ、効率的に両者の特性を引き出す。さらに新たに開発した
高速ガロア体演算アルゴリズムを用いることにより、ハードウェ
アアクセラレーションの効いた AES-256 よりも高速な暗号化・復号化を実現する。本アルゴリズムを実装した QUIC プロトコルは、
パケットロスが起こる通信状態でスループットを大きく改善する。

I. 導入
1929 年に発表された Hill Cipher (HC) [1] は古典的な対称型暗号化アルゴリズムで、以下のような連立方程式に基づいてデータの暗号化・復号化を行う。
(暗号化)

c = Kp
p=K

−1

c

(復号化)

(1)

p 平文
c 暗号文
K 共有鍵行列
R 行列 K の階数
この方式はシンプルで直感的であるが、既知平文攻撃に脆弱であることが知られており、そのため数多くの改良型が提唱されてきた [2]–[7]。これらの中には依然として脆弱なものもあるが、現時点で高い安全性を保持してると考えられているものも存在する。
ランダムネットワークコーディング (RNC) [8]–[13] は基本的に (1) と同様の方法でデータをエンコード・デコードす
るが、伝達ロスの大きい通信において、データの再送を減らすために冗長性を用いる。例えば (1) において R = 3, K
を 3 × 3 の行列、|p| = |c| = 3 とすると、(1) における暗号化部分はc0 =k0,0 p0 + k0,1 p1 + k0,2 p2

c1 =k1,0 p0 + k1,1 p1 + k1,2 p2(2)c2 =k2,0 p0 + k2,1 p1 + k2,2 p2 .

のように表される。RNC は例えば以下のように (2) にもう一つの方程式を足し、
c0 =k0,0 p0 + k0,1 p1 + k0,2 p2c =k p + k p + k p
1
1,0 0
1,1 1
1,2 2
(3)

c2 =k2,0 p0 + k2,1 p1 + k2,2 p2
c3 =k3,0 p0 + k3,1 p1 + k3,2 p3©2023 ASUSA Corporation, ASJ Inc.

のようにし、c0 · · · c2 に加え c3 も生成し、これら全てを受信側に送る。すると例え c0 · · · c3 の 1 つを失ったとしても、残り 3 つの ci から p0 · · · p2 を復号することができる。例えば c1 が失われたとし、

k0,0 k0,1 k0,2
K̂ =  k2,0 k2,1 k2,2  ,k3,0 k3,1 k3,2とする。すると受信者は




p0
c0
 p1  = K̂ −1  c2  .
p2
c3のようにデコードすることによって、元の平文 p を復元することができる。このようにして RNC はデータの冗長性と引き換えに、伝達ロスによるパケットの再送頻度を減少させる。通信時におけるパケットロスは、繰り返し行われる
データ再送要求のやり取りのため、著しくスループットを落とす原因となり、円滑な通信の妨げとなる。RNC はそれを大きく改善する役割を果たす。
RNC の欠点の 1 つにエンコード・デコードにかかるコストが高いということが挙げられる。平文の通信に RNC を用いることは、余分な CPU の使用とメッセージ伝達の遅延をもたらすことになる。しかし元のデータが暗号化されるという前提の場合、もし RNC がその暗号化を兼ねるとすれば、その欠点が打ち消される。これが本通信法の狙いである。
通常 (1) (2) (3) のような暗号化・復号化における計算はガロア体で行われる。そのためガロア体における計算速度
が暗号化・復号化の実速度を大きく左右する。実際に我々のアルゴリズムは、使用するガロア体演算ライブラリーによって大きく処理速度が異なることを検証結果より得ている。我々は以前に開発した高速ガロア体演算ライブラリー[14] に新たなアルゴリズムを追加し、それを使用することによって、アルゴリズム内の暗号化・復号化部分の高速化に成功している。第 V 章で AES-NI によるハードウェアア
クセラレーションの効いた OpenSSL の AES-256 と比較しているが、実際にそれよりも高速な暗号化・復号化を実現していることが示されている。
本稿では改良型 HC と RNC の詳細について第 II、III 章で述べ、第 IV 章で我々のアルゴリズムについて解説している。
そして通信時における我々のアルゴリズムのスループット
および処理速度の測定結果を第 V 章に記している。

II. 関連研究
既知平文攻撃に対処するため、多くの改良型 HC が提唱されてきた。Augmented Hill Cipher [2] は 3 つの鍵行列を用
い、新しく暗号化されたデータと一つ前の暗号化時に生成されたデータとの排他的論理和 (⊕ または XOR) を繰り返すことによって既知平文攻撃を始めとした攻撃に対処している。またさらに + と ⊕ の演算を組み合わせることによって、様々な攻撃に対する耐性を高めており、 既知平文攻撃を始め、選択平文攻撃、暗号文単独攻撃、辞書攻撃、総当
たり攻撃、フォールト攻撃の全てに対して安全であると結論づけている。詳細は第 III 章を参照していただきたい。この方法は現時点で我々の知る限り脆弱性が見つかっておらず、我々の提唱するアルゴリズムの暗号化・復号化の部分にこのアルゴリズムを拡張したものを用いている。
[7] は可逆行列を公開鍵、巡回行列を秘密鍵にした改良型 HC を紹介しているが、[2] において複数の脆弱性が指摘されている。その他の改良型 HC には、アフィン暗号化と組み合わせたものがいくつか存在する [3], [15]。これらは平文を構成するアルファベットをシンプルな関数で変換することによって暗号化・復号化を行う。また [16] は非正方な鍵行列を用いて暗号化されたデータに冗長性を持たせている。しかしこれは安全性のためであり、RNC のように通信における冗長性には使用されていない。
[8], [9] は RNC によりどれほどパケットロスが効率的に対処されるかを説明している。特に [9] は RNC を TCP に実装し、伝達ロスが起こる通信でスループットが劇的に改善されることを示している。[17]–[20] は RNC を用いた安全な通信について述べているが、これらは多数の中間ノードが存在するネットワークで複数の経路を通ってデータが伝達されることを前提としており、一対一通信での安全性を保証していない。我々の調査では、RNC を安全な一対一の通信に特化して利用した研究は見つかっていない。
QUIC [21] は TCP で見られる様々な問題を解決するために新たに開発されたネットワークプロトコルであり、HTTP/3
で採用される唯一のプロトコルである。QUIC は UDP 上に実装され、TCP よりも低レイテンシーで、トラフィックの混雑やパケットロスを効率的に制御できるように設計されている。本稿では我々のアルゴリズムの有効性を実証する
ために、QUIC にアルゴリズムを実装し、スループットの測定を行っている。

Algorithm 1 Augmented Hill Cipher における暗号化′
1: C−1= K2
2: for i ← 0 to N − 1 do

3:Ci′ ← (Ki mod 3 Pi + K(i+1) mod 3 ) mod n′
4:
Ci ← Ci′ ⊕ Ci−1
5: end forFig. 1: Augmented Hill Cipher における暗号化を Ci′ として保存し、Ci′ から K(i+1) mod 3 を引いたものに
Ki−1mod 3 を掛けることによって平文 Pi を復号させる。

Algorithm 2 Augmented Hill Cipher における復号化′= K2
1: C−1

2: for i ← 0 to N − 1 do′
3:Ci′ ← Ci ⊕ Ci−1
−1

4:Pi ← (Ki mod 3 (Ci′ − K(i+1) mod 3 )) mod n
5: end forFig. 2: Augmented Hill Cipher における復号化

III. AUGMENTED H ILL C IPHER
本章では [2] で紹介されている Augmented Hill Cipher(AHC) について以下の表記を用いて解説する。

R
n
P
C
K

行列の階数
モジュラス
p（平文）の R × R 行列型
c（暗号文）の R × R 行列型
R × R な共有鍵行列

A. アルゴリズム
AHC は 3 つの共有鍵行列 K0 , K1 , K2 を用い、アルゴリ
ズム 1 や図 1 のように平文を暗号化する。 アルゴリズム 1の 3 行目に見られるように、まず Ki と i 番目の平文 Pi の積を取り、それに K(i+1) mod 3 を足す。その結果は Ci′ として Ci+1 を求める際のために保存しておく。そして Ci′ と′Ci−1の排他的論理和が i 番目の暗号文 Ci となる。
復号化は暗号化と全く逆の手順でアルゴリズム 2 や図 2′のように行われる。まず暗号文 Ci と Ci−1の排他的論理和B. 安全性の分析
暗号化時、AHC は初めに (K0 mod 3 P0 +K(1) mod 3 ) mod n′と C−1(= K2 ) の排他論理和を取り（図 1 の一番左参照）、元のデータの先頭部分である P0 が 容易に判明されないようにしている。その後、新しく暗号化されたデータと 1 つ前に暗号化されたデータの排他論理和を取ることにより、後続データの安全性を確保している。また + と ⊕ の演算を組み合わせることで、より安全性を高めている。
鍵長に関しては、n = 2α のモジュラスで構成される R×Rの正則行列の数は

l=2(α−1)R2R−1∏(2R − 2k )k=0であり [22]、これが AHC における Ki (0 ≤ i ≤ 2) の各々の鍵長となる。ここで n = 216 、R = 8 ならば l ≈ 21022 となり、AHC の全鍵長は 21022×3 = 23066 となる。これは鍵長として充分な長さで、また AHC は n, R の値や K の数を増やすことにより、さらに鍵長を伸ばすことも可能である。
これらにより、第 II 章と [2] の第 6 章に記述されてる通り、AHC は一般的な攻撃に対しての耐性を保持しているものと考えられる。
とは言え、将来 AHC に脆弱性が見つかることは大いにあり得る。現在我々のアルゴリズムは AHC をベースにしているが、AHC に脆弱性が見つかれば他の改良型 HC へ移行する。本稿では AHC は現時点では安全だと仮定し、改良型
HC の一例として用いる。

IV. H ILL C IPHER + ネットワークコーディング
この章では本法である HNC (= Hill Cipher + Network
Coding) の詳細について以下の表記を用いて解説する。
R
行列の階数
n
各データのサイズまたはガロア体の大きさ (= 216 ま
たは 28 )
M
SIMD によって決定される処理されるデータ数 (= 32)
P
p（平文）の R × M 行列型
C
c（暗号文）の R × M 行列型
K
R × R な共有鍵行列
Kβ R × M な共有鍵行列′
KC−1
R × M な共有鍵行列

A. Augmented Hill Cipher の実装
暗号化と復号化の実処理速度を最大限にするために、我々は実装において AHC に若干手を加える必要があった。まず我々は Ki mod 3 Pi といった行列の積にガロア体（GF）での演算を用いるが、検証時に実際の演算速度は、使用する
ガロア体演算ライブラリーに大きく左右することが分かった。そのため、我々は以前に開発した gf-nishida-16 [14] に
新たに AVX や NEON といった SIMD を使用するアルゴリ
ズムを加え、GF (216 )、GF (28 ) における現時点で知りう
る限り最も高速な領域積演算を実現し、それを採用した。
ガロア体の大きさについては、GF (232 ), GF (264 ), ... と指数関数的に大きくなるほど共有鍵長も指数関数的に長くなりより安全度を増すが、多くの GF ライブラリーにおいて
GF (2α ) (α = 8, 16, 32, 64, · · · ) のデータを処理するためにかかる計算量は O(α) であり、例えば GF (232 ) での計算量
は GF (216 ) の約倍となる。そのため α ≥ 32 ではコストが高すぎると判断し、α = 8, 16 を用い、代わりに新たなる共′有鍵である 3 つの Kβ と KC−1を導入することとした。
AVX, SSE や NEON といった SIMD は基本的に 512, 256
または 128bit 単位でデータを処理する。A が R × R で B
が R × M のような行列同士の積 AB に gf-nishida-16 を使用する場合、B の各行のデータの合計サイズは GF (216 ) では 512bit、GF (28 ) では 256bit である必要がある。ここで512/16 = 256/8 = 32 であるため、M = 32 となり、結果的に平文行列 P と暗号文行列 C のサイズは R × 32 となる。
これにより次章に記すように、AHC の暗号化・復号化アル
ゴリズムに変更を加える必要があった。

B. 冗長性のない HNC のアルゴリズム
AHC の暗号化では Ki mod 3 Pi と K(i+1) mod 3 の両者はともに R × R の行列であった（アルゴリズム 1 の 3 行目参照）。しかし冗長性のない HNC (HNCn) では Ki mod 3 Pi は
R × 32 であるのに対して、 K(i+1) mod 3 は R × R であるた

め、行列の大きさに差異が生じる。そのため我々は新しい′を導入する。これ
R × 32 な鍵行列 Kβ0 , Kβ1 , Kβ2 と KC−1
により HNCn の暗号化アルゴリズムはアルゴリズム 3 と図
3 のようになり、復号化アルゴリズムはアルゴリズム 4 と
図 4 のようになる。なおこれら新しい鍵行列は鍵長をさらに長くするため、HNC の安全性向上につながる。

Algorithm 3 冗長性のない HNC における暗号化′′
1: C−1= KC−1
2: for i ← 0 to N − 1 do
3:Ci′ ← (Ki mod 3 Pi + Kβ i mod 3 ) mod n′
4:
Ci ← Ci′ ⊕ Ci−1
5: end forFig. 3: 冗長性のない HNC における暗号化
Algorithm 4 冗長性のない HNC における復号化′′
1: C−1= KC−1
2: for i ← 0 to N − 1 do′
3:Ci′ ← Ci ⊕ Ci−1
−1

4:Pi ← (Ki mod 3 (Ci′ − Kβ i mod 3 )) mod n
5: end forFig. 4: 冗長性のない HNC における復号化
C. 安全性の分析′ ）とまず、HNCn は新しく追加された鍵行列（Kβ s, KC−1
拡張された行列の大きさを除けば、AHC と同じアルゴリズ
ムを使用する。そのためアルゴリズムの観点から、HNCn はAHC 以上に安全だと言える。次に HNC の鍵長を求める。
K0 , K1 , K2 は R × R 行列であるが、正則行列でなくてはいけない。GF (2α ) な要素で構成される正則な R × R 行列
の数は
R−1
∏
l=
(2αR − 2αk )
(4)

k=0

である [23]。従って n = 216 , 28 と R = 4, 6 に対する K0 ,K1 , K2 の各々の鍵長は表 I の 2 行目のようになる。また

n = 216
R=4

n = 216R=6n = 28R=4n = 28R=6255.99997

575.99997

127.994287.994

各 Kβ 2048

3072

1024

1536

KC ′

2048

3072

1024

1536

合計

8959.99991 14015.99991 4479.982 7007.982

各K−1

Algorithm 6 冗長性を持った HNC における復号化′
1: Ĉ−1= K̂Ĉ ′−1

2: for i ← 0 to N − 1 do
3:Ĉi において、失われた行 r ∈ [0, R] を特定する。
4:
if パケットロスが見当たらない thenTABLE I: HNC における鍵長 (bit)′Kβ の各々と KC−1
は 216 の要素より成る R × 32 行列であり、さらに制限はないためそれらの鍵長は表 I の 3 と 4 行
目のようになる。HNC における鍵の全長は

{

2
∏

′ ),
(Key len of Ki )(Key len of Kβi )}(Key len of KC−1

(5)

i=0

であるため、 n = 216 , 28 , R = 4, 6 における HNC の鍵長は
表 I の最後の行のようになる。これらより、AHC が安全であれば HNCn は安全だと言える。

D. ランダムネットワークコーディングの実装
この章ではどのようにして RNC を HNC に組み込み、冗長性を持った HNC (HNCr) を作り出すかを解説する。第 I章で述べたように、鍵行列に新たな行を足すことによって通信に冗長性がもたらされ、パケットロスに耐性ができる。
これが RNC の原理であるが、これを前章で説明した HNCに導入する。本章で用いる表記は以下の通りである。なお
冗長度は 1 とする。
K̂(R + 1) × R 共有鍵行列
K̂β(R + 1) × 32 共有鍵行列
K̂Ĉ ′(R + 1) × 32 共有鍵行列−1

c の (R + 1) × 32 行列型
Ĉ
A(r) A から r 番目の行を取り除いた行列
L
パケットロス率 (0 ≤ L ≤ 1)
アルゴリズム 3, 4 はそれぞれアルゴリズム 5, 6 に置き換えられる。
Algorithm 5 冗長性を持った HNC における暗号化′
1: Ĉ−1= K̂Ĉ ′−1

2: for i ← 0 to N − 1 do
3:Ĉi′ ← (K̂i mod 3 Pi + K̂β i mod 3 ) mod n′
4:Ĉi ← Ĉi′ ⊕ Ĉi−1
5: end for

送信者は Ĉi の各行を別々のパケットで送信する。Ĉi の
r 番目 (0 ≤ r ≤ R) の行のデータをパケット r で送信するとすると、たとえ R + 1 個あるパケットの 1 つが失われたとしても、受信者は残り R 個のパケットから平文 Pi を復号することができる。パケットロス率 L = 0 の時は冗長性のためスループットは 1/(R + 1) 減少する。しかしそれ以外の際はパケットロスによるパケット再送回数を減らし、ス
ループットを大きく改善する。冗長性がない場合、パケッ
トロスが起こる度に送信者は失われたパケットを再送しなくてはならない。冗長度が 1 でパケットロスが起こった場
合、R + 1 個ある同じ Ĉi 内の行のデータのうち、別の行のr ← 任意の値 ∈ [0, R].
P acketLoss ← F alseelse
P acketLoss ← T rue
end if′Ĉi′ ← Ĉi ⊕ Ĉi−1
(r)
′(r)
(r)
11:
Pi ← (K̂i mod 3 )−1 (Ĉi − K̂β i mod 3 )) mod n
12:
if P acketLoss then13:
アルゴリズム 5 を用いて、失われた Ĉi′ の r 番目の行を Pi から作る
14:
end if
15: end for
5:
6:
7:
8:
9:
10:

データを含むパケットも失われた際にのみ送信者は再送を要求される。その確率は

1 − (1 − L)R(6)

で、再送率は (1 − L)R 減少することになる。これは例えば
L = 0.01, R = 4 で 1 − (1 − 0.01)4 = 0.04 となり、パケッ
トロス率が 1%ならば、失われたパケットの 4%にのみ再送を要求すればいいことを意味する。このように冗長性の実
装は再送回数を激減させ、スループットの向上に寄与することが分かる。実際に L = 0.01, R = 4 でスループットは、
第 V-C 章に見られるように 200%増加している。
安全性に関しては、HNCr をクラックする方法が存在すると仮定すると、HNCn は HNCr の特殊なケースとして捉えることができるので（例: 全ての K の R 番目の行が R − 1 番
目の行と同一）、HNCn も同様に簡単にクラックすることができる。つまり HNCr の安全性は HNCn 以上であり、AHCが安全であれば HNCr も安全であると言える。

V. 測定結果
A. TCP におけるスループット
この章ではローカルホスト上の TCP 通信におけるスルー
プットと処理速度を OpenSSL（AES-NI アクセラレーション
付、TLS AES 256 GCM SHA384 アルゴリズム）と HNCnの n = 216 , 28 , R = 4, 6 とで比較する。CPU には AMD
Ryzen 7 5800X と Apple M1 を用い、暗号化または復号化と通信処理はすべて同一のシングルスレッドで行っている。
結果は図 5 に見られるように、Apple M1 での n = 216 ,R = 6 (HNCn-16bit-6) 以外は OpenSSL よりも HNCn の方が高いスループットを記録している。特に Ryzen 7 での
HNCn-8bit-4 と HNCn-16bit-4 のスループットは、それぞれOpenSSL の 3 倍と 2.5 倍と特に高くなっている。
行列の積のコストが HNCn の R = 4 と 6 での結果の差として現れている。アルゴリズム 3、4 における行列の積の計
算量は O(R3 ) で、R = 6 は明らかに R = 4 よりもスルー
プットが低くなっている。表 I にあるように、R = 4（特Fig. 6: ローカルホスト上での QUIC 通信における OpenSSL とFig. 5: ローカルホスト上での TCP 通信における OpenSSL と HNCnのスループット値の比較。HNCn の殆どが OpenSSL より高いス
ループット値を示している。

TABLE II: ローカルホスト上での TCP 通信における HNCn のOpenSSL に対する処理速度（SHNCn /SOpenSSL ）の比較。HNCn の殆どが OpenSSL よりも速いが、Ryzen 7 と M1 の間で差がある。

に n = 216 ）でも鍵長は充分な長さが保持されているので、
HNC には R = 4 の方が望ましいと考えられる。
アルゴリズムによって暗号化や復号化の処理速度が変わるのはもちろんであるが、アルゴリズムによってもたらされるオーバーヘッドの量も異なってくる。ここで対象のアルゴリズム（Algo）における処理速度を測る基準値として以下のメトリックを用いる。
()
1
1
SAlgo = 1/−,
(7)
T PAlgoT PNon-crypto
ここで T P はスループット値を表し、平文でのスループッ
ト値である T PNon-crypto は Ryzen 7 で 126.55Gbps、M1 で105.58Gbps である。表 II はその SHNCn /SOpenSSL 値を表している。OpenSSL に対して HNCn は Ryzen 7 で 2.2 から 4.3倍の処理速度を示しており、M1 では 0.9 から 1.9 倍の処理速度を示している。R = 4 の HNCn は OpenSSL よりも高速にデータを処理することが分かるが、M1 での値は Ryzen 7での値よりも全般的に低くなっている。これは ARM NEONのレジスターのサイズによるものと考えられ、AVX の 256bit
に対し NEON は半分の 128bi しかないことが原因だと思われる。実際に同じ 128bit のレジスターを持つ SSE は、AVX
よりも処理速度が 30%落ちることが我々の実験で判明している。高速な暗号化・復号化のためにはレジスターのサイズが大きい SIMD を用いる方が望ましい。

B. QUIC におけるスループット
QUIC は暗号化された多重化接続と低遅延などを実現するプロトコルで、従来の HTTPS のトラフィックにおける問題点を様々な点で改善している [24]。QUIC ではデータが暗号化されることが前提となっているため、HNC を実装するには最適なプラットフォームであると考えられる。
QUIC を実装するオープンソースプロジェクトは幾つか存在するが、Microsoft が主導する MsQuic [25] は最もコードのコミットが多いプロジェクトの一つで、Linux と MacOS
では OpenSSL を暗号化アルゴリズムとして使用している。
我々は HNCn を MsQuic に組み込み、前章と同じ条件でス
ループットと処理速度を測定した。

HNCn のスループット値の比較。HNCn-16bit-6 を除く HNCn がOpenSSL より高いスループット値を示している。

TABLE III: ローカルホスト上での QUIC 通信における HNCnの OpenSSL に対する処理速度（SHNCn /SOpenSSL ）の比較。M1 の
HNCn-8bit-4 で異常に高い値が見られる。

結果は図 6 と表 III に示される通りであり、T PNon-crypto はRyzen 7 で 6.31Gbps、M1 で 4.80Gbps である。 HNCn-16bit6 を除く HNCn が OpenSSL よりも高いスループット値を示しているが、TCP に比べると差は小さい。処理速度に関しては、SHNCn /SOpenSSL の値が Ryzen 7 で TCP ほど高くなっていないが、M1 では HNCn-16bit-6 を除いて高くなっている。
注意して頂きたいのは、我々の実装は現時点でパケット長を有効に利用しておらず、QUIC においてあまり効率のいいデータ処理がなされていないという点である。QUIC は
UDP 上に構築されたプロトコルであるため、各パケットとそれに含まれるペイロードのサイズは MTU のサイズによって決められる。1500byte の MTU に対して、QUIC における一般的なペイロード長は 1450byte 以上であり、MsQuic は
そのペイロードになるべく沢山のデータを詰め込むように設計されている。しかしながら HNC はブロック暗号アルゴリズムであり、HNCn において最も理想的なペイロード
長は、n = 216 で 64 × R × N （N は自然数）、n = 28 で
32 × R × N である。MTU 長 1500byte、R = 4 におけるそれらの上限値は n = 216 で 64 × 4 × 5 = 1280byte、n = 28
で 32 × 4 × 8 = 1408byte であり、R = 6 ではそれぞれ
64 × 6 × 3 = 1152byte、32 × 6 × 7 = 1344byte となる。このように HNCn における理想的なペイロード長は一般的な
QUIC でのペイロード長よりも短く、これが TCP の際と比べも非効率になる原因となり、Ryzen 7 での測定結果で低い
SHNCn /SOpenSSL 値として現れているものと考えられる。現時点でどうして HNCn-8bit-4 を除く M1 での SHNCn /SOpenSSL
値が TCP 時よりも高いのか判明していない。これについての調査と、HNCn でのペイロード長の最適化が今後の課題である。

C. パケットロスが起こる通信でのスループット
パケットロスが見られない通信では冗長付きの HNC(HNCr) は必要ない。しかしパケットロスがわずかでも定常的に観測されるような環境であれば、スループット改善のため、HNCr に移行すべきである。我々は HNCr を扱えるよ
うに MsQuic に手を加え、パケットロスが起こる通信環境をエミュレートし、MsQuic のデフォルト暗号化アルゴリズム

Fig. 7: パケットロスが起こる QUIC 通信での冗長付き HNC (HNCr)と OpenSSL (No Redundancy) でのスループット値の比較。HNCr
が OpenSSL よりも全範囲で高いスループット値を示している。

である OpenSSL とのスループットを比較した。HNCr の冗
長度は 1 である。パケットロスのエミュレーションは、パケットロス率 L に従って意図的に MsQuic 内部で受け取ったパケットが落とされるように処理し、また Linux の tc コ
マンドを用いて帯域を 60Mbps に、ネットワークの遅延を50ms に設定した。
結果は図 7 および以下の通りである。
1) HNCr のスループットは全域に渡って OpenSSL よりも高くなっている。全体での平均 T PHNCr /T POpenSSL
は 3.08 である。
2) HNCr は L = 0.1–0.5% で OpenSSL よ り も 遥
かに高いスループットを記録している。そこでのT PHNCr /T POpenSSL は 2.69 から 5.00 である。しかしながら L = 1.5% 付近では HNCr と OpenSSL のスルー
プット値が接近している。
3) HNCr 同士での違いはさほどないが、L = 1.0% で R =4 と 6 間で若干差がある。
4) OpenSSL は L = 0 と 0.1% の間でスループットに大きな落ち込みが見られる。しかしその後 L = 0.5% まで
は若干値が回復し、それ以降は緩やかに下がっている。
5) HNCr-*-4 と HNCr-*-6 のスループットはそれぞれ L =0.5–1.5% と L = 0.5–1.0% で著しく落ちている が、その後は安定している。
HNCr の長所は 1) で見られるが、2) は T PHNCr /T POpenSSL s
が一定でなく L によって大きく変わることを意味している。
4) と 5) の原因については現時点では分かっていないが、おそらく MsQuic の設計と実装によるものだと思われる。
QUIC はかつてグループ内におけるパケットロスを補完するために前方誤り訂正（FEC）をサポートしていたが、効果が限定的であったため削除された。また FEC はわずかに動画再生の遅延と再バッファリング率を増加させることが報告されており、使用帯域の増加に見合った利点が得られないと結論付けられている [24]。我々は HNCr がもたらす全ての影響を測定したわけではないが、HNCr はこの FECの代替となる可能性を持っている。

VI. 今後の課題
HNC が有線よりも無線通信に適していることは間違いない。我々はその中でも HNC は衛星通信と非常に親和性が高いと考えており、衛星通信が求める「盗聴と妨害電波に強く、安全で安定した通信」という条件を満たすことができるものと考えている。衛星通信が Ch0 , Ch1 , ..., ChR の R + 1
個のチャンネルを持っているものとする。ここで第 IV-D 章
で述べたパケット r を Chr mod (R+1) で送信するとすると、
もしチャンネルの 1 つが妨害されたとしても、受信者は残りのチャンネルで送られてきたパケットより元のデータを復号することができる。またたとえ全チャンネルのパケッ
トが盗聴されたとしても、HNC により暗号化されたデータを復号することはほぼ不可能である。このようにして HNCは安全で安定した衛星通信を実現する可能性があり、今後これについての研究を進めていくことを課題としている。また第 V-B 章で述べた通り、我々の MsQuic での実装は定められたパケット長に対して最適なデータ送信を実現できていない。これに対する最適化を検討する必要がある。AHCを始めとした改良型 HC の安全性にも注視しなくてはいけない。より安全な暗号化アルゴリズムを模索することは今後も不可欠であると思われる。

VII. 結論
本稿ではデータを安全かつ高速に暗号化・復号化し、パケットロスにも耐性のあるアルゴリズムを紹介した。我々の測定結果では、冗長性のない HNC は AES-256 よりも高速に暗号化・復号化を行い、冗長性を持った HNC はパケッ
トロスが起こる環境で従来よりもスループットを大きく改善することが示された。我々は本方法が円滑で信頼性の高い無線通信の発展に貢献し、より安全で快適なインターネッ
ト通信をもたらすものと信じている。

R EFERENCES[1] Lester S. Hill, “Cryptography in an algebraic alphabet,” The American
Mathematical Monthly, vol. 36, no. 6, pp. 306–312, 1929.
[2] Abdallah A. Alhabshy, “Augmented hill cipher,” International Journalof Network Security, vol. 21, pp. 812–818, 2019.
[3] Mohsen Toorani and Abolfazl Falahati, “A secure variant of the hill
cipher,” in 2009 IEEE Symposium on Computers and Communications,2009, pp. 313–316.
[4] Narendra B. Parmar and Kiritkumar Ramanbhai Bhatt, “Hill cipher
modiﬁcations: A detailed review,” International Journal of Innovative
Research in Computer and Communication Engineering, vol. 3, pp.
1467–1474, 2015.
[5] M.N.A. Rahman, A.F.A. Abidin, Kamir Yusof, and N.S.M. Usop,“Cryptography: A new approach of classical hill cipher,” International
Journal of Security and its Applications, vol. 7, pp. 179–190, 01 2013.
[6] Ahmed Mahmoud and Alexander Chefranov, “Secure hill cipher
modiﬁcations and key exchange protocol,” in 2010 IEEE International
Conference on Automation, Quality and Testing, Robotics, AQTR 2010
- Proceedings, 06 2010, vol. 2, pp. 1 – 6.
[7] K. Adinarayana Reddy, B. Vishnuvardhan, Madhuviswanatham, and
A.V.N. Krishna, “A modiﬁed hill cipher based on circulant matrices,”
Procedia Technology, vol. 4, pp. 114–118, 2012, 2nd International
Conference on Computer, Communication, Control and Information
Technology( C3IT-2012) on February 25 - 26, 2012.
[8] Desmond S. Lun, Muriel Médard, Ralf Koetter, and Michelle Effros,“On coding for reliable communication over packet networks,” CoRR,
vol. abs/cs/0510070, 2005.
[9] J. K. Sundararajan, D. Shah, M. Medard, M. Mitzenmacher, and J. Barros, “Network coding meets tcp,” in IEEE INFOCOM 2009, April 2009,
pp. 280–288.
[10] B. Li and D. Niu, “Random network coding in peer-to-peer networks:
From theory to practice,” Proceedings of the IEEE, vol. 99, no. 3, pp.
513–523, March 2011.
[11] Hiroshi Nishida and Thinh Nguyen, “Rncdds - random network coded
distributed data system,” in 2017 IEEE International Conference on
Multimedia Expo Workshops (ICMEW), July 2017, pp. 297–302.

[12] Luı́sa Lima, Steluta Gheorghiu, João Barros, Muriel Médard, andAlberto Lopez Toledo, “Secure network coding for multi-resolution
wireless video streaming,” IEEE J.Sel. A. Commun., vol. 28, no. 3, pp.
377–388, Apr. 2010.
[13] D. Vukobratović, C. Khirallah, V. Stanković, and J. S. Thompson,“Random network coding for multimedia delivery services in lte/lteadvanced,” IEEE Transactions on Multimedia, vol. 16, no. 1, pp. 277–
282, Jan 2014.
[14] Hiroshi Nishida, “gf-nishida-16 web site,” https://github.com/scopedog/
gf-nishida-16/.
[15] Mozhgan Mokhtari and Hassan Naraghi, “Analysis and design of afﬁne
and hill cipher,” Journal of Mathematics Research, vol. 4, 01 2012.
[16] Mohd Aziz UR Rehman, Hasan Raza, and Israr Akhter, “Security
enhancement of hill cipher by using non-square matrix approach,”
Proceedings of the 4th international conference on knowledge andinnovation in Engineering, Science and Technology, 2018.
[17] Luı́sa Lima, Muriel Médard, and João Barros, “Random linear network
coding: A free cipher?,” CoRR, vol. abs/0705.1789, 2007.
[18] Keesook Han, Tracey Ho, Ralf Koetter, Muriel Medard, and Fang Zhao,“On network coding for security,” in MILCOM 2007 - IEEE MilitaryCommunications Conference, 2007, pp. 1–6.
[19] João P. Vilela, Luı́sa Lima, and João Barros, “Lightweight security for
network coding,” CoRR, vol. abs/0807.0610, 2008.
[20] Mohamed Amine Brahimi and Fatiha Merazka, “Data conﬁdentialitypreserving schemes for random linear network coding-capable networks,” Journal of Information Security and Applications, vol. 66, pp.
103136, 2022.
[21] John Dellaverson, Tianxiang Li, Yanrong Wang, Jana Iyengar, Alexander
Afanasyev, and Lixia Zhang, “A quick look at quic,” The Internet
Protocol Journal, pp. 2–12, 2019.
[22] Jeffrey Overbey, William Traves, and Jerzy Wojdylo, “On the keyspaceof the hill cipher,” Cryptologia, vol. 29, no. 1, pp. 59–72, 2005.
[23] Gabe Cunningham, “The genral linear group,” https://math.mit.edu/∼dav/genlin.pdf.
[24] A. Langley, A. Riddoch, A. Wilk, A. Vicente, C. Krasic, D. Zhang,
F. Yang, F. Kouranov, I. Swett, J. R. Iyengar, J. Bailey, J. Dorfman,
J. Roskind, J. Kulik, P. Westin, R. Tenneti, R. Shade, R. Hamilton,
V. Vasiliev, W. Chang, and Z. Shi, “The quic transport protocol: Design
and internet-scale deployment,” Proceedings of the Conference of the
ACM Special Interest Group on Data Communication, 2017.
[25] Microsoft, “Msquic,” https://github.com/microsoft/msquic.