Two generalizations of a coding theorem for a (2, 2)-threshold scheme with a cheater
Hiroki Koga · 2010
This paper presents two new coding theorems on a (2, 2)-threshold scheme with an opponent who impersonates one of the shareholders. In the (2, 2)-threshold scheme an encoder blockwisely generates two shares Xnand Ynfrom n secrets Snand a uniform random number En, where Snis generated from a general source. There are three kinds of inputs to a decoder, (Nn., Yn), (X̅n, Xn) and (Xn, Y̅n), where X̅nand Y̅nare fraudulent shares generated by the opponent. The decoder judges whether the input is legitimate or not under negligible decoding error probability that vanishes as n → ∞. The two coding theorems given in this paper characterize the minimum attainable rates of Xn, Ynand Enand the maximum attainable exponent of the probability of the successful impersonation attack. It turns out that the (2, 2)-threshold scheme with a cheater is related to not only hypothesis testing but also optimistic coding of general sources and channels.