Permutation of ciphertext slots in CKKS

Library Questions
1

Hello, I would like to apply a permutation to the slots of a CKKS ciphertext. For this, I believe that I just need to multiply the ciphertext by the corresponding permutation matrix.

I’ve found two past topics discussing this: Slot-shuffling homomorphically and Is there a built in method to perform vector - matrix multiplication?.

I’ve tried to use EvalLinearTransform to perform the multiplication by using the class FHECKKSRNS, but I run into errors which I’m unable to debug at the moment.

Any advice on how to use EvalLinearTransform independently of the bootstrapping procedure? A working example would be fantastic. I’m also wondering if the matrix-vector multiplication that was discussed in one of the aforementioned topics has been exposed to the end user already, I was not able to find it either.

Thank you!

2

What is the error and can you share some minimal code to replicate it?

3

Here is the code:

std::vector<uint32_t> levelBudget = {2, 2};

#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDMANUAL;
    usint dcrtBits               = 78;
    usint firstMod               = 89; /*firstMod*/
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60; /*firstMod*/
#endif

    usint depth = levelsRemaining + FHECKKSRNS::GetBootstrapDepth(9, levelBudget, secretKeyDist);

    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetMultiplicativeDepth(depth);
    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetRingDim(n);
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetNumLargeDigits(3);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetKeySwitchTechnique(HYBRID);
    parameters.SetFirstModSize(firstMod);

    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);

    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);
    
    auto keyPair = cc->KeyGen();

    cc->EvalMultKeyGen(keyPair.secretKey);

    std::vector<std::complex<double>> input({0.111111, 0.222222, 0.333333, 0.444444});

    Plaintext plaintext = cc->MakeCKKSPackedPlaintext(input, 1, depth - 1, nullptr, slots);
    auto ciphertext = cc->Encrypt(keyPair.publicKey, plaintext);

    FHECKKSRNS ckksrns;

    std::vector<uint32_t> dim = {0, 0};

    std::vector<std::vector<std::complex<double>>> matrix = genIdentityPlaintext(slots);

   
    cc->EvalBootstrapSetup(levelBudget, dim, slots, 0);
    cc->EvalBootstrapKeyGen(keyPair.secretKey,slots);

    ckksrns.EvalBootstrapSetup(*cc, levelBudget, dim, slots, 0);

    size_t encodedLength = input.size();
    double scale = 1;
    uint32_t L = 0;

    auto matrix_pre = ckksrns.EvalLinearTransformPrecompute(*cc, matrix, scale, L);
    auto output = ckksrns.EvalLinearTransform(matrix_pre, ciphertext);

    Plaintext result;
    cc->Decrypt(keyPair.secretKey, output, &result);
    result->SetLength(encodedLength);
    std::cout << "After permutation = " << result;

It is just a modification of the function BootstrapExampleClean that can be found here.
I’m using the paramters (SPARSE_TERNARY, 1 << 12, 4, 10) as a test.

The matrix that I’m using as a permutation is simply the identity for the moment.

The error is this:

terminate called after throwing an instance of ‘lbcrypto::openfhe_error’
what(): openfhe-development/src/pke/lib/scheme/ckksrns/ckksrns-leveledshe.cpp:421 EvalKey for index [5] is not found.
Aborted

4

I managed to make it work after changing a few parameters, here is the code just in case it is useful for anybody:

std::vector<uint32_t> dim1 = {0, 0};
    std::vector<uint32_t> levelBudget = {1, 1};


#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDMANUAL;
    usint dcrtBits               = 78;
    usint firstMod               = 89; /*firstMod*/
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60; /*firstMod*/
#endif

    // computes how many levels are needed for
    usint depth = levelsRemaining + FHECKKSRNS::GetBootstrapDepth(9, levelBudget, secretKeyDist);

    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetMultiplicativeDepth(depth);
    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetRingDim(n);
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetNumLargeDigits(3);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetKeySwitchTechnique(HYBRID);
    parameters.SetFirstModSize(firstMod);

    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);

    // Turn on features
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);

    const std::shared_ptr<CryptoParametersCKKSRNS> cryptoParams =
        std::dynamic_pointer_cast<CryptoParametersCKKSRNS>(cc->GetCryptoParameters());

    //this determines the size of the permutation matrix. In this example, we can go up to 64.
    auto size_of_permutation = 8;
    
    cc->EvalBootstrapSetup(levelBudget, dim1, size_of_permutation);

    auto keyPair = cc->KeyGen();
    cc->EvalMultKeyGen(keyPair.secretKey);

    cc->EvalBootstrapKeyGen(keyPair.secretKey, size_of_permutation);
    std::vector<std::complex<double>> a(
        {0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888,
        0.111111, 0.222222, 0.333333, 0.444444, 0.555555, 0.666666, 0.777777, 0.888888});

    size_t encodedLength = a.size();

    std::vector<std::complex<double>> input(Fill(a, size_of_permutation));
    Plaintext plaintext = cc->MakeCKKSPackedPlaintext(input, 1, 0, nullptr, size_of_permutation);
    auto ciphertext     = cc->Encrypt(keyPair.publicKey, plaintext);

    //change this for any function that produces a permutation matrix
    std::vector<std::vector<std::complex<double>>> matrix = genIdentityPlaintext(size_of_permutation);

    std::cout << "permutation matrix" << matrix << std::endl;

    FHECKKSRNS ckksrns;

    ckksrns.EvalBootstrapSetup(*cc,levelBudget,dim1,size_of_permutation,0);

    double scale = 1;
    uint32_t L = depth;

    Plaintext result;

    auto matrix_pre = ckksrns.EvalLinearTransformPrecompute(*cc, matrix, scale, L);
    auto output = ckksrns.EvalLinearTransform(matrix_pre, ciphertext);

    cc->Decrypt(keyPair.secretKey, ciphertext, &result);
    result->SetLength(encodedLength);
    std::cout << "Before permutation = " << result;
    
    cc->Decrypt(keyPair.secretKey, output, &result);
    result->SetLength(encodedLength);
    std::cout << "After permutation = " << result;