# 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 impratical.

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:

ReKeyGen(ski, pkj): On input user i’s private key ski = (xi1, xi2 ) and user j’s public key pkj = (pkj1, pkj2), this algorithm generates the re-encryption key rkij as below:

1. Pick h←{0,1}^l0 and π←{0,1}^l1, compute v= H1(h,π).
2. Compute V=pkj2^v and W=H2(g^v) xor (h,π).
3. Define rkij = h/(xi1*H4(pki2)+xi2). Return rkij = (rkij,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 at 18:59