  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.
