見出し画像

暗号理論（２）

No.5

はじめに

こんにちは、No.5です。
今回も暗号についての記事となります。

暗号理論１回目の前回は公開鍵暗号とRSA暗号を紹介しましたが、
暗号理論２回目は秘密分散法を紹介します。

秘密分散法とは

秘密分散法とは、秘密情報を保有するディーラーが秘密情報をシェアに分散して参加者が管理し、ユーザーがシェアの一部を参加者から集めることで秘密情報に復元できる、という方式です。[1][2]

秘密分散法の分散
秘密分散法の復元

秘密分散法には、ユーザー、ディーラー、参加者、シェアという用語が出てきます。

  • ユーザー
    機密情報や個人情報などの秘密情報を利用します

  • ディーラー
    秘密情報からシェアを生成したうえで参加者に分散します

  • 参加者
    ディーラーから分散されたシェアを保管します

  • シェア
    秘密情報に復元するための情報です

利用用途

企業や組織における個人情報の漏えい、紛失事故が後を絶ちませんが、発生原因としては情報の管理ミス、誤操作、紛失、置き忘れなどの人為的ミスが多いのです。[3]
人為的ミスを完全に防ぐことは困難なので、発生した場合の影響を最小限に抑えることが重要です。
この対策に有効な技術の１つとして秘密分散法が利用できます。

例）安全に情報資産を搬送する

秘密分散法を利用することで、安全に情報資産を搬送できるようになります。[4]
例えば、自社で作成した機密文書を客先まで安全に搬送したい場合、まず機密文書を３個のシェアに分散し、２人の担当者がそれぞれのシェアをUSBメモリーなどの記録媒体に格納して客先まで搬送します。
次に、客先で復元できる数のシェアを集めて元の機密文書に復元します。
もし、復元できる数未満の担当者が搬送途中にシェアを紛失しても、機密文書が漏えいすることはありません。

例）安全に情報資産を保管する

秘密分散法を利用することで、クラウドストレージサービスにおいて安全に情報資産を保管できるようになります。[5]
例えば、機密文書を社内で安全に共有したい場合、まず分散したシェアを異なるクラウドストレージに格納します。
復元できる数未満のシェアが漏えいしても機密情報の漏えいにはなりません。
また、クラウドストレージの障害や激甚災害などにより復元できる数未満が稼働していない状態でも機密文書を保護でき、業務が停止することはありません。

主な方式

秘密分散法の性質を持つ主な方式は次のとおりです。

  • (𝑘,𝑛)しきい値秘密分散法 [1][2]

  • ランプ型しきい値秘密分散法 [6][7]

  • プロアクティブ秘密分散法 [8]

  • VSS法（Verifiable Secret Sharing scheme）[8]

  • AONT（All Or Nothing Transform）[9]

このうち、(𝑘,𝑛)しきい値秘密分散法においてAdi Shamirが提唱した方式（Shamirの(𝑘,𝑛)しきい値秘密分散法 [1]）を紹介します。

Shamirの(𝒌,𝒏)しきい値秘密分散法とは

Shamirの(𝑘,𝑛)しきい値秘密分散法（以下、Shamir方式）は、ディーラーが秘密情報を𝑛個のシェアに分散し、そのうち、しきい値である𝑘個を集めることで秘密情報に復元できるという特性を持ちます。

シェア生成には、シェア生成多項式

を用います。
参加者𝑖のシェアは

となります。

Shamir方式の利点として、秘密鍵による暗号処理を使用しないため、鍵を管理する必要がないことがあります。
また、情報理論的安全性に基づいているため、しきい値未満のシェアが漏えいしても将来にわたり秘密情報が漏えいする危険性がないこともあります。

一方、Shamir方式の欠点として、シェアのデータサイズが秘密情報と同じになる仕組みのため、多数のシェアに分散するとシェアの合計サイズが大きくなることがあります。

安全性

Shamir方式の安全性は情報理論的安全性に基づいており、無限の計算リソースを集めて処理しても、𝑘個未満のシェアからは秘密情報の部分的な情報も全く得ることができません。
なお、情報理論的安全性に対して計算量的安全性という安全性の概念があります。解読することが非常に困難な仕組みであることを安全性の根拠としていますが、解読能力の向上によりその安全性が脅かされる可能性があります。

例えば、しきい値𝑘=3の場合は、シェア生成多項式である

において、秘密情報である𝑠を得るためには𝑛個のシェアのうち３(=𝑘)個が必要ですが、次の𝑓(𝑥)=𝑠+𝑓_1 𝑥+𝑓_2 𝑥^2 mod 𝑝のグラフでは２(=𝑘−1)個（(1,𝑓(1))と(2,𝑓(2))）しか与えられていないため、もう１個のシェアによっては𝑠があらゆる値をとり得て一意に定まりません。
よって、𝑘個未満のシェアでは秘密情報が全く分からないことになります。

𝑓(𝑥)=𝑠+𝑓_1 𝑥+𝑓_2 𝑥^2 mod 𝑝

有限体

Shamir方式では、扱う値を無限にせず、整数で計算するために位数（集合の元の個数）が素数の有限体を利用します。

