IACR News item: 26 May 2015
Serge Fehr, Max Fillinger
ePrint ReportThis poses the natural question whether there exists a two-prover commitment scheme that is secure under the sole assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known.
In this work, we give strong evidence for a negative answer: we show that any single-round two-prover commitment scheme can be broken by a non-signaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) $1$ in case of a perfectly sound scheme. In the case of multi-round schemes, our impossibility result is restricted to perfectly hiding schemes.
On the positive side, we show that the impossibility result can be circumvented by considering {\\em three} provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.
Additional news items may be found on the IACR news page.