saver

使用SAVER进行可验证加密

基于SAVER实现。实现了

• 使用Groth16
• 以及LegoGroth16。

可验证加密构造的基本思想是将要加密的消息（一个域元素）分成几个小段，例如b位，并用Elgamal加密的指数变体加密每个段。解密时，在扩展域（F_{q^k}）中的离散对数问题通过穷举法解决，其中离散对数的位数最多为b位，因此需要进行最多2^b - 1次迭代。使用SNARK（Groth16）来证明每个段最多为b位，因此是一个范围证明。

加密除了密文外还输出一个承诺。对于消息m的加密，承诺psi的形式如下

psi = m_1*Y_1 + m_2*Y_2 + ... + m_n*Y_n + r*P_2

m_i 是原始消息 m 的位分解，满足以下条件：m_1*{b^{n-1}} + m_2*{b^{n-2}} + ... + m_n（大端序）其中 b 是 m 分解的基数，r 是承诺的随机性。例如，如果 m = 325 并且 m 在 4 位块中分解，b 为 16（2^4），分解为 [1, 4, 5]，如下所示：325 = 1 * 16^2 + 4 * 16^1 + 5 * 16^0。