Investigate double-hoisting for BSGS matrix vector product
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
The Orion paper mentions that they use double-hoisting for all their BSGS matrix vector products. One hoisting is the repeated rotations of the same vector, which can only be used to compute all the baby step rotations of the input vector. The double hoisting technique extends the technique to also be applied to the giant steps. This is described as coming Bossuat et al's paper https://link.springer.com/chapter/10.1007/978-3-030-77870-5_21
```
The first level, proposed by Halevi et al. [18], applies to the inner-loop rotations (line 8 of Algorithm 5). This renders the computation devoted to Decompose
independent of the value n1, so the complexity is reduced to
(n2 + n1) · (MultSum + ModDown + Permute) + (n2 + 1) · Decompose.
The second level, which we propose, introduces an additional hoisting for
the inner-loop rotations, as the ModDown step is a coefficient-wise operation.
Similarly to the Decompose step, this operation commutes with the Permute step
and the ciphertext-plaintext multiplications (line 8 of Algorithm 5). Therefore,
we need to apply it only once after the entire inner-loop of n1 rotations. Applying
the same reasoning for the ModDown step of the outer-loop rotations we can
reduce the number of key-switch operations from n1 + n2 to n2 + 1:
```
Contributor guide
Assessment
This issue has not been assessed yet.