# Secrete message sharing using N private keys

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

Let,

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

-
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

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.

Setup:

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

-
I may end up using this. Thank you. – Komo2020 Feb 18 '14 at 21:55