google / google/heir

Investigate double-hoisting for BSGS matrix vector product

Open
#2,215 3 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.