# Proxy re-encryption mod operations

I managed to implement the proxy re-encryption scheme from http://eprint.iacr.org/2009/189.pdf in Python 2.7, however I am having performance issues. As it is, I can run the algorithm for key sizes up to 5 bits, which is impractical.

I think the problem is the lack of mod operations throughout the algorithm. As the paper does not specify which operations are mod something (or it is trivial they omitted) and I do not have a strong math background, I am having a hard time figuring it out. For example:

$\operatorname{ReKeyGen}(sk_i, pk_j)$: On input user $i$’s private key $sk_i = (x_{i,1}, x_{i,2} )$ and user $j$’s public key $pk_j = (pk_{j,1}, pk_{j,2})$, this algorithm generates the re-encryption key $rk_{i\to j}$ as below:

1. Pick $h\overset{\$}\leftarrow \{0,1\}^{l_0}$and$\pi \overset{\$}\leftarrow \{0,1\}^{l_1}$, compute $v= H_1(h,\pi)$.
2. Compute $V=pk_{j,2}^v$ and $W=H_2(g^v) \oplus (h || \pi)$.
3. Define $rk_{i\to j}^{(1)} =\dfrac{h}{x_{i,1} H_4(pk_{i,2})+x_{i,2}}$. Return $rk_{i\to j} = (rk_{i\to j}^{(1)},V,W)$.

Since there are some huge exponentiations throughout the algorithm, I am sure I am missing some mod operations there.

I have checked others ElGamal and Schnorr signatures implementations, but adding mod as described makes the proxy re-encryption stop functioning. Anyone has a light on this?

-
yes they omitt it for the group operations. Operations in group elements are mod p (they operate in $Z_p^*$) and operations in the exponents are mod q (they work in an order q subgroup). – DrLecter Jun 4 '14 at 18:59