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

Abstract

In this paper, we discuss coding theorems on a \((2, 2)\)--threshold scheme in the presence of an opponent who impersonates one of the two shareholders in an asymptotic setup. We consider a situation 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 an opponent. It is shown that, if the correlation level between the two shares equals to an \(\ell \ge 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\). We also give a simple construction of an encoder and a decoder using an ordinary \((2,2)\)--threshold scheme where the two shares are correlated and attains all the bounds.