Is such a crypto-system available?

$E(k_1, pt) = c_1, E(k_2, c_1) = c_2, D(k_{new}, c_2) = pt$, where $k_{new} = f(k_1, k_2).$ Sharing $k_{new}$ and $k_2$ should reveal no information about $k_1$.

Clarifications:

1. Being able to decrypt the ciphertext $c_2$ knowing only $k_{new}$ is the first desired property of the system
2. One cannot derive $k_1$ knowing both $k_{new}$ and $k_2$.
3. One cannot easily derive $k_1$ knowing other pairs $k_2'$ and $k_{new}'$. See @poncho's comments.

$D(k_{new}, c_2) = pt$ or $E(k_{new}, c_2) = pt$ doesn't matter as long as you recover the plaintext.

Real world example to clarify things even more:

1. Alice has a very large database which it chooses to store at Eve's site. Because Alice doesn't want Eve to read the data, nor doesn't she know in advance which data will be shared with whom, she encrypts all the records with a single key ($k_1$).
2. Now Bob requests access to some specific information. Bob and Alice know each other so Alice gives him access to that subset. However Alice wants to do that efficiently. Also Alice doesn't want Bob to be able to read anything else except the shared subset. Therefore she cannot: a) Decrypt the shared subset at Eve's site and then re-encrypt with a different key (this would expose all the database contents to Eve), b) Retrieve the data from Eve, decrypt, re-encrypt and store back data at Eve's site - this implies a round-trip delay which is prohibitively expensive.

Thus Alice needs a cryptosystem which would allow re-encrypting the data directly at Eve's site, however Eve shouldn't be able to read any plain text (nor the one shared with Bob, nor the rest of the database records). Sharing the decryption key ($k_{new}$) is done through a direct channel between Alice and Bob (e.g. using Diffie-Hellman).

The "cryptosystem" stated in the question is just a way I saw that happening. Note that $k_1$ shouldn't become known to Bob (e.g. if Bob colludes with Eve or other people with whom Alice shares (possibly different sets of) data).

• Knowledge of $k_{new}$ and $k_2$ will allow the decryption of any plaintext encrypted by $k_1$; what further information about $k_1$ do you want to be certain isn't revealed? – poncho Feb 5 '13 at 15:35
• The value of k1 – Eugen Feb 5 '13 at 20:28
• Typically, keys don't have any intrinsic value; the only reason we would prefer that people don't learn them is because of the ability that those keys would confer (for example, being able to decrypt traffic). Revealing knew and k2 allows people to decrypt; what further ability would you prefer people not to have? – poncho Feb 5 '13 at 20:33
• @jug Searching for "DES is not a group" I gradually found proxy re-encryption which seems like something I am looking for. – Eugen Feb 6 '13 at 9:26
• It doesn't matter for me as long as it satisfies the properties specified in the question. The originator of the data has key k1, Alice has key k_new. Even if Alice finds k2 or any other pairs (k2', k_new') she shouldn't be able to compute k1. – Eugen Feb 6 '13 at 12:13

2 Answers

This can be done with RSA where k1 and k2 are encryption keys and f is multiplication modulo the totient of the public modulus. The last property, that knowledge of other pairs $k_2'$ and $k_{new}'$ does not reveal $k_1$ is satisfied by using a different modulus for each pair generated.

• You mean that f is the inverse of the multiplication of k1 and k2. In any case, this has a subtle problem; if someone learns k2, f(k1, k2), k3, f(k1, k3), they can deduce k1. Does this matter? Well, we can't tell from the question. – poncho Feb 5 '13 at 16:12
• Doesn't work. 1) k_new would be an encryption key, not a decryption key 2) f is invertable. So you can calculate k1 = k_new/k2. – CodesInChaos Feb 5 '13 at 16:13
• @CodesInChaos 1)No. My definition of f is correct because the post specifies D(k_new,c2)=pt not E(k_new,c2)=pt. Presumably the Decryption function magically obtains the decryption exponent from k_new! 2)Give me an example of inverting f which is not equivalent to factoring the modulus and hence breaking RSA. – Barack Obama Feb 5 '13 at 16:20
• @poncho I guess I could have specified that D=E and then f is the inverse as you said. – Barack Obama Feb 5 '13 at 16:25
• Checking my understanding of the suggested solution: $pt^{k_1} = c_1, c_1^{k_2} = c_2, k_{new} = (k_1 * k_2)^{-1} mod(\phi(N))$. $pt = c_2^{k_{new}} = pt^{k_1 * k_2 *(k_1 * k_2)^{-1}}$ Is that right? – Eugen Feb 5 '13 at 21:02

