Score:1

SS/HE/GC/OT secure integer comparison

de flag

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.

Geoffroy Couteau avatar
cn flag
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.
Geoffroy Couteau avatar
cn flag
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?
rzxh avatar
de flag
@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?
Score:3
cn flag

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.

rzxh avatar
de flag
@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
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.