Unnecessary condSelect in CompareAndSwap (for booleans)

[basitkhurram]

Looks like CompareAndSwap requires three AND gates per bit of an input bitstring (i.e., if two bitstrings with m bits each are being compared and swapped, we would use 3m AND gates in total).

It should be possible to perform a "compare and swap" operation with only two AND gates per bit.

Looking at the following code, I think that there may be an unnecessary condSelect used here:

fresco/core/src/main/java/dk/alexandra/fresco/lib/compare/CompareAndSwap.java

Lines 33 to 39 in 65ff15b

	List<DRes<SBool>> first = left.stream()
	.map(e -> {return par.advancedBinary().condSelect(data, e, right.get(left.indexOf(e)));})
	.collect(Collectors.toList());
	List<DRes<SBool>> second = right.stream()
	.map(e -> {return par.advancedBinary().condSelect(data, e, left.get(right.indexOf(e)));})
	.collect(Collectors.toList());

Instead, we could XOR the bits in right with the bits in left and then XOR this result with the bits from first:

List<DRes<SBool>> second = right.stream()
              .map(e -> {return par.binary().xor(e, par.binary().xor(left.get(right.indexOf(e)), first.get(right.indexOf(e))));})
              .collect(Collectors.toList());

However, this approach requires second to be computed after first has been computed, so we lose some parallelism.

A better solution would be to implement a condSwap gate and use such a gate in place of the condSelect gates.

A conditional swap gate takes in a selection bit and two other bits and then sets the order of these two bits depending on the value of the selection bit. A condSwap gate would be parallelizable. (See page 10 from "Improved Garbled Circuit: Free XOR Gates and Applications").