The Starknet Homomorphic Encryption (SHE) library provides low-level cryptographic primitives for proving and verification of Sigma protocols over the Stark elliptic curve. This includes Zero-Knowledge proof of ElGamal encryption.

SHE is the cryptographic foundation of Tongo but its building blocks can be used in other products that rellies on basic Sigma Protocols. SHE was audited by ZKSECURITY, you can find the report here. You can read more about SHE in the documentation.

All protocols implemented in SHE are Sigma protocols. A Sigma protocol is a protocol in which a prover P and a verifier V interact, after the interaction the verrifier can be convinced that the prover has knowledge of some witness x that satisfies a statement y, the general strutcute of the interaction between the prover and the verifier is

1. P computes a message A called commitment and sends it to V
2. Upon receiving P's commitment A, V chooses a challenge c at random and sends it to P
3. Upon receiving V's challenge c, P computes a response s and sends it to V
4. Upon receiving P's response c, V outputs either accept or reject based only on the statement y and the interaction (A, c, s).

The protocol descrived above is interactive because the prover and the verifier are forced to respond one to another. The standar way of converting an interactive protocol into a non-interactive one is by using the Fiat-Shamir heuristic. Broadly speaking this means to use as a challenge c some hash of the commitment A. This means the prover can compute c and there is not need to wait for the verifier to create a full proof.

We have developed the following ZK protocols:

• POE: Proof of Exponent (knowledge of discrete log)
• POE2: Proof of double exponent
• POEN: Proof of N exponents
• Bit: Proof that committed value is 0 or 1
• Range: Proof that value is in [0, 2^n)
• ElGamal Proof that a encryption is a correct ElGamal encryption
• SameEncryption: Proof that two ElGamal encryptions encrypt the same value

In the cairo implementation of the SHE protocols, for each protocol we expose a verify() function. This function mimics the last step for the verifier. It accepts or rejects the proof and take as imputs the statement y, the commitment A, the challenge c and the response s.

We have also exposed functions called verify_with_prefix(). These functions dont take the challenge c as an input, in its place the take a prefix. Internally the function computes the challenge c by hashing the comitment A with the given prefix

 c = Hash(prefix, A)

The prefix is useful to bind some external data to the proof (the proof at this stage can also be seen as a signature of the prefix). For example in Tongo part of the prefix is the chain_id so any proof intended to be validated in mainet will not be valid in sepolia.

Here there is a example of the implementation of this function for the POE protocol

pub fn verify_with_prefix(inputs: PoeInputs, proof: PoeProofWithPrefix) -> Result<(), Errors> {
    let PoeInputs { y, g } = inputs;
    let PoeProofWithPrefix { A, prefix, s } = proof;
    let commitments = array![A];
    let c = compute_challenge(prefix, commitments);
    verify(y, g, A, c, s)
}