5
$\begingroup$

Is there a system that would allow to encrypt values with one or more keys, sum the encrypted values, and reveal a key which could only decrypt the sum.

Essentially would be able to show encrypted values where anyone could verify the sum by adding all of the encrypted values, then decrypting it.

Improve this question
$\endgroup$
  • $\begingroup$ Is it a requirement that the key you reveal only decrypts the sum, and NOT the encrypted terms of the sum? Otherwise this sounds like standard additively homomorphic encryption. $\endgroup$ – Guut Boy Oct 3 '16 at 7:27
  • $\begingroup$ @GuutBoy, I would agree, except Jeff says "one or more keys". That sounds like he wants multiple public keys. That is definitely not "standard" additive HE. $\endgroup$ – mikeazo Oct 3 '16 at 12:05
  • 1
    $\begingroup$ I think there is many ways to achieve something along the lines of what the question asks. Homomorphic threshold encryption could be one way. Simple secret sharing (like Shamir) is an other. The question needs to be a bit more specific to be able to say what is the right solution. $\endgroup$ – Guut Boy Oct 3 '16 at 12:38
  • $\begingroup$ Yes, it is a requirement that the original terms not be disclosed to anyone but themselves, so multiple public keys. Say you have a fundraiser where you know the members but would like to keep everyone's donations anonymous. By doing the addition with encrypted data, it gives re-assurance that the data was not manipulated. Under standard HE, I would have to release the private key to let others verify the sum, but then they can also decrypt individual donations. With the original terms known, you can probably guess which members donated what with the largest numbers. $\endgroup$ – Jeff Oct 3 '16 at 15:18
  • $\begingroup$ What exactly do you mean by "verify" the sum? Sounds like you could have each party secret share their term, using additively homomorphic secret sharing (such as Shamir), add up the shares and reconstruct the sum. $\endgroup$ – Guut Boy Oct 3 '16 at 20:33
3
$\begingroup$

There is a recent line of work that does exactly this; it is called functional encryption for inner-product. It allows to encrypt a vector of integers (from some exponent space $\mathbb{Z}_p$) so that one can generate secret keys that do only allow to decrypt a given inner product between the components of any such encrypted vector.

There is a simple construction under DDH, and under LWE. The construction from the Paillier cryptosysem is way more involved and was presented at the CRYPTO conference in august this year.

For the DDH-based variant, the intuition is simple: encrypt your vector with different keys, but the same random coin each time (id est: $E((m_1, \cdots, m_n);r) = (g^r, h^r_1g^{m_1}, \cdots, h^r_ng^{m_n})$, where $g$ is a generator of some group where DDH is hard, and each $h_i$ is $g^{s_i}$ for some secret key $s_i$). The secret key to decrypt an inner product with $a_1, \cdots, a_n$ is just $\sum_i s_i a_i$.

Here is the original article: http://eprint.iacr.org/2015/017. If you want to look into the more advanced constructions, I suggest looking the papers that cite this one.

EDIT: I forgot to mention, the DDH-based instantiation has the same drawback that the additive variant of ElGamal it relies on, which is that a discrete logarithm must be performed on $g^{\sum_i a_i m_i}$ at the end, so it works only when $\sum_i a_im_i$ remains small (say, less than $2^{30}$). If the messages can be large, then the LWE-based or the Paillier-based instantiations must be used.

Improve this answer
$\endgroup$
  • $\begingroup$ Correct me if I'm wrong, but the $a_1, \cdots, a_n$ terms are the weighted terms, which would be all 1 for a sum. Therefore the secret key is simply $\sum_i s_i$? $\endgroup$ – Jeff Oct 3 '16 at 16:50
  • $\begingroup$ In your case, exactly :) The result I gave is a bit more general than what you are asking for. Note that the sum is over $\mathbb{Z}_p$, where $p$ is the order of the DDH group. This is the reason why it is way harder to do the same thing with Paillier, as the group of exponents is of unknown order in the case of Paillier. $\endgroup$ – Geoffroy Couteau Oct 3 '16 at 16:53
  • $\begingroup$ Interesting, but does this allow multiple parties to each encrypt a term and then reveal the sum (by revealing the key associated with the $(1, \ldots, 1)$ vector)? $\endgroup$ – Guut Boy Oct 4 '16 at 6:30
  • $\begingroup$ In this case, not satisfyingly, as the parties would have to somehow use "the same randomness". $\endgroup$ – Geoffroy Couteau Oct 4 '16 at 7:48
  • $\begingroup$ Woops, too late to edit. Not here, you need a "vector encryption scheme" which encrypts all the components at once. What you are looking for is called "multi-key functional encryption", and it is clearly harder. There are generic theoretical constructions (totally inefficient, but they are proof of concept for arbitrary functions) (eprint.iacr.org/2016/524.pdf). In the case of sum and inner product, there is very good hopes that this can be done efficiently - but this is the subject of ongoing research, so I guess you'll have to wait a bit if this is what you are looking for :) $\endgroup$ – Geoffroy Couteau Oct 4 '16 at 7:54
-1
$\begingroup$

Interesting simplistic construction is shown. There are far more advanced methodologies. The question references summing encrypted values etc. "Summing" encrypted values in of itself, in my view (ideas I have) is not the only "manipulation" of encrypted values that may be done to reveal key(s) to decrypt the "non-sum manipulation". Noting also references to vectors which can be expressed in n-space.

Improve this answer
$\endgroup$

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.