Random data to curve points

[bellebaum]

I am trying to implement BBS signatures, for which I need a Hash-to-Curve for BLS12-381.
I basically need something similar to the following function:

relic/src/ep/relic_ep_map.c

Lines 208 to 232 in 3b9a4a8

	void ep_map_sswum(ep_t p, const uint8_t *msg, size_t len) {
	/* enough space for two field elements plus extra bytes for uniformity */
	const size_t elm = (FP_PRIME + ep_param_level() + 7) / 8;
	uint8_t *r = RLC_ALLOCA(uint8_t, 2 * elm);
	RLC_TRY {
	/* for hash_to_field, need to hash to a pseudorandom string */
	/* XXX(rsw) the below assumes that we want to use MD_MAP for hashing.
	* Consider making the hash function a per-curve option!
	*/
	md_xmd(r, 2 * elm, msg, len, (const uint8_t *)"RELIC", 5);
	/* figure out which hash function to use */
	const int abNeq0 = (ep_curve_opt_a() != RLC_ZERO) &&
	(ep_curve_opt_b() != RLC_ZERO);
	void (*const map_fn)(ep_t, const fp_t) =
	(ep_curve_is_ctmap() || abNeq0 ? ep_map_sswu : ep_map_svdw);
	ep_map_from_field(p, r, 2 * elm, map_fn);
	}
	RLC_CATCH_ANY {
	RLC_THROW(ERR_CAUGHT);
	}
	RLC_FINALLY {
	RLC_FREE(r);
	}
	}

Except, I need to be able to exchange the DST for md_xmd, which is currently hardcoded to "RELIC", and for some modes, replace the entire XOF with SHAKE.
My current workaround is to reimplement much of src/ep/relic_ep_map.c and include some internal template headers.

Would it be possible to provide an interface publicly which takes random data of the correct length (i.e. r) instead of deriving it from a message?

[dfaranha]

Sure, give me a few days to cook something!

[dfaranha]

Take a look at 8858084, feedback is welcome!

I just need to add checks to ensure enough randomness is given, but the API should stay the same.

[bellebaum]

Thanks :)
I left a few comments on the commit. As you mentioned, checks on len are probably a good idea

[dfaranha]

I just pushed some error-handling to HEAD, it should be better now.

[bellebaum]

Thanks :)
Though it still seems a bit weird to require 2*elm+1 bytes even though only one map needs that many:

relic/src/ep/relic_ep_map.c

Lines 547 to 554 in 0cff31b

	void ep_map_rnd(ep_t p, const uint8_t *uniform_bytes, size_t len) {
	/* Make sure that input is long enough for any of the hash functons. */
	if (len < ep_map_rnd_size()) {
	RLC_THROW(ERR_NO_BUFFER);
	ep_set_infty(p);
	return;
	}

Maybe guards in ep_map_rnd_size would make sense, something like this:

size_t ep_map_rnd_size(void) {
	const size_t elm = (FP_PRIME + ep_param_level() + 7) / 8;


#if EP_MAP == BASIC || !defined(STRIP)
	return elm;
#elif EP_MAP == SSWUM || !defined(STRIP)
	return 2 * elm;
#elif EP_MAP == SWIFT || !defined(STRIP)
	return 2 * elm + 1;
#endif
}

This would work as long as STRIP is defined.
I am not entirely sure what not defining STRIP is supposed to do. My initial idea was that defining it should have an effect like -ffunction-sections -Wl,--gc-sections except not even compiling the unneeded functions, but ep_rnd_map right now would calculate all three maps if STRIP is undefined.

[dfaranha]

Oh, that with STRIP is a bug, fixing ASAP.

The problem with requiring less bytes is obtaining from the API a lower number of bytes than the chosen function needs due to the different configurations.