目次
開催案内
多変数多項式署名とその効率化手法について
日時
2024年12月5日（木）16:45〜18:15
開催形式
対面(北部構内)とオンライン(Zoom)のハイブリッド
参加登録 https://forms.gle/kuSj1bLTZWD8bpgA6
登録されたアドレスに教室の場所とZoomの接続情報を送付いたします。
講師
古江 弘樹 氏（NTT）
概要
多変数多項式暗号は、量子計算機を用いた攻撃に対して耐性を持つ暗号方式として注目を集めている。本公演では、多変数多項式問題ベースの署名方式UOVと、その効率化手法について解説する。
備考
◎問い合わせ先：itami.masato.7u ＊ kyoto-u.ac.jp（＊を@に変えてください）
活動報告
NTTの古江弘樹さんに「多変数多項式署名とその効率化手法について」というタイトルで講演していただきました。
講演は多変数多項式暗号のレビューから始まりました。多変数の連立2次方程式系の解を求める問題は、多変数多項式問題(MQ問題)と呼ばれ、NP完全問題であることが知られています。そして、ディジタル署名方式に適性を持つ多変数多項式暗号は、このMQ問題の困難性に基づいて構成されています。多変数多項式署名の利点は署名サイズが小さいことや、効率的な実装が可能なことで、欠点は公開鍵サイズが大きいことです。多変数多項式署名を具体的に構成する際には、秘密の情報を用いれば効率的に求解可能なMQ問題を用意する必要があります。効率的に求解可能なMQ問題の用意の仕方は、大きく分けて2通りあります。拡大体を利用するものと、Unbalanced Oil and Vinegar(UOV)と呼ばれる手法を利用するものです。前者を利用した署名方式の一部が破られてしまったこともあり、現在では後者が有力視されているようです。UOVでは、変数をvinegar変数とoil変数の2種類に分け、oil変数に関しては1次方程式系になるように連立2次方程式系を用意します。こうすることで、vinegar変数の値をランダムに固定し、oil変数についての線形方程式を解くことで、容易に解を求めることができます。UOVを利用した署名方式は、現時点でも安全だと考えられているそうです。
続いて、古江さんらが提案したQuotient Ring UOV(QR-UOV)について説明していただきました。UOVを利用した多変数多項式署名も公開鍵サイズが大きいため、QR-UOVでは公開鍵に剰余環の構造を導入し、UOVよりも公開鍵長を削減しています。秘密鍵に剰余環の構造を導入しても、一般には公開鍵に同じ構造が入らないため、公開鍵長は簡単には削減できないのですが、ある行列を対称化することで解決していたのが印象的でした。QR-UOVはNIST Security Level 1という安全性の基準でみたとき、UOVよりも公開鍵長が約50%削減されるそうです。
最後に、NIST PQC標準化に関して説明していただきました。NIST(米国国立標準技術研究所)は2016年から耐量子計算機暗号の標準化をコンペ形式で開始しており、2022年に署名の追加公募が開始したため、古江さんらはQR-UOVで応募したそうです。QR-UOVは14件の候補の1つとして選ばれたため、現在は幅広い事柄に関して学び、様々な人の協力を得ながら、仕様書を改訂中とのことでした。
講演中も講演後も多くの質問が出て、QR-UOVと他の手法との差異などに関して活発な議論が行われました。
（文責：伊丹將人）