11
$\begingroup$

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for sizable $k$ but $k\ll\sqrt q$ ?

I see that for small $k$, it is enough to try incremental values of $x$ until finding an $x$ that fits, with expected cost $O(k)$ modular multiplications in $\mathbb Z_p^*$. Is there better?

Assume $p$ is an $l$-bit prime; $q$ is an $n$-bit prime with $q$ dividing $p-1$; and $g=h^{(p-1)/q}$ for some (random?) $h$ in $\mathbb Z_p^*$. For concrete values, assume $l\approx1024$, $n\approx160$, $k\approx2^{64}$.

Update: I'm expecting the problem to be hard, and thus that the more difficult problem of exhibiting $x$ with $g^x\bmod p$ in a range of width $p/k$ must be hard.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Choose $x = 0$ ? Runs in $\Theta(1)$ ;) $\endgroup$ – puzzlepalace Jun 20 '17 at 22:01
  • $\begingroup$ @puzzlepalace: thank you for finding a hole; plugged it. $\endgroup$ – fgrieu Jun 20 '17 at 22:08
  • $\begingroup$ Do you get to choose what the $g^x \mod p$ value is? $\endgroup$ – Samuel Neves Jun 26 '17 at 7:43
  • $\begingroup$ @SamuelNeves: yes; the only constraint on $g^x\bmod p$ is that it is small (about $\log_2(k)$-bit smaller than $p$ is). $\endgroup$ – fgrieu Jun 26 '17 at 7:49
  • 1
    $\begingroup$ This seems to reduce to a discrete logarithm problem in the multi-target setting, with a potentially very high target number depending on $k$. For a $k\ approx \sqrt{p}$ index calculus seems like the best choice. Once you have one solution, getting more is relatively fast. Unsure if there's something better. $\endgroup$ – Samuel Neves Jun 26 '17 at 12:44

Your Answer

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

Browse other questions tagged or ask your own question.