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.
翻译:零知识协议(ZKP)允许一方向另一方证明一个事实的有效性,而不披露任何额外的知识。例如,它可以用于使客户向潜在恶意的银行机器证明其身份,而不泄露私人信息,如个人识别号码。这样,任何恶意银行机器在交互过程中获取的知识都无法在以后用于破坏客户的银行账户。在许多ZKP中,一个重要的工具是比特承诺,它本质上是发件人以数字方式将消息放在一个锁盒中,将其锁定,然后将其发送到接收方。稍后,发送密钥以便接收方打开锁盒并读取消息。这样,消息对接收方隐藏,直到他们收到密钥,并且发送方无法在发送锁盒后改变主意。在本文中,利用特定的多方承诺方案的同态性质来允许接收方对承诺执行操作,从而得到了多项式时间的ZKP,用于两个NP-完全问题:子集和问题和3SAT问题。即使拥有共享的量子纠缠,这些ZKP也是安全的,而且证明者上没有计算限制。在效率方面,子集和ZKP与文献中其他实用的量子安全ZKP竞争,所需的回合更少,计算量更少。