Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Consider a cloud-based accounting system that needs access to aggregate information such as an account's balance but doesn't need access to individual transaction amounts in a ledger.

Does there exist a homomorphic encryption scheme that allows a public observer (such as a cloud computing provider) to compute the plaintext sum of a set of encrypted unsigned integers without being able to decode any individual transaction value (n=1 notwithstanding)?

As another example, regulations exist to ensure capital reserves. An institution could use such a scheme to furnish proof of compliance without disclosing individual transactions.

share|improve this question
    
With "plaintext sum" do you mean that the public server is able to "decode only the result of the sum of the encrypted integers (sum allowed by adopting the homomorphic encryption)" ? –  Marzio De Biasi Feb 3 '12 at 17:36
    
Yes that's right –  H D Feb 4 '12 at 0:12
    
It would be interesting to know if such a system exist for non-arbitrary intervals. For example the customer may allow the decryption of $n_4$ and $n_9$ only, so the accountant could calculate the difference $n_9 - n_4$ but not arbitrary differences. In this way the steps that led to the sum would still be concealed. –  gioele Feb 4 '12 at 19:36
1  
maybe this belongs to crypto.stackexchange.com –  Diego de Estrada Feb 4 '12 at 20:19
1  
@Diego, the question is in the scope as explained in the FAQ. –  Kaveh Feb 5 '12 at 5:23
add comment

2 Answers

up vote 6 down vote accepted

For all non-negative integers $n_0$,$n_1$,$n_2$ and random strings $r_0,r_1,r_2$

$n_0 \:\: = \:\: (n_0+n_1+n_2)-(n_1+n_2)$
$=$
$\operatorname{plaintextsum}(\operatorname{encrypt}(n_0,r_0),\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$
$- \: \operatorname{plaintextsum}(\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$

.


Therefore any such scheme would be completely insecure
if more than 2 non-negative integers are encrypted with it.

share|improve this answer
    
Thanks! That certainly answers it! –  H D Feb 4 '12 at 0:12
add comment

The idea could work. The cyphertext would need to come with a non-interactive zero-knowledge proof that the plaintext lies in a certain interval ([0,100] for example) See link below for more details.

It is important to note that the answer at the end needs to be decrypted so it requires use of a decryption oracle at least once. Threshold encryption might be useful here.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.4029&rep=rep1&type=pdf

share|improve this answer
    
Interesting, thanks! I will read up on that citation. –  H D Feb 4 '12 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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