I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap operation swaps only if the integers being compared are in wrong order. I've to implement this operation using just integer addition and multiplication as the atomic operations. I've figured out the comparing bit, but I need to efficiently swap integers. Is there an efficient solution (minimum multiplication gates) to this problem?

P.S: I have integers in the form of binary vectors, but I can't apply mod 2 operations on them. I can only use integer addition and multiplication.

  • 2
    $\begingroup$ I don't understand the model. If $x,y$ are the inputs, just let the first output be $y \times 1$ and the second output be $x \times 1$, and you are done. What exactly are the restrictions? First you say only addition & multiplication, but later you say compare-and-swap, so which is it? Exactly what gates are permitted, and what restrictions are there on how they are allowed to be connected? $\endgroup$
    – D.W.
    Commented May 23, 2017 at 6:16
  • $\begingroup$ I'm trying to homomorphically sort an araay of encrypted integers. So, I need to implement a compare and swap operation using integer addition and multiplication gates as atomic operations. Since the result of comparison will be encrypted as well, I don't know which one will come before. Compare and Swap only swaps if the numbers being compared are in wrong order. I hope you get the idea now. $\endgroup$
    – AdveRSAry
    Commented May 23, 2017 at 10:00
  • 1
    $\begingroup$ $x - y == x + y * (-1)$. Does that help? $\endgroup$ Commented May 23, 2017 at 10:07
  • $\begingroup$ Yes, I can do that. Thanks. I'll have to change the representation a little, and I think I can include this operation. I guess that's as efficient as it gets. $\endgroup$
    – AdveRSAry
    Commented May 23, 2017 at 10:15

1 Answer 1


Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:

notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y

Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.


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.