I am new to cryptography and do not have sufficient background knowledge, and I am sorry for any possible vagueness in my question.

I am reading a paper (https://eprint.iacr.org/2019/129.pdf) about homomorphic secret-sharing and is confused by the key generation protocol mentioned (HSS.Gen) in the paper.

The key generation protocol is based on the key generation of a PKE scheme. It generates a key pair $(\mathsf{pk}, \mathbf s)\gets \mathsf{PKE.Gen}(1^{\lambda})$ and a PRF key $K$, then "secret share the secret key" by selecting $\mathbf s_0$ at random, computing $\mathbf s_1=\mathbf s-\mathbf s_0\mod q$, and generating two evaluation keys $\mathsf{ek}_0=(K,\mathbf s_0)$ and $\mathsf{ek}_1=(K,\mathbf s_1)$. The overall output of this procedure is $\mathsf{pk}, \mathsf{ek}_0,$ and $\mathsf{ek}_1$.

In my understanding, the definition of homomorphic secret-sharing is to directly perform a series of computations on the secret shares of data, and the parties will not communicate until shares of the final result are acquired and aggregated. Also, with secure 2-PC computation and private information retrieval being the application shown in the paper, I think it should protect each party's private inputs. Such inputs should be known by other parties in the encrypted form because they might be used in later computation during which there is no more communication.

Due to the above reasoning, it seems natural to conclude that none of the parties should know the complete secret key $\mathbf s$, since it may decrypt others' data otherwise. However, during the execution of the key generation protocol, the secret key is visible in plaintext. So I am wondering if this protocol needs a trusted third party to generate the key or if there are some mechanisms to ensure the original secret key is not exposed to all the parties. Both are not mentioned in the paper.

Please help me find out if there is something I overlooked or if there is something I need to learn in order to understand how this protocol should work with secrecy ensured. Thanks very much!


1 Answer 1


It is not like some of the parties create $s$ and then compute $s_0, s_1$. Usually $s_0, s_1$ is an output of some distributed protocol. We only assume that the output of this protocol is indistinguishable from another protocol which first crate $s$, take random $s_0$, set $s_1=s-s_0$ and sent this keys to corresponding parties.

Here is example of key generation in distributed ElGamal:

Securing Threshold Cryptosystems against Chosen Ciphertext Attack (p. 12)

  • $\begingroup$ Thank you for answering! So is it a common practice to define the key generation procedure of a secret-sharing scheme only in a non-distributed version? I once thought it should be defined in a distributed version because a non-distributed one is not useful and needs further efforts to make it distributed. $\endgroup$ Sep 7, 2023 at 4:00
  • $\begingroup$ Of course we need distributed key generation scheme, because in other case our scheme is useless. For example I read some article dedicated distributed generation of RSA key. (So output is secret share of private key). So it is some nontrivial protocol with some number of rounds of communication. For ElGamal encryption the protocol is much more strighforward. $\endgroup$ Sep 7, 2023 at 6:12
  • $\begingroup$ I added key generation in distributed ElGamal. $\endgroup$ Sep 7, 2023 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.