0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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