Usage of polynomial evaluation with different degrees

[ProgrammingFlorian]

Hello, I'm currently working on logistic regression for my thesis.
In order to compute the sigmoid function, I'd like to use the polynomial evaluator to approximate the function using the Chebyshev approximation.
According to the tutorial I've implemented it like this:

interval := bignum.Interval{
	Nodes: 3,
	A:     *bignum.NewFloat(-8, params.EncodingPrecision()),
	B:     *bignum.NewFloat(8, params.EncodingPrecision()),
}

sigmoidApprox := bignum.ChebyshevApproximation(func (x complex128) complex128 {
	return 1.0 / (1.0 + cmplx.Exp(-x))
}, interval)
polyEval := polynomial.NewEvaluator(params, ev)

res, err := polyEval.Evaluate(ip, sigmoidApprox, params.DefaultScale())
if err != nil {
	panic(err)
}

I'm having trouble adjusting the parameter Nodes. While the code does execute with the parameter 63, I'm running out of levels during the process. From my understanding, 63 Nodes correspond to a polynomial degree of 6 ((2^6)-1 = 63). I only need a polynomial degree of 2 and 3, which are sufficient for my algorithm and save levels. I've tried setting the parameter to 3 ((2^2)-1) and 7 ((2^3)-1) but I'm getting the runtime error "1 levels < 2 log(d) -> cannot evaluate poly".

I would be glad about help on how to properly use this function.

[lehugueni]

Hi!

Thanks for the question. Could you please provide a full self-contained code snippet that don't behave as you expect?

[ProgrammingFlorian]

Unfortunately I haven't been able to replicate the exact error message in a self-contained snippet, instead the error message changed to "not enough levels" which was more descriptive and probably the root of the issue.

While the code is running now, the results are far off. I'm approximating the sigmoid function, which should only output numbers in the range [0, 1], but the numbers are far larger (e.g. -265233004940829888.000000).

Here is a fully self-contained snippet, comparing my expected and actual output:

package main

import (
	"fmt"
	"github.com/tuneinsight/lattigo/v6/circuits/ckks/polynomial"
	"github.com/tuneinsight/lattigo/v6/core/rlwe"
	"github.com/tuneinsight/lattigo/v6/schemes/ckks"
	"github.com/tuneinsight/lattigo/v6/utils/bignum"
	"math"
	"math/big"
)

func main() {
	// init parameters
	var err error
	var params ckks.Parameters
	if params, err = ckks.NewParametersFromLiteral(
		ckks.ParametersLiteral{
			LogN:            14,                                    // A ring degree of 2^{14}
			LogQ:            []int{55, 45, 45, 45, 45, 45, 45, 45}, // An initial prime of 55 bits and 7 primes of 45 bits
			LogP:            []int{61},                             // The log2 size of the key-switching prime
			LogDefaultScale: 45,                                    // The default log2 of the scaling factor
		}); err != nil {
		panic(err)
	}

	keyGen := rlwe.NewKeyGenerator(params)

	secretKey := keyGen.GenSecretKeyNew()
	publicKey := keyGen.GenPublicKeyNew(secretKey)

	relinearizationKey := keyGen.GenRelinearizationKeyNew(secretKey)
	evaluationKey := rlwe.NewMemEvaluationKeySet(relinearizationKey)

	encoder := ckks.NewEncoder(params)

	encryptor := rlwe.NewEncryptor(params, publicKey)
	decryptor := rlwe.NewDecryptor(params, secretKey)

	evaluator := ckks.NewEvaluator(params, evaluationKey)

	// encrypt example messages
	numbers := []float64{3416, -2381, 4635, 3853, -4505}
	plaintext := ckks.NewPlaintext(params, params.MaxLevel())

	if err := encoder.Encode(numbers, plaintext); err != nil {
		panic(err)
	}

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

	// calculate polynomial evaluation of sigmoid function

	// Polynomial degree should be 1 according to https://eprint.iacr.org/2019/223.pdf (page 2)
	// Nodes: -> 2^1 - 1 = 1
	// For now, we set this parameter to 63 in hopes that the higher accuracy will yield better results
	const nodes = 63
	const K = 8
	interval := bignum.Interval{
		Nodes: nodes,
		A:     *bignum.NewFloat(-K, params.EncodingPrecision()),
		B:     *bignum.NewFloat(K, params.EncodingPrecision()),
	}

	sigmoidApprox := bignum.ChebyshevApproximation(sigmoid, interval)
	polyEval := polynomial.NewEvaluator(params, evaluator)

	resultingCiphertext, err := polyEval.Evaluate(ciphertext, sigmoidApprox, params.DefaultScale())
	if err != nil {
		panic(err)
	}

	// decrypt result
	decrypted := decryptor.DecryptNew(resultingCiphertext)

	result := make([]float64, params.MaxSlots())
	if err := encoder.Decode(decrypted, result); err != nil {
		panic(err)
	}

	// result comparison

	expected := []float64{sigmoidTest(numbers[0]),
		sigmoidTest(numbers[1]),
		sigmoidTest(numbers[2])}

	fmt.Printf("Mult: expected [%f, %f, %f], actual [%f, %f, %f]\n",
		expected[0], expected[0], expected[0],
		result[0], result[1], result[2])
}

func sigmoid(x *big.Float) (y *big.Float) {
	f64 := func(x float64) float64 {
		return 1 / (math.Exp(-x) + 1)
	}

	xF64, _ := x.Float64()
	return new(big.Float).SetPrec(x.Prec()).SetFloat64(f64(xF64))
}

func sigmoidTest(x float64) float64 {
	// clamp x to [-8, 8] = [-K, K]
	x = math.Max(math.Min(8, x), -8)
	return 1.0 / (1.0 + math.Exp(-x))
}

[lehugueni]

The input values should be between [-K, K]. Here your values in numbers are too large. I guess you clamp the values in sigmoidTest but not in sigmoid.
Also, the approximation polynomial is given in the Chebyshev basis, thus you need to perform some kind of rescaling (or change of basis) on your input before evaluating the polynomial.
To do it in an encrypted form you can do:

	if err = evaluator.Mul(ciphertext, scalarmul, ciphertext); err != nil {
		panic(err)
	}

	if err = evaluator.Add(ciphertext, scalaradd, ciphertext); err != nil {
		panic(err)
	}

	if err = evaluator.Rescale(ciphertext, ciphertext); err != nil {
		panic(err)
	}

before the polynomial evaluation. This seems to give correct results on my side (if I change the print to expected[0], expected[1], expected[2]). Hope it helps!