A Cryptanalysis against the Cheating Detectable Secret Sharing from NISS 2019
Kiminori Kaneko, Satoshi Obana · 2023
A cheating detectable secret sharing (CDSS for short) scheme is a variant of secret sharing scheme with the extra functionality to detect forgery of shares when some of shares are submitted maliciously. In NISS 2019, Becerra and Vega proposed a CDSS which employs addition over $\mathbb{Z}_{2^{m}}$ as the verification function whereas the secret is distributed and reconstructed with computation over $\mathbb{F}_{2^{m}}$. They proved that the scheme is secure and the bit length of the share meets the lower bound with equality. In this paper, we show that the scheme is insecure by showing that only a single cheater can forge the resulting secret without being detected by the reconstruction algorithm. We present two types of attack. The probability of successful cheating attack of the first attack is 1 but the pattern of forgery is limited. In the second attack, the successful cheating probability is less than the first one but the pattern of forgery is more flexible. The successful cheating probabilities of the proposed attacks are evaluated with the careful analysis about structures of additions over $\mathbb{Z}_{2^{m}}$ and $\mathbb{F}_{2^{m}}$, which will be of independent interest.