突貫で書いてしまった部分もあるので、大いに誤りを含む可能性があります。誤字・脱字レベルでも構いませんので、ご指摘ください。
また、予告なしに内容の加筆や構成の変更を行うことがありますが、読みやすくするためのものですので、ご容赦ください
はじめに
2025年3月11日に、NIST PQC 標準化プロジェクトにおいて、符号ベース暗号方式である HQC が Selected Algorithms となりました
NIST PQC Standardization Process | HQC Announced as a 4th Round Selection
他にも書かないといけない記事がいくつかあるのですが、HQC が Selected Algorithms に掲載されたことが嬉しすぎて、ついこちらの記事から投稿することにしました
＊と書いているのに、半年以上経ってしまった理由として、元々2025年2/19時点での仕様書とコードを参考に記事を書いていたのですが、8/22にガラッと変わってしまい、諸々を書き直していたら遅くなったという・・・
今回の連載は↓の4つで構成されます:
- 概要編←イマココ
- 基本編
- 設計編
- 発展編
本記事では、下記の仕様書の概要を掴むことを目標にします
この仕様書の構成は、次のようになっています:
1章: イントロダクション
2章: 前提（符号理論の基礎知識や HQC 方式で使われる計算問題など）
3章: HQC の仕様（HQC の設計）
4章: パラメタや暗号文・鍵サイズ
5章: 性能評価
6章: 安全性分析（HQC による KEM が IND-CCA2 安全性を満たすことの証明だったり、既存の攻撃手法だったり）
7章: 利点と制限
正直なところ、4章・5章・7章は読めばわかるかな〜という感じなので、軽く触れる程度で
この仕様書を本連載では↓で分割して扱います:
- 概要編（1章, 7章）: HQC 方式の概要を掴む
- 基本編（2.1節, 2.2節, 2.3節, 2.4節）: HQC 方式の基礎知識を整理する
- 設計編（3.1節, 3.2節, 3.3節, 3.4節, 3.5節, 6.3節）: HQC 方式の中身を理解する
- 発展編（4章, 5章, 実装）: HQC 方式の実装や最新動向を追う
安全性証明もやりたいんですが・・・時間かかりそうなので、今回は割愛します
＊HQC による PKE と KEM の2つの構成があるのですが、今のところは、PKE のみ解説しようと思っています（長くなりすぎるかもしれないので・・・そうでもないなと思ったらどちらも）
また、設計編・発展編では、
を元に中身のコードも概説します
このうち
src/ref/hqc.c
src/ref/reed_muller.c
src/ref/reed_solomon.c
は、設計編でも軽く解説し、残りは、発展編で解説する予定です
＊例えば、Reed-Solomon 符号の Decode アルゴリズムでは、多項式乗算が用いられるのですが、それを工夫するための Toom-Cook アルゴリズムや Karatsuba アルゴリズムは、発展編に回します（positive-cyclic であることが分かればよいので）
ちなみに、CRYPTREC のガイドラインに軽く HQC の解説があるので、もし興味のある方はそちらも
CRYPTREC 暗号技術ガイドライン（耐量子計算機暗号）2024年度版
全然関係ないですが、旧版と今ではどちらの仕様書が読みやすいかと聞かれたら、今の方がかなりまとまっていて読みやすいと思います
＊とはいえ、旧版の仕様書とめちゃ異なる解説もいくつか（2.4節で PKE と KEM の定義とか）あり、全部消さないといけないものもあったのがもったいなかったです・・・
＊旧版の雰囲気を見たい方は、以下のアーカイブをご覧ください、めちゃ有名人ばかりですね（HQC の原案では、Reed-Muller 符号や Reed-Solomon 符号は使われておらず、別の符号を使っていたらしいですね）
HQC 方式の概要（1章・7章）
HQC とは、符号ベース暗号方式の1つで、Hamming Quasi-Cyclic の略称です
Hamming 距離に基づいた符号であり、Parity 検査行列と呼ばれる符号に関する行列が Quasi Cyclic（準巡回とか擬巡回）ということです
HQC 方式を用いる利点（7.1 節）として
- 使用している符号の隠れ構造（hidden structure）を復元する攻撃に対して耐性（immunity）がある
- 暗号文や鍵サイズが小さい（同じ符号ベース暗号方式の Classic McEliece と比較して、って感じですかね）
が挙げられていて、制約（7.2 節）として
- PKE 方式は、暗号化率（encryption rate）が低い
- ML-KEM（Kyber）と比べて、暗号文や鍵サイズが大きい
もうそれは仕方ないのでは
などがあるそうですね
まとめ
次回から数式がたくさん出てくるので Zenn へ移行します Qiitaの数式表示は（以下略）
久しぶりに耐量子計算機暗号のみのトピックを書いた気がします
準同型暗号の方で CKKS や TFHE の連載記事を書いていますが、あれらほどは深くは書けないかなぁという感じです
途中で紹介した CRYPTREC の暗号技術ガイドラインよりは詳しく・・・おっと誰かが
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！