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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.