[cronokirby]

A subtle point which I don't really explain in the post, since it was initially targeted to people who had done some cryptography with groups before, is that you need to carefully distinguish a group as a mathematical object, and a group as a computational object.

In cryptography, you not only need a mathematical group, but you also need a group as a concrete object, with ways of representing elements as bits, and efficient algorithms for manipulating elements of the group.

In fact, you also assume that computing other representations of the group is difficult. If you take the kind of group I mention in the post, it is the same group, mathematically, as just taking the integers mod q, along with addition. However, it should be very difficult to figure out how to convert the representation of the group you have into the the "simpler" representation as integers.

As for the field properties, you do need to be able to invert for some things later on in the post.

[contravariant]

Ah you need division for the extractability, fair enough. Though if it can be extended to arbitrary groups the field structure can't be crucial.