It is known that DSA admits universal forgery under assumption that the Attacker can solve the equation $x\equiv R^x\pmod p.$ Are there any other protocols admitting universal forgery based on non-trivial mathematical problem?
2
$\begingroup$
$\endgroup$
-
2$\begingroup$ I'm confused by your question. If you allow some highly non-trivial mathematical computation, then any signature scheme / protocol can be broken. So what specifically is your question? Whether there exist other schemes which allow for UF if some "non-obviously-associated" computation can be carried out? $\endgroup$ – SEJPM♦ Jan 6 '18 at 13:30
-
$\begingroup$ @SEJPM Yes, exactly. My question is about "non-obviously-associated" mathematical problems which allow to construct UF for some protocols. $\endgroup$ – Alexey Ustinov Jan 6 '18 at 14:47
-
$\begingroup$ Just a note: In most popular signature schemes (which usually have a security proof, *DSA being an exception) such a "hidden security assumption" would be caught by the proof not working. $\endgroup$ – SEJPM♦ Jan 6 '18 at 18:13
-
1$\begingroup$ @SEJPM: Apparently, reducibility of DSA and ECDSA to the corresponding discrete logarithm problem was finally proved by Manuel Fersch, Eike Kiltz and Bertram Poettering's On the Provable Security of (EC)DSA Signatures, in proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. It flies above my head, though. $\endgroup$ – fgrieu Jan 8 '18 at 17:02
2
$\begingroup$
$\endgroup$
Elliptic Curve Digital Signature Algorithm admits universal forgery if the Attacker can solve the equation $$z=\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},$$ where $k$ is unknown, $\psi_{k}(x,y)$ are Division polynomials and $(x,y)$ are the coordinates of a point $P$ on the elliptic curve $ E:y^{2}=x^{3}+Ax+B$. This UF is based on the formula for the coordinates of the nth multiple of $ P(x,y)$: $$kP=\left(x-\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},\ldots\right).$$
The question Elliptic curve sequences needed for universal forgery about hardness of this UF was asked at MathOverflow separately.
