Let $L = [b_1, \dots, b_k]$ be a list of blocks of a file.

I want to compute the function $f = h(g(b_1), \dots, g(b_k))$ on $N$ untrusted nodes such that:

  • Anyone can be reasonable convinced (with high probability) of the correctness of the result.

  • The algorithm is practical (no homomorphic encryption nonsense or similar).

  • No node has seen the entire list L or can gather it by knowing where the rest of the blocks are.

  • I'm willing to replicate computation up to a multiplicative constant (not too big).

Is there any protocol you know of that can solve this problem?

  • $\begingroup$ Why do you feel that homomorphic encryption is not practical enough? What specific timing/practicality requirements do you have? $\endgroup$ – mikeazo Oct 26 '17 at 12:32
  • $\begingroup$ "No node has seen the entire list L or can gather it by knowing where the rest of the blocks are." What do you mean by this? You are okay with one node learning all blocks except one? Are these untrusted nodes fully-malicious or are they semi-honest (honest-but-curious)? Is there a limit on what fraction of the N nodes might be corrupted or do you assume they are all corrupted? Are the corrupted nodes fixed at the beginning of the protocol or can more become corrupted throughout the execution of the protocol? $\endgroup$ – mikeazo Oct 26 '17 at 12:35
  • $\begingroup$ My actual function is to compute an acoustic fingerprint of a music file. Thus homomorphic encryption is unacceptable since it would be hugely inefficient. I want the time to be reasonable ~ 10 mins maybe tops. $\endgroup$ – user47376 Oct 27 '17 at 18:17
  • $\begingroup$ I don't have specific assumptions about the nodes, I will accept any protocol with reasonable assumptions. I think most of the nodes should be honest but I don't have a hard bound or anything. $\endgroup$ – user47376 Oct 27 '17 at 18:20

Your Answer

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

Browse other questions tagged or ask your own question.