Cipher text transformation in Proxy Re-Encryption

Question

I am trying to implement proxy re encryption for the proof of concept with the following parameters.

q = 31, g = 2, sk_a = 3, sk_b = 5,

sk_a and q are co-primes thus inverse of sk_a exits in mod q.

proxy_key = sk_b/sk_a  

where proxy_key is calculated by multiply sk_b with modular inverse of sk_a i.e., (sk_b.sk_a inverse) mod q

cipher text: y = (g^sk_a) mod q

To transform cipher text I am using (y^proxy) mod q.

Accoding to the algorithm cipher text transformation should turn out to be (g^sk_b) mod q, but it does not work for me.

I am not sure what's the catch in it. I am using the following code.

    BigInteger q = new BigInteger("31");

    BigInteger g = new BigInteger("2");
    BigInteger sk_a = new BigInteger("3");
    BigInteger sk_b = new BigInteger("5");

    BigInteger proxy_key = sk_b.multiply(sk_a.modInverse(q)).mod(q);

    BigInteger y = g.modPow(sk_a, q);
    System.out.println("Cipher Text: " + y);

    BigInteger transformation = y.modPow(proxy_key, q);
    System.out.println("Cipher Text Transformation: " + transformation);

Answer 1

You have two problems:

1. 2 is not a primitive root modulo 31, so your "g" is not a generator for the multiplicative group. You can use 3 instead.

2. It looks like somebody made a mistake when explaining Blaze, Bleumer & Strauss. You need to calculate b/a modulo phi(q) instead of modulo q. Then you can use Euler's theorem to show that the reencryption works. It is not true that (g^a)^(a^-1)=g (mod q) when a^-1 is calculated modulo q. This also means that sk_a and sk_b should be relatively prime to phi(q). Try using 7 and 11 instead.

The following should work as you expect:

BigInteger q = new BigInteger("31");
BigInteger phi = new BigInteger("30");

BigInteger g = new BigInteger("3");
BigInteger sk_a = new BigInteger("7");
BigInteger sk_b = new BigInteger("11");

BigInteger proxy_key = sk_b.multiply(sk_a.modInverse(phi)).mod(phi);

BigInteger y = g.modPow(sk_a, q);
System.out.println("Cipher Text: " + y);

BigInteger transformation = y.modPow(proxy_key, q);
System.out.println("Cipher Text Transformation: " + transformation);