はじめに

ネットワーク技術の進歩に伴い,組織外の計算器資源を動的に活用する情報システムが広がりを見せる一方,情報システムからの情報漏洩の危険性が指摘されている.本論文では,情報システムにおいて,データを安全に保護する暗号化方式に関する研究成果を報告する.まず,安全かつ効率的な対称型述語暗号の研究成果を報告する.標準的な暗号化方式では,暗号文は復号のみが可能な処理であるが,本研究成果を用いると,暗号文における述語処理が実現可能である.さらに,長期間に渡る情報システムの利用に備え,暗号化方式は強力な量子計算機による暗号解析にも対抗する必要がある.次いで,暗号化方式の安全性評価に関連する,最短近似ベクトル問題の計算手法の研究成果を報告し,最後に最短近似ベクトル問題を安全性の根拠とする暗号化方式を報告する.

対称型述語暗号の研究

述語暗号は,暗号文と暗号化トークンにおける述語を,秘密鍵を所有しない第三者が処理可能な暗号化方式である.特に,暗号文と暗号化トークンを作成する鍵を秘密裏に管理する方式を対称型述語暗号と呼ぶ.一般に,用いる群の数が少ない述語暗号は性能が良い.そこで,性能を重視し,利用する群の数を3つに絞った対称型述語暗号の研究成果を報告する.

準備として,3素数の積からなる合成数位数の双線形群を説明する.セキュリティパラメータspを入力とし,相異なる素数p1,p2,p3を含む,組(p1,p2,p3,G,GT,e)を出力する,合成数位数の双線形群の生成アルゴリズムをAとする.GとGTを位数N=p1p2p3の巡回乗法群とし,そのペアリング写像e(G×G→GT)は,以下の性質(双線形性と非退化)を満たす.

記号G1,G2,G3はGの部分群であるとし,その位数はそれぞれp1,p2,p3とする.n次元ベクトルをx=(x1,…xn),y=(y1,…yn)かつxi,yi∈ZNとし,内積<x,y>をx1y1+…xnynとする.

提案する対称型述語暗号は,以下4つの関数で構成される.

・Setup(sp):セキュリティパラメータspを引数とする.生成アルゴリズムAを実行し,(p1,p2,p3,G,GT,e)を得る.ただしG=G1×G2×G3である.次に,一様ランダムにG1,G2,G3の生成元g1,g2,g3と,q1,i,q2,i∈Zp1,r1,i,r2,i∈Zp3(i=1,…n)を生成する.公開パラメータをN(=p1p2p3),G,GT,eの組,秘密鍵SKを生成元g1,g2,g3と,素数位数p1,p2,p3,乱数q1,i,q2,i,r1,i,r2,i(i=1,…n)の組とする.

・Encrypt(SK,x):一様ランダムに生成した乱数S∈Zp1,α1,α2∈Zp2,U1,i,U2,i∈Zp3(i=1,…n),U1∈Zp1,U2∈Zp2を用い,平文を表わすn次元ベクトルxを暗号化した暗号文CTを出力する.

・GenToken(SK,y):一様ランダムに生成した乱数T∈Zp3,β1,β2∈Zp2,V1,i,V2,i∈Zp1(i=1,…n),V1∈Zp2,V2∈Zp3を用い,平文を表わすn次元ベクトルyを暗号化した暗号化トークンTKを出力する.

・Check(CT,TK):正規ペアリング写像Eを用い,E(CT,TK)=1ならば1を,E(CT,TK)≠1ならば0を出力する.ただし,E(CT,TK)=e(C1,1,K1,1)…e(C1,n,K1,n)e(C2,1,K2,1)…e(C2,n,K2,n)e(C1,K1)e(C2,K2)である.

従来の対称型述語暗号(表1では従来法3と記載)に比べると,提案法は用いる群の数を3つに絞ったために性能が良く,かつNon-Intractiveな仮定で安全性を証明できる.なお,表1における記号Non-IはNon-Intractive,記号IはIntractiveを示す.

SVP近似アルゴリズムの高速化の研究

最短ベクトル問題(SVP:Shortest Vector Problem)は,量子計算機でも解読困難とされるNP困難な問題の一つである.一方で,SVPの近似解は,その近似度次第では古典計算機でも多項式時間で解読できる.そこで,暗号化方式の安全性を評価する上で重要な指標である,SVP近似アルゴリズムに関する研究成果を報告する.

正則行列B∈Z(n×n)を,n本の線形独立ベクトルb1,…bnから構成される,ラティスの基底とする.直交ベクトルai∈Qは,b1,…bnが張る(i-1)次空間と内積<x,y>に関し,直交する.基底b1,…bn,直交ベクトルa1,…anは,任意のi(1≦i≦n)において,式bi=u(i,1)a1+…+u(i,n)anを満たす.ただし,u(i,j)=1(i=j)かつu(i,j)=<bi,aj>/<aj,aj>,(i>j)である

