0
$\begingroup$

I want to evaluation following functionality:

Parties have secret shares of private input [a] and public input b, they want to measure if a>b, additionally only one party should learn the output

I know this could be directly done with millionaire problem solutions such as:

CrypTFlow2: Practical 2-Party Secure Inference Practical and Secure Solutions for Integer Comparison

or in offline/online model as given here

Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation

But I feel the problem I am trying to solve is slightly easier as one of the input is not private, so I am hopping if I could find slightly more efficient solution.

$\endgroup$
1
  • $\begingroup$ If one of the two parties knows their own secret input, and the other public input, then the trivially know the output of the comparison and no MPC is needed. If you want the party with the public input to be the sole learner of the output, then you are out of luck because the other party already knows all inputs. I take it I am missing something about your question that makes it not so obvious. $\endgroup$
    – Nic
    Jul 10, 2022 at 17:03

1 Answer 1

1
$\begingroup$

You can make a digital comparator circuit (see the equation (A>B) and (A < B) from https://en.wikipedia.org/wiki/Digital_comparator) but hardwire one of the inputs. Then use a garbled circuit for the computation.

This way you don't need to garble all the gates of a full comparator. For example, if the input to an AND gate of a bit from B is 1 (assuming B is public), then you don't need to garble this gate since the output is always 1.

$\endgroup$
1
  • $\begingroup$ okay thanks for suggestion, any suggestion in secret shared setting rather than garbled? Don't wanna pay high communication cost $\endgroup$
    – LWE-13
    Jul 7, 2022 at 4:01

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.