Bootstrap not work with default parameters, HEFloatRealParamsN13QP218

[JohnJimAir]

// Package main implements an example showcasing the basics of the bootstrapping for fixed-point approximate arithmetic over the reals/complexes.
// The bootstrapping is a circuit that homomorphically re-encrypts a ciphertext at level zero to a ciphertext at a higher level, enabling further computations.
// Note that, unlike other bootstrappings (BGV/BFV/TFHE), the this bootstrapping does not reduce the error in the ciphertext, but only enables further computations.
// This example shows how to bootstrap a single ciphertext whose ring degree is the same as the one of the bootstrapping parameters.
// Use the flag -short to run the examples fast but with insecure parameters.
package main

import (
	"flag"
	"fmt"
	"math"
	"time"

	"github.com/tuneinsight/lattigo/v5/core/rlwe"
	"github.com/tuneinsight/lattigo/v5/examples"
	"github.com/tuneinsight/lattigo/v5/he/hefloat"
	"github.com/tuneinsight/lattigo/v5/he/hefloat/bootstrapping"
	"github.com/tuneinsight/lattigo/v5/utils/sampling"
)

var flagShort = flag.Bool("short", false, "run the example with a smaller and insecure ring degree.")

func main() {

	flag.Parse()

	// Default LogN, which with the following defined parameters
	// provides a security of 128-bit.
	LogN := 16

	if *flagShort {
		LogN -= 3
	}

	//==============================
	//=== 1) RESIDUAL PARAMETERS ===
	//==============================

	// First we must define the residual parameters.
	// The residual parameters are the parameters used outside of the bootstrapping circuit.
	// For this example, we have a LogN=16, logQ = 55 + 10*40 and logP = 3*61, so LogQP = 638.
	// With LogN=16, LogQP=638 and H=192, these parameters achieve well over 128-bit of security.
	// params, err := hefloat.NewParametersFromLiteral(hefloat.ParametersLiteral{
	// 	LogN:            LogN,                                              // Log2 of the ring degree
	// 	LogQ:            []int{55, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}, // Log2 of the ciphertext prime moduli
	// 	LogP:            []int{61, 61, 61},                                 // Log2 of the key-switch auxiliary prime moduli
	// 	LogDefaultScale: 40,                                                // Log2 of the scale
	// 	Xs:              ring.Ternary{H: 192},
	// })
	params, err := hefloat.NewParametersFromLiteral(examples.HEFloatRealParams[1])

	if err != nil {
		panic(err)
	}

	//==========================================
	//=== 2) BOOTSTRAPPING PARAMETERSLITERAL ===
	//==========================================

	// The bootstrapping circuit use its own Parameters which will be automatically
	// instantiated given the residual parameters and the bootstrapping parameters.

	// !WARNING! The bootstrapping parameters are not ensure to be 128-bit secure, it is the
	// responsibility of the user to check that the meet the security requirement and tweak them if necessary.

	// Note that the default bootstrapping parameters use LogN=16 and a ternary secret with H=192 non-zero coefficients
	// which provides parameters which are at least 128-bit if their LogQP <= 1550.

	// For this first example, we do not specify any circuit specific optional field in the bootstrapping parameters literal.
	// Thus we expect the bootstrapping to give a precision of 27.25 bits with H=192 (and 23.8 with H=N/2)
	// if the plaintext values are uniformly distributed in [-1, 1] for both the real and imaginary part.
	// See `he/float/bootstrapping/parameters_literal.go` for detailed information about the optional fields.
	LogN = 14
	btpParametersLit := bootstrapping.ParametersLiteral{
		// // We specify LogN to ensure that both the residual parameters and the bootstrapping parameters
		// // have the same LogN. This is not required, but we want it for this example.
		LogN: &LogN,

		// // In this example we need manually specify the number of auxiliary primes (i.e. #Pi) used by the
		// // evaluation keys of the bootstrapping circuit, so that the size of LogQP  meets the security target.
		// LogP: []int{61, 61, 61, 61},

		// // In this example we manually specify the bootstrapping parameters' secret distribution.
		// // This is not necessary, but we ensure here that they are the same as the residual parameters.
		// Xs: params.Xs(),
	}

	//===================================
	//=== 3) BOOTSTRAPPING PARAMETERS ===
	//===================================

	// Now that the residual parameters and the bootstrapping parameters literals are defined, we can instantiate
	// the bootstrapping parameters.
	// The instantiated bootstrapping parameters store their own hefloat.Parameter, which are the parameters of the
	// ring used by the bootstrapping circuit.
	// The bootstrapping parameters are a wrapper of hefloat.Parameters, with additional information.
	// They therefore has the same API as the hefloat.Parameters and we can use this API to print some information.
	btpParams, err := bootstrapping.NewParametersFromLiteral(params, btpParametersLit)
	if err != nil {
		panic(err)
	}

	if *flagShort {
		// Corrects the message ratio Q0/|m(X)| to take into account the smaller number of slots and keep the same precision
		btpParams.Mod1ParametersLiteral.LogMessageRatio += 16 - params.LogN()
	}

	// We print some information about the residual parameters.
	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())

	// And some information about the bootstrapping parameters.
	// We can notably check that the LogQP of the bootstrapping parameters is smaller than 1550, which ensures
	// 128-bit of security as explained above.
	fmt.Printf("Bootstrapping parameters: logN=%d, logSlots=%d, H(%d; %d), sigma=%f, logQP=%f, levels=%d, scale=2^%d\n",
		btpParams.BootstrappingParameters.LogN(),
		btpParams.BootstrappingParameters.LogMaxSlots(),
		btpParams.BootstrappingParameters.XsHammingWeight(),
		btpParams.EphemeralSecretWeight,
		btpParams.BootstrappingParameters.Xe(),
		btpParams.BootstrappingParameters.LogQP(),
		btpParams.BootstrappingParameters.QCount(),
		btpParams.BootstrappingParameters.LogDefaultScale())

	//===========================
	//=== 4) KEYGEN & ENCRYPT ===
	//===========================

	// Now that both the residual and bootstrapping parameters are instantiated, we can
	// instantiate the usual necessary object to encode, encrypt and decrypt.

	// Scheme context and keys
	kgen := rlwe.NewKeyGenerator(params)

	sk, pk := kgen.GenKeyPairNew()

	encoder := hefloat.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)
	}
	fmt.Println("Done")

	//========================
	//=== 5) BOOTSTRAPPING ===
	//========================

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

	// Generate a random plaintext with values uniformely distributed in [-1, 1] for the real and imaginary part.
	valuesWant := make([]float64, params.MaxSlots())
	for i := range valuesWant {
		valuesWant[i] = sampling.RandFloat64(-1, 1)
	}

	// We encrypt at level 0
	plaintext := hefloat.NewPlaintext(params, 0)
	if err := encoder.Encode(valuesWant, plaintext); err != nil {
		panic(err)
	}

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

	// Decrypt, print and compare with the plaintext values
	fmt.Println()
	fmt.Println("Precision of values vs. ciphertext")
	valuesTest1 := printDebug(params, ciphertext1, valuesWant, decryptor, encoder)

	// Bootstrap the ciphertext (homomorphic re-encryption)
	// It takes a ciphertext at level 0 (if not at level 0, then it will reduce it to level 0)
	// and returns a ciphertext with the max level of `floatParamsResidualLit`.
	// CAUTION: the scale of the ciphertext MUST be equal (or very close) to params.DefaultScale()
	// To equalize the scale, the function evaluator.SetScale(ciphertext, parameters.DefaultScale()) can be used at the expense of one level.
	// If the ciphertext is is at level one or greater when given to the bootstrapper, this equalization is automatically done.
	fmt.Println("Bootstrapping...")
	startTime := time.Now()
	ciphertext2, err := eval.Bootstrap(ciphertext1)
	if err != nil {
		panic(err)
	}
	endTime := time.Now()
	fmt.Printf("time of bts: %s\n", endTime.Sub(startTime))
	fmt.Println("Done")

	//==================
	//=== 6) DECRYPT ===
	//==================

	// Decrypt, print and compare with the plaintext values
	fmt.Println()
	fmt.Println("Precision of ciphertext vs. Bootstrap(ciphertext)")
	printDebug(params, ciphertext2, valuesTest1, decryptor, encoder)
}

