I have a multiplicative group $G$ of prime order $p$ implemented using a twisted Edwards curve (similar to Ed25519).

I want to compute a set of $k$ distinct points $P_1,...,P_k$ that generate $G$, such that the mutual discrete logarithms of these points are hard to compute. I.e., for any distinct $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that $P_i=s\cdot P_j$.

To obtain such a point $P_i$, I do the following steps:

  • I select $y$,
  • I use $y$ to compute $x$,
  • I verify if $(x,y)$ is on the curve,
  • I verify if the order of $(x,y)$ is $p$.

If $(x,y)$ is not valid, I retry with a different $y$. I repeat this process until I have found my $k$ points.

My question:

Can I generate the points by simply increasing $y$ (e.g., $y=3,4,5,...$) or will this affect the security if the $y$ coordinates of all my points are in a very small range?

  • $\begingroup$ Two clarification requests: a) Is it OK if you (the generator) can know the mutual discrete logarithms? b) Would you be satisfied with an answer that solves your problem (generating many point with hard mutual discrete logarithms) rather than stating that tightly grouped coordinates are [not] exploitable? $\endgroup$ – SEJPM Aug 5 '16 at 20:42
  • $\begingroup$ My first thought is that if you can get 2+ parties to participate in a key generation ceremony, you do something like Pedersen's DKG protocol $k$ times and ask them all to delete their secret keys. As long as at least one party is honest, this should work. Unfortunately this will not solve the problem of generating $k$ points up front for future use in a "nothing up my sleeve" manner. $\endgroup$ – Bristol Apr 26 '18 at 20:02

It would be more confidence-inspiring to choose a hash-to-curve method and pass consecutive integers through that. There is a current (2019-05-16) internet-draft surveying hash-to-curve techniques with references, draft-irtf-cfrg-hash-to-curve. The most popular method for Ed25519 is Elligator 2. Since invertibility is not required for your application, you could also just use the hash-and-pray technique: for each $i$, find the smallest $j$ such that $H(i) + j$ is an $x$ coordinate on the curve, where $H(x)$ is (say) $\operatorname{SHAKE128-512}(x) \bmod{2^{255} - 19}$.

| improve this answer | |

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.