Zero-Knowledge MIPs using Homomorphic Commitment Schemes

A Zero-Knowledge Protocol (ZKP) allows one party to convince another party of a fact without disclosing any extra knowledge except the validity of the fact. For example, it could be used to allow a customer to prove their identity to a potentially malicious bank machine without giving away private information such as a personal identification number. This way, any knowledge gained by a malicious bank machine during an interaction cannot be used later to compromise the client's banking account. An important tool in many ZKPs is bit commitment, which is essentially a digital way for a sender to put a message in a lock-box, lock it, and send it to the receiver. Later, the key is sent for the receiver to open the lock box and read the message. This way, the message is hidden from the receiver until they receive the key, and the sender is unable to change their mind after sending the lock box. In this paper, the homomorphic properties of a particular multi-party commitment scheme are exploited to allow the receiver to perform operations on commitments, resulting in polynomial time ZKPs for two NP-Complete problems: the Subset Sum Problem and 3SAT. These ZKPs are secure with no computational restrictions on the provers, even with shared quantum entanglement. In terms of efficiency, the Subset Sum ZKP is competitive with other practical quantum-secure ZKPs in the literature, with less rounds required, and fewer computations.