1
$\begingroup$

I am trying to understand if it possible to use DLP to build a keyed one-way function with the following properties:

  1. $H_a(H_b(M)) = H_c(M)$, where $a$ and $b$ are the keys, and $c=a*b$
  2. The output of the function is relatively small - e.g. 256 bits

The function itself could be $h_a=M^a$ mod $p$, where $p$ is a 256-bit prime. However, I'm not sure how secure this would be given that the prime is pretty small. Specifically, I want to understand if the following would hold:

  1. Given $h_a$ and $p$, it would be impractical to compute $M$
  2. Given $h_a$, $M$, $c$, and $p$, it would be impractical to compute $a$

The messages I need to process are relatively small (256 - 512 bits), but can be padded if that would increase security.

$\endgroup$
1
$\begingroup$

An adversary who can compute discrete logs modulo $p$, given oracle access to $H_a$ for unknown $a$, can compute $\log_2 H_a(2) \equiv \log_2 2^a \equiv a \pmod p$ with a single query to the oracle.

After that, given $h = H_a(M)$ for unknown $M$, they can compute $$h^{a^{-1}} \equiv (M^a)^{a^{-1}} \equiv M^{a\cdot a^{-1}} \equiv M \pmod p,$$ where $a^{-1}$ is the inverse of $a$ modulo $\phi(p) = p - 1$.

If $p$ is 256 bits, adversaries can compute discrete logs modulo $p$ today. You need $p \gg 1024$ to be safe, among other criteria.

It might be helpful to go into more detail about why you need these properties, and what you are trying to achieve more generally.

$\endgroup$
2
  • $\begingroup$ Thanks! This makes sense. I need these properties for a zero-knowledge info sharing system I'm designing. It seems like Pohlig-Hellman cipher would work for me (based on this) - but it produces ciphertext that is pretty large (compared to my message sizes). So, I was trying to figure out if it would be possible to reduce the output size by making it a one-way-function, but it doesn't seem so. $\endgroup$ – irakliy Apr 7 '18 at 15:56
  • $\begingroup$ But you actually can secure discrete logarithms using ECC using curves like curve25519 or P-256 $\endgroup$ – VincBreaker Apr 8 '18 at 6:13

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.