A inperfect partial proof and verification

ZKP,零知识证明

实际上对于这个问题,我们已经可以证明它是NP复杂的。但是因为最近需要使用一些伪ZKP,所以就拿出来再提一提。

目前市面上的大多数伪ZKP都是基于一种随机校验,区别于非对称加密的数字签名,ZKP的难点在于证明人不能暴露任何信息,而验证人在这个情况下,进行一次校验的材料也不存在。 举一个常见的ZKP例子,数独有9张卡片,答案为一个secret,证明人可以填写全部的9张卡片,在随机取得一列3张后即可验证该证明人知道数独的答案。

然而这并非完美的方案,对手可以采用一种侥幸的模式对3张卡片进行作弊,从而使得在某个小概率下,验证人得到了正确的证明,却无法辨别答案的完整性。 这一类伪ZKP都是基于“随机低概率”的认知,也就是说3张卡片全部碰巧被选上的概率很小,排除边界情况,约等于1/(987),但是在大量的数据面前,0.2%的碰撞概率仍然是致命的,所以目前伪ZKP的复杂度依然为线性,即与秘钥长度和校验次数正相关。