Private simultaneous message passing

Private simultaneous message passing (PSM) is a primitive, studied in information-theoretic cryptography, which allows multiple, non-communicating, parties to reveal the output of a function to a referee without revealing the inputs to the function.

PSM was introduced as a simple toy model for secure multi-party computation, and is related to the conditional disclosure of secrets setting, among other subjects.

Definition

The private simultaneous message (PSM) setting involves three players; Alice, Bob and the referee. Alice receives an input

x

∈

{

0

,

1

}

n

{\displaystyle x\in \{0,1\}^{n}}

, and Bob receives a string

y

∈

{

0

,

1

}

n

{\displaystyle y\in \{0,1\}^{n}}

. A choice of Boolean function

f

:

{

0

,

1

}

2

n

→

{

0

,

1

}

{\displaystyle f:\{0,1\}^{2n}\rightarrow \{0,1\}}

is fixed in advance and known to all players. Alice and Bob cannot communicate with one another, but share a string of random bits which we label

r

{\displaystyle r}

. Alice and Bob compute messages

m

A

=

m

A

(

x

,

r

)

{\displaystyle m_{A}=m_{A}(x,r)}

and

m

B

=

m

B

(

y

,

r

)

{\displaystyle m_{B}=m_{B}(y,r)}

, which they send to the referee. A PSM protocol consists of the encoding maps applied by Alice and Bob.

A protocol is said to be

ϵ

{\displaystyle \epsilon }

-correct if, for all inputs

(

x

,

y

)

{\displaystyle (x,y)}

, the referee can output a bit

z

{\displaystyle z}

with

P

r

[

z

=

f

(

x

,

y

)

]

≥

1

−

ϵ

{\displaystyle Pr[z=f(x,y)]\geq 1-\epsilon }

.

A protocol is said to be

δ

{\displaystyle \delta }

-secure if the distribution of the messages, call it

P

M

{\displaystyle P_{M}}

, is

δ

{\displaystyle \delta }

-close in total variational distance to a simulator distribution, which itself depends only on

f

(

x

,

y

)

{\displaystyle f(x,y)}

,

D

(

P

M

,

S

i

m

M

(

f

(

x

,

y

)

)

)

≤

δ

{\displaystyle D(P_{M},Sim_{M}(f(x,y)))\leq \delta }

.