How to exponentiate arbitrary group element instead of ctx->initial?

[vusirikala]

I explored the library and finally came up with the following code for generating a random element on the elliptic curve.

	secp256k1_ecmult_gen_context context;
	void * prealloc = checked_malloc(&default_error_callback, SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE);

        secp256k1_ecmult_gen_context_init(&context);
        secp256k1_ecmult_gen_context_build(&context, &prealloc);

	unsigned char exp[32];
	secp256k1_scalar exponent;
	secp256k1_gej generator;
	int overflow;
    	secp256k1_rand256(exp);
	secp256k1_scalar_set_b32(&exponent, exp, &overflow);
	secp256k1_ecmult_gen(&context, &generator, &exponent);

The function secp256k1_ecmult_gen raises the context->initial group element to given exponent.

1. Is there an inbuilt function to raise a given group element to a given exponent?
2. I see 2 files ecmult_impl.h and ecmult_gen_impl.h. What's the difference?
3. If my point is in secp256k1_ge group, should I first convert it into secp256k1_gej group using secp256k1_gej_set_ge() function and then apply the above function? Or is there a more efficient way?

[gmaxwell]

You haven't provided enough context to answer, the correct function depends on the nature of the protocol you're constructing. To exponentiate a variable base you potentially either secp256k1_ecmult_const() or secp256k1_ecmult with you point in a and ng=0 depending on your needs. _gen means with the generator-- a fixed base, and isn't what you want.

There are other functions that let you efficiently compute the sum of P_i^a_i for many i.

Ge can be converted to gej using secp256k1_gej_set_ge. Generally if a function exist that takes a ge you want to use a ge because it'll be faster to operate using ge.

The non _impl .h files have the function prototypes that describe what the functions do (though I see ecmult_const's is lacking). Alternatively, it's usually easiest to find things by walking in from the external API, e.g. ecdsa_verification uses a variable base, and ECDH uses a variable base in constant time.

If your goal is to generate a random group element exponentiation is probably not what you want: it's slow-ish and it means you know the discrete log of the selected point, in many protocols you need a 'random' point specifically so you do not know the discrete log. In those cases hashing onto the x-value and retrying with a new hash if the result wasn't on the curve or using shallue_van_de_woestijne from secp256k1-zkp if constant time is appropriate, may be preferred/necessary.

Do take care, the insides of the library are not a general user interface and are not as footgun proof as the external interfaces. Their user is expected to have some understanding about how they work under the hood, and of course any work that builds its own cryptosystem has the according risks from doing so! At a minimum exponentiating a random point with a random value means that the result might be the point at infinity, which cannot be serialized in the standard serializations... so correct code should have some way of handling that.

[vusirikala]

That's a really nice answer. You mentioned that Ge can be converted to gej using secp256k1_gej_set_ge. Generally if a function exist that takes a ge you want to use a ge because it'll be faster to operate using ge. Did you mean it'll be faster to operate using gej? Because I heard operations on projective coordinates are usually faster.

[gmaxwell]

Good question. I didn't make an error. Operations which output projective coordinates (gej) are faster but taking an affine (ge) input can be faster.

A ge point can be seen as a projective point with z=1 and it's particularly simple to square or multiply by one. :) Libsecp256k1 has functions like gej_add_ge (gej = gej + ge) which are faster than a generic gej = gej + gej.

None of libsecp256k1's internals output affine, except for the specific conversion functions.

The function secp256k1_ecmult is somewhat special in that it gets affine-input like performance without requiring ge input due to doing some internal magic (it performs the operations using affine-input group law on an isomorphic curve).