search

herumi / mcl

a portable and fast pairing-based cryptography library
BSD 3-Clause "New" or "Revised" License
458 stars 157 forks source link

Question about constant time exponentiation/multiplication #7

Closed arybczak closed 7 years ago

arybczak commented 7 years ago

Constant time version of these seems to be constant in a sense that it doesn't reveal information about particular bits of the input, but it does reveal information about the bitlength of input, i.e. multiplying a point from bn256::G1 by 42 is much faster than multiplying it by a "proper" 254bit scalar. I wonder if that can be a problem?

herumi commented 7 years ago

The situation to use constant time version is multiplication by a secret number, then I think that the bit length of the number is known or almost same as the sizeof(Fr) so it is not necessary to hide the length. Is it wrong idea? then I'll fix it.

herumi commented 7 years ago

Or I add the notification in the comments for mulCT. is it ok? https://github.com/herumi/mcl/blob/56811bbb125cd1f4f7351241c4615ec6042c90ef/include/mcl/util.hpp#L280-L283

arybczak commented 7 years ago

The notification is nice to have.

Right, the secret itself will be large, but I've seen in a protocol multiplication by secret^-1 (in Fr) and it is not clear to me if that might be a potential issue (or if that's the exhaustive list of use of a transformed secret that might potentially be exploited).

herumi commented 7 years ago

It is an interesting problem. #{L bit length number} = 2^(L-1). Let the size of (1/s) be M bit (L > M), then the probability is 1 / 2^(L - M) and it might leak a little information. I will modify that mulCT does not depend on the bit-length in the future.

herumi commented 7 years ago

I will modify that mulCT does not depend on the bit-length in the future.

The latest version of mulCT does not depend on the bit-length.