Bug/Regression [BGV]: Wrong result from innerSum for params.N() elements

[VReyesUOL]

What version of Lattigo are you using?

v6.1.0

Does this issue persist with the latest release?

Yes

What were you trying to do?

Let N = params.N().
Create a vector of length N, populate with random 1s and 0s.
Count the number of 1s by computing the inner sum of the encrypted vector with batch_size 1 and group size N

What were you expecting to happen?

The result to match the number of 1s in the clear text bit vector.

What actually happened?

The computed result was constantly slightly off from the expected result.
The answer was correct when

• Only filling the first N/2 slots of the plaintext and calling inner sum with group size N/2
  OR
• Call to innerSum with group size N/2 and addition with RotateRowsNew

Variant 1:
clear text vector has length N with 1s all over.
inner sum is called with batch_size 1 and group size N
-> Incorrect result

Variant 2:
clear text vector has length N with 1s all over.
inner sum is called with batch_size 1 and group size N >> 1
Addition with RotateRowsNew
-> Correct result

Variant 3:
clear text vector has length N >> 1 with 1s all over.
inner sum is called with batch_size 1 and group size N >> 1
-> Correct result

"I think the library should return an error when asking innersum with N or handle this case internaly in the BGV side (because the backend of innersum is in the RLWE package, which is agnostic of the scheme and packing, hence why it doesn't return an error). The BGV evaluator should re-implement this method by calling the RLWE innersum but then add this last step if n = N." -Jean-Philippe Bossuat

Reproducibility

Minimal example with variant 1.
Variant 2 is achieved by removing comments around RotateRowsNew
Variant 3 is achieved by replacing all 'params.N()' by 'params.N() >> 1'

package main

import (
	"fmt"
	"github.com/tuneinsight/lattigo/v6/core/rlwe"
	"github.com/tuneinsight/lattigo/v6/schemes/bgv"
	"math/rand/v2"
)

func innerSumTest() {
	// Setup copied from examples
	var err error
	var params bgv.Parameters

	if params, err = bgv.NewParametersFromLiteral(bgv.ExampleParameters128BitLogN14LogQP438); err != nil {
		panic(err)
	}

	kgen := rlwe.NewKeyGenerator(params)

	sk := kgen.GenSecretKeyNew()
	ecd := bgv.NewEncoder(params)

	enc := rlwe.NewEncryptor(params, sk)
	dec := rlwe.NewDecryptor(params, sk)

	decrypt := func(ct *rlwe.Ciphertext) []uint64 {
		pt := bgv.NewPlaintext(params, params.MaxLevel())
		dec.Decrypt(ct, pt)

		decoded := make([]uint64, params.N())
		if err = ecd.Decode(pt, decoded); err != nil {
			panic(err)
		}
		return decoded
	}

	rlk := kgen.GenRelinearizationKeyNew(sk)
	gal := params.GaloisElementsForInnerSum(1, params.N())

	evk := rlwe.NewMemEvaluationKeySet(rlk)

	galk := kgen.GenGaloisKeysNew(gal, sk)

	eval := bgv.NewEvaluator(params, evk)
	evalks := rlwe.NewMemEvaluationKeySet(rlk, galk...)
	eval = eval.WithKey(evalks)

	//Init inputs
	values1 := make([]uint64, params.N())

	sum := 0
	for i := range values1 {
		if rand.Int()%3 == 0 {
			values1[i] = 1
			sum += 1
		}
	}
	fmt.Printf("Input: %v...\n", values1[:100])

	//Encode + encrypt
	pt1 := bgv.NewPlaintext(params, params.MaxLevel())

	if err = ecd.Encode(values1, pt1); err != nil {
		panic(err)
	}

	var ct *rlwe.Ciphertext
	if ct, err = enc.EncryptNew(pt1); err != nil {
		panic(err)
	}

	//Eval inner sum
	tmp := bgv.NewCiphertext(params, 1, params.MaxLevel())
	if err = eval.InnerSum(ct, 1, params.N(), tmp); err != nil {
		panic(err)
	}
/*
	var tmpRot *rlwe.Ciphertext
	if tmpRot, err = eval.RotateRowsNew(tmp); err != nil {
		panic(err)
	}

	if err = eval.Add(tmp, tmpRot, tmp); err != nil {
		panic(err)
	}
*/

	//Verify output
	decRes := decrypt(tmp)
	fmt.Printf("Expected: %d\n", sum)
	fmt.Printf("Computed: %d\n", decRes[0])
}

Edited: RotateRowsNew does compute the correct result

[lehugueni]

Thanks for the bug report. Fixed in #513.