# Multi-party computation with untrusted nodes?

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?

• Why do you feel that homomorphic encryption is not practical enough? What specific timing/practicality requirements do you have? Oct 26, 2017 at 12:32
• "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? Oct 26, 2017 at 12:35
• 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. Oct 27, 2017 at 18:17
• 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. Oct 27, 2017 at 18:20

I will try to answer this question ,although the OP asks for $$n$$ untrusted participants, I have to note something here. You cannot have SMPC with $$n$$ untrusted nodes, assuming $$n$$ is the total number of the participants. In SMPC you are supposed to be part of the computation, otherwise you are outsourcing the computation which is part of another field, more specifically Secure Outsourced Computation, where HE, FHE belong.
Now, if you want to use SMPC you have to go with maximum $$n-1$$ untrusted nodes, passive or active, controlled by an adversary. For this purpose you can use various protocols, such as SPDZ* 1.