Collusion resistance in proxy re-encryption scheme depending on bilinear map rules 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:


$\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}$?
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...