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 , z , r ) {\displaystyle m_{A}=m_{A}(x,z,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 } . In this article the communication cost of implementing function f {\displaystyle f} in the PSM model with ϵ {\displaystyle \epsilon } -correctness and δ {\displaystyle \delta } -security will be denoted P S M ϵ , δ ( f ) {\displaystyle PSM_{\epsilon ,\delta }(f)} . When ϵ , δ = 0.1 {\displaystyle \epsilon ,\delta =0.1} we abbreviate this as P S M 0.1 , 0.1 ( f ) = P S M ( f ) {\displaystyle PSM_{0.1,0.1}(f)=PSM(f)} . When ϵ , δ = 0 {\displaystyle \epsilon ,\delta =0} we abbreviate this as P S M 0 , 0 ( f ) = p P S M ( f ) {\displaystyle PSM_{0,0}(f)=pPSM(f)}
Another variation of the PSM model allows k {\displaystyle k} players, each of whom sends a message to the referee. We will add a superscript k {\displaystyle k} , i.e. to denote the communication cost with k {\displaystyle k} players, we write P S M k ( f ) {\displaystyle PSM^{k}(f)} .
Upper and lower bounds on communication cost There is a large gap between the best upper and lower bounds on the PSM model. For every function, it is known that the communication cost of PSM is at most 2 n / 2 {\displaystyle 2^{n/2}} . The following upper bounds are known for structured functions:
… excerpt ends here. Continue reading the full article.
