#accumulator #arkworks #pairing-based-cryptography #schnorr-protocol #zero-knowledge-proofs #signatures #brute-force

saver

SAVER SNARK-friendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization

4 releases (breaking)

Uses new Rust 2021

new 0.5.0 Sep 30, 2022
0.4.0 Sep 22, 2022
0.3.0 May 27, 2022
0.2.0 May 2, 2022

#685 in Cryptography

Download history 8/week @ 2022-06-12 7/week @ 2022-06-19 8/week @ 2022-06-26 8/week @ 2022-07-03 27/week @ 2022-07-10 14/week @ 2022-07-17 23/week @ 2022-07-24 38/week @ 2022-07-31 23/week @ 2022-08-07 48/week @ 2022-08-14 26/week @ 2022-08-21 14/week @ 2022-08-28 19/week @ 2022-09-04 13/week @ 2022-09-11 58/week @ 2022-09-18 51/week @ 2022-09-25

142 downloads per month
Used in proof_system

Apache-2.0

170KB
4K SLoC

saver

Verifiable encryption using SAVER

Implementation based on SAVER. Implemented

The basic idea of the verifiable encryption construction is to split the message to be encrypted (a field element) into small chunks of say b bits and encrypt each chunk in an exponent variant of Elgamal encryption. For decryption, discrete log problem in the extension field (F_{q^k}) is solved with brute force where the discrete log is of at most b bits so 2^b - 1 iterations. The SNARK (Groth16) is used for prove that each chunk is of at most b bits, thus a range proof.

The encryption outputs a commitment in addition to the ciphertext. For an encryption of message m, the commitment psi is of the following form:

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

m_i are the bit decomposition of the original message m such that m_1*{b^{n-1}} + m_2*{b^{n-2}} + .. + m_n (big-endian) with b being the radix in which m is decomposed and r is the randomness of the commitment. eg if m = 325 and m is decomposed in 4-bit chunks, b is 16 (2^4) and decomposition is [1, 4, 5] as 325 = 1 * 16^2 + 4 * 16^1 + 5 * 16^0.

Getting a commitment to the full message from commitment to the decomposition.

To use the ciphertext commitment for equality of a committed message using a Schnorr protocol, the commitment must be transformed to a commitment to the full (non-decomposed) message. This is implemented with ChunkedCommitment and its docs describe the process.

Use with BBS+ signature

See the tests.rs file

License: Apache-2.0

Dependencies

~6.5MB
~132K SLoC