---
title: "CKKS Bootstrapping: Refreshing Deep Circuits"
author: "Balasubramanian Narasimhan"
date: "`r Sys.Date()`"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{CKKS Bootstrapping: Refreshing Deep Circuits}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
# Cap OpenMP to CRAN's two-core policy (see ?openfhe.R::set_num_threads).
library(openfhe.R)
openfhe.R::set_num_threads(2L)
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

CKKS has a budget. Every multiplication consumes a level in
the ciphertext's modulus chain, and when the chain is
exhausted the ciphertext stops being decryptable. For a
linear sequence of multiplications the budget is exactly the
multiplicative depth you configured at context construction;
once it's spent, you either finish the computation or you
find a way to refresh the ciphertext.

**Bootstrapping is the refresh operation.** It produces a
new ciphertext that encrypts the same plaintext but at a
fresh modulus level. From the outside it's an identity
function; internally it runs a small circuit of its own
(typically consuming 10–15 levels) that leaves the
ciphertext at a higher level than it started.

OpenFHE exposes three flavors of bootstrap. This vignette
walks all three, with runnable examples, and maps each to
the R interface that `openfhe.R` ships:

1. **Non-interactive bootstrap** — the classical form. The
   server holds bootstrap keys and can refresh any
   ciphertext on its own.
2. **Iterative non-interactive bootstrap** — the same thing
   in a loop, for circuits deep enough that one refresh
   isn't enough.
3. **Interactive multi-party bootstrap** — the 9117
   addition. Each party contributes to the refresh, no
   single party holds enough key material to bootstrap
   alone. This is the variant that composes with the
   threshold-FHE workflow the cox-threshold and
   cvxr-consensus-admm vignettes build on.

Key point: **the bootstrap is invisible to the R user's statistical
code.** You still call the same `eval_mult` / `eval_add` / `decrypt`
functions; the bootstrap adds one call and the R script reads through
as if nothing happened.

## The depth budget problem

To see why bootstrapping matters, start with a depth-limited
context and run out of budget.

```{r depth-budget}
library(openfhe.R)

cc_shallow <- fhe_context("CKKS",
  multiplicative_depth = 3L,
  scaling_mod_size     = 50L,
  batch_size           = 8L
)
kp_shallow <- key_gen(cc_shallow, eval_mult = TRUE)

x <- c(0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5)
pt <- make_ckks_packed_plaintext(cc_shallow, x)
ct <- encrypt(kp_shallow@public, pt, cc = cc_shallow)

## Three multiplications in sequence — right at the depth
## budget. This succeeds.
ct_a <- ct * ct           # level 1
ct_b <- ct_a * ct         # level 2
ct_c <- ct_b * ct         # level 3
res <- decrypt(ct_c, kp_shallow@secret, cc = cc_shallow)
set_length(res, 8L)
round(get_real_packed_value(res)[1:3], 5)
## ~ c(0.5^4, 0.5^4, 0.5^4) = c(0.0625, 0.0625, 0.0625)
```

One more multiplication on `ct_c` would fail: the modulus
chain is empty and the next multiply has nothing to rescale
into. That's the depth wall. The rest of the vignette shows
how to climb past it.

## Non-interactive bootstrap

The classical CKKS bootstrap is a server-side operation.
The server holds a set of *bootstrap keys* (generated from
the secret key at setup time) and can call `eval_bootstrap`
on any ciphertext to refresh it. No client interaction
needed once the keys are in place.

### Setup

Bootstrap has significant level overhead — the bootstrap
circuit itself consumes modulus-chain levels, so the
context's `multiplicative_depth` must be at least the
bootstrap budget plus whatever user compute the refreshed
ciphertext needs to support.

`get_bootstrap_depth()` computes the per-bootstrap level
cost from the `level_budget` and the secret-key distribution.

```{r noninteractive-setup}
## Choose the bootstrap level budget. The two integers are
## the encoding and decoding budgets; (3, 3) is a reasonable
## middle ground. Larger values give faster bootstrap at the
## cost of deeper required chain.
level_budget   <- c(3L, 3L)
secret_key_dist <- SecretKeyDist$UNIFORM_TERNARY

boot_depth <- get_bootstrap_depth(level_budget, secret_key_dist)
boot_depth

## User compute budget after a single bootstrap — how many
## multiplications we want to do between refreshes.
user_depth <- 2L

total_depth <- boot_depth + user_depth
total_depth
```

