I would like to find an injective function f: Z_p x Z_p -> Z_{q}, i.e., a function from the cartesian product of the group of integers modulo a prime p to the integers modulo another prime q such that q > (p-1)^2.

The problem can just be solved by creating a table that maps each value (a,b) \in Z_p x Z_p to a different c \in Z_{q}, and from there deriving the algebraic expression of the function. But I would need a polynomial function with few now-zero coefficients. I.e., the degree of the polynomial can be large, but the amount of non-zero coefficients should be logarithmic in the degree. E.g., an injective function like this one (where n can be large):

f(x,y) = a_n x^n y^n + a_4 x^4 y^4 + a_1 x y + _0 mod q

PS: my orininal problem was to design an injective function f: Z_p x Z_p -> Z_{p}, but this is impossible since the cardinality of Z_p x Z_p is bigger than that of Z_p.