# Algorithm design to verify an assertion on encrypted values

I'm trying to design some kind of protocol but I'm stuck, need some help please..

Given $(a,b,c)\in \mathbb{N}^+$ with $a + b = c$

I need to send an asymmetric encrypted version of a,b and c though a third-party that must verify that $a + b = c$ but this third-party can't have access to those numbers, only their encrypted values.

I would appreciate a lot some suggestions.

There are two natural solutions to your problem.

The first one would be to rely on an additively homomorphic encryption scheme. In such a scheme, given encryptions of two numbers $a$ and $b$, anyone can, given only the public key, homomorphically compute an encryption of their sum, $a+b$ (usually modulo some value $M$, which can be set large enough so that no overflow occurs, given bounds on the values $a,b$).

If the values $(a,b)$ are small enough, this can be instantiated using the ElGamal encryption scheme, with messages in the exponent (decryption then requires computing a discrete log). If the inputs might be large, a good alternative is to use the Paillier encryption scheme, which does not have this small input requirement.

With such a cryptosystem, the protocol you want is straightforward: simply send only encryptions of $a$ and $b$ to the third party, and let him compute the encryption of $a+b=c$ by himself - that way, he is automatically convinced that the third ciphertext indeed encrypts $a+b$.

If you cannot really choose which encryption scheme you want to use, or want to rely on a different encryption scheme for other reasons, an alternative to the above is to use zero-knowledge proofs. After sending the three ciphertexts to the third party, you can perform with this party a zero-knowledge proof that the third ciphertext encrypts the sum of the first two ciphertexts - this will not leak any information about the content of the ciphertexts, appart from the fact that the statement is true. Zero-knowledge proofs for such linear statements are known for most standard public-key encryption scheme (they can in theory be designed for arbitrary encryption schemes, even e.g. AES, but would be a quite inefficient for encryption schemes without algebraic structures), using e.g. standard Sigma-protocols (which you can make non-interactive in the random oracle model if you don't want to require interactions with the third party).