The Landscape of Computing
Symmetric 𝑛𝑛-Variable Functions
with 2𝑛𝑛 Cards

Suthee Ruangwises
The University of Electro-Communications,Tokyo, JapanCiE 2023 - Batumi, Georgia
July 24, 2023
1

Introduction

2

Secure Multi-Party Computation
 Alice and Bob want to know if they bothlike each other.

◦ No one wants to confess first.
 Needs a protocol that only distinguishes

between the two cases: they both likeeach other, and anything else.
YES / NOYES / NO

3

Secure Multi-Party Computation
 Each having a bit 𝑎𝑎 and 𝑏𝑏 of either 0 or 1.
 Needs a protocol that computes 𝑎𝑎 ∧ 𝑏𝑏

without leaking unnecessary information.
◦ If a player’s bit is 1, he/she inevitably knows
other player’s bit.
◦ If a player’s bit is 0, he/she should know
nothing about other player’s bit.

4

Card-based Protocols
 Protocols using physical cards
 Does not require computer Uses only small, portable objects
 Easy for observers to verify thecorrectness and security, even for nonexperts
 Suitable for teaching purpose

5The Five-Card Trick
 Developed by den Boer in 1989,

beginning of the study in card-basedcryptography.
 Uses five cards: three identical ♣ cards
and two identical ♥ cards.
 Encodes 0 by ♣♥ and 1 by ♥♣.

6

The Five-Card Trick Each player is given one ♣ and one ♥,with another ♣ (helping card) faced
down on the middle of table.
 Alice places her cards encoding 𝑎𝑎 to theleft of the middle card.
 Bob places his cards encoding 𝑏𝑏 to theright of the middle card.

⍰⍰♣⍰⍰𝑎𝑎𝑏𝑏7

♣♥♣♣♥♣♥♣♥♣

𝑎𝑎 = 0, 𝑏𝑏 = 0

♣♥♣♥♣

♣♥♣♣♥

𝑎𝑎 = 0, 𝑏𝑏 = 1

𝑎𝑎 = 0, 𝑏𝑏 = 0♥♣♣♣♥♥♣♣♥♣

𝑎𝑎 = 1, 𝑏𝑏 = 0

𝑎𝑎 = 0, 𝑏𝑏 = 1

♥♣♣♥♣

♥♣♣♣♥

𝑎𝑎 = 1, 𝑏𝑏 = 1

𝑎𝑎 = 1, 𝑏𝑏 = 0
𝑎𝑎 = 1, 𝑏𝑏 = 1

Then, we swap the fourth and the fifth cards.
8♣♥♣♥♣
𝑎𝑎 = 0, 𝑏𝑏 = 0♣♥♣♣♥
𝑎𝑎 = 0, 𝑏𝑏 = 1♥♣♣♥♣
𝑎𝑎 = 1, 𝑏𝑏 = 0♥♣♣♣♥
𝑎𝑎 = 1, 𝑏𝑏 = 1

♣

♣ ♥♥♣
♣♥ ♥♣♣
♥
♣ ♣♥♣
♥♣
♥
♣♣

Observe the cyclic rotation of the deck.
9The Five-Card Trick We obscure the initial position of the cards

by shuffling the deck into a random
uniform cyclic permutation.

◦ i.e. a permutation uniformly chosen from𝑖𝑖𝑖𝑖, 12345 , 12345 2 , 12345 3 , 12345 4

 Can distinguish the case 𝑎𝑎 = 𝑏𝑏 = 1 fromother cases.

10The Four-Card Trick Later, in 2012, Mizuki et al. showed that theAND function can be computed with fourcards, using no helping card.

11Other Functions
 Besides the AND function, protocols tocompute other Boolean functions have also
been developed.
 In 2009, Mizuki and Sone developed a fourcard XOR protocol.

12Other Functions
 As each input bit is encoded by two cards,computing an 𝑛𝑛-variable function requires
at least 2𝑛𝑛 cards.
 Any 𝑛𝑛-variable symmetric function can becomputed with 2𝑛𝑛 + 2 cards (Nishida etal., 2015).
 We are interested in optimal protocols
that use exactly 2𝑛𝑛 cards.

13

Properties of Protocols
 Number of shuffles – as low as possible
 Committed format – output is in the sameformat as input (♣♥ for 0 and ♥♣ for 1)

14

Symmetric Boolean Functions

15

Symmetric Boolean Functions
 A Boolean function 𝑓𝑓: {0,1}𝑛𝑛 → {0,1}𝑛𝑛 iscalled symmetric if
𝑓𝑓 𝑥𝑥1 , … , 𝑥𝑥𝑛𝑛 = 𝑓𝑓 𝑥𝑥𝜎𝜎 1 , … , 𝑥𝑥𝜎𝜎 𝑛𝑛
for any 𝑥𝑥1 , … , 𝑥𝑥𝑛𝑛 and any permutation(𝜎𝜎 1 , … , 𝜎𝜎 𝑛𝑛 ) of (1, … , 𝑛𝑛).

 Note that the output value only depends

on the sum ∑𝑛𝑛𝑖𝑖=1 𝑥𝑥𝑖𝑖 .

16

Symmetric Boolean Functions
 Denote an n-variable symmetric Booleanfunction by 𝑆𝑆𝑋𝑋𝑛𝑛 for some 𝑋𝑋 ⊆ {0, … , 𝑛𝑛}.

