# Extra multiplication performed in bootstrapping

**URL:** <https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917>\
**Category:** Library Questions\
**Created:** [November 16, 2023, 3:57pm UTC](https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917 "2023-11-16T15:57:12Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [November 16, 2023, 3:57pm UTC](https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917/1 "2023-11-16T15:57:12Z")

</div>

Hello there, newbie question here.

I am trying to optimize my CKKS circuit, and I found that [`here`](https://github.com/openfheorg/openfhe-development/blob/f6f1b9c29592bf474d00899d05ccbbc74842693d/src/pke/lib/scheme/ckksrns/ckksrns-fhe.cpp#L418C2-L418C51) (line 418 of `ckksrns-fhe.cpp`, v.1.1.1), the `EvalBootstrap` procedure of CKKS perform a multiplication, does this add another level in the bootstrapping process?

AFAIK, I am using 5 + 5 for CoeffToSlots and SlotsToCoeff, 6+6 for Modular Reduction, but my bootstrapping uses 23 levels (which is \neq 22= 5+5+6+6)

Thank you very much!

---

<div class="post-metadata">

**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\
**Post date:** [November 17, 2023, 1:38am UTC](https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917/2 "2023-11-17T01:38:30Z")

</div>

Hi @narger ,

If you are referring to the built-in configuration, then 7 levels are used for the Chebyshev interpolation (degree close to 90 - see the table at [https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/FUNCTION\_EVALUATION.md](https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/FUNCTION_EVALUATION.md) for the case when the inputs are normalized), 6 iterations are used for the double-angle formula, and 5 + 5 for encoding and decoding. This adds up to 23, as computed by .`GetBootstrapDepth`.

However, the multiplication you are referring adds one extra level, which is not accounted for by `GetBootstrapDepth`. I opened the issue for it: [GetBootstrapDepth gives an incorrect depth (off by 1) · Issue #594 · openfheorg/openfhe-development · GitHub](https://github.com/openfheorg/openfhe-development/issues/594)

---

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [November 17, 2023, 9:06am UTC](https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917/3 "2023-11-17T09:06:08Z")

</div>

Thank you for the quick response! I have two more questions:

- Why not using 119 as a degree for the Chebyshev Interpolation (since it requires the same number of levels) ?
- Can that extra multiplication be added at user-level? Let’s say that before bootstrapping I perform a multiplication by a, couldn’t that extra multiplication be added so that I multiply by a \cdot x (where x is the value of that extra multiplication), saving one level?

Thank you again 🙂

---

<div class="post-metadata">

**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\
**Post date:** [November 17, 2023, 2:27pm UTC](https://openfhe.discourse.group/t/extra-multiplication-performed-in-bootstrapping/917/4 "2023-11-17T14:27:25Z")

</div>

> - Why not using 119 as a degree for the Chebyshev Interpolation (since it requires the same number of levels) ?

There are several tradeoffs here: 1) degree 119 requires higher computational complexity than 89 (more key switching and rescaling operations; 2) the accuracy depends on many factors, the approximation of modular reduction using the sine wave, which depends on how much q is bigger than the message, recursive double-angle iterations after Chebyshev, etc.

For the second question, the scaling is not the first step (raising the modulus is done before that). If the scaling is done before raising the modulus, then the sine approximation will not work well (will have very poor accuracy).