With the budget computed, build a CKKS context that has
enough depth to cover both the bootstrap circuit and the
post-bootstrap user compute.

```{r noninteractive-context}
cc <- fhe_context("CKKS",
  multiplicative_depth = total_depth,
  scaling_mod_size     = 59L,
  first_mod_size       = 60L,
  ring_dim             = 4096L,
  security_level       = SecurityLevel$HEStd_NotSet,
  scaling_technique    = ScalingTechnique$FLEXIBLEAUTO,
  features             = c(Feature$ADVANCEDSHE, Feature$FHE)
)
kp <- key_gen(cc, eval_mult = TRUE)
```

`Feature$FHE` is the feature flag that turns on the
bootstrap; `Feature$ADVANCEDSHE` is required
alongside it because the Chebyshev approximations used
inside the bootstrap circuit live in that feature.

### Bootstrap key generation

Once the context exists, generate the bootstrap keys
(rotation keys that the bootstrap circuit uses internally)
and pre-compute the encoding / decoding plaintexts.

```{r noninteractive-keygen}
## ring_dim / 2 is the number of CKKS slots. Query it off
## the context rather than hard-coding.
ring_dim  <- ring_dimension(cc)
num_slots <- as.integer(ring_dim / 2)

eval_bootstrap_setup(cc, level_budget = level_budget)
eval_bootstrap_key_gen(cc, kp@secret, num_slots)
```

The setup call accepts the optional `bt_slots_encoding`
argument for a small efficiency improvement
in specific slot configurations — it defaults to `FALSE`
matching the upstream default.

### Run a refresh

Encrypt a small vector, burn through most of the user
compute budget, then bootstrap and verify the refreshed
ciphertext still decrypts to the expected plaintext.

```{r noninteractive-run}
y <- c(0.25, 0.5, 0.75, 1.0)
pt_y <- make_ckks_packed_plaintext(cc, y)
ct_y <- encrypt(kp@public, pt_y, cc = cc)

## Burn a couple of levels to simulate "the user circuit has
## run and now we need to refresh".
ct_y <- ct_y * ct_y     # y^2
## At this point ct_y sits at a lower level than it started.

## One bootstrap call refreshes the ciphertext. Default
## num_iterations = 1L is the standard case.
ct_refreshed <- eval_bootstrap(ct_y)

## Decrypt the refreshed ciphertext and confirm it holds
## the same value as y^2 did.
res_refresh <- decrypt(ct_refreshed, kp@secret, cc = cc)
set_length(res_refresh, 4L)
round(get_real_packed_value(res_refresh)[1:4], 4)
## ~ c(0.0625, 0.25, 0.5625, 1.0) = y^2
```

Post-refresh, the ciphertext has enough headroom to continue
computing — `ct_refreshed * ct` works where a second
`ct_y * ct_y` on the pre-bootstrap form would have been
exhausted.

## Iterative bootstrap

For circuits deep enough that one refresh isn't enough,
`eval_bootstrap()` accepts a `num_iterations` argument that
runs multiple refreshes in sequence with increasing
precision. This is the iterative form — a quality/performance
trade-off that lets the caller spend more cycles for tighter
noise bounds.

```{r iterative-bootstrap, eval = FALSE}
## Same cc, same keys — just more iterations per call.
ct_refreshed_2 <- eval_bootstrap(ct_y, num_iterations = 2L)
```

The cost scales roughly linearly in `num_iterations`; two
iterations is the typical value when a single refresh's
precision drop is the dominant source of error in a long
user circuit. Three or more iterations have diminishing
returns and are rarely needed.

The iterative form is hidden inside the same
`eval_bootstrap()` entry point — there is no separate
`eval_iterative_bootstrap()` generic. The `num_iterations`
argument is optional and defaults to `1L`, so existing code
that calls `eval_bootstrap(ct)` gets the classical non-
iterative form unchanged.

## Interactive multi-party bootstrap

The non-interactive forms require a party that holds the
bootstrap keys — and the bootstrap keys are generated from
the secret key, so whoever holds them effectively holds the
decryption capability. In a threshold-FHE setting where no
single party is supposed to decrypt on their own, the
classical bootstrap isn't viable: granting any party the
bootstrap keys would break the threshold security model.

The **interactive multi-party bootstrap** (`IntMPBoot*`
family) solves this. The refresh
operation itself becomes a distributed protocol: each party
contributes a share, the shares are aggregated into a
single "shares pair", and a final re-encryption step
produces a refreshed ciphertext at a fresh modulus level
without any party ever holding enough key material to
decrypt alone.

