Equality circuit in BGV/BFV results in wrong plaintext

[kragall]

Hi there,

I tried to implement a comparison for integers using the BGV/BFV scheme. The equality circuit seems to work, but once I add two "comparisons" together, an overflow seems to happen and I can't get rid of it by Rescaling. Here's the code:

package main

import (
	"fmt"

	"github.com/tuneinsight/lattigo/v5/core/rlwe"
	"github.com/tuneinsight/lattigo/v5/he/heint"
)

func eq() {
	params, err := heint.NewParametersFromLiteral(heint.ParametersLiteral{
		LogN:             15,
		LogQ:             []int{60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60},
		LogP:             []int{60, 60, 60},
		PlaintextModulus: 65537,
	})
	if err != nil {
		panic(err)
	}

	encoder := heint.NewEncoder(params)
	kgen := rlwe.NewKeyGenerator(params)
	Sk, _ := kgen.GenKeyPairNew()

	decryptor := rlwe.NewDecryptor(params, Sk)
	encryptorSk := rlwe.NewEncryptor(params, Sk)
	rlk := kgen.GenRelinearizationKeyNew(Sk)
	evk := rlwe.NewMemEvaluationKeySet(rlk)
	evaluator := heint.NewEvaluator(params, evk)
	
	input := make([][]uint64,0)
        input = append(input, []uint64{1,1,1,1,1,1,1,1,1})
	input = append(input, []uint64{1,2,3,4,5,6,7,8,9})
	input = append(input, []uint64{5,5,5,5,5,5,5,5,5})
	input = append(input, []uint64{2,3,4,5,6,7,8,9,1})
	input = append(input, []uint64{4,4,4,4,4,4,4,4,4})
	
	pts := make([]*rlwe.Plaintext, 0)
	cts := make([]*rlwe.Ciphertext, 0)

	for _, v := range input{
		pt := heint.NewPlaintext(params, params.MaxLevel())
		if err := encoder.Encode(v, pt); err != nil {
			panic(err)
		}
		pts = append(pts, pt)
	}

	for _, v := range pts{
		ct, err := encryptorSk.EncryptNew(v)
		if err != nil {
			panic(err)
		}
		cts = append(cts, ct)
	}

	diffs := make([]*rlwe.Ciphertext, 0)
	diffCt, err := evaluator.SubNew(cts[1], cts[2])
	if err != nil {
		panic(err)
	}
	diffs = append(diffs, diffCt)
	diffCt, err = evaluator.SubNew(cts[3], cts[4])
	if err != nil {
		panic(err)
	}
	diffs = append(diffs, diffCt)

	cmps := make([]*rlwe.Ciphertext, 0)
	for _, v := range diffs{
		difference := make([]uint64, params.MaxSlots())
		if err := encoder.Decode(decryptor.DecryptNew(v), difference); err != nil {
			panic(err)
		}
		fmt.Println("diff = ", difference[0:9])
		
		powers := heint.NewPowerBasis(v)	
		powers.GenPower(65536, false, evaluator)
		cmp := powers.Value[65536]
		
		neg, err := evaluator.SubNew(cts[0], cmp)
		if err != nil {
			panic(err)
		}

		cmps = append(cmps, neg)

		result := make([]uint64, params.MaxSlots())
		if err := encoder.Decode(decryptor.DecryptNew(neg), result); err != nil {
			panic(err)
		} 

		fmt.Println("eq = ", result[0:9])
	}

	add, err := evaluator.AddNew(cmps[0], cmps[1])
	if err != nil {
		panic(err)
	} 
	result := make([]uint64, params.MaxSlots())
	if err := encoder.Decode(decryptor.DecryptNew(add), result); err != nil {
		panic(err)
	} 

	fmt.Println("addition = ", result[0:9])
}

func main() {

	eq()
}

The output is:

diff =  [65533 65534 65535 65536 0 1 2 3 4]
eq =  [0 0 0 0 1 0 0 0 0]
diff =  [65535 65536 0 1 2 3 4 5 65534]
eq =  [0 0 1 0 0 0 0 0 0]
addition =  [0 0 134 0 134 0 0 0 0]

I would expect that addition results in [0 0 1 0 1 0 0 0 0]. Could you point out the error in my code?

[Pro7ech]

Hi @kragall there is indeed a bug, the method eval.Add doesn't set the scale of the output ciphertext correctly. I've opened an issue: #467

In the meantime you can correct it by manually setting the metadata:
*add.MetaData = *cmps[0].MetaData

[yusufozturk]

@Pro7ech Is there an example of how to rewrite this example in v6? I see that v6 structure is changed. I am looking for an integer comparison in lattigo.

[lehugueni]

You can just replace all the heint with bgv, the evaluator generation with evaluator := bgv.NewEvaluator(params, evk, true) and the powers variable can be set to powers := polynomial.NewPowerBasis(v, bignum.Monomial) (and modify the imports accordingly).

[kragall]

Oh, so it was a bug! Thanks for the workaround!