aicis / aicis/fresco

Unnecessary condSelect in CompareAndSwap (for booleans)

未关闭
#334 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
Good beginner issue Type: Enhancement
主要语言
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 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。