Question about constant time exponentiation/multiplication

[arybczak]

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]

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]

Or I add the notification in the comments for mulCT. is it ok?

mcl/include/mcl/util.hpp

Lines 280 to 283 in 56811bb

	/*
	constant time pow
	@note depends on bit length of y[n]
	*/

[arybczak]

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]

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]

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.