About key combination in Threshold FHE

Library Questions
1

I’m trying to make an application where n participants encrypt n numbers, add them and multiply by another encrypted number (given by one of the n participants).

I was following the threshold-fhe.cpp in the examples and didn’t understand the steps in the key combinations (for example, to generate evalMultFinal).

What is the purpose of these keys (not present in the addition example)? How to generate them in my case? How to generate them in a “generic” case?

2

Hi @trandus

The evalMultFinal is the evaluation (or relinearization) key, that is an “encryption” of s^2, where s is the secret key. I guess the variables evalMultAAB, evalMultBAB in the example are shares of such key. Those shares are aggregated into evalMultFinal to create the actual evaluation key.

I wrote down the evaluation key generation for three participants P0, P1, P2, with the hope it can help you understanding it a bit better:

// Shares of encryption of s
// P0 share: (a, s_0 * (1 - a) + e)
auto evalMultKey0 = cc->KeySwitchGen(s[0], s[0]);
// P1 share: (a, s_1 * (1 - a) + e)
auto evalMultKey1 = cc->MultiKeySwitchGen(s[1], s[1], evalMultKey0);
// P2 share: (a, s_2 * (1 - a) + e)
auto evalMultKey2 = cc->MultiKeySwitchGen(s[2], s[2], evalMultKey1);

// Joint encryption of s
// (a, s (1 - a) + e)
auto evalMult012 = cc->MultiAddEvalKeys(evalMultKey0, evalMultKey1, pk->GetKeyTag());
evalMult012 = cc->MultiAddEvalKeys(evalMult012, evalMultKey2, pk->GetKeyTag());

// Shares of encryption of s^2
// P0 share: (s_0 * a + e, s_0 * s * (1 - a) + e)
auto evalMult0012 = cc->MultiMultEvalKey(s[0], evalMult012, pk->GetKeyTag());
// P1 share: (s_1 * a + e, s_1 * s * (1 - a) + e)
auto evalMult1012 = cc->MultiMultEvalKey(s[1], evalMult012, pk->GetKeyTag());
// P2 share: (s_2 * a + e, s_2 * s * (1 - a) + e)
auto evalMult2012 = cc->MultiMultEvalKey(s[2], evalMult012, pk->GetKeyTag());

// Joint encryption of s^2
// (s * a + e, s^2 * (1 - a) + e)
auto evalMultFinal = cc->MultiAddEvalMultKeys(evalMult0012, evalMult1012, evalMult012->GetKeyTag());
evalMultFinal = cc->MultiAddEvalMultKeys(evalMultFinal, evalMult2012, evalMult012->GetKeyTag());

On my repository you can find an example for Threshold BFV with an arbitrary number of participants: openfhe-ml/threshold_bootstrap_BFV.cpp at main · FedericoMazzone/openfhe-ml · GitHub

In particular, at line 437, the method multipartyEvalMultKeyGen shows you how to generalize the generation of the evaluation key to an arbitrary number of participants.

3 Likes
3

Thank You a lot. I’ll check it out