IACR News item: 29 October 2015
Benny Applebaum; Pavel Raykov
ePrint ReportIn this paper, we relate this new notion to the well-studied model of \\emph{Private Simultaneous Messages} (PSM) that was originally suggested by Feige, Naor and Kilian (STOC, 1994). Roughly speaking, we show that the randomness complexity of ZAM essentially corresponds to the communication complexity of PSM, and that the communication complexity of ZAM essentially corresponds to the randomness complexity of PSM. This relation works in both directions where different variants of PSM are being used. Consequently, we derive better upper-bounds on the communication-complexity of ZAM for arbitrary functions. As a secondary contribution, we reveal new connections between different variants of PSM protocols which we believe to be of independent interest.
Additional news items may be found on the IACR news page.