有限体は次の性質を持ちます。

  • 素数𝑝を法とする整数の集合

  • 四則演算（加減乗除）が可能

    • 加法、乗法が定義されている

    • 逆元が存在するため、減法、除法も定義できる

位数が３（素数）の例は次のとおりです。
減法のうち「０から２を引いた値」は２を足して０になる数となり、２の加法の逆元となる「１」が求められます。
除法のうち「１を２で割った値」は２を掛けて１になる数となり、２の乗法の逆元となる「２」が求められます。

位数が３の加法、減法、乗法、除法

位数が４（素数ではない）の例は次のとおりです。
位数が素数でないと除法が定義できません。
{0,1,2,3}の場合「１を２で割った値」 と「３を２で割った値」の値が求められないため、有限体ではなくなり割り算ができなくなります。

位数が４の加法、減法、乗法、除法

分散方法

Shamir方式において、実際に秘密情報からシェアを生成してみましょう。
手順は次のとおりです。

  1. まず、秘密情報𝑠を用意します
    例）99

  2. 有限体に含まれる数値の総数𝑝（素数）を用意します
    例）127

  3. 分散したデータを復元するために必要なデータの数（しきい値）𝑘を選びます
    例）4

  4. 𝑘−1個の多項式の係数を有限体からランダムに選びます
    例）𝑓_1:8, 𝑓_2:3, 𝑓_3:7

  5. 𝑘−1次の多項式（𝑓(𝑥)=𝑠+𝑓_1 𝑥+…+𝑓_(𝑘−1) 𝑥^(𝑘−1) mod 𝑝）を生成します
    例）𝑓(𝑥)=99+8𝑥+3𝑥^2+7𝑥^3 mod 127

  6. 分散する数分のシェア𝑓(𝑖)を計算します
    例）(1, 117), (2, 56), (3, 85), (4, 119), (5, 73)

𝑓(𝑥)=99+8𝑥+3𝑥^2+7𝑥^3 mod 127のグラフは次のとおりです。
シェア𝑓(𝑥)は0から126までの間の値になっています。

𝑓(𝑥)=99+8𝑥+3𝑥^2+7𝑥^3 mod 127

𝑓(𝑥)=99+8𝑥+3𝑥^2+7𝑥^3のグラフは次のとおりです。
有限体ではないので、シェア𝑓(𝑥)は(2, 183), (3, 339), ... のように無限大に近づいていきます。

𝑓(𝑥)=99+8𝑥+3𝑥^2+7𝑥^3

復元方法

Shamir方式において、実際に分散したシェアから秘密情報に復元してみましょう。
手順は次のとおりです。

  1. 分散したデータを復元するために必要なデータの数（しきい値）𝑘の個数分のシェアを集めます
    例）(1, 117), (2, 56), (3, 85), (4, 119)

  2. 多項式補間を利用して秘密情報を求めます
    ラグランジュ補間を利用する場合、𝑥が0の場合のみ評価すればよいので次の式になります

　上記の式に値を代入すると秘密情報である「99」が求められます

まとめ

  • 秘密分散法は、ディーラーが秘密情報をシェアに分散して参加者が管理し、ユーザーがシェアの一部を参加者から集めることで秘密情報に復元できる、という方式である

  • Shamir方式は秘密鍵による暗号処理を使用しないため、鍵を管理する必要がない

  • Shamir方式の安全性は情報理論的安全性に基づいており、𝑘個未満のシェアからは秘密情報の部分的な情報も全く得ることができない

  • Shamir方式のシェアのデータサイズは秘密情報と同一になる

いかがでしたか？
Shamir方式は、前回紹介したRSA暗号と同様に、素数と剰余演算を用いることによって分散と復元を簡単に実現していることがお分かりいただけたでしょうか？

アルゴリズムや安全性などについてさらに詳しく知りたい方は参考文献を参照してみてください。

参考文献

  • [1] Adi Shamir, "How to Share a Secret", Massachusetts Institute of Technology, 1979.

  • [2] G.R. Blakley, "Safeguarding cryptographic keys", Proceedings of the AFIPS 1979 National Computer Conference, Volume 48, pp 313–317, 1979.

  • [3] 日本ネットワークセキュリティ協会, "2016年 情報セキュリティインシデントに関する調査報告書", 2017.

  • [4] 保坂, 多田, 加藤, "秘密分散法とその応用", 東芝レビュー Volume 62, No.7, 2007.

  • [5] 白山, 金井, 谷本, 佐藤, "秘密分散を用いたセキュアなクラウドストレージシステムの実装と評価", SCIS 2016.

  • [6] G.R. Blakley, C. Meadows, "Security of ramp schemes", Advances in Cryptology-CRYPTO '84, Lecture Note on Computer Science, Volume 196, pp 242–268, 1985.

  • [7] 山本博資, "(k, L, n) しきい値秘密分散システム", 電子通信学会論文誌 Volume J68-A, No. 9, pp 945-952, 1985.

  • [8] Herzberg, Jarecki, Krawczyk, Yung, "PROACTIVE SECRET SHARING Or: How to Cope With Perpetual Leakage", IBM T.J. Watson Research Center,　1998.

  • [9] R.L. Rivest, "All-or-Nothing Encryption and the Package Transform", MIT Laboratory for Computer Science, 1997.

この記事が気に入ったらサポートをしてみませんか？