Cooking Cryptographers: Secure Multiparty Computation Based on Balls and Bags

Daiki Miyahara, Yuichi Komano, Takaaki Mizuki, Hideaki Sone

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)


Imagine two cryptographers wishing to securely compute the AND value of their secret input bits. They are in the kitchen, where all they have are three saucepans with Borscht soup and some kinds of ingredients. Interestingly, by secretly putting ingredients in the saucepans depending on their inputs, they can find only the AND value from the taste of the cooked Borscht. Because cooking for secure computations is not so convenient, let us regard ingredients and saucepans (with Borscht soup) as balls and bags, respectively, which are easy to handle and also familiar tools for learning Probability in high school. Then, our problem is generalized as: Can we realize secure multiparty computations (MPCs) with balls and bags? There are techniques to realize MPCs with everyday objects, such as physical cards, coins, and a PEZ dispenser. We encode the input bits with such objects and securely compute some predetermined function using them. In this paper, we present a novel technique based on the physical properties of balls and bags. That is, our challenges are how to utilize an interesting feature that the balls become disordered immediately after they are put into a bag, namely they are "automatically shuffled." We give the first framework of MPCs using balls and bags (namely, ball-based cryptography), and propose secure AND computation and general MPCs. Our protocols are realizations of usable security which helps people with understanding the principles of MPCs as well as solving social problems in daily life.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 34th Computer Security Foundations Symposium, CSF 2021
PublisherIEEE Computer Society
ISBN (Electronic)9781728176079
Publication statusPublished - 2021
Event34th IEEE Computer Security Foundations Symposium, CSF 2021 - Virtual, Online, Croatia
Duration: 2021 Jun 212021 Jun 25

Publication series

NameProceedings - IEEE Computer Security Foundations Symposium
ISSN (Print)1940-1434


Conference34th IEEE Computer Security Foundations Symposium, CSF 2021
CityVirtual, Online


  • Real-life handson cryptography
  • Secure multiparty computation
  • Urn problem


Dive into the research topics of 'Cooking Cryptographers: Secure Multiparty Computation Based on Balls and Bags'. Together they form a unique fingerprint.

Cite this