# Threshold Fully Homomorphic Cryptosystems

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.

fw

• This is more of a curiosity and does not apply directly to your question. Interestingly since the scheme is fully homomorphic a party can homomorphically and recursively create public-private-key pairs. – Ross Snider Feb 12 '11 at 5:49
• Closer to answering your question, but still not enough to post as an answer: FHE is entirely new - there are only two proposed schemes (both by Gentry). To my knowledge no work has been published on Threshold FHE. There may, however, be work that has been done on partially homomorphic systems (like Paillier, Goldwasser, etc). I would start looking there to see if results can be easily 'ported' to FHE. – Ross Snider Feb 12 '11 at 5:53

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$.

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.