LT符号を用いた高速な線形ランプ型しきい値秘密分散法の検討 (情報理論)  [in Japanese] A Construction of an Efficient Linear Ramp Threshold Secret Sharing Scheme Using an LT code  [in Japanese]

Search this Article

Author(s)

    • 古賀 弘樹 KOGA Hiroki
    • 筑波大学大学院システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba
    • 本庄 俊太郎 HONJO Shuntaro
    • 筑波大学大学院システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba

Abstract

これまで提案されてきた(k,L,n)線形ランプ型しきい値秘密分散法は,行列演算によるものが多くその計算量が課題となっている.秘密分散法における秘密情報の復元は消失訂正符号における消失訂正と同じと解釈できることから,高速な消失訂正符号を用いれば高速な秘密分散法を構成できると考えられる.そこで,本稿では符号化・復号化の計算量がある定数δ>0に対してO(k・ln(k/δ))である消失訂正符号であるLT符号を用いて,計算量がO(k・ln(k/δ))の(k,L,n)線形ランプ型しきい値秘密分散法を構成することを試みる.その際, LT符号単独で秘密分散法を構成した場合には, LT符号の生成行列が疎行列であることに起因して,条件付きエントロピーの特性が(k,L,n)線形ランプ型しきい値秘密分散法とは大きく乖離することを数値的に示す.この問題を解決するため, LT符号の前に生成行列が置換行列と下三角行列の積で定義される符号を連接することを提案する.実験により,提案手法は一様独立な秘密情報Sと一様独立乱数Uの長さの和kに対してその計算量をO(k・ln(k/δ))に保ったまま,安全性を(k,L,n)線形ランプ型しきい値秘密分散法に十分近づけることができることを確認した.

In conventional secret sharing schemes computational complexity cannot be negligible when the number of participant is quite large. Since reproduction of a secret in secret sharing schemes can be interpreted as erasure correction in erasure codes, we can construct an efficient secret sharing scheme if an efficient erasure correction code is available. In this paper we investigate construction of a ramp secret sharing scheme using the LT codes with security close to the linear (k,L,n)-threshold ramp scheme, where the computational complexity of the scheme is O(k・ln(k/δ)) for a constant δ>0. We first numerically show that, if we directly apply the LT codes, the security of the scheme is not close to the linear (k,L,n)-threshold ramp scheme due to the sparseness of the generator matrix of the LT codes. Next, we show that a simple precode using a permutation matrix and a certain lower triangular matrix makes the security of the scheme very close to the linear (k,L,n)-threshold ramp scheme, while the precode does not increase the order of the computational complexity.

Journal

  • IEICE technical report. Information theory

    IEICE technical report. Information theory 113(483), 193-200, 2014-03-10

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110009861939
  • NII NACSIS-CAT ID (NCID)
    AN10013083
  • Text Lang
    JPN
  • ISSN
    0913-5685
  • NDL Article ID
    025412178
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top