Paper 2015/501

Multi-Prover Commitments Against Non-Signaling Attacks

Serge Fehr and Max Fillinger

Abstract

We reconsider the concept of two-prover (and more generally: multi-prover) commitments, as introduced in the late eighties in the seminal work by Ben-Or et al. As was recently shown by Crëpeau et al., the security of known two-prover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have quantum information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general so-called non-signaling provers, which are restricted solely by the requirement that no communication takes place. This 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2015
Keywords
bit commitmentnon-signalingmulti-prover
Contact author(s)
Max Fillinger @ cwi nl
History
2015-06-04: revised
2015-05-26: received
See all versions
Short URL
https://ia.cr/2015/501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/501,
      author = {Serge Fehr and Max Fillinger},
      title = {Multi-Prover Commitments Against Non-Signaling Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/501},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/501}},
      url = {https://eprint.iacr.org/2015/501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.