1 背景

今日の情報通信社会において情報セキュリティ技術が果たす役割は非常に重要であり、暗号技術はその中核をなす技術の一つであるため、本論文では暗号技術に焦点を当てる。暗号アルゴリズムは共通鍵暗号と公開鍵暗号との2種類がある。公開鍵暗号は整数論を直接利用しており、攻撃法も多様なアプローチが考えられるため、本論文では公開鍵暗号の安全性解析を目的とする。

現在の暗号の安全性は解読アルゴリズムの計算量に基づいている。解読アルゴリズムを高速に改良するアプローチはここ数十年大きな進展はないが、それ以外にもサイドチャネル攻撃や量子計算機攻撃などの大きな脅威がある。前者はデバイスの物理的挙動を観察することにより秘密情報を引き出すものであり、後者は能力の高い計算機モデルを利用するものである。本論文では、これらのアプローチに対する対策を考える上で必要な安全性解析に関して貢献することを目指す。

2 既存暗号の安全性解析

-ランダム鍵ビット漏洩攻撃に対する安全性解析

サイドチャネル攻撃は1990年代後半から盛んに研究されており、暗号研究の大きな流れの一つとなっている。公開鍵暗号で最もよく使われているRSA暗号[5]に関しては、秘密鍵の一部の漏洩を仮定し秘密鍵全体を求める研究が広範囲に行われていた。2009年にHeningerとShacham[1]は、RSA暗号秘密鍵のランダムな部分情報が漏れたと仮定して秘密鍵全体を求める新しい手法を示した。彼らの方法は以下の4段階からなる。

1. 秘密鍵の各ビットを変数として、その間に成り立つ関係式を求める。

2. 最下位ビットから始めて、上位ビットの解候補値を順に求める。

3. 漏洩情報と解候補の値を比較し、一致しないものは候補から外す。

4. 残った候補が秘密鍵が満たすべき関係式を満たすかどうかを確認する。

彼らの方法はランダム情報が漏れると仮定する点で新しく、ある状況で実現可能でもあるため重要であるが、彼らの安全性解析はRSA暗号の場合のみであった。本論文の貢献は以下の2点である。

1.本攻撃に対する安全性解析を一般の場合に拡張した。

2.安全性解析を他の幾つかの具体的な暗号に適用した。

効果としては、以下の2点であると考える。

1.他の暗号の本攻撃に対する安全性解析が容易かつ統一的になった。

2.本攻撃に対する暗号のセキュリティパラメーター設定が容易かつ統一的になった。

攻撃を他の暗号に適用した場合、第1段階において得られる関係式はRSA暗号と異なり、安全性解析も異なる。この関係式が一般の形の線型連立方程式の場合に、解候補数の期待値の上界は以下の4つの要素により明に記述できる。

1.秘密鍵の各ビットが漏洩する確率δ

2.変数の数γ

3.一つ前までのビットの値からは一意に決まらない変数の数I

4.一意に決まらない変数の方程式系の自由度w

一つ前のビットまでの解の割り当てが正しい場合に生成される誤った解候補数の期待値をEZg 、割り当てが誤っている場合に生成される誤った解候補数の期待値をEWb と書くと、

〓

および

EWb=((2-δ)γ)/2(γ-w)

となる。誤った解候補数の期待値の総計は

