Stronger impossibility results for quantum string commitment
Rahul Jain · arXiv (Cornell University) · 2005
String commitment schemes are similar to the well studied bit commitment schemes in cryptography with the difference that the committing party, say Alice is supposed to commit a long string instead of a single bit, to another party say Bob. Similar to bit commitment schemes, such schemes are supposed to be binding, i.e Alice cannot change her choice after committing and concealing i.e. Bob cannot find Alice’s committed string before Alice reveals it. Strong impossibility results are known for bit commitment schemes both in the classical and quantum settings, for example due to Mayer [13] and Lo and Chau [11, 12]. In fact for approximate quantum bit commitment schemes, trade-offs between the degrees of cheating of Alice and Bob, referred to as binding-concealing trade-offs are known as well for example due to Spekkens and Terry [15]. Recently, Buhrman, Christandl, Hayden, Lo and Wehner [1] have shown similar bindingconcealing trade-offs for quantum string commitment schemes (QSC), both in the scenario of single execution of the protocol and in the asymptotic regime of sufficiently large number of parallel executions of the protocol. We show stronger trade-off in the scenario of single execution of a QSC protocol which also immediately imply the trade-off shown by Buhrman et al. in the asymptotic regime of multiple parallel executions of a QSC protocol. We show our results by making a central use of an important information theoretic tool called the substate theorem due to Jain, Radhakrishnan and Sen [6]. Our techniques are quite different from that of [1] and may be of independent interest.