Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

migrated from May 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.

share|improve this answer

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). $$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.