Abstract: On a zero-knowledge protocol, Alice proves the truth of some statement (e.g. graph is 3-colorable, graph isomorphism, etc.) to Bob in such a way that he does not learn anything else than the truth of the statement. As paradoxical as it may sound, there are several proposals for zero-knowledge protocols in the classical setting and they have far-reaching applications in cryptography. Recently, there has been some effort on proposing new zero-knowledge protocols for quantum statements, but a long-standing open question is the existence of simple “commit-and-open” protocols for such a task. In this talk, I will present how to construct such simple zero-knowledge protocols using a technique called Locally Simulatable proofs, which might be of independent interest in quantum cryptography. As a side remark, notice that this technique also allows us to show that the Consistency of Local Density Matrices problem, proposed by Liu (2006), is QMA-hard. This is a joint work with Anne Broadbent. No previous knowledge of complexity theory (specially zero-knowledge) is assumed.
