How to Properly Perform Bootstrapping in CKKS When LogSlots < LogN/2?

[Tokubara]

To enable bootstrapping, I set LogN (including the residual parameter) to 16, but the plaintext contains only (2^{14}) slots. To speed up bootstrapping, I set LogSlots in bootstrapping.ParametersLiteral to 14. However, I found that the bootstrapping results are almost entirely incorrect. Below are the code and its results. When I set LogSlots to 15, the bootstrapping results appear normal.

So, how can I properly perform bootstrapping when the number of slots of a ciphertext is less than N/2?

package main

import (
	"fmt"
	"math"

	"github.com/tuneinsight/lattigo/v6/core/rlwe"
	"github.com/tuneinsight/lattigo/v6/schemes/ckks"
	"github.com/tuneinsight/lattigo/v6/utils"
	"github.com/tuneinsight/lattigo/v6/circuits/ckks/bootstrapping"
	"github.com/tuneinsight/lattigo/v6/ring"
	"github.com/tuneinsight/lattigo/v6/utils/sampling"
)

func main() {
	var err error
	var params ckks.Parameters
	multiplicativeDepth := 24

	firstModSize := 60
	scalingModSize := 40
	LogN := 16
	LogQ := make([]int, multiplicativeDepth+1)
	LogQ[0] = firstModSize
	for i := 1; i < (1 + multiplicativeDepth); i++ {
		LogQ[i] = scalingModSize
	}

	alpha := 3
	LogP := make([]int, alpha)
	for i := 0; i < alpha; i++ {
		LogP[i] = 61
	}
	var LogSlots int = 14
	rlweParametersLit := ckks.ParametersLiteral{
			LogN:            LogN,
			LogQ:            LogQ,
			LogP:            LogP,
			LogDefaultScale: scalingModSize,
			Xs:              ring.Ternary{H: 192},
	}
	if params, err = ckks.NewParametersFromLiteral(rlweParametersLit); err != nil {
		panic(err)
	} else {
		fmt.Printf("rlwe parameters: %v\n", rlweParametersLit)
		fmt.Printf("Q: %v\n", params.Q())
	}
	prec := params.EncodingPrecision()
	fmt.Printf("prec: %v\n", prec)
	LogMessageRatio := 8

	btpParametersLit := bootstrapping.ParametersLiteral{
		LogN: utils.Pointy(LogN),
		LogP: LogP,
		Xs:   params.Xs(),
		LogMessageRatio: &LogMessageRatio,
		LogSlots: &LogSlots,

	}

	btpParams, err := bootstrapping.NewParametersFromLiteral(params, btpParametersLit)
	if err != nil {
		panic(err)
	}

	fmt.Printf("Residual parameters: logN=%d, logSlots=%d, H=%d, sigma=%f, logQP=%f, levels=%d, scale=2^%d\n",
		btpParams.ResidualParameters.LogN(),
		btpParams.ResidualParameters.LogMaxSlots(),
		btpParams.ResidualParameters.XsHammingWeight(),
		btpParams.ResidualParameters.Xe(), params.LogQP(),
		btpParams.ResidualParameters.MaxLevel(),
		btpParams.ResidualParameters.LogDefaultScale())

	fmt.Printf("Bootstrapping parameters: logN=%d, logSlots=%d, H(%d; %d), sigma=%f, logQP=%f, levels=%d, scale=2^%d, levels=%v\n",
		btpParams.BootstrappingParameters.LogN(),
		btpParams.BootstrappingParameters.LogMaxSlots(),
		btpParams.BootstrappingParameters.XsHammingWeight(),
		btpParams.EphemeralSecretWeight,
		btpParams.BootstrappingParameters.Xe(),
		btpParams.BootstrappingParameters.LogQP(),
		btpParams.BootstrappingParameters.QCount(),
		btpParams.BootstrappingParameters.LogDefaultScale(),
		btpParams.BootstrappingParameters.MaxLevel(),
	)

	kgen := rlwe.NewKeyGenerator(params)

	sk, pk := kgen.GenKeyPairNew()

	encoder := ckks.NewEncoder(params)
	decryptor := rlwe.NewDecryptor(params, sk)
	encryptor := rlwe.NewEncryptor(params, pk)

	fmt.Println()
	fmt.Println("Generating bootstrapping evaluation keys...")
	evk, _, err := btpParams.GenEvaluationKeys(sk)
	if err != nil {
		panic(err)
	}

	var eval *bootstrapping.Evaluator
	if eval, err = bootstrapping.NewEvaluator(btpParams, evk); err != nil {
		panic(err)
	}

	valuesWant := make([]float64, (1<<14))
	for i := range valuesWant {
		valuesWant[i] = sampling.RandFloat64(0, 1)
	}

	plaintext := ckks.NewPlaintext(params, 0)
	if err := encoder.Encode(valuesWant, plaintext); err != nil {
		panic(err)
	}

	ciphertext1, err := encryptor.EncryptNew(plaintext)
	if err != nil {
		panic(err)
	}

	fmt.Println()
	fmt.Println("Precision of values vs. ciphertext")
	valuesTest1 := printDebug(params, ciphertext1, valuesWant, decryptor, encoder)

	fmt.Println("Bootstrapping...")
	ciphertext2, err := eval.Bootstrap(ciphertext1)
	if err != nil {
		panic(err)
	}
	fmt.Println("Done")

	fmt.Println()
	fmt.Println("Precision of ciphertext vs. Bootstrap(ciphertext)")
	printDebug(params, ciphertext2, valuesTest1, decryptor, encoder)
}

