Try EvalFastRotationExt over EvalFastRotation in OpenFHE backend

[j2kun]

We use EvalFastRotation in our OpenFHE backend, but there is another method EvalFastRotationExt https://github.com/openfheorg/openfhe-development/blob/aa391988d354d4360f390f223a90e0d1b98839d7/src/pke/include/cryptocontext.h#L2438

It says that one is supported for hybrid key switching, which we support in HEIR. However, I don't recall if we use hybrid key switching by default, or how to determine when to use it versus other options.

Search the codebase for SetKeySwitchTechnique(HYBRID) for references.

Main goal would be to understand the performance implications of using the Ext variant, and use it in HEIR when appropriate.

[toprakmurat]

Hi! I’d be happy to work on this issue. I’m an undergraduate student at ITU and have recently started doing research in FHE. Could you please assign this issue to me?

[asraa]

I was just looking at this because I found that FastRotation was taking a lot of time in my program - yes, HEIR enables hybrid key switching by default. OpenFHE's default settings enable rotations with HYBRID and HEIR will only SetKeySwitchTechnique in codegen/interpreter when the GenParams op enables BV key switching.

Ext mode enables the fast rotation to be computed in the extended modulus (P*Q). After calling EvalFastRotationExt, you need to explicitly mod down back to the modulus Q with KeySwitchDown. In the meantime, you can perform computations in the extended modulus like EvalAddExt/EvalAddExtInPlace or EvalMultExt/EvalMultExtInPlace

It makes the most sense to do this when we can add/mul_plain many rotation results in the extended modulus and call KeySwitchDown once after taking the sum.

[j2kun]

This sounds like it should then be a larger transformation pass to take advantage of this opporuntity at the OpenFHE level.

[asraa]

Totally - the openfhe EvalLinearTransform functions use this internally so we are losing out on some performance by not using that API when we are computing linear transforms for matvecs/etc

[j2kun]

OK so for @toprakmurat the scope of the transformation will be:

• At the openfhe dialect level (since we don't have a notion of "extended basis operations" at the LWE level)
• Add new ops for openfhe.fast_rotation_ext as well as other ops that can happen at the _ext level.
• Add a new op for the KeySwitchDown (reverting from the extended basis to the normal basis).
• Look for places where openfhe.fast_rotation is used, and convert each one to openfhe.fast_rotation_ext (this will need a new op) plus a key_switch_down op.
• Add patterns that try to greedily push key_switch_down later in the IR, by swapping a sequence of ops like openfhe.key_switch_down + openfhe.add with openfhe.add_ext + openfhe.key_switch_down. I think the only valid ops here are Add/AddExt, AddInPlace/AddExtInPlace, and Mul/MulExt (No MultInPlace in OpenFHE).

There might be a situation where doing ops in the extended basis is more expensive than key switching down and doing the ops in the (slightly smaller) basis? But either way, we can start with the pattern-based greedy approach and improve it if we see a need.

[github-actions]

This issue has 1 outstanding TODOs:

• lib/Dialect/Openfhe/IR/OpenfheOps.td:452: support the "Ext" variant for hybrid key switching.

This comment was autogenerated by todo-backlinks