Multi party Relin key generation

[shuangyichen]

I am using SEAL to implement multi party Relin key following the following protocol in [1]:

I wonder if I can use the same decomposition basis w that SEAL generated in uint64_t factor = barrett_reduce_64(key_modulus.back().value(), get<1>(I)); to compute sw (s_iw in the protocol). s is provided by modifying generate_kswitch_keys(secret_key + 1, count, static_cast<KSwitchKeys &>(relin_keys), save_seed); to generate_kswitch_keys(secret_key, count, static_cast<KSwitchKeys &>(relin_keys), save_seed);

Reference: [1] Mouchet C, Troncoso-Pastoriza J, Bossuat J P, et al. Multiparty homomorphic encryption from ring-learning-with-errors[J]. Cryptology ePrint Archive, 2020.

[WeiDaiWD]

You cannot use generate_kswitch_keys function to implement that algorithm. Fundamentally, generate_kswitch_keys encrypts a new secret key located at secret_key + 1 with the old secret key located at secret_key, where all randomness are generated during the encryption. What the algorithm describes requires a as an input that cannot be fed into generate_kswitch_keys. Also the algorithm is more complicated than Microsoft SEAL's relinearization key generation. You might want to ask the authors whether they know of any implementation based on Microsoft SEAL.

[shuangyichen]

@WeiDaiWD Thanks for the information, I modified code as the protocol described (given common random polynomial a, designing a function in rlwe.cpp to output $-u_i a+ e_{0,i}, s_i a +e_{1,i}$) ` SEAL_ITERATE(iter(new_key, key_modulus, destination, size_t(0)), decomp_mod_count, [&](auto I) {

        SEAL_ALLOCATE_GET_COEFF_ITER(temp, coeff_count, pool_);

        encrypt_zero_symmetric_crp_round_one(secret_key_, context_, u_, key_context_data.parms_id(), true, save_seed, get<2>(I).data());

        uint64_t factor = barrett_reduce_64(key_modulus.back().value(), get<1>(I));

        multiply_poly_scalar_coeffmod(get<0>(I), coeff_count, factor, get<1>(I), temp);

        CoeffIter destination_iter = (*iter(get<2>(I).data()))[get<3>(I)];

        add_poly_coeffmod(destination_iter, temp, coeff_count, get<1>(I), destination_iter);
    });`

Function encrypt_zero_symmetric_crp_round_one outputs $-u_i a+ e_{0,i}, s_i a +e_{1,i}$. My question is that using factor generated by uint64_t factor = barrett_reduce_64(key_modulus.back().value(), get<1>(I)); and old secret key generate_kswitch_keys(secret_key, count, static_cast<KSwitchKeys &>(relin_keys), save_seed); can I compute the correct $s_i w$ then compute $-u_i a+ s_i w + e_{0,i}, s_i a +e_{1,i}$?

Thank you!

[WeiDaiWD]

I see. Then it is just about the value of factor. The decomposition basis used in Microsoft SEAL is described in this paper in section B.2.1. This basis equals to 1 modulo get<1>(I) and therefore disappears from the formula that calculates factor. Microsoft SEAL adopts a special prime for noise reduction, described in section B.1.2, which is key_modulus.back().value(). If you only want to have a new basis w, you should choose uint64_t factor = barrett_reduce_64(w[j], get<1>(I)), where j iterates all elements in the basis w. If you further want to use the same noise reduction adopted by Microsoft SEA, you should have key_modulus.back().value() multiplied to factor; you need to modify the algorithm to make it correct.

[shuangyichen]

Thank you so much. I have completed the algorithm following your suggestion and successfully generated the multiparty version relin key.