4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Why do you feel that homomorphic encryption is not practical enough? What specific timing/practicality requirements do you have? $\endgroup$
    – mikeazo
    Commented Oct 26, 2017 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
    Commented Oct 26, 2017 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
    Commented Oct 27, 2017 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
    Commented Oct 27, 2017 at 18:20

1 Answer 1

Reset to default
1
$\begingroup$

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.

*Beware that, to my knowledge, SPDZ's has actively secure online phase and passively secure preprocessing phase.

Improve this answer
$\endgroup$
3
  • $\begingroup$ SPDZ definitely has an actively secure preprocessing phase -- of course, it is significantly slower. $\endgroup$
    – Mikero
    Commented Oct 7, 2022 at 20:02
  • $\begingroup$ Okay, I didn't know about it. Can you give a reference to update my answer? $\endgroup$
    – tur11ng
    Commented Oct 8, 2022 at 18:16
  • 1
    $\begingroup$ Since the original SPDZ paper, there have been actively secure protocols for the offline phase. Many improvements to the offline phase since then, like eprint.iacr.org/2016/505, eprint.iacr.org/2017/1230, eprint.iacr.org/2019/035, to name a few. $\endgroup$
    – Mikero
    Commented Oct 8, 2022 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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