-1
$\begingroup$
  1. $$h(m) = g^m(\bmod p)$$ where $p$ is a prime number, how can I prove that this is a one way function and collision free?
  2. $$h(m) = g^m(\bmod n) $$ where $n=pq$ for two distinct primes $p,q$, how can I prove that it is a one way function and collision free?
$\endgroup$
  • 2
    $\begingroup$ Neither function is collision resistant $h(m)=h(m+p-1)$ for the first case with $m\neq m+p-1$. Did you maybe forget to restrict $m$ somehow? Also what have you tried in solving this problem yourself and where did you get stuck? The more you tell us, the better we can help you with the concrete problem you have. Also we're not a homework solving service. $\endgroup$ – SEJPM May 7 '18 at 5:52
0
$\begingroup$

Hint:

  • Neither function is is collision resistant, as $h(m+p-1)=h(m)$ if you don't restrict the input space for the first one, as we don't actually know $\varphi(n)$ as pointed out by poncho in his answer.
  • I suppose one-way-ness depends on the techniques you have learned and will most likely make use of the precise formulation of the discrete logarithm problem (you know, that one that uses random sampling for $m$).
$\endgroup$
0
$\begingroup$

Actually, if all the following is true:

  • The factorization of $n$ is secret (as so SEJPM's counterexample doesn't apply, as you don't know the value $\varphi(n)$)

  • $p$ and $q$ are sufficiently large that the factorization problem is infeasible.

  • If the order of $g$, with respect to both $p$ and $q$, is large

Then, yes, the second instance is collision resistant. That is, if you do find a collision, that is, two distinct values $x, y$ such that $g^x \bmod n = g^y \bmod n$, then knowing the difference $x-y$ gives you enough information to efficiently factor $n$, which we assume is hard.

$\endgroup$
  • $\begingroup$ I fixed my answer :p $\endgroup$ – SEJPM May 7 '18 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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