2018年度 ISS Squareシンポジウム (2019/2/22)

No. 230

ランプ型秘密分散法のシェアサイズ変換方式
How to Convert the Share Size of Ramp Secret Sharing Schemes

醍醐康夫・システム分科会・情報セキュリティ大学院大学
In ramp secret sharing scheme, it can be controlled coding efficiency and security of shares by parameter L. Increasing L of shares increases coding efficiency and decreases security.
Decreasing L of shares increases security and decreases coding efficiency. By using this property, for example, when the documents which are distributed by secret sharing scheme areused frequently, increasing L of shares of them increases the business efficiency because of increasing coding efficiency of shares. By reconstructing the secret of shares, and thengenerating new shares of different L, it can be converted L of shares to different L. But, there is an issue of processing cost and security. In this paper, we propose several schemes whichconvert L of shares to different L without reconstructing the secret of them. These schemes are in the premise that the confidential information is distributed by secret sharing scheme, andthe users reconstruct it temporarily and use it in their terminal, and our schemes are efficient if these are limited to its use.

1. 秘密分散法

3. 提案方式

秘密分散法とは，秘密情報の保有者（以下，ディーラー）が秘密情報を𝑛個の断片（以下，シェア）に分散して保管者（以下，参加者）が管理し，利用者（以下，ユーザー）がしきい値である𝑘個以上のシェアを参加者から集めることで秘密情報を復元できる，という技術である．ディーラーが秘密情報を4個のシェアに分散し，任意の3個のシェアを集めることで秘密情報を復元する(3,4)しきい値秘密
分散法の様子を次の図に示す．

ランプ型方式のシェアを，符号化効率や安全性の異なるシェアに変換する方式を提案する．ランプ型方式ではパラメーター𝐿によって符号化効率や安全性を変化させることができるため，𝐿が異なるシェアに変換する方式になる．
この提案方式が有用なのは，個人情報や機密情報などを業務で長期間利用する状
況における，情報の利用度に応じた符号化効率と安全性の切り替えである．例えば，電子文書管理システムにおいて，文書が作成されてから間もない利用度が高い時期は，業務効率を優先してシェアのデータサイズが小さいことが求められる
ため𝐿が大きいシェアを使用する．また，利用度が高い時期が過ぎたものの法的要求や文書管理規定上，数年から永年といった長期保存をしなければならない文書は，業務効率を多少犠牲にしても高い安全性が求められるため𝐿が小さいシェ
アを使用する．
𝐿が異なるシェアに変換するには，変換前のシェアを任意の𝑘個集めて秘密情報を復元してから，それを元に𝐿が異なるシェアを生成して参加者に分散する方法がある．しかし，変換にかかる処理コストが大きくなるうえに，ある時点で秘密情報を完全に復元する必要があるという，処理コストと安全性の課題がある．

2. 先行研究
秘密分散法に関する先行研究のうち，Shamirの (𝑘, 𝑛) しきい値秘密分散法（以下，Shamir方式）とランプ型秘密分散法（以下，ランプ型方式）を紹介する．
Shamir方式は，𝑛個に分散したシェアのうち𝒌個未満のシェアからは秘密情報に関する部分的な情報も全く得ることができないが，シェアのデータサイズが秘密情報と同一になるという特性がある．例えば1GBの秘密情報を8個のシェアに分散した場合は合計で8GBのデータサイズになる．
秘密情報とシェアは2次元平面上の数値として扱う．シェアを生成するための𝑘 −1次の多項式を𝑓 𝑥 ，𝑛個のシェアを 𝑥1 , 𝑦1 , ⋯ , 𝑥𝑛 , 𝑦𝑛 ，秘密情報を𝑦切片である𝑠とすると，𝑥座標が異なる𝑘点，例えば 𝑥1 , 𝑦1 , ⋯ , 𝑥𝑘 , 𝑦𝑘 から 𝑓 𝑥 が一意に定まる．
したがって，𝑠も一意に定まる．(𝑘, 𝑛) = (3,4)の場合のグラフを次の図に示す．
このシェア生成用多項式は
𝑓 𝑥 = 𝒔 + 𝑎1 𝑥 + 𝑎2 𝑥 2 𝑚𝑜𝑑 𝑝であり，秘密情報である𝒔を得るためには4個のシェアのうち3個が必要だが，2個（ 1, 𝑦1 と 2, 𝑦2 ）しか与えられていない場合は，𝒔があらゆる値をとり得て一意に定まらない．よって，𝑘個未満のシェアからは秘密情報が全く分からない．