Actually, I believe that there is a solution, but it follows a different strategy than your proposed approach. The problem with your approach is that if Eve (with $k_{new}$) and Bob (with $k_2$) collude, there's nothing stopping them from reading the entire text (and not just the part that Alice wants Bob to read).

Instead, consider that Alice divides up the plaintext into a series of blocks; she also selects a master key (H1), and creates a tree of keys as:

               H1
/-----/ \------\
/                \
H2                  H3
/    \              /   \
H4     H5           H6    H7
/ \    /  \         / \   /  \
H8 H9  H10 H11    H12 H13 H14 H15


For each internal node $H_i$, you would use some hash function to generate the two child nodes $H_{2i}$ and $H_{2i+1}$:

$H_{2i} = F(H_i)$

$H_{2i+1} = G(H_i)$

Where both $F$ and $G$ are noninvertible functions.

You would use the values in the leaf nodes to encrypt the successive blocks (so in the example, the first block would be encrypted using H8, the second block would be encrypted using H9, etc.

If the entire database consists of $N$ blocks, this would take a depth $\log_2(N)$ tree.

Now, when Alice decided to reveal a portion of the plaintext to Bob, she would just reveal the internal nodes that would allow Bob to recompute the keys used to encrypt those sections. For example, if Alice wanted to reveal the sections protected by H10 through H14, all she would need to reveal would be H5 (which allows Bob to recompute H10 and H11), H6 (which allows Bob to recompute H12 and H13) and H14. In general, to reveal a section of $M$ consecutive blocks, Alice needs to reveal at most $O(\log(M))$ internal nodes.

Now, Bob only gets the data Alice has decided to reveal; and even if a group of Bobs (and Eve) collude, they can only read what Alice has revealed to one of the Bobs.

• The question to which this is a good answer is quite far away from the initial question to which my answer was perfectly correct. Could you separate this into two questions for which yours would be the answer to one of them and mine the other? – Barack Obama Feb 6 '13 at 18:49
• Yes, it's a ways from how the initial question was phrased. However, whether it's a good answer really depends on what Eugen is actually interested in. If he has an academic interest in this type of cipher (and gave his Real World example as a way it might be used), it's off topic. However, if his Real World Example is the problem he is really interested in (and he thought that a cipher as he described might solve it), well, he needs to be told that such a cipher doesn't have the security properties he wants, and here is a better method that does. – poncho Feb 6 '13 at 19:29
• @poncho The solution satisfies the requirements although I would like to share my thoughts on its deficiencies (btw. Bob knows k_new and Eve knows k2). First is the storage overhead needed to store the hash tree. With the Barack Obama's solution I have to store k_new (and modulus) only for the portions I share (although public key crypto is much slower than symmetric encryption). If new data is added there is a problem again (if I shared H8 now Bob would know also H16, H17, right?). Regarding my interests: they are mixed indeed, but solving the real example has a bigger priority for me. – Eugen Feb 6 '13 at 20:04
• @Eugen: as for the amount of storage needed, well, just storing H1 will allow you to recompute the tree as needed with $O(\log N)$ hash operations. If it becomes necessary to append data, well, you don't want to reuse external nodes as internal; you can extend the solution to make multiple trees (with each tree being bigger; this preserves the $O(\log N)$ scaling properties). One problem happens if Alice needs to update database; if she's revealed the key for a block, Bob can decrypt that block even after it has been updated. I'm not sure how to work around that. – poncho Feb 6 '13 at 20:30
• @poncho Regarding the storage you are right: its either storing or recomputing it every time you need to retrieve/share some data. Making new trees requires recomputing not only the hashes but re-encrypting the database on each insertion :). I hope it is understood that this is just an open discussion. I am not nitpicking or something like that. – Eugen Feb 6 '13 at 20:59