Collusion resistance in proxy re-encryption scheme depending on bilinear map rules

Question

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegator. For example, when we have a message that was originally encrypted for Alice and a proxy re-encrypts it for Bob, Alice is the delegator and Bob the delegatee. Bob and the proxy should not be able to "collude" and recover the secret key of Alice.

I'm trying to understand if the first scheme in this paper https://eprint.iacr.org/2006/473.pdf is collusion resistant or not.

With $e:\mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ a bilinear map, $\mathcal{H}_1:\{0,1\}^* \rightarrow \mathbb{G}, \mathcal{H}_2:\mathbb{G} \rightarrow \mathbb{G}_T$ two independent full-domain hash functions, the master secret key $\mathsf{msk}=s$, and $X \xleftarrow{R} \mathbb{G}_T$ we have:

a) Bob has his secret key $sk_{Bob} = \mathcal{H}_1(Bob)^s$,

b) the proxy has the re-encryption key $rk_{Alice \rightarrow Bob} = \langle \mathsf{Enc}(Bob, X), sk_{Alice}^{-1}\cdot \mathcal{H}_2(X) \rangle$.

So obviously, if the proxy and Bob work together they can recover $sk_{Alice}^{-1}$, because it's based on identity encryption and $X$ has been encrypted under Bob's identity. How difficult is it now for them to get $sk_{Alice}$, if they already have the inverse?

But maybe this is not necessary, because how decryption works in the scheme. To decrypt a ciphertext $c = \langle C_1, C_2 \rangle$ that has been encrypted for Alice we have to do this: $m = C_2/e(C_1, sk_{Alice})$.

If the inverse can be treated as any other exponent, then we have:

1. $\frac{C_2}{e(C_1, sk_{Alice})} = C_2 \cdot e(C_1, sk_{Alice})^{-1} = C_2 \cdot e(C_1, sk_{Alice}^{-1})$

So here are my questions:

1) Is 1. correct? That would mean the scheme is not collusion resistant.

2) If 1. is not correct, how difficult is it to get $sk_{Alice}$ from $sk_{Alice}^{-1}$?

Answer 1

Going through the formal definition they gave to 'collusion resistance' (without wondering whether it makes sense)

How difficult is it now for them to get $sk_{\text{Alice}}$, if they already have the inverse?

Your intuition is quite correct; for any group of known finite order, we can compute the inverse (by taking advantage of the identity $x^{n-1} = x^{-1}$, where $n$ is the group order). In many groups (e.g. Elliptic Curve groups), computing inverses can be done even more efficiently; this shows that it is always possible.

Hence, the scheme they have laid out doesn't meet the goal of 'collusion resistance'.

Of course, that is easy to fix; we can add a random bit string to the private key. This random bit string is not used for producing public keys or proxy keys (or decryption); because the random bit string does not affect anything either the proxy or Bob can see, they cannot collude to recover it, hence meeting the definition.

Answer 2

A proxy re-encryption scheme is collusion resistant, if the proxy and a delegatee are not able to recover the secret key of the delegating party.

Are you sure that definition makes sense? After all, if proxy has the Alice->Bob reencryption key, and Bob has his private key, then the two of them can jointly decrypt any message encrypted by Alice's public key. And, the point of a private key is to be able to decrypt messages, so (no matter what we do) the proxy and Bob effectively have the private key (even if they might come up with the same bit pattern).

So, what does collusion resistance mean in this context? If the requirement is that they cannot determine the bit pattern of Alice's key, well, we can easily do that by using a scheme with multiple equivalent keys (and so even if they can come up with 'a' key, it is unlikely to be Alice's bit pattern). However, that doesn't sound very useful...