No | 117615 | |
著者(漢字) | 大塚,玲 | |
著者(英字) | ||
著者(カナ) | オオツカ,アキラ | |
標題(和) | 情報量的に安全な電子現金方式に関する研究 | |
標題(洋) | Unconditionally Secure Electronic Cash | |
報告番号 | 117615 | |
報告番号 | 甲17615 | |
学位授与日 | 2002.09.30 | |
学位種別 | 課程博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 博工第5332号 | |
研究科 | 工学系研究科 | |
専攻 | 電子情報工学専攻 | |
論文審査委員 | ||
内容要旨 | 現代暗号は計算量的な困難性に基づくことで、ネットワーク社会を形成する上で欠くことのできない多くの有益な暗号技術を生み出してきた。電子現金方式も現代暗号の重要な成果の一つであり、将来のネットワーク社会のインフラストラクチャを担う技術として期待されている。しかし、情報技術の驚くべき進展と量子コンピュータの出現により、特に10年以上の長期的な安全性が求められるアプリケーションでは、すでに計算量的な安全性では不十分なことが指摘されている。従って、計算量的な困難性に代わる新たな理論的枠組みが必要となりつつある。 本博士論文の主な目的は、情報量的な安全性と情報量的な匿名性を同時に実現できる電子現金方式の実現を目標に置くことで、個々のプロトコルに要求される課題を発見し、それらの解決を通じて、最終的な目標である情報量的な安全性に基づく暗号理論の体系化に近づくことにある。 本研究の第一の成果は、情報量的に偽造が難しく、計算量的に匿名性が守られるハイブリッド型電子現金方式の存在を初めて示したことにある。既に情報量的に匿名で、かつ計算量的に偽造が難しい電子現金方式は存在しており、本成果はその双対に位置づけられる。本方式は花岡、四方、鄭、今井らによって考案された情報量的な安全性に基づく署名方式を基礎に、Descional Diffe-Hellmann問題(以下、DDH)が計算量的に解けないという仮定を導入し、この仮定の下で支払いの匿名性、すなわち電子現金の追跡不能性を実現した方式である。但し、情報量的な安全性を実現するために、極めて複雑な計算を実行する必要があるため現在の情報技術では実用的ではない。本成果は博士論文の第二章にまとめられている。 第二の成果は、情報量的に安全な非交信型の検証可能な秘密分散方式(Non-interactive Verifiable Secret Sharing)の存在を示したことにある。従来から情報量的に安全な交信型秘密分散方式と、計算量的に安全な非交信型秘密分散方式は存在した。交信型秘密分散方式では、各利用者に分散保持された秘密の正当性確認を他の利用者との交信によって実現し、これによって分散保持された秘密の全体的な一貫性が保証される方式である。この種の方式はブロードキャスト通信路が存在する仮定の下で、半数以上の利用者が正しく振る舞う場合に機能することが証明されている。他方、計算量的な安全性に基づく非交信型秘密分散方式は、秘密の正当性確認は利用者が単独で行える方式である。従って、非交信型秘密分散方式では過半数が不正利用者の場合でも、分散保持された秘密の全体的な一貫性を保証できる特徴がある。ただし、従来の手法では、各利用者の計算能力は多項式時間で抑えられる必要があった。本成果は、鍵事前配布モデルに基づくことで、情報量的な安全性を保証した上で、非交信型の秘密分散方式を初めて実現した。これにより、過半数の利用者が不正かつ無限の計算能力を持つ場合にも正しく動作させることが可能である。さらに、提案方式は各利用者が1,000人規模で1000個の秘密を保持するような規模のアプリケーションを想定した場合に、各利用者が数GBの秘密鍵を保持する必要があるが、通信量や計算量は低く、現在の技術水準でも十分に実用的である。本成果は博士論文の第三章にまとめられている。 第三の成果は、情報量的に安全かつ過半数の不正利用者に対応したマルチパーティ計算プロトコル(Multiparty Computation)の存在を示したことにある。マルチパーティ計算プロトコルは、n人の利用者がそれぞれ秘密の入力Xiを持ち、あらかじめ定められた関数F(X1,X2,...,Xn)を実行するプロトコルである。ここで関数Fは任意の計算可能関数である。ただし、個々の利用者の入力Xiと出力Yiに関する情報は他の利用者には一切漏れない。従って、マルチパーティ計算プロトコルが存在すれば、複数の利用者で実行されるすべてのプロトコルが存在することになる。従来の方式は、検証可能秘密分散方式の場合と同じくブロードキャスト通信路が存在する場合に、半数以上の利用者が正しく振る舞う場合にマルチパーティ計算プロトコルが実現できることが知られている。また、計算量的な仮定である0blivious Transferの存在を仮定すれば、過半数が不正利用者の場合でも、マルチパーティ計算プロトコルが存在することが知られている。本研究の成果は、鍵事前配布モデルに基づくことにより、過半数が不正利用者の場合でも、情報量的に安全なマルチパーティ計算プロトコルが存在することを示したことにある。さらに、本成果は前述の非交信型の検証可能な秘密分散方式を利用しているため、従来の情報量的に安全な方式がO(n4)の通信量を必要としたのに対して、本方式ではO(n2)の通信量で情報量的な安全性を実現している。本方式を1,000人規模で利用し、1,000程度の積演算を含むマルチパーティ計算を実行するようなアプリケーションを想定すると、各利用者が保持するべき秘密鍵のサイズは数+GBになり、現在の技術水準ではやや実用性に欠ける。但し、利用者数を100人規模にした場合には、秘密鍵のサイズは数百MBに抑えられる。本研究の成果は、博士論文の第四章にまとめられている。 最後の成果として、本研究では情報量的に安全かつ情報量的に匿名性が保護される電子現金方式の存在を示した。ここで示した方式は、(1)無限の計算能力を持つ不正利用者が存在しても電子現金の偽造は不可能であり、(2)無限の計算能力を持つ組織が存在しても、個人の支払いに関するプライバシーが完全に保護される、という特徴を持つ。ここで示した方式は、前述のマルチパーティ計算プロトコルと情報量的に安全な署名方式を組み合わせることによって実現されている。具体的には、マルチパーティ計算プロトコルの特別な場合として、2-パーティ計算プロトコルを構成し、関数F(x1,x2)としで情報量的に安全な電子署名方式の署名関数を設定し、利用者1の入力にはコインのシリアル番号を入力し、利用者2(銀行)の入力には署名用秘密鍵の情報を入力し、利用者1の出力に銀行のデジタル署名を出力する。マルチパーティ計算プロトコルの特徴により、利用者1の得たコインのシリアル番号と署名は、利用者2(銀行)から情報量的に隠蔽される。従って、このコインを使用しても、利用者2(銀行)はコインの利用者を追跡することは情報量的に不可能である。 | |
審査要旨 | 本論文は「Unconditionally Secure Electronic Cash(情報量的に安全性な電子現金方式に関する研究)」と題し、究極的な安全性である情報量的な安全性と情報量的な匿名性を同時に実現できる電子現金方式の構成法と、その実現にあたっての基礎となる情報量的な安全性に基づく種々の暗号プリミティブの構成法を示している。本論文は「Introduction」を含め6章からなる. 第1章は「Introduction(序論)」で,本研究の背景を明らかにした上で,研究の動機と目的について言及し,研究の位置付けについて整理している. 第2章は「Hybrid Approach: Combination with Computational Assumption(計算量的仮定との融合方式)」と題し,情報量的に偽造が難しく、計算量的に匿名性が守られるハイブリッド型電子現金方式の構成法を示している。本方式は花岡、四方、鄭、今井らによって考案された情報量的な安全性に基づく署名方式を基礎に、Decisional Diffie-Hellmann問題(以下、DDH)が計算量的に解けないという仮定を導入し、この仮定の下で支払いの匿名性、すなわち電子現金の追跡不能性を実現する手法を提案している。 第3章は「Robust Verifiable Secret Sharing(ロバストな検証可能秘密分散法」と題し,過半数のプレイヤーが不正でかつ無限の計算カを持つ場合においても正しく動作する安全な検証可能秘密分散法の構成法を示している。この成果は鍵事前配布モデルに基づくことで、従来は計算量的な仮定を置かなければ実現不可能だったロバストネスを計算量的な仮定なしに満たす手法を示している。さらに、提案方式は各利用者が1,000人規模で秘密を保持するような規模のアプリケーションを想定した場合に、各利用者は約20MBの秘密鍵を保持する必要があるが、通信量や計算量は低く、現在の技術水準でも十分に実用的である。 第4章は「Robust Multiparty Computation(ロバストなマルチパーティ計算)」と題し,鍵事前配布モデルに基づくことにより、過半数のプレイヤーが不正でかつ無限の計算力を持つ場合においても正しく動作する安全なマルチパーティ計算プロトコルの構成法を示している。マルチパーティ計算は、複数のプレイヤーで事前に決められた任意の計算を実行し、その際に各プレイヤーの入力と出力が他のプレイヤーから秘匿される特徴を備える暗号プロトコルである。提案手法は、従来計算量的な仮定を置かなければ実現できなかったロハストネスを計算量的な仮定なしに実現する手法を与えている。必要な秘密鍵のサイズも100人規模で、1,000程度の積演算を含むマルチパーティ計算の場合であれば数百MBであり、規模の小さいアプリケーションを選べば十分に実用可能と認められる。 第5章は「Unconditionally Secure Electronic Cash(情報量的に安全な電子現金方式)」と題し、情報量的に安全かつ情報量的に匿名性が保護される電子現金方式の構成法を示している。提案手法は(1)無限の計算能力を持つ不正利用者が存在しても電子現金の偽造は不可能であり、(2)無限の計算能力を持つ組織が存在しても、個人の支払いに関するプライバシーが完全に保護される、という特徴を持つ。提案方式は、情報量的に安全な署名方式と前章のロバストなマルチパーティ計算に基づいて構成されており、コインの偽造に関する情報量的な安全性と、マルチパーティ計算の入出力に関する秘匿性を利用して電子現金の偽造不能性と匿名性を同時に実現している。 最後に第6章は「Conclusion(緒言)」で,本研究の総括を行い,併せて将来展望について述べている. 以上これを要するに,本論文は,情報量的な安全性に基づく暗号理論に関する基礎検討を行うとともに,重要な暗号プリミティブと電子現金方式の構成法を明示したものであり,電子情報工学,特に情報セキュリティ工学上貢献するところが少なくない. よって本論文は博士(工学)の学位請求論文として合格と認められる. | |
UTokyo Repositoryリンク |