Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I managed to implement the proxy re-encryption scheme from 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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.