func printDebug(params hefloat.Parameters, ciphertext *rlwe.Ciphertext, valuesWant []float64, decryptor *rlwe.Decryptor, encoder *hefloat.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 := hefloat.GetPrecisionStats(params, encoder, nil, valuesWant, valuesTest, 0, false)

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

	return
}

The program above reports an error: "panic: cannot BootstrapMany: cannot BootstrapMany: initial Q/Scale = 8.000214 < 0.5*Q[0]/MessageRatio = 256.000000"
I set all parameters with default initialization. If I need to set any parameters manually?

[Pro7ech]

This happens because the message ratio (Q/Scale) (~8) is smaller than the parameterized message ratio (256) and the input ciphertext is at level 0 (else it could use a level to bring it up). The parameterized message ratio is changed in this script here to ensure that the precision remains the same as when doing with LogN=16:

if *flagShort {
	// Corrects the message ratio Q0/|m(X)| to take into account the smaller number of slots and keep the same precision
	btpParams.Mod1ParametersLiteral.LogMessageRatio += 16 - params.LogN()
}

[JohnJimAir]

Actually, I run the code without the "-short" flag. Note the "LogN = 14" at line 73.
And I run the code I pasted above with "if *flagShort {}" at line 103 commented out to make "btpParams.Mod1ParametersLiteral.LogMessageRatio += 16 - params.LogN()" effective, as the meaning your reply conveyed I guess. But it still does not work, until I changed "btpParams.Mod1ParametersLiteral.LogMessageRatio += 16 - params.LogN()" to "btpParams.Mod1ParametersLiteral.LogMessageRatio += 8 - params.LogN()".
Is this proper? Thank you very much!

