2
$\begingroup$

Let say I have n computers, with some t-threshold encryption scheme. I want to have n public shares (known to every participant) such that any t of them generates a pair: $g^k, E(k^{-1})$ that is unique, such that $E(x)$ is the encrypted value of x. and $k^{-1}$ is computed in some cyclic group of power $q$. Also no member can know the value of $k$ or $k^{-1}$.

I have a solution that requires communication:

each share is $(g^{k_i}, E(k_i), E(p_i), E(c_i))$. The $k_i$, $p_i$ and $c_i$ are private, the shares are public.

When a group $Is$ of size $t$ wants to generate $g^k$ and $E(k^{-1})$ they compute

$g^k = \prod_{i\in Is}g^{k_i}$, $E(k) = \sum_{i\in Is}E(k_i)$, $E(p) = \sum_{i\in Is}E(p_i)$, $E(c) = \sum_{i\in Is}E(c_i)$

$E(k)*E(p) + q*E(c)= E(kp+qc)$ So we decrypt that and each party receives $kp+qc$. Remember, $q$ is the power of the group and public. So we can have kp by computing $kp = (kp+qc) \space mod \space q$. After that, we can compute $E(k^{-1})=E({(kp)}^{-1}*p)={(kp)}^{-1}*E(p)$.

To use this, we require an homomorphic encryption with level-1 multiplication. Is there anyway I could do this without communication? Is there any encryption scheme that support that properties?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.