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…
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 .
The private simultaneous message (PSM) setting involves three players; Alice, Bob and the referee. Alice receives an input x\in \{0,1\}^n , and Bob receives a string y\in \{0,1\}^n . A choice of Boolean function 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 . Alice and Bob compute messages m_A=m_A(x,r) and 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 \epsilon -correct if, for all inputs (x,y) , the referee can output a bit z with Pr[z=f(x,y)]\geq 1-\epsilon . A protocol is said to be \delta -secure if the distribution of the messages, call it P_M , is \delta -close in total variational distance to a simulator distribution, which itself depends only on f(x,y) , D(P_M,Sim_M(f(x,y)))\leq \delta .
In this article the communication cost of implementing function f in the PSM model with \epsilon -correctness and \delta -security will be denoted PSM_{\epsilon, \delta}(f) . When \epsilon,\delta=0.1 we abbreviate this as PSM_{0.1,0.1}(f)=PSM(f) . When \epsilon,\delta=0 we abbreviate this as PSM_{0,0}(f)=pPSM(f) Another variation of the PSM model allows k players, each of whom sends a message to the referee. We will add a superscript k , i.e. to denote the communication cost with k players, we write PSM^k(f) .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376474320 under CC BY-SA 4.0; modifications have been made.