About key combination in Threshold FHE

Library Questions
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