2015/07/01 by Serge Fehr, Fehr, Serge, Max Fillinger +1 · 1 citation
Computer Science · #Cryptography and Data Security #FOS: Physical sciences #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1507.00240
openalex publication_date 2015/07/01 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We consider the related notions of two-prover and of relativistic commitment\nschemes. In recent work, Lunghi et al. proposed a new relativistic commitment\nscheme with a multi-round sustain phase that enables to keep the binding\nproperty alive as long as the sustain phase is running. They prove security of\ntheir scheme against classical attacks; however, the proven bound on the error\nparameter is very weak: it blows up doubly exponentially in the number of\nrounds. In this work, we give a new analysis of the multi-round scheme of\nLunghi et al., and we show a linear growth of the error parameter instead (also\nconsidering classical attacks only). Our analysis is based on a new and rather\ngeneral composition theorem for two-prover commitment schemes. The proof of our\ncomposition theorem is based on a better understanding of the binding property\nof two-prover commitments that we provide in the form of new definitions and\nrelations among them. These new insights are certainly of independent interest\nand are likely to be useful in other contexts as well. Finally, our work gives\nrise to several interesting open problems, for instance extending our results\nto the quantum setting, where the dishonest provers are allowed to perform\nmeasurements on an entangled quantum state in order to try to break the binding\nproperty.\n