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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Counterfeit Coin Problem Can be Extended to Secure Multiparty Computation

  • Shohei Kaneko,
  • Yang Li,
  • Kazuo Sakiyama,
  • Daiki Miyahara

摘要

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).