科学研究費補助金 基盤研究(A) 冗長ガロア体算術に基づくセキュリティハードウェアの高水準設計技術の研究開発

1.はじめに

 IoT機器等の組込みLSIシステムの性能は、データを処理する算術演算回路に大きく影響されます。近年では、個人の情報や資産に関わるデータをLSIで処理する機会が増加しており、情報秘匿や個人認証、通信誤りの訂正処理で必須となるガロア体上の算術演算回路(ガロア体算術演算回路)の重要性が高まっています。ガロア体とは、有限の要素からなり、四則演算に閉じている集合のことです。例えば、整数をある素数で割ったときの余りを要素としてガロア体を構成できます。ガロア体には多様な表現方法があり、特に近年では冗長な表現がハードウェア設計に有用であることが報告されています。今後、LSIシステムの多様化に伴い、無数に存在するガロア体算術演算回路を用途に応じて適切に設計する必要性はますます高まると予想されています。しかし、現在のLSI設計技術は論理回路の設計を基本として発展しており、ガロア体算術演算回路に対する十分な設計環境が整っていません。

 まず、現在の回路設計で用いられるハードウェア記述言語(HDL: Hardware Description Language) は、ガロア体上の変数を扱うための高水準なデータ構造を持ちません。このため、ガロア体算術演算回路を設計する場合、2値論理信号を用いた長大なAND-XORの論理式による低水準な記述を強いられます。近年LSIに物理的にアクセスして秘密情報を奪う物理攻撃が情報セキュリティ上の重大な脅威の一つとなっており、そのような攻撃への耐性がLSI(特に暗号LSI)の新たな性能要件となっていますが、高い性能を維持しつつそうしたセキュリティを担保することはガロア体算術演算回路の設計をさらに複雑化させています。

 また、一般に多入力多出力の算術演算回路では、その機能を計算機シミュレーションで検証するために膨大な時間が必要となります。現代の暗号処理は、通常128ビット以上の語長での演算を要するため、全ての入力の組合せが2の128乗(約10の38乗)以上となります。これでは、シミュレーションによる完全な検証は事実上不可能です。暗号理論の分野では、暗号処理を実行する算術演算回路のバグを利用して秘密情報を奪う攻撃も報告されており、こうした回路では軽微なバグであっても許容されません。このことから、ガロア体算術演算回路を高速かつ完全に検証することは信頼性だけでなくセキュリティの観点からも強く望まれていました。

 私は、以上の背景から、算術演算回路をより直感的かつ正確に設計・検証・合成するための技術とその応用に関する研究を行ってきました。特に、これまで任意の重み数系を統一的に記述可能な新しい算術演算回路の形式的設計・検証手法を開発してきました。同設計手法では、任意の算術演算回路がそれ自身も算術演算(加算や乗算といった四則演算)の機能を有する部分回路の組み合わせとして階層的に構成できることに着目し、算術演算回路を有向グラフとして形式的に表現します。図1に考案した算術演算回路表現の例を示します。このとき、グラフのノードは算術式で記述される回路機能をもち、有向辺はデータのフローを表します。このように記述された算術演算回路では、すべての部分回路の演算機能がその内部構造(一つ下の階層の部分回路の集まり)によって実現されるかを調べる等価性判定を全部分回路に適用することにより、回路全体の機能を検証することができます。この等価性判定とは、回路を表す連立方程式を解く(余計な中間変数を削除した最簡な数式を導出する)ことに他なりません。連立方程式の解がその上位回路の機能を表す数式と一致するとき、その回路が正しく設計されていると言えます。このとき、連立方程式を多項式の集合とみなしてグレブナー基底と呼ばれる質のよい多項式集合に変換し、イデアル所属問題という計算機代数の問題に帰着することで、計算機によって任意の連立方程式の解を求めることができます(図2)。結果として、従来困難だった規模の算術演算回路であっても、高速に検証できるようになりました(図3)。

図1 開発した算術演算回路記述の例

図1 開発した算術演算回路記述の例

図2 計算機代数による形式的検証の概要

図2 計算機代数による形式的検証の概要

図3 算術演算回路の機能検証にかかる時間

図3 算術演算回路の機能検証にかかる時間

Page Top