func printDebug(params ckks.Parameters, ciphertext *rlwe.Ciphertext, valuesWant []float64, decryptor *rlwe.Decryptor, encoder *ckks.Encoder) (valuesTest []float64) {

	valuesTest = make([]float64, ciphertext.Slots())

	if err := encoder.Decode(decryptor.DecryptNew(ciphertext), valuesTest); err != nil {
		panic(err)
	}

	fmt.Println()
	fmt.Printf("Level: %d (logQ = %d)\n", ciphertext.Level(), params.LogQLvl(ciphertext.Level()))

	fmt.Printf("Scale: 2^%f\n", math.Log2(ciphertext.Scale.Float64()))
	fmt.Printf("ValuesTest: %6.10f %6.10f %6.10f %6.10f...\n", valuesTest[0], valuesTest[1], valuesTest[2], valuesTest[3])
	fmt.Printf("ValuesWant: %6.10f %6.10f %6.10f %6.10f...\n", valuesWant[0], valuesWant[1], valuesWant[2], valuesWant[3])

	precStats := ckks.GetPrecisionStats(params, encoder, nil, valuesWant, valuesTest, 0, false)

	fmt.Println(precStats.String())
	fmt.Println()

	return
}

The output is:

rlwe parameters: {16 0 [] [] [60 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40] [61 61 61] <nil> {0 192} Standard 40}
Q: [1152921504606584833 1099512938497 1099510054913 1099507695617 1099515691009 1099516870657 1099506515969 1099504549889 1099503894529 1099503370241 1099502714881 1099521458177 1099522375681 1099500617729 1099523555329 1099499569153 1099499175937 1099525128193 1099498258433 1099526176769 1099529060353 1099490000897 1099489607681 1099535220737 1099488428033]
prec: 53
Residual parameters: logN=16, logSlots=15, H=192, sigma={3.200000 19.200000}, logQP=1202.999939, levels=24, scale=2^40
Bootstrapping parameters: logN=16, logSlots=15, H(192; 32), sigma={3.200000 19.200000}, logQP=2023.999925, levels=40, scale=2^40, levels=39

Generating bootstrapping evaluation keys...

Precision of values vs. ciphertext

Level: 0 (logQ = 60)
Scale: 2^40.000000
ValuesTest: 0.4469917934 0.5146602212 0.5331587303 0.2273488563...
ValuesWant: 0.4469917934 0.5146602205 0.5331587307 0.2273488565...

┌─────────┬───────┬───────┬───────┐
│    Log2 │ REAL  │ IMAG  │ L2    │
├─────────┼───────┼───────┼───────┤
│MIN Prec │ 27.64 │ 40.00 │ 27.14 │
│MAX Prec │ 40.00 │ 40.00 │ 40.00 │
│AVG Prec │ 31.79 │ 40.00 │ 31.29 │
│MED Prec │ 31.51 │ 40.00 │ 31.01 │
│STD Prec │  1.80 │  0.00 │  1.80 │
├─────────┼───────┼───────┼───────┤
│MIN Err  │  0.00 │  0.00 │  0.00 │
│MAX Err  │ 12.36 │  0.00 │ 12.86 │
│AVG Err  │  8.21 │  0.00 │  8.71 │
│MED Err  │  8.49 │  0.00 │  8.99 │
│STD Err  │  1.80 │  0.00 │  1.80 │
└─────────┴───────┴───────┴───────┘


Bootstrapping...
Done

Precision of ciphertext vs. Bootstrap(ciphertext)

Level: 24 (logQ = 1020)
Scale: 2^40.000000
ValuesTest: 0.2055705164 0.2863262548 0.2699924931 0.0677141145...
ValuesWant: 0.4469917934 0.5146602212 0.5331587303 0.2273488563...

┌─────────┬───────┬───────┬───────┐
│    Log2 │ REAL  │ IMAG  │ L2    │
├─────────┼───────┼───────┼───────┤
│MIN Prec │  0.35 │ 40.00 │ -0.15 │
│MAX Prec │ 16.26 │ 40.00 │ 15.76 │
│AVG Prec │  2.29 │ 40.00 │  1.79 │
│MED Prec │  1.98 │ 40.00 │  1.48 │
│STD Prec │  1.30 │  0.00 │  1.30 │
├─────────┼───────┼───────┼───────┤
│MIN Err  │ 23.74 │  0.00 │ 24.24 │
│MAX Err  │ 39.65 │  0.00 │ 40.15 │
│AVG Err  │ 37.71 │  0.00 │ 38.21 │
│MED Err  │ 38.02 │  0.00 │ 38.52 │
│STD Err  │  1.30 │  0.00 │  1.30 │
└─────────┴───────┴───────┴───────┘

[lehugueni]

Hi!

This is linked to a bug that is fixed in this PR #506 that is yet to be merged.
If you want to try your example with the corresponding branch, don't forget to set the dimension of the plaintext according to LogSlots:

plaintext := ckks.NewPlaintext(params, 0)
plaintext.LogDimensions = ring.Dimensions{Rows: 0, Cols: LogSlots}