研究の関心

線形符号の hull

線形符号とは F_qⁿ の部分空間 C のことで、その双対 C^⊥ は（双線形形式あるいは半双線形形式に関する）C の直交空間です。hull は両者の共通部分であり、その次元 ℓ は 0 から k = dim C までの値をとります。

hull は、自己双対符号など古典的な構造を含む、線形符号全体を記述する概念です。

• ℓ = k のとき符号は双対に含まれ、自己直交符号と呼ばれます。2k = n なら自己双対符号です。
• ℓ = 0 のとき符号と双対の交わりは自明で、これが LCD 符号の場合です。Massey [1] が導入し、独自の大きな文献をもちます。
• その間には残りすべてが並びます。

hull の重要性を示す結果は数多くあります。

• 自己直交符号は符号ベース署名方式 SPECK [2] のインスタンスそのものであり、hull 次元を指定した符号は Hollow LWE [3] の構成要素です。
• LCD 符号は、サイドチャネル攻撃とフォルトインジェクション攻撃への対策として利用できることが Carlet と Guilley [4] によって示されています。
• hull 次元は、置換同値問題の標準的な解法である support splitting algorithm [5] の計算コストを支配し、インスタンスの難しさを決めます。
• シンプレクティック形式とエルミート形式の場合、C の hull 次元は C から作るある種の量子誤り訂正符号（Entanglement-Assisted QECCs）における ebit 数そのものです [6][7]。つまり、ある種の量子符号はこれらの符号と等価です。

このように、線形符号の hull は理論的にも応用的にも非常に興味深い対象です。私は現在、hull の特徴づけと、暗号・量子誤り訂正への応用に取り組んでいます。以下に示すのは、その一部です。

hull 次元を指定した線形符号の一様サンプラー

Uniform Sampling of Linear Codes with Prescribed Hull Dimension は、hull 次元 ℓ の [n, k] 符号を厳密に一様にサンプリングするアルゴリズムを与えます。すべての有限体 F_q と、標準的なすべての内積（ユークリッド・エルミート・シンプレクティック）を、ひとつの枠組みで扱うことができます。証明には反射的形式の古典理論、Witt の拡張定理とその分類 [8]、および群を一様にサンプリングする Diaconis–Shahshahani の部分群アルゴリズム [9] などを用いました。

• 符号同値を利用する方式は、まさにこの一様サンプリングを仮定しています。SPECK [2] は鍵生成で一様ランダムな自己直交符号を構成し、Hollow LWE [3] は hull 次元を指定して一様ランダムな符号を構成することを仮定しています。しかし、これまで知られていた構成は奇標数・2k ≤ n の場合に限られ、hull 次元だけを指定したときの出力は、一様分布から全変動距離 q^{−(k−ℓ)/2} の範囲に収まるだけでした [10]。本研究は、標準的なすべての内積とすべての標数について、厳密な一様性を保証します。
• また、上に述べたことから、ある種の方式の安全性の問題は符号の典型的な振る舞いに帰着します。サンプラーによって、その振る舞いの Monte Carlo シミュレーションと理論解析が可能になります。
• シンプレクティック形式とエルミート形式の場合、hull 次元は C から作るエンタングルメント支援量子符号が消費する ebit 数そのものです。したがって同じサンプラーが、ebit 数を指定した EAQECC を引くことになります。この帰結は QIP 2027 のポスターで発表します。
• 置換同値によって符号を分類する際、通常は順序づけられた全列挙で進みます。符号を決まった順で生成し、これまでに分類した非同値な代表元と比較していくわけです。この方法では計算資源の制約から、順序で後ろに来る同値類には、現実には決して到達できないことがあります。サンプラーは、符号を一様ランダムに1つ返すことで、これを補う道具になります。論文では、有名なクーポン蒐集家の議論を適用して、分類に必要なサンプリングの回数を見積もりました。

置換同値とグラフ同型

2つの符号が置換同値であるとは、座標の置換で一方が他方に写ることです。同値判定はあらゆる符号分類のボトルネックであり、同時にいくつかの暗号方式の困難性仮定でもあります。

Petrank と Roth は、グラフ同型は置換同値に帰着できることを示しました [11]。逆に、Bardet らは LCD 符号の同値判定をグラフ同型に帰着しました [12]。Babai のアルゴリズムはグラフ同型を準多項式時間で解くので [13]、LCD 符号の同値判定は易しいということになります。しかし、ここで自然な問いが生じます。それは、「置換同値がグラフ同型に帰着する符号は LCD 以外にあるのか」というものです。

The Closure of LCD-to-GI Reductions via Generalized Inner Products は、その問いに対する答えです。ユークリッド内積を一般の双線形形式に置き換えると、議論を駆動する直交射影が一般化され、帰着は LCD の場合を越えて hull 次元 1 の一部にまで届きます。さらに、直交射影に基づく帰着で到達できるのはこれがすべてであることを証明しました。帰着できる符号は特徴づけと数え上げが済んでおり、符号全体に占める割合も分かっています。

置換同値に関するもうひとつの仕事は、置換同値問題の標準的な解法である support splitting algorithm [5] についてです。このアルゴリズムの計算コストは hull 次元に支配されます。上と同じ一般化形式を使って、アルゴリズムが適用可能であるための条件を保ったまま hull 次元を下げられるのはいつかを特徴づけ、それが可能な次元のクラスを特定しました。この結果は Bilinear Hulls for Support Splitting として SAC 2026 で発表しています。

2元・3元・4元 LCD 符号の完全分類

ここまでの仕事では、符号理論から出発して結果を暗号に応用しました。逆に、次の仕事では、符号ベース暗号の解析で開発された技法を符号の分類に応用しました。

Sendrier と Simos [14] が導入した線形符号の closure は、線形同値を置換同値に帰着します。しかも LCD であることを保つので、LCD-to-GI 帰着と合成すれば、線形同値から置換同値を経てグラフ同型へという連鎖が得られます。

この帰着によって、Leon のアルゴリズム [15] では届かない長さまで分類を進めることができました。結果、2元 LCD 符号は長さ19、3元は長さ15、4元エルミートは長さ13まで分類を更新しました。さらに、これが到達可能な限界であることも論じました。次の長さへ進むと出力がテラバイトからペタバイト規模になり、現在の計算資源では保存も配布もできないことを示したのです。この結果は、Classification of binary, ternary and quaternary Hermitian LCD codes として発表しました。

各同値類の代表元は、2元 LCD 符号とそのグラフ表現とあわせてオープンデータとして公開しています。データ一覧はこちらから入手できます。