𝑛𝑛∑
1,if𝑥𝑥𝑖𝑖 ∈ 𝑋𝑋;
𝑛𝑛𝑖𝑖=1
 𝑆𝑆𝑋𝑋 = �0, otherwise𝑛𝑛 E.g. 𝑥𝑥1 ∧ ⋯ ∧ 𝑥𝑥𝑛𝑛 is denoted by 𝑆𝑆{𝑛𝑛} .
17Symmetric Boolean Functions
 If 𝑓𝑓 is computable by a number of cards,◦ Negating all variables in 𝑓𝑓 is also computableby the same number of cards.
◦ So is the negation of 𝑓𝑓.

 We can classify all 𝑛𝑛-variable symmetricfunctions into several NPN-equivalenceclasses.
𝑛𝑛 𝑆𝑆𝑋𝑋𝑛𝑛 is in the same class as 𝑆𝑆 0,…,𝑛𝑛 −𝑋𝑋 and𝑛𝑛
𝑆𝑆{𝑛𝑛−𝑥𝑥|𝑥𝑥∈𝑋𝑋}.

18

Summary of Protocols

19

Two Variables
 Eight functions
 Three classes
 Trivial (constant), AND, XOR

20

Two VariablesComm
itted?

#Shuffles

FunctionName𝑆𝑆∅3

Constant
XOR

Mizuki-Sone, 2009✔

13
𝑆𝑆{2}

ANDMizuki et al., 2012

✘23
𝑆𝑆{1}

Protocoltrivial

Other Functions in theSame Class

3
𝑆𝑆{0,1,2}
3
𝑆𝑆{0,2}3
3
3, 𝑆𝑆{0,1}, 𝑆𝑆{1,2}
𝑆𝑆{0} No four-card committed-format AND

protocol with finite number of shuffles(Koch et al., 2015)21

Three Variables
 16 functions
 Six classes (one is trivial) Fully solved in 2023.

22

Three Variables
Committed?

#Shuffles

Function

Name

𝑆𝑆∅3

Constant
XOR

Mizuki-Sone, 2009

✔

2

3
𝑆𝑆{3}

AND

Mizuki, 2016✘53
𝑆𝑆{1,3}3
𝑆𝑆{0,3}3
𝑆𝑆{2,3}3
𝑆𝑆{1}ProtocoltrivialIsuzugawa et al., 2021

Equality

Shinagawa-Mizuki, 2019

R-Itoh, 2021
Majority

Toyoda et al., 2021

-Shikata et al., 2023

✘2✔

2✘✘✘12
3

Other Functions in theSame Class

3
𝑆𝑆{0,1,2,3}
3
𝑆𝑆{0,2}33
3𝑆𝑆{0}, 𝑆𝑆{0,1,2}, 𝑆𝑆{1,2,3}

3
𝑆𝑆{1,2}3
𝑆𝑆{0,1}

3
3
3
𝑆𝑆{2}
, 𝑆𝑆{0,1,3}, 𝑆𝑆{0,2,3}
23

Four Variables
 32 functions
 Ten classes (one is trivial)
 Eight currently have protocols (two ofthem are Las Vegas protocols) Two open problems

24Four Variables
Committed?

#Shuffles

Function

Name

𝑆𝑆∅3

Constant
XOR

Mizuki-Sone, 2009

✔

33
𝑆𝑆{4}

AND

Mizuki, 20165

3
𝑆𝑆{0,4}✘-R-Itoh, 2021✔

3

3𝑆𝑆{2}

-

3

3
𝑆𝑆{1}

✘-

3
𝑆𝑆{1,2}-3
𝑆𝑆{0,3}Div3

3
𝑆𝑆{1,3}3
𝑆𝑆{3,4}3
𝑆𝑆{0,2}Majority-Protocol
trivial

Shikata et al., 2023✘

✘R, 2023✘

Open problem≈7≈84

Other Functions in the SameClass

3
𝑆𝑆{0,1,2,3}
3
𝑆𝑆{0,2,4}

3
3
3
𝑆𝑆{0}
, 𝑆𝑆{0,1,2,3}, 𝑆𝑆{1,2,3,4}

3
𝑆𝑆{1,2,3}3
𝑆𝑆{0,1,3,4}

33
3
𝑆𝑆{3}
, 𝑆𝑆{0,1,2,4}, 𝑆𝑆{0,2,3,4}
33
3
𝑆𝑆{2,3}, 𝑆𝑆{0,1,4}, 𝑆𝑆{0,2,4}
33
3
𝑆𝑆{1,4}, 𝑆𝑆{0,2,3}, 𝑆𝑆{1,2,4}
3
3
3
𝑆𝑆{0,1}, 𝑆𝑆{0,1,2}, 𝑆𝑆{2,3,4}
33
3
𝑆𝑆{2,4}, 𝑆𝑆{0,1,3}, 𝑆𝑆{1,3,4}

25

More than Four Variables
 In 2022, Shikata et al. proved that there

exists a 2𝑛𝑛-card protocol to compute any
𝑛𝑛-variable symmetric function with 𝑛𝑛 ≥ 8.
 Limits the open problems to 𝑛𝑛 = 4,5,6,7.

26

More than Four Variables
 𝑛𝑛 = 5◦ 64 functions, 20 classes◦ 7 solved, 13 open

 𝑛𝑛 = 6◦ 128 functions, 36 classes◦ 10 solved, 26 open

 𝑛𝑛 = 7◦ 256 functions, 72 classes◦ 14 solved, 58 open
27

More than Four Variables
 The number of NPN-equivalence classes isthe number of n-bead black-white reversible
strings.
 Follows the sequence A005418 in OEIS.
 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, …

28

Questions and Comments

29