Counterfeit Coin Problem Can be Extended to Secure Multiparty Computation
摘要
The counterfeit coin problem is a well-known logic puzzle with many variants. In its classic form, the goal is to identify a single counterfeit (lighter) coin among eight visually identical coins using a balance scale with the minimum number of measurements. The answer is not three but two, achieved by cleverly dividing the eight coins. In this study, we extend this problem to the setting of secure multiparty computation. Specifically, given coins whose weights depend on private inputs, a balance scale can be used to compute a predetermined function over those inputs without revealing any additional information. We formalize secure computations with a balance scale and propose secure computation protocols for logical functions such as the logical AND and majority function. In particular, our proposed protocol can efficiently compute the majority function with only a single measurement, whereas existing protocols with everyday objects require several steps, such as card-based protocols (Eurocrypt’89), private PEZ protocols (TCC’19), and bag&ball-based protocols (CSF’21).