1
$\begingroup$

I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in cryptography. There are some papers comparing the efficiency of HE based/ GC based/ OT based protocols, for example https://eprint.iacr.org/2016/544.pdf by Geoffroy Couteau(still a bit hard for me to understand the paper at the moment). My biggest question now is: why exsiting papers seldom compare with methods based on just secret sharing? I think secret sharing is quite a simple approach, is there anything quite oblivious but I just miss that makes secret sharing based secure comparison Not competitive to those HE/GC/OT based methods? I know that my question may seem quite general, but I am kind of lost here and any pointers would help.

$\endgroup$
3
  • $\begingroup$ Hi! If you have a question about my paper, feel free to drop me a mail. An important point to consider: my paper (and others) have the advantage of not revealing the output of the comparison in the clear, but instead provide secret shares of the result of the computation, which is very useful if you want to use the protocol as a building block in a larger protocol. Is this a property you want to have? Also, are you in the 2 party setting? Do you want a semi honest protocol? Do you consider single execution, or many executions? All these considerations can influence what the best solution is. $\endgroup$ Jun 17 at 20:33
  • $\begingroup$ Also: secret sharing is an information theoretic notion, and secure 2 party computation with information theoretic security is impossible. You fundamentally have to use some computational assumption, such as OT. Does that help? $\endgroup$ Jun 17 at 20:35
  • $\begingroup$ @GeoffroyCouteau Wow! Really glad to get a reply from you directly. I can't follow from here: SS is information theoretic secure. Can I take this as : SS has stronger security guarantee? If I did't get it wrong here, SS is also very fast for secure comparison (quite a lot recent works on privacy-preserving machine learning use this kind of SS based building blocks instead of HE/GC, and the speed is very good I think), then SS based comparison protocols should have been competitive to those HE/GC/OT based methods right (good performance, better security)? Or did I get something wrong somewhere? $\endgroup$
    – rzxh
    Jun 18 at 2:12
3
$\begingroup$

I think there is a confusion with the terminology "secure computation from secret sharing". Let me try to clarify.

There are two major settings for secure computation: the honest majority setting (out of $n$ parties, at most $(n-1)/2$ are dishonest) and the dishonest majority setting (up to $n-1$ parties can be dishonest). The two settings have a very important difference: the first one can be achieved without making any computational assumption, since it can be secure even against dishonest parties with unlimited computational power. On the other hand, the second one "pays" its stronger resistance to corruption, by necessarily requiring computational assumptions (a dishonest majority MPC protocol cannot be secure against computationally unbounded parties).

Here, you are talking about secure comparison and citing my paper, so I assume that you are talking about secure two-party computation. Of course, two-party computation falls in the second category: you cannot have a honest majority among two players (unless everyone is honest, in which case there is nothing to protect). This means that you must use computational assumption.

Secret sharing is not a computational assumption. Secret sharing exist unconditionally: Shamir secret sharing, for example, is just polynomial interpolation. It is therefore provably impossible to build a secure 2-party computation protocol for comparison using only secret sharing. All protocols must rely on a computational assumption, which can be homomorphic encryption, oblivious transfer, or something else.

I think the source of the confusion probably comes from the common terminology in MPC: many people use the terminology "secret sharing-based MPC", even in the dishonest majority setting. But this terminology simply means that secret sharing techniques are used in the protocol, usually in a way similar to the GMW protocol. It does not mean, however, that the protocol uses solely secret sharing - since that's impossible. Typically, when we say "secret sharing-based MPC", we refer to an MPC protocol that actually uses secret sharing techniques and oblivious transfer.

So, "methods based on secret sharing" for secure comparison are, exactly like my paper, methods that use oblivious transfer as a computational assumption. If you look at my paper in section 1.5, I also compared my protocol to "generic 2PC applied to [GSV07]". Here, 'generic 2PC' refers to standard GMW-style 2PC, which is precisely what is often called 'secret sharing based MPC'. A GMW-style protocol requires a boolean circuit representation of the target function; that's why I said "applied to [GSV07]", which provides precisely such a circuit. Hence, I do compare my work to what is often called 'secret sharing MPC' - but I simply did not use the terminology that seems to be the source of your confusion.

$\endgroup$
1
  • $\begingroup$ @GeoffreyCouteau So in 2pc setting, we have to use computational assumption to do secure computation. Then, for example, if I want to use a boolean circuit for multiplication, when computing AND gate, I use beaver triples. two situations: 1. 2 computing parties can use HE or OT to generate the triples, is HE and OT here the computational assumption we refer to? 2. We can also use trusted dealers to generate these triples, what's the difference between situation 1/2? If we use trusted dealers pre generate triples and send the shares to 2 parties, the online phase is very efficient I think $\endgroup$
    – rzxh
    Oct 12 at 21:03

Your Answer

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

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