CSF 2021, June 22, Session 4, 15:00–15:45
Cooking Cryptographers:
Secure Multiparty Computation Based on Balls and Bags
Daiki Miyahara1,2 Yuichi Komano3
Takaaki Mizuki1,2 Hideaki Sone1
1. Tohoku University, Email: daiki.miyahara.q4[at]alumni.tohoku.ac.jp
2. National Institute of Advanced Industrial Science and Technology (AIST)
3. Toshiba Corporation1

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion2

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion3

Analog of the Dining
Cryptographers problem[1]What is Cooking Cryptographers Problem?

✓Assume that Alice and Bob are cooking Borscht soup

AliceBorscht soupBob[1] D. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, Journal of Cryptology, vol. 1, pp. 65–75, 1988

4

Analog of the Dining
Cryptographers problem[1]What is Cooking Cryptographers Problem?

✓Assume that Alice and Bob are cooking Borscht soup

AliceBorscht soup

Bob

✓Prepared ingredients either paid out of pockets or funded by NFSA‡[1] D. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, Journal of Cryptology, vol. 1, pp. 65–75, 1988
‡ National Fictional Security Agency

5

Analog of the Dining
Cryptographers problem[1]What is Cooking Cryptographers Problem?

✓Assume that Alice and Bob are cooking Borscht soup

AliceBorscht soup

Bob

✓Prepared ingredients either paid out of pockets or funded by NFSA‡✓Respect each other’s ideology to have a relation to NFSA, but…

[1] D. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, Journal of Cryptology, vol. 1, pp. 65–75, 1988
‡ National Fictional Security Agency

6

Analog of the Dining
Cryptographers problem[1]What is Cooking Cryptographers Problem?

✓Assume that Alice and Bob are cooking Borscht soup
NFSA?

NFSA?

AliceBorscht soup

Bob

✓Prepared ingredients either paid out of pockets or funded by NFSA‡✓Respect each other’s ideology to have a relation to NFSA, but…
✓Wonder if they eat food funded by NFSA
[1] D. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, Journal of Cryptology, vol. 1, pp. 65–75, 1988
‡ National Fictional Security Agency

7

Cooking Cryptographers Problem: Secure AND Computation

AliceBob✓They are in the kitchen, and there are the ingredients and saucepans

8Cooking Cryptographers Problem: Secure AND Computationa∈ 0,1

Aliceb∈ 0,1

Bob✓They are in the kitchen, and there are the ingredients and saucepans✓Each of them has their private bit:
Funded by NFSA = 0, Paid out of pocket = 1
9Cooking Cryptographers Problem: Secure AND Computationa∈ 0,1

Aliceb∈ 0,1

Bob✓They are in the kitchen, and there are the ingredients and saucepans✓Each of them has their private bit:
Funded by NFSA = 0, Paid out of pocket = 1✓The goal: obtain a∧b without revealing any information about a and b
10

Cooking Cryptographers Problem: Secure AND Computationa∈ 0,1

Alice

Input

Input

ab

OutputOutputa∧ba∧bb∈ 0,1

Bob✓They are in the kitchen, and there are the ingredients and saucepans✓Each of them has their private bit:
Funded by NFSA = 0, Paid out of pocket = 1✓The goal: obtain a∧b without revealing any information about a and b
11

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion
12

Our Proposed Protocol Performing Secure AND Computation

AliceBob

1. Alice puts ingredients into saucepans depending on the value of a(so that Bob cannot see them):
a=0

a=1

13

Our Proposed Protocol Performing Secure AND Computation

AliceBob

2. Bob puts ingredients into saucepans depending on the value of b
(so that Alice cannot see them):
b=0

b=1

14

Our Proposed Protocol Performing Secure AND Computation

AliceTheposition isThe positionBobis the
2. Bob putsdifferentingredients
into saucepans depending
value of bto Alicesameonto theAlice(so that Alice cannot see them):

b=0

b=1

15

Our Proposed Protocol Performing Secure AND Computation✓Consider the breakdown of ingredients in the three saucepans:

16

Our Proposed Protocol Performing Secure AND Computation✓Consider the breakdown of ingredients in the three saucepans:

a=0/b=0a=1/b=0a=0/b=1

a=1/b=1

17