This is the bootstrap variant that composes with the
threshold-FHE flow used in the `cox-threshold` and
`cvxr-consensus-admm` vignettes.

### Setup

Build a CKKS context with `Feature$MULTIPARTY` alongside
the `FHE` + `ADVANCEDSHE` features, then generate the lead
party's key material and daisy-chain a second party off it.

```{r mp-bootstrap-setup}
cc_mp <- fhe_context("CKKS",
  multiplicative_depth = 6L,
  scaling_mod_size     = 50L,
  first_mod_size       = 60L,
  ring_dim             = 4096L,
  security_level       = SecurityLevel$HEStd_NotSet,
  batch_size           = 8L,
  features             = c(Feature$ADVANCEDSHE, Feature$FHE,
                           Feature$MULTIPARTY)
)
kp1 <- key_gen(cc_mp, eval_mult = TRUE)
kp2 <- multiparty_key_gen(cc_mp, kp1@public)
```

### Refresh a ciphertext through the multi-party protocol

Encrypt a plaintext under party 2's public key (the
daisy-chained "joint" public key in the two-party threshold
protocol), adjust the scale via `int_mp_boot_adjust_scale()`,
generate a common random element that all parties will use
in their partial decryptions, and then run each party's
partial decryption.

```{r mp-bootstrap-decrypt}
z <- c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8)
pt_z <- make_ckks_packed_plaintext(cc_mp, z)
ct_z <- encrypt(kp2@public, pt_z, cc = cc_mp)

## Step 1: scale adjustment. Prepares the ciphertext for
## the interactive refresh protocol.
ct_z_adjusted <- int_mp_boot_adjust_scale(ct_z)

## Step 2: generate the common random element. Can be
## derived from either the lead party's public key or from
## a reference ciphertext — the two overloads produce
## equivalent output.
a <- int_mp_boot_random_element_gen(cc_mp, kp1@public)

## Step 3: each party computes their masked-decryption
## shares pair. Each party's output is a list of two
## Ciphertexts.
shares1 <- int_mp_boot_decrypt(kp1@secret, ct_z_adjusted, a)
shares2 <- int_mp_boot_decrypt(kp2@secret, ct_z_adjusted, a)
```

### Aggregate and finalize

The shares pairs are aggregated into a single shares pair
via `int_mp_boot_add()` (parallel to how
`multiparty_decrypt_fusion()` aggregates lead + main
partials in the ordinary threshold decrypt). The aggregated
shares pair, the common random element, and the original
ciphertext all go into `int_mp_boot_encrypt()` — the final
step that produces the refreshed ciphertext at a fresh
modulus level.

```{r mp-bootstrap-finalize}
## Aggregate both parties' shares pairs.
aggregated <- int_mp_boot_add(cc_mp, list(shares1, shares2))

## Final re-encryption step.
ct_refreshed_mp <- int_mp_boot_encrypt(kp1@public, aggregated,
                                       a, ct_z_adjusted)
```

The refreshed ciphertext composes with subsequent
computation exactly like the output of the non-interactive
bootstrap would — the bootstrap is still invisible to the
user circuit layer, only the key-management and setup
details change.

## Comparison

The three variants have different properties. This table
summarizes when to reach for each.

| Variant | Feature flags | Who holds bootstrap capability | Typical use |
|---|---|---|---|
| Non-interactive | `ADVANCEDSHE`, `FHE` | Single server | Standard single-party CKKS with deep circuits |
| Iterative | `ADVANCEDSHE`, `FHE` | Single server | Same as above, when one refresh's precision isn't enough |
| Interactive multi-party | `ADVANCEDSHE`, `FHE`, `MULTIPARTY` | Distributed across parties | Threshold FHE where no single party can decrypt |

For the audience that this package primarily serves —
precision-critical distributed statistics with a
threshold-FHE backbone — **the interactive multi-party
form is the right default** whenever a circuit needs more
depth than the initial context budget provides. The
non-interactive form is simpler but requires giving
someone the bootstrap keys, which is exactly what the
threshold flow is trying to avoid. The iterative form is
an efficiency knob on the non-interactive path and is only
relevant when the classical single-server bootstrap is
already viable.

## Further reading

Besides the package help, see:

- [OpenFHE docs](https://openfhe-development.readthedocs.io/)
- Vignettes in the companion
  [homomorpheR](https://cran.r-project.org/package=homomorpheR)
  package (version >= 1.0).