4
$\begingroup$

I am exploring a modification to ECDSA to produce shorter signatures, even though it compromises security (in a controllable way). My rationale behind this change is in this discussion. In my application, the main focus is on keeping the signature short, while storage isn't as crucial.

Here is my new ECDSA method: (the notation I'm using aligns with Wikipedia's ECDSA)

During setup, I generate a set of random values $( p_1, p_2, ..., p_{10} )$ which remain private to the signer. These values are then multiplied by the generator point $( G )$ to obtain corresponding points on the elliptic curve, denoted as $( Q_1 = p_1 \cdot G, Q_2 = p_2 \cdot G, ..., Q_{10} = p_{10} \cdot G )$, and shared with the verifier.

In the signing phase, instead of utilizing a random $ k $, I calculate it deterministically based on the input message, using $ k = \text{hash}(msg|1) \cdot p_1 + \text{hash}(msg|2) \cdot p_2 + ... $. The rest of the process follows the standard ECDSA, except the signer omits the $ r $ component, resulting in a signature half the size of normal ECDSA signatures.

For verification, the verifier can calculate $ r $ using the provided points $ (Q_1, Q_2,..,Q_{10}) $: $r=$ the $ x $ part of $ \text{hash}(msg|1) \cdot Q_1 + \text{hash}(msg|2) \cdot Q_2 + ... $.

I need to analyze the security of the proposed system. I think that an attacker with fewer than 10 signatures cannot compromise the system. However, once they exceed this threshold and has 10 equations in a finite field ($ s_i = {k_i}^{-1}(z_i + r_i d_{A}) $), does this imply the attacker can discover secrets?

Even if the system is breached after reaching 10 signatures, I can to adjust the number of points and a limit on the number of signatures. Is this scenario still secure?

$\endgroup$
5
  • 3
    $\begingroup$ I fear you want to optimize the signature size but discard what you pay in terms of storage of the various $Q$. Then, why don't you just precompute many $r$ instead of precomputing points ? $\endgroup$
    – Ruggero
    Mar 28 at 9:14
  • $\begingroup$ Thanks for your comment. In your suggestion, should I add a few more bits to the signature to show which precomputed $r$ is used? Also, I'm hopeful that my proposed method might offer better security than using a static $r$ but I'm still seeking analysis. $\endgroup$
    – Ehsan
    Mar 28 at 13:54
  • 1
    $\begingroup$ "However, once they exceed this threshold and has 10 equations in a finite field"; actually, I believe 11 signatures are needed; after all, there are 11 unknowns for the attacker to solve for ($p_1, ..., p_{10}, d_A)$. However, once he has 11, recovering them is simple linear algebra (unless the 11 equations happen to not to be independent; quite a low probability of that happening) $\endgroup$
    – poncho
    Mar 29 at 19:20
  • $\begingroup$ Thanks. Does the fact that these equations are in a finite field provide any additional security? If the finite field doesn't have any effect, as you said, 11 signatures leaking all secrets. $\endgroup$
    – Ehsan
    Mar 29 at 20:05
  • 1
    $\begingroup$ No, it doesn't provide any additional security (given that we're in a nontiny finite field): linear algebra in a finite field is just like linear algebra anywhere else. $\endgroup$
    – poncho
    Mar 29 at 20:08

1 Answer 1

0
$\begingroup$

Thanks to poncho and Ruggero, I've found my answer. With $n$ random points in the system, the maximum safe signing threshold is $n$. Beyond this, an attacker can compromise the system. Additionally, compared to precomputed $r$, the system offers slightly smaller signature sizes and a bit more flexibility.

$\endgroup$
1
  • 1
    $\begingroup$ Actually, the safe signing threshold is $n$ - with $n+1$ signatures, the attacker can easily compromise the system. $\endgroup$
    – poncho
    Mar 30 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.