Our Proposed Protocol Performing Secure AND Computation✓Consider the breakdown of ingredients in the three saucepans:

a=0/b=0a=1/b=0a=0/b=1a=1/b=1

The carrots are in
the same saucepan

Both paid out of pockets
18

Our Proposed Protocol Performing Secure AND Computation✓Consider the breakdown of ingredients in the three saucepans:
At least one of them was funded by NFSA
a=0/b=0a=1/b=0a=0/b=1

a=1/b=1

The carrots are in
the same saucepan

The carrots are indifferent saucepans

Both paid out of pockets
19Our Proposed Protocol Performing Secure AND Computation

3. Shuffling
AliceBob

3. Shuffle the order of the three saucepans

20Our Proposed Protocol Performing Secure AND Computation3. ShufflingAlice

4. EatingBob

3. Shuffle the order of the three saucepans
4. Enjoy eating the cooked Borscht soup:
If there is a saucepan only with carrots, then a∧b=1 (pockets);
otherwise, a∧b=0 (NFSA)

21

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion
22

Change the Settings from Kitchen to Using Balls and Bags
✓Replace: ingredients ↦ balls, saucepans ↦ bags
Cooking every time to performsecure computations is difficult…

？

23Change the Settings from Kitchen to Using Balls and Bags
✓Replace: ingredients ↦ balls, saucepans ↦ bags
Cooking every time to performsecure computations is difficult…

？
✓ Balls and bags are easy to prepare, and they are also familiar tools
for learning Probability in high school24Change the Settings from Kitchen to Using Balls and Bags
✓It also performs the secure computation if we replace ingredients andsaucepans with balls and bags, respectively
The red balls arein different bags

a=0/b=0a=1/b=0a=0/b=1

a=1/b=1

The red balls arein the same bag25

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion
26

Contribution: Secure computations using balls and bagsa∈ 0,1

Alice

Input

Input

ab

OutputOutputa∧ba∧bb∈ 0,1

Bob✓Employ a property that the order of balls in a bag is disordered✓Extend our two-input AND to the multi-input AND27

Contribution: Secure computations using balls and bagsa∈ 0,1

Alice

Input

Input

ab

OutputOutputa∧ba∧bb∈ 0,1

Bob✓Employ a property that the order of balls in a bag is disordered✓Extend our two-input AND to the multi-input AND✓Formalize secure computation using balls and bags
✓Construct a protocol for any Boolean function28

Outline
1. Introduction: Cooking Cryptographers Problem
2. Our Proposed Protocol

3. Changing the Settings
4. Contribution
5. Conclusion
29

Merits of cryptographic protocols using physical objects✓Employ physical properties that can be intuitively understood[2]✓Correctness and security are clear even for non-experts✓The notion of secure multiparty computations can be illustrated[3,4]？

？

？

Invisible[2] T. Moran et al., Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, EUROCRYPT 2006, vol. 4004, pp. 88–108, 2006
[3] A. Marcedone et al., Secure Dating with Four or Fewer Cards, Cryptology ePrint Archive, Report 2015/1031, 2015[4] R. Pass et al., A Course in Cryptography, 2010[5] S. Izmalkov et al., Rational Secure Computation and Ideal Mechanism Design, FOCS 2005, pp. 585–594, 2005
[6] M. Lepinksi et al., Collusion-free protocols, STOC 2005, pp. 543–552, 200530

Merits of cryptographic protocols using physical objects✓Employ physical properties that can be intuitively understood[2]✓Correctness and security are clear even for non-experts✓The notion of secure multiparty computations can be illustrated[3,4]？

？

？

Invisible✓Implement stronger cryptographic notions✓Ballot boxes can be used to implement rational secure computations[5]✓The use of envelopes is essential to realize collusion-free protocols[6][2] T. Moran et al., Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol, EUROCRYPT 2006, vol. 4004, pp. 88–108, 2006
[3] A. Marcedone et al., Secure Dating with Four or Fewer Cards, Cryptology ePrint Archive, Report 2015/1031, 2015[4] R. Pass et al., A Course in Cryptography, 2010[5] S. Izmalkov et al., Rational Secure Computation and Ideal Mechanism Design, FOCS 2005, pp. 585–594, 2005
[6] M. Lepinksi et al., Collusion-free protocols, STOC 2005, pp. 543–552, 2005

31