## no-std saver

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

### 14 breaking releases

 new 0.17.0 Jun 21, 2024 Mar 4, 2024 Oct 2, 2023 Jun 23, 2023 May 27, 2022

#884 in Cryptography

Used in 2 crates (via proof_system)

Apache-2.0

655KB
15K 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