Proof of computing (g^a => g^(a^2)) is impossible under the DH assumption.

g^(a^2) incomputability.md

Statement

We prove that g^(a^2) cannot be computed efficiently from g^a under the Diffie-Hellman (DH) assumption. More rigorously, the following statement holds:

Let G be a cyclic group and g be a generater of G.
Given an oracle which can compute g^(a^2) from a given g^a for any integer a,
there exists a polynomial time algorithm which computes g^(xy) from g^x and g^y for any integers x and y.

Proof

We prove this statement by showing a concrete algorithm which computes the answer to the DH problem.

The proof starts with the case that the number of elements in a group G (= #G) is odd. Let F: G → G be an oracle described as above. If #G is odd, the following function H: G ✕ G → G gives a solution to the DH problem (H(g^x, g^y) = g^(xy)).

H(X, Y) = (F(X・Y)・F(X・Y^(-1)))^(4^(-1))

Y^(-1) and 4^(-1) can be computed efficiently using the same technics as computing a modular inverse of integers such as the extended Euclidean algorithm or the Euler's theorem[1]. The equality can be checked easily by writting X = g^x and Y = g^y and

(RHS) = ( F(g^((x+y)^2))・F(g^((x-y)^2)) )^(4^(-1)) = (g^(4xy))^(4^(-1)) = g^(xy).

If #G is even, 4^(-1) is not well defined under the multiplicative group of integers modulo #G and thus this function is also not well defined. However, if #G is even and if we write #G = 2n, there exists a explicit isomorphism:

G ⇔ H := <g^n> ✕ <g^2>.

Any group element X ∈ G can be identified to a group element in H by computing X^2 ∈ <g^n> and X^n ∈ <g^2>. By continuing this discussion, the problem reduces the case with solving the DH problem in a group with an odd integer, and is proved already. ■

References

[1] https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

I coined this theorem by trying to inventing an encryption scheme (KeyGen, Enc, Dec) which has a homomorphic boolean function:

Equal(Enc(i), j) = Enc(i == j ? 1 : 0)

which can be easily idealized if this encryption scheme is fully homomorphic encryption scheme by:

Equal(E(i), j) = (E(i) - E(j))^(φ(n))

where n is the plain modulus and φ is the Euler's totient function.
The equality holds by the Euler's theorem (if n is a prime number, φ(n) will be n-1 and thus reduces to the Fermat's little theorem).

The bad news is the current practical fully homomorphic encryption schemes like BFV or BGV
(which uses so-called "learning with errors" encryption) cannot perform significant amount of multiplication with practical time.
The computation itself can be done by homomorphic addition, multiplication and "relinearlization",
however it is too slow to compute in modern PCs (may take several minutes).