Threshold Fully Homomorphic Cryptosystems

Question

recently, Craig Gentry published the first public key encryption scheme (over plaintext space {0,1}) which is fully homomorphic, meaning that one can efficiently and compactly evaluate AND and XOR on encrypted plaintexts without knowledge of the secret decryption key.

I am wondering if there is any obvious way to turn this public key cryptosystem into a threshold public key cryptosystem such that everybody can encrypt, AND and XOR, but decryption is only possible if some (all) people sharing the key team up.

I would be interested in any ideas about that subject.

Thanks in advance

fw

Answer 1

A new paper by Steven Myers, Mona Sergi, and Abhi Shelat on eprint, "Threshold Fully Homomorphic Encryption and Secure Computation", claims a threshold fully homomorphic encryption scheme.

From their abstract:

...

Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$ and computation that is polynomial in $|f|$. This paper addresses the major drawback's of Gentry's approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim's compiler.

To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes.

...

Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$.

Answer 2

I don't know the specifics of Gentry's scheme, but all other threshold cryptosystems require two homomorphisms (the third is implied) relating to the public and secret keys:

1. ${\sf KG}(sk1)\otimes{\sf KG}(sk2)={\sf KG}(sk1\oplus sk2)$
2. $c={\sf Enc}_{pk1}({\sf Enc}_{pk2}(m,r))={\sf Enc}_{pk1\otimes pk2}(m,r)$
3. $m={\sf Dec}_{sk1}({\sf Dec}_{sk2}(c))={\sf Dec}_{sk1\oplus sk2}(c)$

(${\sf KG}$ is a function that given the secret key, returns the public key: $pk={\sf KG}(sk)$.)

If these conditions hold, for some operations $\oplus$ and $\otimes$, it is trivally possible to make distributed (n-out-of-n) decryption, and it may be possible for threshold (m-out-of-n) if the operation $\oplus$ is, for example, sufficient for interpolating a polynomial.

For example, in threshold Elgamal, $\oplus$ is addition and this allows interpolation.

Even though no one has answered the original question, perhaps someone can answer these questions: (1) Does Gentry's FHE fit the blueprint above (in terms of ${\sf KG}$, ${\sf Enc}$, ${\sf Dec}$). (2) Do such homomorphisms exist between the public and secret keys exist? (3) If so, what are the operations?

Also, I am not saying these conditions are necessary to have a threshold cryptosystem. The lack of such a homomorphism does not imply (to my knowledge) that threshold decryption is impossible.