Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1507.00240

On the Composition of Two-Prover Commitments, and Applications to Multi-Round Relativistic Commitments

Serge Fehr, Max Fillinger

Published Jul 1, 2015• 2 citations
arXivHTMLPDF

Abstract

We consider the related notions of two-prover and of relativistic commitment schemes. In recent work, Lunghi et al. proposed a new relativistic commitment scheme with a multi-round sustain phase that enables to keep the binding property alive as long as the sustain phase is running. They prove security of their scheme against classical attacks; however, the proven bound on the error parameter is very weak: it blows up doubly exponentially in the number of rounds. In this work, we give a new analysis of the multi-round scheme of Lunghi et al., and we show a linear growth of the error parameter instead (also considering classical attacks only). Our analysis is based on a new and rather general composition theorem for two-prover commitment schemes. The proof of our composition theorem is based on a better understanding of the binding property of two-prover commitments that we provide in the form of new definitions and relations among them. These new insights are certainly of independent interest and are likely to be useful in other contexts as well. Finally, our work gives rise to several interesting open problems, for instance extending our results to the quantum setting, where the dishonest provers are allowed to perform measurements on an entangled quantum state in order to try to break the binding property.

DOI
10.48550/arxiv.1507.00240

Related papers

Two-Prover Bit-Commitments : Classical, Quantum and Non-Signaling

Max Fillinger

This thesis considers multi-prover commitment schemes whose security is based on restrictions on the communication between the provers. The results are applicable to so-called relativistic commitment schemes: schemes whose security is guaranteed by the fact that information does not travel faster than the speed of light. A commitment scheme is a cryptographic protocol solving the following problem: One party, the prover, has selected a value which he wants to keep secret at first. The prover wants to have the option to reveal it to the other party, the verifier, at a later time, but the verifier wants a guarantee that no value other than the originally selected one can be revealed. Standard commitment schemes can only be proven secure with computational hardness assumptions. This can be circumvented by splitting the prover into multiple entities and restricting their communication, e.g., no communication at all, or communication only with a delay (as in relativistic commitment schemes). This dissertation introduces new methods for analyzing and designing such multi-prover schemes. As an application, we show that the Lunghi et al. commitment scheme from 2015 has much stronger security that their original analysis indicated.

•Mar 19, 2019•0 citations

Multi-Prover Commitments Against Non-Signaling Attacks

Serge Fehr, Max Fillinger

We reconsider the concept of 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 provers cannot communicate, but also depends on their information processing capabilities. 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; 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 three provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.

arXiv:1505.03040•May 12, 2015•1 citation

On the Relativistic Zero Knowledge Quantum Proofs of Knowledge

Kaiyan Shi, Kaushik Chakraborty, Wen Yu Kon +3 more

We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).

arXiv:2409.03635•Sep 5, 2024•0 citations

Arbitrarily Long Relativistic Bit Commitment

Kaushik Chakraborty, André Chailloux, Anthony Leverrier

We consider the recent relativistic bit commitment protocol introduced by Lunghi et al. [Phys. Rev. Lett. 115, 030502 (2015)] and present a new security analysis against classical attacks. In particular, while the initial complexity of the protocol scales double exponentially with the commitment time, our analysis shows that the correct dependence is only linear. This has dramatic implications in terms of implementation: in particular, the commitment time can easily be made arbitrarily long, by only requiring both parties to communicate classically and perform efficient classical computation.

arXiv:1507.00239•Physical Review Letters•Dec 17, 2015•25 citations

Recursive cheating strategies for the relativistic $\mathbb F_Q$ bit commitment protocol

Rémi Bricout, André Chailloux

