# Elligator-2 against curves over Fq, q mod 4 = 3

It appears that the conditions for applicability of Elligator-2 against many of the SaveCurves curves, where $q \mod 4 = 3$ will inevitably poke a hole in the bit-string set over $(0, 1, .. (q-1)/2)$.

There are two conditions for use of the decoding of a bit string to a point on the curve: $(1 + u \cdot r^2) \neq 0$ and $A^2 \cdot ur^2 \neq B(1 + ur^2)^2$, where $r$ is the numeric equivalent of the bit string, $A,B$ come from curve equation: $y^2 = x^3 + Ax^2 + B \cdot x$, and $u$ is non-square over the field $F_q$.

And when $q \mod 4 = 3$, these conditions will be violated for some valid bit string representation(s) in the set $(0, 1, ... (q-1)/2)$.

Conversely, when $q \mod 4 = 1$, it can be shown that there are no holes in the mapping from bit strings to curve points, and all valid bit strings in the set $(0, 1, ... (q-1)/2)$ map to curve points.

Hence, it becomes clear to me that the intent of Elligator mappings was never to allow arbitrary bit strings to map to curve points, but rather to support a compressed encoding for selected random curve points to bit strings that mimic uniformly random bit strings. The effect is near full coverage of the bit space, but not totally. And it can be shown that Decode(Encode(pt)) = pt. It cannot always hold true for the inverse case: Encode(Decode(bits)) = bits, when $q \mod 4 = 3$, which is the case of many, or most, of the SafeCurves.

The stated purpose of such obfuscation was to avoid censorship from unfriendly authorities who could otherwise spot the use of EC points, even compressed representations of points, during transactions such as ECDH key exchange or ElGamal encryption.

So… the question is:

If the authorities have the wherewithal to spot the use of EC points, or compressed representations of points, then why would one expect that the authorities could not also detect the Elligator obfuscations? They have access to the Elligator equations just as we do. And they could run the decodings for themselves to see if a curve is being referenced.

• I see from deeper digging that hashing into curves is a lively topic for pairing-based encryption, and so perhaps that is an application for the inverse mapping of bits -> points? – DBM Jul 12 '15 at 18:02

As an additional security, as described in section 5.1 of the paper, the definition of Elligator 2 is parametrized with a non-square element $u\in \mathbb{F}_q$. So if I understand this correctly, an attacker will not know this parameter $u$ and will thus not be able to decode and encode points of the curve. All the attacker can do is observe a uniformly distributed sequence of bits.