18

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.

fgrieu
  • 140,762
  • 12
  • 307
  • 587
  • 1
    Choose $x = 0$ ? Runs in $\Theta(1)$ ;) – puzzlepalace Jun 20 '17 at 22:01
  • @puzzlepalace: thank you for finding a hole; plugged it. – fgrieu Jun 20 '17 at 22:08
  • Do you get to choose what the $g^x \mod p$ value is? – Samuel Neves Jun 26 '17 at 07:43
  • @SamuelNeves: yes; the only constraint on $g^x\bmod p$ is that it is small (about $\log_2(k)$-bit smaller than $p$ is). – fgrieu Jun 26 '17 at 07:49
  • 1
    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. – Samuel Neves Jun 26 '17 at 12:44
  • @fgrieu, did you get any more updates on the problem? I'm also curious – pintor Oct 27 '22 at 07:48
  • 1
    @pintor: no, I have made no progress nor got more feedback than the above comments. – fgrieu Oct 27 '22 at 08:55
  • Can you please provide me with some real values of variables in question instead of me attempting with random values. – madhurkant Mar 21 '24 at 05:24

0 Answers0