SVP近似問題の解読手法であるRSR(Random Sampling Reduction)を説明する.SVP近似アルゴリズムが出力する第一基底b1と各直交ベクトルai(1≦i≦n)は,関係式||ai||2=q(i-1)||b1||2(ただし,3/4≦q<1)を近似的に満たす.従って,添字iの値が大きくなるにつれ,||ai||は小さくなる.この性質を利用し,RSRでは,包含関係式ui∈(-1/2,1/2](1≦i<n-μ),ui∈(-1,1](n-μ≦i<n),ui=1(i=n)を満たす,ベクトルb=u1a1+…+unanを探索する.

しかし,上記のRSRは,十分に短いベクトルが見つかるまで,ほぼ全ての係数uiの計算を繰り返す必要がある.そこで,効率的にuiを計算可能な,RSRwP(Random Sampling Reduction with Precomputation)を提案した.ベクトルbの探索は,包含関係式ui∈(-1/2,1/2](1≦i≦βk),ui∈(-1,1](βk<i≦βk+μ),ui∈(-1/2,1/2](βk+μ<i<n),ui=1(i=n)に従う.ただし,k<βk<n-μとする.

提案法RSRwPでは一度だけ係数u(βk+u)+…u(n-1)を計算すればよい。その結果、従来法RSRに比べ,RSRwPは計算量がO(n2(k/6)(k/4))からO(k2log2k(k/6)(k/4))に改善した.ただし,kはユーザが指定するパラメータである.RSRwPとRSRの実計算量の見積もりの比較結果を表2にまとめる.100次元では,RSRwPはRSRよりも35.4%高速であり,最も次元が高い1000次元ではRSRの130倍以上も高速である.

ラティス暗号の研究

SVPに関連する暗号化方式であるGGH暗号の安全性を改良した,GGH+暗号を報告する.

GGH+暗号の鍵生成では,直交に近いラティスを構成するよう,基底Rを式(R←αnβI+P)に従い,作成する.ただし,α∈Z,1/2≦β<1,nβ∈Z,Iは単位行列,pi,jは置換行列Pの要素,pi,j∈{-1,0,1}である.次に,Rの逆行列Qが以下の条件式を満たすかを確認する.満たさない場合は,基底Rを再生成する.

qi,jをQの要素とする.Qが上記の条件を満たせば,R(とQ)を秘密鍵,Rの正規エルミート形式を公開鍵Bとする.

GGH+暗号における暗号化では,SVP近似アルゴリズムに対する暗号文の安全性を向上させるため,従来方式よりも(ノルムが)大きなn次元のベクトルeを平文として用いる.ベクトルeの要素eiはメッセージのバイナリ値(0,1)に基づき,一様ランダムに二つの集合から選択する.即ち,ei∈{-s,…-1,1,…s},ただし#{ei}=n-kかつei∈{-h,h},ただし#{ei}=kとする.

生成したベクトルeと公開鍵Bを用い,GGH+暗号の暗号文を表わすn次元ベクトルcを式(c←e-Bx)で作成する.復号は,式(t←Qc-「Qc」)よりベクトルtを計算し,次いでRt+Ra∈{-h,h}∪{-s,…-1,1,…s}を満たすベクトルaを探索する.最後に,ベクトルeを式(e←t+a)より求め,平文を復号する.

GGH+暗号の安全性は,特殊な最近ベクトル問題である唯一最短ベクトル問題に帰着される.この唯一最短ベクトル問題の解読可否は,最短ベクトルと2番目に短い第2最短ベクトルとの比率で評価できる.GGH+暗号では最短ベクトルがベクトルe,第2最短ベクトルが最も短い基底であり,式(γ=min||ri||/||e||)で評価できる.即ち、比率γがある閾値を超える場合,暗号文cが解読可能である.最も強力なSVP近似アルゴリズムであるBKZに最大値(ブロック長85)を設定した場合,その閾値は0.48(1.01)nである.GGH+暗号に各種パラメータ(α=4,β=12,s=3,k=10,h=7,n=400)を設定すると,γ≒5.1<11.63≒0.48(1.01)nであり,実用的な低次元でもGGH+暗号の安全性が保証可能である.

まとめ

○性能に優れた,3つの群を用いる対称型述語暗号を提案し,Non-intractiveな仮定で安全性を証明した.

○SVP近似アルゴリズムの一種であるRSRに事前計算を導入し,より計算効率の高いRSRwPを提案した.

○SVP近似アルゴリズムに耐性を有するGGH+暗号を提案し,その安全性を評価した.

表1:述語暗号の性能(群の数)と安全性

表2:実計算量の見積(k,μ) = (24,13)

