Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for an encryption scheme that could possibly meet the following requirements.


$X = plaintext$
$M = (pub, priv)$, where $priv == (Ky + Kz)$

Given func [genKeys, partDec, fullDec, enc] perform,

$genKeys() \rightarrow (Ky, Kz)$
$enc(X, Mpub) \rightarrow C$

$partDec(C, Ky) \rightarrow C'$
$fullDec(C', Kx) \rightarrow X$

Now this is just my view of how the process should be done. I'm familiar with the aspects of symmetric vs asymmetric encryption. However, I have never encountered such requirements before.

To sum it all up:

I would like to share some encrypted message $C$ using $Mpub$. Generate dynamic keys $Ky$ and $Kz$.

$Ky_1+C$ can only be decrypted using $Kx_1$ and not any of the the other $Kx_n$ keys. This may be similar to one of the secret sharing algorithms or key regression scheme.

If this is not possible, then something similar should be sufficient.

share|improve this question
Did you mean $Kz$ instead of $Kx$ in definition of $fullDec$? Anyway, your notation is quite unusual, because plaintexts are usually denoted as $m$, and $x,X,y,Y,k_{pub},k_{priv}$ etc. are used for keys (e.g. lowercase letter for the private key, uppercase letter for the public key). Otherwise I don't know what you mean with your plus-signs, and where your $n$ keys come from all of a sudden. Maybe you can clarify your scenario? – tylo Feb 18 '14 at 19:47
I think by + he means concatenate? If so, $||$ would be more standard notation – figlesquidge Feb 18 '14 at 20:13
It is also not clear where $\:pub\:$ comes from. $\;\;\;$ – Ricky Demer Feb 18 '14 at 20:13
Sorry about the improper use of notations. I should've simply stated the reason behind this requirement. – Komo2020 Feb 18 '14 at 21:34
There is a message that is encrypted using a public key. I would like to share this message with a group of users without having to decrypt/re-encrypt message for every single user. There are some cases where a user's privileges to read the messages are revoked. The user may still be able to receive the messages, but can not decrypt them. So it really narrows down to code send(encr_msg, usr_lst){for(usr->usr_lst) some_func(enc_msg, usr.pub_key)[...]};//client-> dec_msg(){//dec msg}; – Komo2020 Feb 18 '14 at 21:54
up vote 1 down vote accepted

I am not sure if I understand your requirement correctly, but from the first part of your description I think you want the following (I skipped the second part since I do not understand the meaning of "$+$") :

Set up a public key $pk$ which can be used to encrypt a message $m$ and you want to split the corresponding private key $sk$ into two shares $sk_1$ and $sk_2$ such that given a ciphertext $c$ encrypting a message $m$ under $pk$ can first be decrypted using $sk_1$ to some intermediate ciphertext $c'$ and then using $sk_2$ be decrypted to $m$. The goal is that decrypting with $sk_1$ reveals nothing about the message but if decrypted with $sk_1$ first and then with $sk_2$ will reveal the message to the entity holding $sk_2$.

Here is an example using ElGamal encryption.


Let $p$ be a safe prime and $g$ be a generator of an order $q$ subgroup of $Z_p^*$. Let the public key $y=g^x$ for some random $x\in Z_q^*$ and $x$ be the private key.

Now the partial private keys are $x_1$ and $x_2$ such that $x\equiv x_1+x_2 \pmod q$ and give $x_1$ to $A$ and $x_2$ to $B$.

Standard Encryption:

To encrypt a message $m\in Z_p^*$ just do it as with standard ElGamal, i.e., compute the ciphertext $c$ as $c=(c_1,c_2)=(g^k,m\cdot y^k)$ for $k$ random in $Z_q^*$.

Standard Decryption

You can decrypt as you do it with ElGamal when you want to directly decrypt using $x$, i.e., compute $m$ as $c_2\cdot (c_1^x)^{-1}=m\cdot c_1^x\cdot (c_1^x)^{-1}=m$. Note that in the equation I write $y^k$ as $c_1^x$ as $c_1^x=(g^k)^x=(g^x)^k=y^k$.

Sequential Decryption

Now in order to sequentially decrypt a ciphertext $c=(g^k,m\cdot y^k)$ encrypted under public key $y$ by first $A$ and then $B$ (one can also switch to first $B$ and then $A$) one proceeds as follows:

$A$ is given a ciphertext $c=(c_1,c_2)=(g^k,m\cdot y^k)$ and partially decrypts it to $c'$ by computing $c'=(c_1,c_2')$ where $c_2'= c_2\cdot (c_1^{x_1})^{-1}$.

Then $A$ gives the "partially decrypted" ciphertext $c'=(c_1,c_2')$ to $B$. $B$ then decrypts $c'$ to $m$ by computing $m=c_2'\cdot (c_1^{x_2})^{-1}$.

To see that this is correct observe that

$$c_2'\cdot (c_1^{x_2})^{-1} = c_2\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1} = m\cdot c_1^{x_1}\cdot c_1^{x_2}\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1}=m.$$

Clearly you can generalise this to arbitrary $n>2$ additive shares of the private key $x$ such that only the $n$'th user in the chain of partial decryption learns the message $m$.

share|improve this answer
I may end up using this. Thank you. – Komo2020 Feb 18 '14 at 21:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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