Is such a crypto-system available?

Question

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

Answer 1

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.

Answer 2

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.