5
$\begingroup$

Elliptic Curve Digital Signature Algorithm (ECDSA) admits universal forgery (UF) if the Attacker can solve the equation $$z=\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},$$ where $k$ is unknown, $f_{k}(x,y)$ are Division polynomials and $(x,y)$ are the coordinates of some fixed point $P$ on the elliptic curve $E:y^{2}=x^{3}+Ax+B\;$ (everything is over $\mathbb{F}_p$). This UF is based on the formula for the coordinates of the $k$ th multiple of $P(x,y)$: $$kP=\left(x-\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},\ldots\right).$$

It is known that division polynomials satisfy the following (elliptic divisibility sequence-) recurrence (see Ch. 2 in Lang S. Elliptic curves: Diophantine analysis. 1978) $$f_{m+n}f_{m-n}=f_{m+1}f_{m-1}f_{n}^2-f_{n+1}f_{n-1}f_{m}^2.$$ In particular $$f_{m+2}f_{m-2}=\alpha f_{m+1}f_{m-1}-\beta f_{m}^2.$$ It means that $h_k:=\frac{f_{k-1}f_{k+1}}{f_{k}^2}$ (needed for UF) satisfy the recurrence $$\tag{$*$}h_{m-1}h_{m}^2h_{m+1}=\alpha h_{m}-\beta.$$

Q: Were the properties of sequences defined by $(*)$ studied before (period lengths, randomness, uniform distribution, ...)? Can $\{h_m\}$ be cryptographically better than $\{f_m\}$?

This is only $\!\!\mod p$-question because over $\mathbb{C}$ such sequences are well-known: $h_n=\wp(z)-\wp(z_0+nz).$ They arise in the study of Somos-4 sequences (see Hone A. Elliptic curves and quadratic recurrence sequences. Bull. Lond. Math. Soc. 2005.)

The question Universal forgery based on mathematical problem about another problems needed for UF was asked at Crypto separately.

$\endgroup$
  • $\begingroup$ Cryptographically better, you mean more secure, equation has less solutions,or hard to find solutions. It could be certain operations allow for more private solutions, one operation(recurrence?) could change the scheme, others offering more secure factoring type, just difficult. $\endgroup$ – user3483902 Jan 17 '18 at 20:12
  • $\begingroup$ @user3483902 By "better" I mean "stronger=secure". $\endgroup$ – Alexey Ustinov Jan 18 '18 at 0:41

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.