0
$\begingroup$

I have two questions I couldn't find straightforward answers to after many searches.

(1) We can perform 2-party MPC over arbitrary functions using Garbled Circuit. To do that, we first need to convert a function to a boolean circuit and then garble it. Is there any tool available where we can convert any arbitrary function to a boolean circuit? Say I want to sort three numbers from a given input. How can I convert this function to a boolean circuit?

(2) How do conditional statements work in the boolean circuit? I understand mux or X switch and Y switch operations can be done for simple operations like if (c) swap(a,b) can be done. But how it works in the case of multiple statements?

E.g, I have three numbers a, b, c. The operation I want to perform is like below:

func(a,b,c):
    if c == 1:
        c = a + b
        a = 2 * c
        b = 2 * a
    else
        a = 0
        b = 0

What will the above function look like in boolean circuits? Please give me references if available.

Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

Say I want to sort three numbers from a given input. How can I convert this function to a boolean circuit?

For this particular question, there are simple answers. The traditional way to sort number using circuits (which show up when one wants to sort in parallel) are with sorting networks. For very small input sizes optimal sorting networks are known. In general the sorting network with the best asymptotics (AKS) is not particularly practical. Instead, a good (general) recommendation is Batcher Odd-Even Mergesort, which uses $O(n (\log n)^2)$ comparisons, and is a depth $O((\log n)^2)$ circuit.

How do conditional statements work in the boolean circuit?

The main answer is "they are a pain". General (conditional) statements can be seen as computing something of the form.

if val:
    C1(x1,...,xn)
else:
    C2(x1,...,xn)

here, C1 and C2 are smaller circuits/functions/whatever. Anyway, to compute this branch using a circuit, one can first convert it to be branchless by writing

ytrue = C1(x1,...,xn)
yfalse = C2(x1,...,xn)
yreturn = (val and ytrue) or (not val and yfalse)

Essentially, when val is true one can simplify this to the first part of the branch. When val is false, one can simplify it to the second part of the branch.

In princple it should be straightforward to compile some broad class of programs to binary circuits. Searching for "MPC Circuit Compiler" finds some relevant results, i.e. this paper which includes some discussion of prior literature.

$\endgroup$
3
  • $\begingroup$ Thanks for the detail description. So, in the boolean circuit, it will eventually execute both branches and select the result for the true branch. Is there any way we can only activate the true branch? Or in a boolean circuit, we must calculate both branches all the time? Is there any reference for that? $\endgroup$
    – taserghar
    Nov 19, 2022 at 10:05
  • 2
    $\begingroup$ It is possible to pay (in communication) only for the longest branch: in garbled circuits, secret-sharing, GMW paradigm. These are all relatively recent developments. $\endgroup$
    – Mikero
    Nov 19, 2022 at 16:42
  • 1
    $\begingroup$ I think it is worth emphasizing that if one ignores MPC (and solely discusses boolean circuits), you always have to evaluate both branches of the computation. Circuits always evaluate every computation path. This makes them useful for constant-time code (they, by definition essentially, cannot have timing differences). It also makes them annoying for code that branches heavily. $\endgroup$
    – Mark
    Nov 19, 2022 at 20:40

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.