Presentation | 2009-03-09 A Coding Theorem for Cheating-Detectable (2,2)-Threshold Schemes Hiroki KOGA, Mitsugu IWAMOTO, Hirosuke YAMAMOTO, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In this paper, we focus on a (2,2)-threshold scheme in the presence of an opponent who impersonates one of the two participants. We consider an asymptotic setting where two shares are generated by an encoder at one time from n secrets generated from a stationary memoryless source and a uniform random number available only to the encoder. We introduce a notion of the correlation level of the two shares and give a coding theorem for the rates of the shares and the uniform random number. It is shown that, for any (2,2)-threshold scheme with the correlation level r in a certain class, none of the rates can be less than H(S)+r, where H(S) denotes the entropy of the source. We also show that the impersonation by the opponent is successful with probability at least 2^<-nr>. In addition, we prove the existence of a sequence of encoders and decoders of the (2,2)-threshold scheme that asymptotically achieves all the bounds on the rates and the success probability of the impersonation. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Secret sharing scheme / (2,2)-threshold scheme / coding theorem / cheating detection |
Paper # | IT2008-66,ISEC2008-124,WBS2008-79 |
Date of Issue |
Conference Information | |
Committee | WBS |
---|---|
Conference Date | 2009/3/2(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Wideband System(WBS) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Coding Theorem for Cheating-Detectable (2,2)-Threshold Schemes |
Sub Title (in English) | |
Keyword(1) | Secret sharing scheme |
Keyword(2) | (2,2)-threshold scheme |
Keyword(3) | coding theorem |
Keyword(4) | cheating detection |
1st Author's Name | Hiroki KOGA |
1st Author's Affiliation | Graduate School of Systems and Information Engineering, University of Tsukuba() |
2nd Author's Name | Mitsugu IWAMOTO |
2nd Author's Affiliation | Graduate School of Information Systems, University of Electro-Communications |
3rd Author's Name | Hirosuke YAMAMOTO |
3rd Author's Affiliation | Graduate School of Frontier Sciences, University of Tokyo |
Date | 2009-03-09 |
Paper # | IT2008-66,ISEC2008-124,WBS2008-79 |
Volume (vol) | vol.108 |
Number (no) | 474 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |