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?


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.