@FelixLL - if you could please post details on how you plan to use ECC it would be much appreciated.

Sorry that should read dedicate an additional 8 bits not $2^8$ bits.

I don't think we can actually ensure short messages. From a conceptual level, each user needs to be able to get what is effectively $b$-bits of private information out, so we can't really go down below $ub$ bits. If we're willing to shorten our starting message space, we could dedicate padding space to bits that we'd search through in order to shorten the message, but at exponential cost. For example, if dedicate an additional $2^8$ bits, we can then search through $2^8$ different $m$'s and take the one with the smallest length - but we should only expect 8 bits of savings.

I am accepting since this was a good answer (even without the reference to XOR-ing by a fixed second block).

Perhaps you should define it as $G_{A,B}(x)$, and then you are asking $|G_{A,B}(\cdot)|$, in other words, how many unique $G$ functions are there?