Unnecessary condSelect in CompareAndSwap (for booleans)
- 主要语言
- Java
- 星标
- 143
- 派生
- 61
- PR 合并指标
- 30 天内没有已合并 PR
描述
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:
https://github.com/aicis/fresco/blob/65ff15beec45ea52536af66379ab0c10827621bf/core/src/main/java/dk/alexandra/fresco/lib/compare/CompareAndSwap.java#L33-L39
Instead, we could XOR the bits in `right` with the bits in `left` and then XOR this result with the bits from `first`:
```
List> 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](http://www.cs.toronto.edu/~vlad/papers/XOR_ICALP08.pdf)").
贡献指南
评估
这个 Issue 还没有评估数据。