# Building cryptographic primitives using additive maps?

Suppose we have a one-way function F(x) that exhibits the property F(a + b) = F(a) + F(b). Such a function could be used as a cryptographic primitive, no?

-

## migrated from math.stackexchange.comMay 8 '14 at 14:16

This question came from our site for people studying math at any level and professionals in related fields.

Yes, take an elliptic curve group $E$ with a point $P$ of prime order $p$ such that the discrete logarithm problem is hard. Then we have a cyclic subgroup $\langle P\rangle$ of $E$ generated by $P$ of order $p$.

Define the map $F: \mathbb{Z}_p \rightarrow \langle P\rangle$ as $F(a):=a\cdot P$ (scalar multiplication) which gives you such a linear map (homomorphism and actually it is an isomorphism) as you have that $F(a+b)=F(a)+F(b)$. Apparently, if the discrete logarithm problem is hard, this map is one-way. The first addition is in $\mathbb{Z}_p$ and the second addition is the "abstract" addition in the elliptic curve group.

This fact is used in various constructions when instantiating DL based crypto with elliptic curves, such as homomorphic commitments, making ElGamal additively homomorphic (aka exponential ElGamal) etc.

-

Yes in some sense under the LWE assumption.

For a matrix $A \in \mathbb{Z}_q^{m \times n}$, two vectors $s \in \mathbb{Z}_q^{n}$ and $x \in \mathbb{Z}_q^{m}$, we define $$F_A(s,x) = As + x \in \mathbb{Z}_q^{m}.$$

Under the LWE assumption, the family of functions is one-way, when the function index $A$ is chosen uniformly at random, $s$ is chosen uniformly at random and $x$ is chosen according to an appropriate distribution, say, a folded Gaussian over $\mathbb{Z}_q$ with small variance.

Apparently, this function is additively homomorphic, that is, $$F_A(s,x) + F_A(t,y) = F_A(s+t,x+y).$$

-