Coding Theorems for a (2,2)-threshold Scheme with Detectability of Impersonation Attacks

Mitsugu Iwamoto, Hiroki Koga, and Hirosuke Yamamoto

IEEE Transactions on Information Theory, Vol. 58, No.9, pp.6194-6206, September 2012

Coding theorems on a $(2,2)$-threshold scheme with an opponent are discussed in an asymptotic setup, where the opponent tries to impersonate one of the two participants. A situation is considered where $n$ secrets $S^{n}$ from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to $S^{n}$ with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a $(2, 2)$-threshold scheme that is secure against the impersonation attack by the opponent. It is shown that if the correlation level between the two shares equals to $\ell geq 0$, the minimum attainable rates coincide with $H(S)+\ell $, where $H(S)$ denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to $\ell $. It is also shown that a simple scheme using an ordinary $(2,2)$-threshold scheme attains all the bounds as well.

Index Terms : Correlated sources, hypothesis testing, impersonation attack secret sharing scheme, threshold scheme.

Final submission version (PDF) (261 Kbytes)
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

DOI: 10.1109/TIT.2012.2204546