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).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.