ランプ型方式は，Shamir方式よりも安全性は低いが，符号化効率は高い，という特性を持つ．𝑘, 𝑛の他に𝐿というパラメーターが追加されており，この𝐿によって𝑘 − 𝐿個以下シェアからは秘密情報に関する部分的な情報も全く得ることができな
いが，𝑘 − 𝑡個(1 ≤ 𝑡 ≤ 𝐿 − 1)のシェアからは段階的に情報が得られる．また，1個のシェアに𝐿個の秘密情報を含めることができるため，例えば1GBの秘密情報を8個のシェアに分散した場合，𝐿を4とすると合計で2GBのデータサイズになる．
よって，Shamir方式と比較してシェアのデータサイズは1/𝐿となるが，安全性は低下する．
Shamir方式では秘密情報をシェア生成用多項式における定数項としていたが，ランプ型方式では秘密情報を複数の係数とすることでShamir方式の𝐿倍の秘密情報を扱えるようになる．
Shamir方式のシェア生成用多項式
𝑓 𝑥 = 𝒔 + 𝑎1 𝑥 + ⋯ + 𝑎𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝
ランプ型方式のシェア生成用多項式
𝑔 𝑥 = 𝒔𝟎 + ⋯ + 𝒔𝑳−𝟏 𝑥 𝐿−1 + 𝑏𝐿 𝑥 𝐿 + ⋯ + 𝑏𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝

提案方式は，ランプ型方式のシェアを集めて秘密情報を復元することなく，𝑳が異なるシェアへの変換を実現する．
シェアの変換は，シェアに含まれる秘密情報の一部を乱数でマスクすることで実現する．
例えば，次のような(𝑘, 𝐿, 𝑛) = 𝟖, 𝟔, 𝒏 のランプ型方式のシェア
𝑔𝑠1 𝑥𝑖 = 𝒔𝟎 + 𝒔𝟏 𝑥𝑖 + 𝒔𝟐 𝑥𝑖2 + 𝒔𝟑 𝑥𝑖3 + 𝒔𝟒 𝑥𝑖4 + 𝒔𝟓 𝑥𝑖5 + 𝑏𝑠1,6 𝑥𝑖6 + 𝑏𝑠1,7 𝑥𝑖7があるとして，シェアに含まれる𝒔𝟑 , 𝒔𝟒 , 𝒔𝟓 の係数の位置に乱数𝑟を配置した多項式から変換情報というデータ
𝑢1 𝑥𝑖 = 𝒓𝟏,𝟑 𝑥𝑖3 + 𝒓𝟏,𝟒 𝑥𝑖4 + 𝒓𝟏,𝟓 𝑥𝑖5 + 𝑏𝑟1,6 𝑥𝑖6 + 𝑏𝑟1,7𝑥𝑖7を生成する．この変換情報をシェアに加算することで 𝟖, 𝟑, 𝒏 のランプ型方式のシェア
𝑔𝑑1 𝑥𝑖 = 𝑔𝑠1 𝑥𝑖 + 𝑢1 𝑥𝑖= 𝒔𝟎 + ⋯ + 𝒔𝟐 𝑥𝑖2 + 𝒔𝟑 + 𝒓𝟏,𝟑 𝑥𝑖3 + ⋯ + 𝒔𝟓 + 𝒓𝟏,𝟓 𝑥𝑖5 + 𝑏𝑑1,6 𝑥𝑖6 + 𝑏𝑑1,7𝑥𝑖7に変換できる．

変換情報とあわせて，マスクする乱数を秘密情報とするシェアを分散することによって変換が完了する．これらのデータはコンバーターが生成する．シェアを変換する様子を示す．