Paillier 零知识证明
令 为对消息，使用随机值和公钥的Paillier加密:
假设有个有效的消息，真正加密的消息包含于其中。
下述零知识证明协议可以使第三方在不知道或的情况下判断是否是其中的一个的加密。
对，算出如下:
准备
证明者随机选取一系列的值：
除了时的 和。
随机选取
承诺
证明者对计算:
对计算：
证明者发送给验证者
挑战
这一步可以分为两种实现，交互式证明和非交互式证明：
交互式
验证者随机生成长度为的比特串发送给证明者
非交互式
用承诺值的哈希作为比特串
应答
证明者现在计算对的 和 ：
证明者发送下列系列值给验证者：
包括新计算的放到正确位置的 和
验证
验证者验证下式，不成立则验证失败：
验证者验证下式，不成立则验证失败：
如果上述两个检验通过则验证者接受
正确性
对所有的 使得 第二个验证都通过，因为这就是证明者预计算的方式
对 使得 t 由下列式子：
可将检验方程替换如下：
注意
本质是一个协议OR-proof的一个变体 仅适用于特定场景，比如网关过滤时，判断密文在可接受明文的列表中则放行，否则拒绝放行 不简洁，证明大小和验证时间皆非亚线性。 不通用，仅适用于可接受明文列表是多项式大小的限定情况，对于证明属于指数大的明文空间时不适用。没有用通用算术电路证明，没有用zk-SNARKs