本博士論文は九章から構成されている.第一章では,研究全体の位置づけとして,格子問題および隠れ部分群問題に基づく暗号化技術の研究が,今後の計算機環境においては非常に重要であり,かつどちらか一方の研究だけでは不十分であることが述べられている.基本的な暗号化/復号機能に加え,格子問題に基づく暗号化技術は暗号文同士の演算が実行可能な準同型暗号に関係し,また隠れ部分群問題に基づく暗号化技術は暗号化したまま条件判定を可能とする述語暗号に関係する.暗号化技術では,情報の秘匿性を数学的に保証する為に安全性証明技法が広く使われているが,本研究では特に安全性の根拠となる格子問題と隠れ部分群問題の計算量的困難性に着目し,それらの数論仮定を十分に検証した上で,各暗号化技術の安全性を数学的に証明している.第二章から第五章は隠れ部分群に基づく述語暗号の安全性と効率性について述べられている.述語暗号とは,情報を暗号化したまま,論理和(OR)や論理積(AND)などを用いた条件判定を第三者に委託可能な暗号化技術である.これまでの暗号化技術では対応できなかった,クラウドコンピューティング等の複数の組織に渡る計算機環境でも,情報漏洩を防止可能な技術として実利用が有望視されている.以降では,簡便のため,暗号化した情報を暗号文とし,暗号化した条件判定を暗号化トークンと呼ぶ.本研究の目的は,十分に計算量的困難性が保証された数論仮定の下で,暗号文と暗号化トークンが最高レベルの安全性(多項式時間で構成された任意の攻撃者に対し,暗号文と暗号化トークンから元の情報が1ビットも漏洩しない)を有する述語暗号の設計にある.これまでに提案された述語暗号のほとんどは,暗号文の安全性のみに着目し,暗号化トークンの安全性は不十分であった.例えば,近年(2000年以降)盛んに研究されている述語暗号は,総じて,暗号化トークンが頻度分析を行う攻撃者に対して脆弱である.また,暗号化トークンの安全性を証明した述語暗号も存在はするものの,肝心の数論仮定が特殊な隠れ部分群問題に帰着しているため,その計算量的困難性が不十分であり,解読される危険性が高い.本博士論文では,これらの研究動向を鑑み,まず取り扱う数論仮定の計算量的困難性を証明した上で,その数論仮定に基づく述語暗号を新たに設計し,暗号文と暗号化トークン双方の安全性を数学的に証明している.また,設計した述語暗号を別の数論仮定に帰着させた場合,ICチップ等の計算能力に乏しい小型機器でも軽快に動作できるまで計算量を削減できることも示している.第六章と第七章は,暗号文同士の演算が実行可能な準同型暗号の数論仮定において,代表的な格子問題である最短近似ベクトル問題の計算量的困難性を高速に検証可能な解読アルゴリズムについて述べられている.最短ベクトル問題は,複数本の線形独立なベクトルが与えられた時に,線形結合により,ゼロベクトルを除いた最も短いベクトルを発見する問題である.ただし,線形結合するベクトルの係数は整数とし,ベクトルの長さをユークリッドノルムで評価する.最短ベクトル問題はNP困難性が証明されている一方,その近似解(以降,最短近似ベクトル問題と呼ぶ)は近似度合によっては多項式時間で解読可能なことが知られている.本博士論文では,安全性証明における数論仮定に最短近似ベクトル問題を利用できるよう,その計算量的困難性を評価する検証アルゴリズムを設計している.具体的には,従来研究で報告された検証アルゴリズムの中でも計算効率の高さで優位性があるランダムサンプリング法に事前計算を適用し,より高速なアルゴリズムを設計できることを証明している.その結果,最短近似ベクトル問題の線形独立なベクトルの本数の自乗に比例していた計算量が,利用者が設定可能なパラメータのその対数の積の自乗に抑えられており,大幅に計算量が改善されている.第八章は,安全性の根拠とする数論仮定に最短近似ベクトル問題を用い,暗号文の加減算と乗算を第三者に委託可能な準同型暗号について述べられている.本博士論文では,検証アルゴリズムによって安全性が保証された最短ベクトル問題を数論仮定とし,暗号文の安全性が保証された準同型暗号を設計している.具体的には,数論仮定に用いた最短近似ベクトル問題が従来の検証アルゴリズムでは解読不可能であることを示した上で,その最短近似ベクトル問題に安全性が帰着可能な準同型暗号を新たに設計している.

本論文第二章から第五章は,佐藤尚宜,長沼健,國廣昇との共同研究,第六章から第八章は,國廣昇との共同研究であるが,論文提出者が主体となり貢献を行っており,論文提出者の寄与が十分であると判断する.したがって,博士(科学)の学位を授与できると認める.