As we know, in order to have multi-party protocol secure against the malicious parties, researchers usually utilise the standard techniques such as zero-knowledge proofs or cut-and-choose technique.

Question: Which one of the two is computationally more expensive?

  • $\begingroup$ Zero knowledge and cut-and-choose rather describe the properties of an algorithm than the algorithm itself. The order of the number of primitive operations required is a property of the algorithm and therefore depends on the algorithm chosen. How computational expensive it is depends on the algorithm implementation. Still, I presume that one could be generally more expensive than the other so I upvoted the question, but please keep above in mind - you're making not one but two jumps: choosing the algorithm and choosing the implementation. $\endgroup$ – Maarten Bodewes Feb 9 '17 at 11:41
  • $\begingroup$ (If you'd have asked which one is faster than you also depend on the runtime, so hey, it's just two jumps instead of three at least :) ) $\endgroup$ – Maarten Bodewes Feb 9 '17 at 11:43
  • $\begingroup$ @MaartenBodewes thank you! Mainly I meant complexity wise. Please feel free to edit the question if needed. $\endgroup$ – user153465 Feb 9 '17 at 11:43
  • $\begingroup$ Although I edit questions a lot I try to leave significant changes to the question to the person that asked the question in the first place. This change is too significant to edit in in my opinion. $\endgroup$ – Maarten Bodewes Feb 9 '17 at 12:22

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.