Evaluation of average of an array with length smaller than params.Slots()

[cutukmirza]

Hello,

I have been trying to do an average of a 1000 number array with CKKS (evaluator.Average). I am using ckks.NewParametersFromLiteral(ckks.PN14QP438) as my parameters, and have logBatch=0, batch=1, and n=1000. I generate the rotation keys with the given arguments and then try to evaluate Average, but I get a "specific rotation has not been generated: 1024". On the other hand if I take n=params.Slots(), which is 8192, then I don't get an error, but my average is calculated as sum(values)/8192, instead of sum(values)/1000.

Here is the code snippet if necessary:

package main

import (
    "fmt"
    "reflect"

    "github.com/tuneinsight/lattigo/v3/ckks"
    "github.com/tuneinsight/lattigo/v3/rlwe"
)

func test() {
    var err error

    // Scheme params are taken directly from the proposed defaults
    params, err := ckks.NewParametersFromLiteral(ckks.PN14QP438)
    if err != nil {
        panic(err)
    }

    encoder := ckks.NewEncoder(params)

    // Keys
    kgen := ckks.NewKeyGenerator(params)
    sk, pk := kgen.GenKeyPair()

    logBatch := 0
    //batch := 1 << logBatch
    batch := 1 << logBatch
    n := 1000 / batch
    fmt.Println(n)
    fmt.Println(1000 * 1001 / 2 / 8192)
    //n(n+1)/2

    rotKey := kgen.GenRotationKeysForRotations(params.RotationsForInnerSumLog(batch, n), false, sk)

    // Relinearization key
    rlk := kgen.GenRelinearizationKey(sk, 2)
    fmt.Println("***", reflect.TypeOf(params), reflect.TypeOf(sk), reflect.TypeOf(pk), reflect.TypeOf(rlk))
    // Encryptor
    encryptor := ckks.NewEncryptor(params, pk)

    // Decryptor
    decryptor := ckks.NewDecryptor(params, sk)

    // Evaluator
    evaluator := ckks.NewEvaluator(params, rlwe.EvaluationKey{Rlk: rlk, Rtks: rotKey})
    start := 0.0

    // Values to encrypt
    data_vector := make([]float64, 0)
    start = 0.0
    for j := 0; j < 1000; j++ {
        start += 1.0
        data_vector = append(data_vector, start)
    }
        p_vector := encoder.EncodeNew(data_vector, params.MaxLevel(), params.DefaultScale(), params.LogSlots())
    c1 := encryptor.EncryptNew(p_vector)
        evaluator.Average(c1, logBatch, c1)

    tmp := encoder.Decode(decryptor.DecryptNew(c1), params.LogSlots())

    valuesTest := make([]float64, len(tmp))
    for i := range tmp {
        valuesTest[i] = real(tmp[i])
    }
    fmt.Println("decrypted ", valuesTest[:3])
    //fmt.Println(params.Slots())
    //fmt.Println(params.LogSlots())
}

func main() {
    test()
}

I am obviously doing something wrong, but I'm not quite sure what it is. Could you point me in the right direction?

Thank you!

[Pro7ech]

Hello @cutukmirza,

You are not doing something wrong. The Average method can only be evaluator on a power of two array. This is why it is parameterized as Average(ctIn *Ciphertext, <logBatchSize> int, ctOut *Ciphertext) and not with <batchSize>.

The reason is how it works internally (it uses the trace function, which allows to pre-scale the values by the modular inverse of 2^logBatchSize = n which removes the need afterward to scale the values by 1/n).

If you want to do an average on a non-power of two array you can use InnerSumLog with batchSize = 1 and n the size of your array, but you will have to divide your values by 1/n or to multiply ciphertext.Scale by 1/n.

I hope this help.

[cutukmirza]

Hello @Pro7ech,

Thank you very much for your quick reply and for your help. I managed to do it using InnerSumLog and divide.

Cheers, Mirza

[cutukmirza]

Hello,

A side question to this, is there a (relatively) simple way to edit innerSumLog to have the inner sum value fill the array (like for the average), instead of filling just left-most value, which wouldn't compromise the performance significantly?

Thank you!

[Pro7ech]

Internally, Average calls InnerSumLog, so you shouldn't have to modify anything, just call InnerSumLog with the same input parameters.

If you want to fill an array that is empty except for a small vector, you can call ReplicateLog.

[macknight]

thanks to this issue, I found the solution to calculating average of a vector sized power of 2.

[macknight]

If you want to do an average on a non-power of two array you can use InnerSumLog with batchSize = 1 and n the size of your array, but you will have to divide your values by 1/n or to multiply ciphertext.Scale by 1/n.

If you want to do an average on a non-power of two array you can use InnerSumLog with batchSize = 1 and n the size of your array, but you will have to divide your values by 1/n or to multiply ciphertext.Scale by n, not 1/n. right?

BR