(EZg9/(1-EWb)

に秘密鍵のビット長を掛けた数で上から抑えられる。

本結果をPaillier暗号[4]および高木によるRSA暗号の変形[6]に適用した。Paillier暗号は、データを暗号化したまま加算が可能であり、クラウドサービス環境において近年期待が大きい技術である。Paillier暗号の本攻撃に対する安全性は、RSA秘密鍵のうち3変数の情報が漏洩する場合とほぼ同等であることが判明した。高木によるRSA暗号の変形は、暗号鍵の法の形がRSAの場合は であるものを、 という形に変形することにより復号性能を向上させたものである。この形の法は他の標準暗号でも用いられることがあり、安全性を検討しておくことは重要である。RSA暗号と比較すると、 のときのみトータルの解候補数は高木の変形の方が大きくなることが判明した。ただし高木の変形の場合、事前計算により得られる情報が少なく、トータルの攻撃計算量はRSAに比べて公開鍵指数をe とするとO(e2)倍となり、本攻撃に対しては、より安全であると言える。

3 将来に備えた暗号の安全性解析

-異なる区間からの部分和問題の困難性

量子計算機の実現等により現在の暗号が効率的に解かれる場合に備え、異なる問題の困難性に安全性を依拠する暗号を準備しておく必要がある。候補として幾つかの問題が提案されているが、本論文では格子理論に関連した問題、特に部分和問題と最短ベクトル問題(SVP : Shortest Vector Problem)とに焦点を当てる。格子理論に関連した問題に基づく暗号が、現時点では実用に最も近いと考えるからである。

部分和問題とは、n個の正の整数(重み)a1,...,an およびその部分和sが与えられたときに、その部分和を与える部分集合を求める問題である。即ち

〓

となるような、m=(mi)∈{0,1}nを求める問題である。ナップサック型暗号では、重みa1,...,an を公開鍵とし、平文 mに対して暗号文をs とするため、暗号文と公開鍵とから平文を求める問題は正に部分和問題となる。LagariasとOdlyzko[2]は、すべての重みが、ある同一区間[1,A]から一様ランダムに選択されたと仮定し、部分和問題の密度d を

d=n/log2A

と定義し、密度がある閾値do=0.6463 より小さい場合には部分和問題をSVPに帰着する方法(LOアルゴリズム)を提示した。更に最短ベクトルをLLLアルゴリズム[3]などの近似アルゴリズムにより求め、それが真の最短ベクトルである場合には元の部分和問題を解くことができる。このことから密度 は、部分和問題の困難性の指標と見ることができる。

これまでの研究は、すべての重みが同一区間から一様ランダムに選択されるという仮定に基づいていた。しかしながらナップサック型暗号の改良を考える上で、上記仮定は必ずしも満たされるとは限らない。例えば公開鍵のサイズを削減する方法として、各重みaiのビット長をiによって変える方法が考えられるが、そのような場合には上記仮定は満たされない。そこで本論文では、上記仮定が満たされない場合の部分和問題の困難性について考察する。本論文の貢献は以下の2点である。

1.各重みが異なる区間から選択されたと仮定した場合の部分和問題の困難性を解析した。

2.そのような場合に新しい密度の定義を導入し、その有効性を示した。

これらの結果の効果は、鍵生成などにおいて、より柔軟な暗号の設計が可能となることであると考える。

各 が、それぞれ異なる区間[1,Ai]( Aiは正の整数)から一様ランダムに選択されたと仮定し、密度dの代わりに新たな密度dHを

dH=n/log2HM(A1,…,An)

により定義すると、dHが閾値doより小さい場合にはLOアルゴリズムが有効に働くことを示した。ただしHM(A1,…,An)は、A1,…,Anの調和平均

〓

を表す。また、各重みが異なるビット長の場合に解読実験を行い、その困難性を示す指標としてdよりもdHの方が適切であることを示した。

[1] Heninger, N. and Shacham, H.: Reconstructing RSA Private Keys from Random Key Bits. In: Proceedings of CRYPTO 2009, LNCS 5677, pp.1--17, Springer, Heidelberg (2009)

[2] Lagarias, J. C. and Odlyzko, A. M.: Solving low-density subset sum problems. In: J. ACM, 32(1), pp. 229--246, 1985

[3] Lenstra, A. K., Lenstra Jr., H. W., and Lovasz, L.: Factoring polynomials with rational coefficients. In: Mathematische Annalen, 261, pp.515--534, 1982

[4] Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of EUROCRYPT 1999. LNCS 1592, pp.223--238, Springer, Heidelberg (1999)

[5] Rivest, R.L., Shamir, A., and Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. In: Comm. of the ACM, Vol. 21(2), pp.120--126, 1978

[6] Takagi, T.: Fast RSA-type Cryptosystem Modulo . In: Proceedings of CRYPTO 1998, LNCS 1462, pp.318--326, Springer, Heidelberg (1998)

本論文は「Security Analysis against Random Key Bits Leakage Attack and Hardness of Subset Sum Problem from Different Intervals(ランダム鍵ビット漏洩攻撃に対する安全性解析と異なる区間からの部分和問題の困難性)と題し、5章から構成されている。情報の安全性を守るために暗号技術が広く使われているが、計算量的な安全性に基づく暗号では、素因数分解, 離散対数問題, ナップザック問題などを解くのに非常に多くの時間がかかるという計算量的な安全性に根拠が置かれている.しかし,サイドチャンネル攻撃(デバイスの物理的挙動を観測することなどにより秘密情報の一部を得る攻撃)による安全性の脅威や、将来量子コンピュータが実用化したときに、素因数分解や離散対数問題が多項式時間で解けるという脅威が存在することが知られている。本論文では、このような背景の下で、前者の脅威に対する評価として素因数分解の困難さに根拠を置く暗号系に対するランダム鍵ビット漏洩攻撃に対する安全性解析を行い、後者の脅威に対しては、量子コンピュータを用いても多項式時間の解法が知られていないナップザック問題に対して安全性評価を行なっている。

第1章「Introduction」では、研究の背景を述べると共に、本研究の目的および従来研究に対する本研究の位置付けを述べている。

第2章「Preliminaries and Notation」では、本研究で対象とする公開鍵暗号であるRSA暗号、Paillier暗号、Takagi暗号、Okamoto-Tanaka-Uchiyama暗号の暗号化および復号化の手続きを紹介すると共に、本論文で使用する表記法を示している。

第3章「Security Analysis against Random Key Bits Leakage Attack」では、RSA暗号の秘密鍵のランダムな部分情報が漏洩したと仮定して秘密鍵全体を求めるHeningerとShachamの攻撃手法の安全性解析を、特定の暗号に拠らない一般の場合に拡張している。また、その一般的な解析手法を、Pailler暗号, RSA暗号の素数の積pqをptqに拡張したTakagi暗号に適用している。その結果、本攻撃に対してPailler暗号はRSA暗号とほぼ同等の安全性を有し、Takagi暗号は、t = 2のときのみTakagi暗号がRSA暗号より安全となることを明らかにしている。

第4章「Hardness of Subset Sum Problem from Different Interval」では、部分和問題の困難さに基づくナップサック型暗号を取り上げている。将来、量子コンピュータが実現すると素因数分解が多項式時間で解かれるため、第3章で取り上げたような暗号は安全でなくなるため、他の暗号を準備しておく必要があるが、部分和問題に基づくナップサック型暗号が有力な候補の1つと考えられている。部分和問題は、格子理論に基づく最短ベクトル問題と密接に関係しており、部分和の各重みがある一定の区間から一様に取られている場合、その区間幅の対数値の逆数で決まるように定義された密度が、ある閾値d0以下であれば部分和問題が解けることをLagariasとOdlyzkoが格子理論に基づき示している。これに対して、本研究では、各重みがそれぞれ異なる区間から一様に取られる場合に対して、LagoriasとOdlyzkoの解析手法を拡張することにより、安全性解析を行なっている。その結果、密度を各区間幅の調和平均の対数値の逆数で決まるように定義すると、その密度が同じ閾値d0以下のときに、部分和問題が解けるという、より一般的な結果を理論的に証明している。本研究の成果は、秘密鍵サイズをよりフレキシブルに変化させるようなナップサック型暗号を検討するときに重要となる。

最後に、第5章「Conclusion」で本研究の結果と貢献をまとめている。

なお、本論文の第3章と第4章の成果は、山本博資および國廣昇との共同研究であるが、論文提出者が主体となって新しい解析手法の提案、理論解析、数値実験を行なったものであり、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。