In this paper, we study relativistic bit commitment, which uses timing and location constraints to achieve information theoretic security. We consider the FQ multi-round bit commitment scheme introduced by Lunghi et al. [LKB + 15]. This protocol was shown secure against classical adversaries as long as the number of rounds m is small compared to √ Q where Q is the size of the used field in the protocol [CCL15, FF16]. In this work, we study classical attacks on this scheme. We use classical strategies for the CHSHQ game described in [BS15] to derive cheating strategies for this protocol. In particular, our cheating strategy shows that if Q is an even power of any prime, then the protocol is not secure when the number of rounds m is of the order of √ Q. For those values of Q, this means that the upper bound of [CCL15, FF16] is essentially optimal.

•Aug 1, 2017•2 citations

On the Composition of Two-Prover Commitments, and Applications to Multi-round Relativistic Commitments

Serge Fehr, Max Fillinger

Lecture notes in computer science•Jan 1, 2016•5 citations
We consider the related notions of two-prover and of relativistic commitment schemes. In recent work, Lunghi et al. proposed a new relativistic commitment scheme with a multi-round sustain phase that enables to keep the binding property alive as long as the sustain phase is running. They prove security of their scheme against classical attacks; however, the proven bound on the error parameter is very weak: it blows up doubly exponentially in the number of rounds. In this work, we give a new analysis of the multi-round scheme of Lunghi et al., and we show a linear growth of the error parameter instead (also considering classical attacks only). Our analysis is based on a new and rather general composition theorem for two-prover commitment schemes. The proof of our composition theorem is based on a better understanding of the binding property of two-prover commitments that we provide in the form of new definitions and relations among them. These new insights are certainly of independent interest and are likely to be useful in other contexts as well. Finally, our work gives rise to several interesting open problems, for instance extending our results to the quantum setting, where the dishonest provers are allowed to perform measurements on an entangled quantum state in order to try to break the binding property.
This thesis considers multi-prover commitment schemes whose security is based on restrictions on the communication between the provers. The results are applicable to so-called relativistic commitment schemes: schemes whose security is guaranteed by the fact that information does not travel faster than the speed of light. A commitment scheme is a cryptographic protocol solving the following problem: One party, the prover, has selected a value which he wants to keep secret at first. The prover wants to have the option to reveal it to the other party, the verifier, at a later time, but the verifier wants a guarantee that no value other than the originally selected one can be revealed. Standard commitment schemes can only be proven secure with computational hardness assumptions. This can be circumvented by splitting the prover into multiple entities and restricting their communication, e.g., no communication at all, or communication only with a delay (as in relativistic commitment schemes). This dissertation introduces new methods for analyzing and designing such multi-prover schemes. As an application, we show that the Lunghi et al. commitment scheme from 2015 has much stronger security that their original analysis indicated.
We reconsider the concept of 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 provers cannot communicate, but also depends on their information processing capabilities. 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; 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 three provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.
We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).
We consider the recent relativistic bit commitment protocol introduced by Lunghi et al. [Phys. Rev. Lett. 115, 030502 (2015)] and present a new security analysis against classical attacks. In particular, while the initial complexity of the protocol scales double exponentially with the commitment time, our analysis shows that the correct dependence is only linear. This has dramatic implications in terms of implementation: in particular, the commitment time can easily be made arbitrarily long, by only requiring both parties to communicate classically and perform efficient classical computation.
Recursive cheating strategies for the relativistic FQ\mathbb F_QFQ​ bit commitment protocol
In this paper, we study relativistic bit commitment, which uses timing and location constraints to achieve information theoretic security. We consider the FQ multi-round bit commitment scheme introduced by Lunghi et al. [LKB + 15]. This protocol was shown secure against classical adversaries as long as the number of rounds m is small compared to √ Q where Q is the size of the used field in the protocol [CCL15, FF16]. In this work, we study classical attacks on this scheme. We use classical strategies for the CHSHQ game described in [BS15] to derive cheating strategies for this protocol. In particular, our cheating strategy shows that if Q is an even power of any prime, then the protocol is not secure when the number of rounds m is of the order of √ Q. For those values of Q, this means that the upper bound of [CCL15, FF16] is essentially optimal.