Homomorphic Commitments in Exponents of RSA groups

hom_com.py

# The extended euclidean algorithm
def egcd(aa, bb):
	lastremainder, remainder = abs(aa), abs(bb)
	x, lastx, y, lasty = 0, 1, 1, 0
	while remainder:
		lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
		x, lastx = lastx - quotient * x, x
		y, lasty = lasty - quotient * y, y
	return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

# Compute the modular inverse of a mod m
def inv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise ValueError
	return x % m


# Two random safe primes
P = 1019
Q = 1319
n = P * Q

# The corresponding Sophie Germain primes
p = (P-1)//2
q = (Q-1)//2

# A random generator of the multiplicative group mod n
g0 = 2

# A generator of the multiplicative subgroup of order pq
g = pow(g0, 4, n)

# The "magic" exponent allowing us to do multiplications in the exponent
n_exp = (n-1)//2

# g^(p+q)
h = pow(g, n_exp, n)


# Secret
x = 43
k = 1234 # a random nonce

# Encrypted x
c = x - p - q + k * p * q


# Compute x squared
A = pow(h, n_exp, n)
B = pow(h, 2 * c, n)
C = pow(g, c * c, n)
D = A * B * C % n 
print('x^2', c, D, 'expected:', pow(g, x * x,n))


# Compute x cubed
E = pow(D, n_exp, n) * pow(D,c,n) % n
print('x^3', E, 'expected:', pow(g, x * x * x, n))



# Multiply x and y
x = 122
k_x = 456 # a random nonce
c_x = x - q - p + k_x * p * q

y = 124
k_y = 879 # a random nonce
c_y = y - q - p + k_y * p * q

A = pow(h, n_exp, n) # q^2
B = pow(h, c_x, n) * pow(h, c_y, n) % n # q(x+y)
C = pow(g, c_y * c_x, n)
D = A * B * C % n 
print('x * y', c_x, c_y, D, 'expected:', pow(g, x * y,n))