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.

That is true.

That said, there are few situations where the modulus being used is not a public parameter of a protocol, and it is very difficult to perform operations with a secret modulus in constant-time, as your comment points out.

You'll always be able to get an approximate guess of the size of the modulus too, since larger moduli will need more registers to represent data.

If you have a random stream of bits, and you use rejection sampling to extract a value from that stream, then you don't reveal any information about the value. At most, you reveal information about the stream prior to the value you chose, but each bit of a secure RNG should be unrelated to all prior bits, so this is not an issue.

It does sometimes get abused, but such abuses fall under wire fraud laws, which carry heavy punishments.

So, the legal system is the prevention mechanism for abuse here.

One big difference is the density of the fuel.

You can fill a car with gas in under a minute.

While fast-charging (like Tesla's super charging) has growing deployment, that's still at least 15 minutes or so, which is a significant difference.

And, the density of that is just not there yet, so for the near future having charging at home makes daily driving much more convenient.

Reading this post, this is actually an explanation of Schnorr signatures, not ECDSA signatures. Bitcoin uses the latter, except for new transactions after the Taproot update, which the author doesn't reference here. In fact, the author isn't even describing a signature scheme, but rather an identification scheme, since the only step that involves the message is the vague: "5. Alice customizes a hash function with a message that she is signing". I believe what the author is referencing is to turn the Schnorr identification scheme into a signature scheme, you include the message along with the nonce commitment, hashing H(R, m) instead of H(R). In fact, you should also include the public key, hashing H(X, R, m).

I remain somewhat confused as to how this article was written.

Sleeping just long enough to fill the remaining time-slot for an operation is actually a valid countermeasure; in theory.

The problem is figuring out how much sleep is necessary based on what variable time work has been done, and actually sleeping the right amount. This can be difficult with the granularity involved.

In practice, attempting to fill the remaining time is either not effective, or requires a level of instrumentation that severely degrades performances.

I'd recommend section 5 of https://eprint.iacr.org/2016/613.pdf for a survey of these ideas.

Author here.

To illustrate my point further, let's say that your operation takes either 0.1ms or 0.0ms.

If you add in a uniform random delay of 100-1000ms, your expected random delay becomes 450ms.

The expected total runtime is thus either 450.1ms or 450.0ms. If you have a way to calculate this expected value with enough precision, you can completely recover the timing signal.

The amount of noise you inject can only make recovering the signal harder, not impossible. I also believe that the difficulty is only polynomial in the amount of noise, which limits the effectiveness of this strategy.

The reason why password hashes like PBKDF2 try and make the operation take longer is for a different reason, as far as I know. If you try and crack a password's hash by trying many different common passwords, until you can find a match, then it helps your attack if calculating a hash is very fast. Password hashes intentionally try and make calculating hashes more expensive, both in time, but also in memory consumption (in Argon2, for example), to limit the effectiveness of this attack.