Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am facing the following situation and I am trying to break down the problem into some specific cryptographic primitives:

  • There is a function $F$ that takes as input a bit string and produces a fingerprint.

  • The used protocol has one user $u$ who holds the input of $D$ and there are $n$ other parties. I want those parties to compute $F(D)$ and all the parties to agree on that computed value. For example: if $t$ out of $n$ where $t$ > $n/2$ agree on value $Y_1$ then the winner is $Y_1$.

  • If there is no majority I want the protocol to run again.

  • I also want the results to be secret; in other words: I do not want the parties to learn the results and I don't want the parties to learn anything about the given input $D$. So, practically, they will compute $F(D)$ without learning $D$.

  • To verify/evaluate $F(E(D))$, they will receive an encrypted $E(D)$, which they only use to evaluate the function.

To be able to implement the above I would like to know if what I described can be considered to be a "secure multiparty computation", or is it rather some kind of "verifiable secret sharing" scheme? Are there any alike schemes/protocols available which I could use/combine to be able to do what I described?

share|improve this question
Wait... you say you "don't care about the confidentiality of inputs", but if I'm reading your description right, anyone who knows the function $F$ (which I'd normally assume to be public knowledge unless specified otherwise) and the input $D$ can obviously compute the output $F(D)$. So I must be missing something, but what? –  Ilmari Karonen May 23 '12 at 20:13
my fault. I correct it. We do care about inputs. There are secret. i update the question with sth else. I want operation on encrypted data.Sorry i am thinking while i am writing –  curious May 23 '12 at 20:19
"I do not want the parties to learn the results and i want the parties to learn anything about the given $\hspace{.2 in}$ input $D$." $\:$ How does either part of that sentence make sense? $\;\;$ –  Ricky Demer May 24 '12 at 0:11
@RickyDemer i changed the question appropriately –  curious Oct 1 '13 at 12:33
What do you mean by "Can we say that this is a secure multiparty computation?" What is "this"? Is "this" a solution to the problem or the problem itself? –  mikeazo Oct 1 '13 at 12:42
show 2 more comments

closed as unclear what you're asking by D.W., rath, e-sushi, B-Con, mikeazo Oct 8 '13 at 1:42

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

This question makes no sense to me. You probably will need to edit it. It makes no sense to ask for the users to "agree" on anything, since the other $n$ parties have absolutely no information about $D$ other than what is provided by $u$. So, your requirements don't make any sense to me.

If the output of the protocol depends only upon $D$, and if one user $u$ knows $D$, the obvious answer is to have $u$ compute the result of $F(D)$ and tell everyone the answer. If none of the parties have any knowledge about $D$ that would let them verify the correctness of the result, you're not going to be able to guarantee that you get the "correct" (desired) result.

If for some reason you must do an "agreement" protocol, you can follow that up with a standard Byzantine agreement (from the distributed systems literature; nothing to do with crypto): each of the $n$ users has $F(D)$ as an input, so they all use Byzantine agreement to take a majority vote of their value of $F(D)$. I'm not seeing much point to that latter Byzantine agreement stage, though. It seems extraneous. It's not going to defend you against a lie by user $u$. So, I suspect that in most applications, you might as well have everyone receive $F(D)$ directly from $u$ and just trust $u$.

More broadly: I suggest you read about secure multi-party computation. One standard formulation is that there are $n$ parties, $u_1,\dots,u_n$; each party $u_i$ holds a private input $x_i$, and we want to compute some function $F(x_1,\dots,x_n)$ so that everyone learns $F(x_1,\dots,x_n)$ but no one learns anything more about anyone else's private input (beyond what is implied by $F(x_1,\dots,x_n)$).

share|improve this answer
My "answer" addresses the last sentence of your first paragraph. $\;$ –  Ricky Demer Oct 2 '13 at 21:03
add comment

One could do much better by having $u$ give a computational ZK argument of knowledge of such a $D$. $\:$ One could get concurrent non-malleable ZK proofs against adaptive input selection or against adaptive corruption of parties. $\:$ One could instead get concurrent (statistical) ZK arguments of knowledge by using "Stage Init" and "Stage 1" from page 7 of this paper, and replacing "Stage 2" with an $\omega(1)$-round black-box statistically WI argument of knowledge (since as described in that paper, one would need to allow the knowledge extractor to take expected polynomial time.). $\;\;\;$

share|improve this answer
add comment

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