[Pro7ech]

@yiquedexianshi I get your issue now, you modified the example by using parameters from examples/params and it broke it. These parameters were not designed to be residual parameters after the bootstrapping, they are standalone example parameters. The main issue comes from the ration between LogQ[0] = 33 and LogDefaultScale=30. It is 3, i.e. $2^3 = 8$. For this to work, you either need increase the size of LogQ[0] (but you'll need to update the entire parameter set to ensure it stays 128-bit secure) or modify the field LogMessageRatio in the bootstrapping parameters to be 3 (and remove the lines of code that update it afterward depending on the ring degree). But keep in mind that the default bootstrapping parameters were designed for LogMessageRatio=8, which means that if you modify it you will not get the same precision as the one advertised.

[JohnJimAir]

Thank you.
The whole story is that my application needs to use the bootstrapping, and I want the bootstrapping to be fast. I have some basic konwledge about FHE, but "LogMessageRatio" and so on is out of my experience.
I just want to konw that is this proper that I use "examples.HEFloatRealParams[2]" with "LogN=15" or "examples.HEFloatComplexParams[2]" with "LogN=14", since "examples.HEFloatRealParams[1]" with "LogN=14" does not work as I said above. Or do you have some other advises?

[Pro7ech]

If you do not feel comfortable in fine-tuning the bootstrapping parameters, it is better to stick with the default ones: btpParametersLit := bootstrapping.ParametersLiteral{}

You can look at the GoDoc of the struct bootstrapping.ParametersLiteral{}, it explains what are the expected performance of the default parameters.

You can still freely (mostly up to the issue you encountered) chose the residual parameters, but know that it will only have a marginal impact on the bootstrapping performance, because they use their own parameters that are abstracted to the user.

[JohnJimAir]

Well, actually you can not just use btpParametersLit := bootstrapping.ParametersLiteral{}, because LogN's default value is 16. So if I want to use examples.HEFloatRealParams[2] whose LogN is 14, I have to set the LogN in bootstrapping parameters to be 15, because that the residual parameters now is "Real". Or set the LogN of bootstrapping parameters to be the same value as the LogN in residual parameters if use "Complex" parameters, for example set both to be 15.
And different LogN in bootstrapping parameters have different impacts on both the execution time of bootstrapping and the memory consumed. So I guess what you mean by "marginal impact" is that the presicion of bootstrapping is almost the same?

[Pro7ech]

To keep it simple, LogN=16 is necessary to ensure a secure instance of the bootstrapping parameters. If you reduce it, your instance will be insecure.

edit: typo

[JohnJimAir]

"will not be insecure." or "will not be secure." ? A typo?
I am not a native english speaker, such grammar is difficult for me to understand what it exactly mean.

[Pro7ech]

yes, it was a typo