Does ECDSA work without cyclic groups

Question

I'm currently working on the different signature schemes, here is my question :

Does ECDSA work without cyclic groups ? Is it secure ?

For example, if I use a non cyclic group, are there some cases in which the signature will not work ? If it always work, is it secure ? why / why not ?

Thank you

Answer 1

Being cyclic adds a property to a group $G$ such that there is an element $g \in G$ so that $\langle g \rangle = G$. Instead of adding a property, cryptographers look the other way, the Generic Group Model;

The generic group model is an idealized cryptographic model, where the adversary is only given access to a randomly chosen encoding of a group, instead of efficient encodings, such as those used by the finite field or elliptic curve groups used in practice.

The model includes an oracle that executes the group operation. This oracle takes two encodings of group elements as input and outputs an encoding of a third element.

In 2016, there is an interesting work that showed the security of the GenericDSA then they indicated that forging signatures in (EC)DSA is as hard as solving discrete logarithms.

• On the Provable Security of (EC)DSA Signatures

based on this we can say that (EC)DSA is secure when the discrete log is secure.

While choosing a non-cyclic group, be careful, since all elements have some finite order in the finite groups. So, if you choose your element to have a small order then DLog will be easy.

Since you are asking on ECDSA here a non-cyclic ECC example from Stinson's book;

Suppose that $p > 3$ is an odd prime, and $a,b$ is an element of $\mathbb Z_p$. Further, suppose that the equation $x^3 + ax + b$ is congruent to $0 \bmod p$) has 3 distinct roots in $\mathbb Z_p$. Prove that the corresponding elliptic curve group $(E, +)$ is not cyclic.

Still, you will still work on a cyclic-subgroup of the Curve.

In some constructions, the signature may fail, need to be looked for cases.