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

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.
Comment: Independently and concurrently, Chakraborty, Chailloux, and Leverrier proved a similar bound on the Lunghi et al. scheme (https://arxiv.org/abs/1507.00239) with respect to a weaker notion of security. The latest revision also contains a tightness result similar to the one by Bricout and Chailloux (https://arxiv.org/abs/1608.03820), but with a different proof and a slightly better constant term