ある多数決ルールを用いた不正者全員の特定が可能な(k,n)しきい値法 (情報理論)  [in Japanese] A (k,n)-Threshold Scheme with Detectability of All the Cheaters Based on a Certain Majority Rule  [in Japanese]

Search this Article

Author(s)

    • 島崎 憲明 SHIMAZAKI Noriaki
    • 筑波大学大学院システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba
    • 古賀 弘樹 KOGA Hiroki
    • 筑波大学大学院システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba

Abstract

(k,n)しきい値法ではn個のシェアのうち任意のk個のシェアが集まれば秘密を復元できるが,k個の中に改ざんされたシェアが存在した場合には正しい復元が行えないという問題がある.不正者がc人存在し,全員がシェアの改ざんを行う状況下における正しい秘密の復元と不正者の特定を可能とするため,筆者らは2012年にHarn-Linによる手法の改良策である「改良多数決法」を提案し,正確な秘密の復元と不正者特定が成功するための条件がn-c>c+k-1であることを示した.本稿では成功条件をn-c≧c+k-1に拡大するため,改良多数決法に(c+1,n)しきい値法(cは既知とする)から生成されるチェックシェアを追加で導入した「参加者部分集合法」を提案し,1に近い確率で正しい秘密の復元と不正者全員の正確な特定を実現できることを示す.

In Shamir's (k, n)-threshold scheme, if cheaters are involved in k participants and give illegal shares in the reconstruction phase, the k participants always fail to reconstruct the correct secret. In order to raise robustness of Shamir's scheme against cheaters, we recently proposed a reconstruction scheme and showed that the secret is always reconstructed correctly if n-c > c+k-1, where c denotes the number of cheaters and all the c cheaters collude for generating illegal shares. In this paper, we consider the situation where n-c ≧ c+k-1 is satisfied and c is known. It is shown that if shares of Shamir's (c, n)-threshold scheme as well as (k, n)-threshold scheme are distributed to n participants in advance, we can not only reconstruct a secret correctly but also identify all the c cheaters with probability close to one.

Journal

  • IEICE technical report. Information theory

    IEICE technical report. Information theory 114(224), 19-24, 2014-09-19

    The Institute of Electronics, Information and Communication Engineers

Codes

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