産総研様との共同研究の第二期結果概要報告
先にお知らせしておりますように（文末参考部参照のこと）表題共同研究に関する経過成果等の公表の一環として、第２期「電子割符方式の現状の安全性評価」の報告書が届きました。そのうち、報告書追補版の書記載内容の全体を公表します。今後も計画している共同研究成果概要は公表していく所存です。現状はあくまで経過報告であり、共同研究の全体及び詳細公表は控えております。
今回の成果概要としては、前回第一期報告「電子割符方式のアルゴリズムの厳密な理解」（文末参考を参照のこと）の発展として弊社秘密分散技術（電子割符）の割符生成アルゴリズムに関して、割符ファイルの１つを入手した攻撃者が元データを完全に復元する攻撃に対する安全性評価を行い、そうした攻撃に対して当該アルゴリズムが充分な安全性を持つことを確認した。というものです。
成果は報告書本文と追補版があり、追補版は特段数学や暗号に精通していない一般の皆様にも理解していただけるよう記述の仕方等を工夫したものです。
ーー以下、共同研究第二期成果報告書追補版記載内容全体ーー
ＧＦＩ電子割符（Ｒ）の安全性評価について
産業技術総合研究所 縫田 光司
２０１５年１１月３日
概要
当文書では、グローバルフレンドシップ株式会社（以下「GFI社」と記載）が開発した「ＧＦＩ電子割符（Ｒ）」（以下「電子割符技術」と記載）の概要および本文書作成時点での同技術の安全性評価内容について述べる。
１．電子割符技術と他の暗号技術の比較
文書・画像・ソフトウェアなどのデジタルデータ（以下「元データ」と呼ぶ）を秘匿する技術としては、公開鍵暗号が広く用いられている。その暗号文を「金庫」、復号鍵を「錠前の鍵」に例えるならば、元データを「金庫」に収納（暗号化）して「錠前」を掛けることで、「鍵」を持つ人だけが元データを取り出せるようになる、という具合である。一方、電子割符技術の原理はこれと異なる。前提として、デジタルデータである元データはその種類に関わらず、究極的には0や1という数字（ビット）の並びである。電子割符技術では、元データをビット単位に分解し、それらを毎回異なる振り分け方で無作為に振り分けて複数の集合（「割符ファイル」と呼ばれている）に分割している。そして、割符ファイルがすべて揃えば、特殊な操作によって元データを復元することが可能となる。一方、割符ファイルが一つでも欠けた状態では元データを復元できない、ということが期待されるようにデータの分割方法が設計されている。
この元データを複数に分割するという設計思想自体は、暗号理論における秘密分散法と相通ずる。電子割符技術の割符ファイルに相当するデータは、秘密分散法では「分散情報」などと呼ばれている。例えば、元データを２個の分散情報に分割する場合、分散情報が二つ揃えば元データを復元できるが一つだけでは復元できない、という具合である【注１】。さらに、理想的な安全性を実現する秘密分散法【注２】は、
- 残りの分散情報が揃わない状態では、分散情報の各々は「完全にランダムなビットの並び」と全く区別できない
という顕著な特徴を持っている。ハードディスクのデータを廃棄処理する際にランダムなビットの並びで上書きする方法があるが、分散情報の各々はそのような「廃棄処理後の残渣」と同様に振る舞うとも理解できる。そのため、元データを盗み見ようとする人は、分散情報をすべて手に入れない限りは、そこから元データの情報を何も得ることができない。 公開鍵暗号では、「鍵」を持たない人が「金庫」をこじ開けて元データを取り出すことは非常に困難である。にもかかわらず、数十年あるいは100年程度の極めて長い時間の後には、コンピュータの性能向上などによって「金庫」をこじ開ける困難さが減少する可能性が否定できない。実際、NIST（米国）、CRYPTREC（日本）といった国内外の専門機関により、公開鍵暗号については安全のため20年程度を目途に鍵の強度を高く設定し直すよう求められている【注３】。一方、理想的な安全性を実現する秘密分散法では、こうした安全性の経年劣化が生じないことが理論的に保障されている。この観点では、秘密分散法は公開鍵暗号よりも本質的に高度な安全性を実現しているといえる。
上述の通り、電子割符技術も秘密分散法と同様の設計思想に基づいていることから、もし電子割符技術が理想的な安全性を実現できていれば、割符ファイルの各々は「廃棄処理後の残渣」と同様に振る舞い、どれだけ長い時間が経ってもその安全性が損なわれないと期待される。例え話としては、元データが白黒の碁石（ビット）を碁盤に並べた盤面であるならば、割符ファイルはその中から取り出されたいくつかの碁石に対応する。このとき、取り出した碁石（割符ファイル）がすべて揃っていない状況では、足りない碁石の色や個数の手がかりが無いため、どれだけ時間をかけて考えても元々の盤面を特定することはできないであろう、という発想である。ただし、電子割符技術では効率化（割符ファイルの小型化）のために設計の細部が既存の秘密分散法と異なっていることから、秘密分散法の持つ理想的な安全性にどの程度近い安全性を実現できているかは注意が必要である。この点を解析することが今回の安全性評価の目標である。
２．現時点での安全性評価内容
当文書の作成時点で、電子割符技術の安全性評価は完了していないものの、現時点では電子割符技術の実用上の安全性を否定する材料は見つかっていない。例えば、攻撃者が割符ファイルの一つを入手した状態で元データを完全に復元できる可能性について評価を行ったところ、ある理論的な前提条件の下では、そのような可能性は現実的に全く問題とならないほど小さいことを確認した（詳細は次段落を参照）。今後の安全性評価では、より実際の利用環境に近い前提条件の下で、攻撃者がより多くの（ただし全部ではない）割符ファイルを入手した状態での元データの完全な復元可能性や、元データの部分的な復元可能性といったより詳しい評価を行う予定である。
上記の安全性評価についてより詳しく述べる。通常の暗号技術の標準的安全性レベルである「80ビット安全性」では、暗号の解読が2の80乗（およそ10の24乗）通りの全数探索と同程度以上に困難であることを要求している。一方、現時点での安全性評価では、例えば、攻撃者が３個ある割符ファイルのうち一つのみを入手した状態で元データを完全に復元できる可能性について、およそ10の105,000乗通りの場合の数から正解を言い当てるのと同程度に困難であるとの見積もりを得ている（なお、この数値は、アイスランド（人口約33万人）の国民全員が一斉にコインを投げて全て表が出るのと同程度に「現実にはまず起こらない」確率である）。ここで、「80ビット安全性」は暗号解読に必要な「計算量」を尺度とする評価である一方、今回の安全性評価は元データを正しく復元する「確率」という異なる尺度を用いているため、両者は直ちに比較できないと思われるかもしれない。
しかしながら、「80ビット安全性」の基準である「2の80乗通りの全数探索」において、探索の最初の候補が偶然にも正解であったために解読が瞬時に成功してしまう確率ですら2の80乗分の1はあることを鑑みると、元データを正しく復元できる確率が2の80乗分の1を下回るならば実用的な暗号技術の安全性レベルとして問題ないものと考えられる。つまり、こうした攻撃者に対する安全性という観点に限れば、電子割符技術の安全性は暗号技術の標準的安全性レベルを大きく上回っている（現時点での安全性評価で得られている内容に限るならば、充分な情報理論的安全性を持っていると考えられるレベルにある）と解釈することができる。
なお、GFI社によると、ＧＦＩ電子割符（Ｒ）は、1999年に現行の骨子となるアルゴリズムを実装後、複数OS環境でのデータ互換性維持や32bit OSから64bit OSへの変更を含む更新を経て、現在まで安定した動作実績を有している。現在、秘密分散技術に関する事実上初のJIPDEC公開のガイドライン【注４】や、秘密分散技術の標準化を進めている秘密分散法コンソーシアムにおいて、同社技術が標準化のベースとして想定されているが、上述した現時点での安全性評価の途中経過を見る限りにおいて、当該技術の安全性はこうした技術標準化の検討に値する水準にあるものと期待できると考える。
【注１】秘密分散においては、分散情報が「全部揃うかどうか」だけでなく、例えば３個の分散情報のうちいずれか２個以上揃うと元データを復元できる、といったより複雑な設定も可能であるが、当文書ではそこまで深入りしない。
【注２】例えば、Adi Shamir教授が1979年に提案した方式などが知られている。
【注３】例えば、国立研究開発法人情報通信研究機構による公開文書
http://www.nict.go.jp/publication/NICT-News/1303/01.html の図２を参照。
【注４】ECにおける情報セキュリティに関する活動報告書2009
http://www.jipdec.or.jp/archives/publications/J0004291
のTF1報告書及び法的意見書部分が該当。
ーー以上、共同研究第二期成果報告書追補版記載内容全体ーー
本件問い合わせ先：
グローバルフレンドシップ株式会社
担当：保倉 豊
参考：
産総研様との共同研究の第一弾結果概要報告[2015.04.30]
http://www.gfi.co.jp/01news20150430_377.html
産業技術総合研究所様との共同研究について[2014.11.27]
http://www.gfi.co.jp/01news20141127_362.html
その他関連リリース：
厚生労働省 改正労働安全衛生法 ストレスチェックでも
http://www.gfi.co.jp/01news20151201_391.html
ＧＦＩ ＩＳＭＳ再取得事前準備実験状況
ttp://www.gfi.co.jp/01news20151104_390.html
マイナンバーの行政機関等・地方公共団体等編から
http://www.gfi.co.jp/01news20151025_389.html
日本年金機構情報流出の検証報告から
http://www.gfi.co.jp/01news20151009_388.html
秘密分散技術（電子割符）の標準化について、
http://www.gfi.co.jp/01news20151002_387.html
次回マイナンバー法勉強会は、１０月０６日です。
http://www.gfi.co.jp/01news20150911_386.html
特定個人情報保護委員会様（以下、「委員会」）より、Q&Aの追加が出ました
http://www.gfi.co.jp/01news20150820_385.html
セキュリティ事故は発生するものです。
http://www.gfi.co.jp/01news20150728_384.html
注意喚起：秘密分散技術（一般名称：電子割符）の亜種にご注意ください。
http://www.gfi.co.jp/01news20150707_381.html
GFI電子割符R技術の基本的アルゴリズムに関して
http://www.gfi.co.jp/01news20120130_278.html